数组实现线性表

跟着视频抄的

/*
 *用数组实现线性表
 */

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct LNode *List;  // List的类型是指向线性表的指针
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;  // 线性表最后一个元素所在的位置
};

/*
 *struct LNode L;  //创建一个线性表；
 *List Ptrl;  // 创建一个指向线性表的指针
 *访问下表为 i 的元素：L.Data[i] 或 Ptrl->Data[i]
 *线性表的长度：L.Last+1 或 PtrL->Last+1
 */
 
// 初始化
List MakeEmpty(void)
{
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));
    PtrL->Last = -1;
    return PtrL;
}

// 查找
int Find(ElementType X, List PtrL)
{
    int i = 0;
    while ( (i <= PtrL->Last) && (PtrL->Data[i] != X)){
        i++;
    }
    if (i > PtrL->Last){
        return -1;  // 如果没找到，返回 -1
    } else {
        return i;   // 找到了，就返回存储位置
    }
}

// 插入 （第 i（i<=i<=n+1）个位置上插入一个值为 X 的新元素）
void Insert(ElementType X, int i, List PtrL)
{
    int j;
    if (PtrL->Last == MAXSIZE-1){
        printf("表满");
        return;
    }
    if (i<1 || i>PtrL->Last+2){  // 位置是从 i 开始的
        printf("位置不合法");
        return;
    }
    for (j=PtrL->Last; j>=i-1){
        PtrL->Data[j+1] = PtrL->Data[j];  // 将 ai ~ an 倒序向后移动
    }
    PtrL->Data[i-1] = X;
    PtrL->Last++;           // last仍指向最后元素
    return;
}

// 删除（删除表的第i（i<=i<=n）个位置上的元素）
void Delete(int i, List PtrL)
{
    int j;
    if (i<1 || PtrL->Last+1){  // 检查空表与位置合法性
        printf("不存在第%d个元素", i);
        return;
    }
    for (j=0; j<=PtrL->Last; j++){
        PtrL->Data[j-1] = PtrL->Data[j];  // 将ai+1~an向前移动
    }
    PtrL->Last--;            // Last仍指向最后元素
    return;
}

跟着老师思路自己写的：

/*
 *数组实现线性表
 *按老师的思路自己写的
 */

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

// 在线性表中：
// 存储位置是 0~last
// 逻辑位置是 1~last+1

typedef struct list_{
    int data[MAXSIZE];
    int last;  // 最后一个元素的存储位置
}List;

List* MakeEmpty(void);
int Find(int k, List *list);
void Insert(int x, int i, List *list);
void Delete(int i, List *list);
int Length(List *list);

List* MakeEmpty(void)
{
    List *PtrL;
    PtrL = (List *)malloc(sizeof(List));
    PtrL->last = -1;
    return PtrL;
}

int Find(int x, List *list)
{
//  int i = 0;
//  while (i<list->last+1 && x != list->data[i]){
//      i++;
//  }
//  if (i == list->last+1){
//      return -1;  // 没有找到返回 -1
//  } else {
//      return i;  // 找到了返回存储位置 i
//  }

    int i;
    for (i=0; i<list->last+1; i++){
        if (x == list->data[i]){
            return i;  // 找到了
        }
    }
    return -1;  // 没找到
}

void Insert(int x, int i, List *list)
{
    if (list->last == MAXSIZE-1){
        printf("表满");
        return;
    }
    if (1 > i || i > list->last+2){
        printf("位置不合法");
        return;
    }
    int j;
    for (j=list->last; j>=i; j--){
        list->data[j+1] = list->data[j];
    }
    list->data[i] = x;  // 将 x 插入 i 位置
    list->last++;       // 更新
}

void Delete(int i, List *list)
{
    // 检查空表及位置合法性
    if (i<1 || i>list->last+1){
        printf("不存在第%d个元素", i);
        return;
    }
    int j;
    for (j=i; j<list->last; j++){
        list->data[j] = list->data[j+1];
    }
    list->last--;
    return;
    
}