C语言数据结构顺序表

一、线性表

线性表（List）：零个或多个数据元素的有限序列。

线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

顺序表

1.顺序表的结构体

#define MaxSize 50
typedef struct {ElemType data[MaxSize]; // 顺序表的元素int length; // 顺序表的当前长度
} SqList;

​ 一维数组可以是静态分配的，也可以是动态分配的。对数组进行静态分配时，因为数组的大小和空间事先已经固定，所以一旦空间占满，再加入新数据就会产生溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数组空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要为线性表一次性地划分所有空间。

动态分配的顺序表存储结构描述为

#define InitSize 100
typedef struct {ElemType *data; // 指示动态分配数组的指针int MaxSize, length; // 数组的最大容量和当前个数
} SeqList;

C 的初始动态分配语句为

L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

C++的初始动态分配语句为

L.data = new ElemType[InitSize];

注意

动态分配并不是链式存储，它同>样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

注意

在各种操作的实现中（包括严蔚>敏老师撰写的教材），往往可以忽略边界条件判断、变量定义、内存分配不足等细节，即不要求代码具有可执行性，而重点在于算法的思想。

2.顺序表的初始化

静态分配和动态分配的顺序表的初始化操作是不同的。静态分配在声明一个顺序表时，就已为其分配了数组空间，因此初始化时只需将顺序表的当前长度设为 0。

// SqList L;
void InitList(SqList &L) {L.length = 0;
}

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为 0。

void InitList(SeqList &L) {L.data = (ElemType*)malloc(InitSize*sizeof(ElemType)); // 分配存储空间L.length = 0; // 顺序表初始长度为 0L.MaxSize = InitSize; // 初始化存储容量
}

3.插入操作

在顺序表 L 的第 i(1<=i<=L.length+1)个位置插入新元素 e。若 i 的输入不合法，返回 false，表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e，顺序表长度增加 1，插入成功，返回 true。

bool ListInsert(SqList &L, int i, ElemType e) {if (i < 1 || i > L.length + 1)return false; // 判断 i 的范围是否有效if (L.length >= MaxSize)return false; // 当前存储空间已满，不能插入for (int j = L.length; j >= i; j--)L.data[j] = L.data[j - 1]; // 将第 i 个元素及之后的元素后移L.data[i - 1] = e; // 在位置 i 处放入 eL.length++; // 线性表长度加 1return true;
}

注意
区别顺序表的位序和数组下标。为何判断插入位

4.删除操作

删除顺序表 L 中第 i(1<=i<=L.length)个位置的元素，并将该位置之后的所有元素依次往前移动一个位置。若 i 的输入不合法，则返回 false；否则，将被删除元素赋给引用变量 e，并将第 i+1 个元素及之后的所有元素依次往前移动一个位置，线性表长度减 1。

bool ListDelete(SqList &L, int i, ElemType &e) {if (i < 1 || i > L.length)return false; // 判断 i 的范围是否有效e = L.data[i - 1]; // 将被删除的元素赋值给 efor (int j = i; j < L.length; j++)L.data[j - 1] = L.data[j]; // 将第 i 个位置后的元素前移L.length--; // 线性表长度减 1return true;
}

注意

最坏情况：删除表头元素(i=1)，需移动除头元素外的所有元素，时间复杂度为 O(n)。
平均情况：假设 p_i(p_i=1/n)是删除第 i 个位置上结点的概率，则在长度为 n 的线性表中删除一个结点时，所需移动结点的平均次数为

$$\sum {i=1}^n{p}_i(n-i)=\sum {i=1}^n\frac{1}{n}(n-i)=\frac{1}{n}\sum {i=1}^n(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}$$

因此，顺序表删除算法的平均时间复杂度为 O(n)。

5.按值查找

在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序。若查找失败，返回 0。

int LocateElem(SqList L, ElemType e) {int i;for (i = 0; i < L.length; i++) {if (L.data[i] == e) // 标记为 i 的元素值等于 e，返回其位序 i+1return i + 1;}return 0; // 退出循环，说明查找失败
}

注意

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 O(1)。
最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为 O(n)。
平均情况：假设 p_i(p_i=1/n)是查找的元素在第 i(1<=i<=L.length)个位置上的概率，则在长度为 n 的线性表中查找值为 e 的元素所需比较的平均次数为

$$\sum {i=1}^n{p}_i\cdot i=\sum {i=1}^n\frac{1}{n}\cdot i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}$$

