基本概念

线性表定义：长度为n的有序元祖。当n = 0时称为空表。线性表的基本操作是插入和删除。线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。线性表的顺序存储结构是一种随机存取的存储结构。线性表第i个数据元素ai的存储位置是：Loc(ai) = Loc(a1) + (i - 1)l (l为每个元素需占用的存储单元）。

实现

头文件如下：

/* 顺序表头文件 */ #ifndef HEAD_H_INCLUDED #define HEAD_H_INCLUDED #define LIST_INIT_SIZE 100 #define LISTADD 10 typedef int ElemType; typedef struct SqList { ElemType *elem; int length; int listsize; }; //顺序表初始化 bool Init_list(SqList &L); //顺序表是否为空 bool isEmpty(SqList L); //在指定位置添加元素 bool addElem(SqList &L, int i, ElemType e); //删除指定位置元素 ElemType deleteElemByIndex(SqList &L, int i); //删除指定元素 ElemType deleteElemByData(SqList &L, ElemType e); //查找元素位置 int selectIndex(SqList L, ElemType e); //查找指定位置的元素 ElemType selectElem(SqList L, int i); //显示顺序表全部元素 void showup(SqList L); #endif // HEAD_H_INCLUDED

构造空的线性表

bool Init_list(SqList &L){ L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) return false; else{ L.length = 0; L.listsize = LIST_INIT_SIZE; return true; } }

向顺序表中添加新的元素

//在指定位置之前添加元素 bool addElem(SqList &L, int i, ElemType e){ if(i < 1 || i > L.length + 1) { //i超出范围 printf("位置错误\n"); return false; } if(L.length == L.listsize){ //当前存储空间已满，增加分配 ElemType *temp = (ElemType *)realloc(L.elem, (L.listsize + LISTADD) * sizeof(ElemType)); if(!temp) return false; L.elem = temp; L.listsize += LISTADD; } ElemType *q = &(L.elem[i - 1]); for(ElemType *p = &(L.elem[L.length - 1]); p >= q; p --){ *(p+1) = *p; } *q = e; L.length ++; return true; }

这份代码中采用了指针的写法，也可以采用数组的表示方法，会更简单一些。

for(int j = L.length; j >= i; j --){ L.elem[j] = L.elem[j - 1]; } L.elem[i - 1] = e;

删除顺序表中元素

//删除指定位置元素 ElemType deleteElemByIndex(SqList &L, int i){ if(i < 1 || i > L.length){ printf("错误位置\n"); exit(0); }else{ ElemType e = L.elem[i - 1]; while(i < L.length){ L.elem[i - 1] = L.elem[i]; } L.length --; return e; } } //删除指定元素 int deleteElemByData(SqList &L, ElemType e){ for(int i = 0; i < L.listsize; i ++){ if(L.elem[i] == e){ int temp = i; while(temp < L.length){ L.elem[temp] = L.elem[++temp]; } L.length --; return i + 1; } } return -1; }

有两种形式：根据索引删除元素和删除第一个与e相等的元素。

在顺序表中查找元素

//查找元素位置 int selectIndex(SqList L, ElemType e){ for(int i = 0; i < L.listsize; i ++){ if(L.elem[i] == e){ return i + 1; } } } //查找指定位置的元素 ElemType selectElem(SqList L, int i){ return i < 1 || i > L.length +1 ? -1 : L.elem[i-1]; } //显示顺序表全部元素 void showup(SqList L){ for(int i = 0; i < L.length; i ++){ printf("%d ", L.elem[i]); } printf("\n"); }

整理

完整代码地址：GitHub