因此，顺序表按值查找算法的平均时间复杂度为 O(n)。
顺序表按序号查找非常简单，即直接根据数组下标访问数组元素，其时间复杂度为 O(1)。

cpp代码实现

#include<stdio.h>
#include<stdlib.h>//定义结构体 ：静态结构
#define MaxSize 50 //顺序表最大长度 
typedef struct{int data[MaxSize];//顺序表的元素int length;//元素个数 
}SqList; //定义结构体 ；动态结构
#define InitSize  100 //表长度的初始定义
typedef struct{int *data; //顺序表的首地址 int length;//元素个数 
}SeqList; //顺序表的功能(以静态顺序表为例)
bool InitList (SqList &L); //初始化顺序表
bool ListInsert(SqList &L,int i,int e);//给顺序表第i个位置插入元素e
bool ListDelete(SqList &L,int i, int &e);//删除顺序表第i个元素
int LocateElem(SqList L,int e);//按值查找// 打印菜单
void printMenu() {printf("\n顺序表操作菜单：\n");printf("1. 初始化顺序表\n");printf("2. 插入元素\n");printf("3. 删除元素\n");printf("4. 按值查找元素\n");printf("5. 打印顺序表元素\n");printf("6. 退出\n");printf("请输入你的选择：");
}
// 主函数
int main() {SqList L;int choice, position, element, deletedElement;bool success;while (1) {printMenu();scanf("%d", &choice);switch (choice) {case 1:if (InitList(L)) {printf("顺序表初始化成功！\n");} else {printf("顺序表初始化失败！\n");}break;case 2:printf("请输入要插入的位置和元素：");scanf("%d %d", &position, &element);success = ListInsert(L, position, element);if (success) {printf("在位置 %d 插入元素 %d 成功！\n", position, element);} else {printf("插入失败！可能是位置不合法或顺序表已满。\n");}break;case 3:printf("请输入要删除的位置：");scanf("%d", &position);success = ListDelete(L, position, deletedElement);if (success) {printf("删除位置 %d 的元素成功，删除的元素是：%d\n", position, deletedElement);} else {printf("删除失败！可能是位置不合法。\n");}break;case 4:printf("请输入要查找的元素：");scanf("%d", &element);position = LocateElem(L, element);if (position != 0) {printf("元素 %d 在顺序表中的位置是：%d\n", element, position);} else {printf("未找到元素 %d！\n", element);}break;case 5:printf("当前顺序表元素：");for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");break;case 6:printf("退出程序。\n");return 0;default:printf("无效的选择，请重新输入。\n");}}return 0;
}
bool InitList (SqList &L){L.length = 0;/**初始化动态结构 需要使用mallocL.data = (int*)malloc(sizeof(int）*InitSize);L.length = 0; */
}
bool ListInsert(SqList &L,int i,int e){//判断i位置是否合法if(i<1 || i>L.length+1){//说明插入位置越界return false;}//判断顺序表是否满if(L.length>=MaxSize){//顺序表元素已经满/**若是动态分配可以调用扩容函数 进行扩容 */ return false; } //开始插入操作 1.元素后移 for(int j = L.length;j>=i;j--){L.data[j] = L.data[j-1];} //2.插入元素 L.data[i-1] = e;L.length++;return true;
}
bool ListDelete(SqList &L,int i, int &e){//判断i位置是否合法if(i<1 || i>L.length){//说明删除位置越界return false;}e = L.data[i-1];//元素前移 for(int j = i;j<L.length;j++){L.data[j-1] = L.data[j]; } L.length--;return true; 
}
int LocateElem(SqList L,int e){int i;for(i=0;i<L.length;i++){if(L.data[i] == e){ /**注意：如果是顺序表元素是结构体那么不能直接‘==’比较 */return i+1;//返回元素所在的位置 }}return 0;//查找不到 
}