数据结构1 线性表1.1 线性表的定义通俗一点来说线性表就是指各个数据元素它们之间的逻辑关系、逻辑结构是这种一条线的结构就是被穿到一起数据元素之间有这样的前后关系。严谨的定义线性表是具有相同数据类型的n(n0)个数据元素的有限序列其中n为表长当n等于0时线性表是一个空表。若用L命名线性表则其一般表示为​ L(a1,a2,…,ai,ai1,…,an)ai是线性表中的第i个元素线性表中的位序位序从1开始数组下标从0开始a1是表头元素an是表尾元素除第一个元素外每个元素有且仅有一个直接前驱除最后一个元素外每个元素有且仅有一个直接后继。1.2 线性表的基本操作InitList(L)初始化表。构造一个空的线性表L分配内存空间DestoryList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e.ListDelete(L,i,e)删除操作删除表L中第i个位置的元素并用e返回删除元素的值LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值其他常用操作Length(L)求表长。返回线性表L的长度即L中数据元素的个数。PrintList(L)输出操作。按前后顺序输出线性表L的所有元素值。Empty(L)判空操作。若L为空表则返回true否则返回false。注意对数据的操作记忆思路——创销、增删改查。C语言函数的定义——返回值类型函数名(参数1类型参数1,参数2类型参数2…)什么时候要传入引用“——对参数的修改结果需要带回来”。总结1.3 顺序表的定义顺序表——用顺序存储的方式来实现的线性表1.4 顺序表的实现顺序存储——把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。元素之间的关系由存储单元的邻接关系来体现。1.4.1 顺序表的实现——静态分配1.4.2 顺序表的实现——动态分配为了让顺序表的大小可变可以利用动态分配的实现方式malloc和free动态申请空间用malloc释放内存空间用freeL.data(ElemType*) malloc(sizeof(ElemType) *InitSize);int*arr(int *)malloc(sizeof(int) *10)malloc(size) → 向系统申请 size 字节的连续内存返回这块内存的起始地址 void* 类型需要强转为指定类型用完必须用free否则内存泄漏malloc申请的总空间大小单个元素的大小*元素的最大数量malloc、free函数的头文件#includestdlib.h练习#include stdio.h // 加了printf需要的头文件 #include stdlib.h // malloc/free的头文件 #define InitSize 10 // 默认最大长度初始化顺序表 // 动态顺序表结构体 typedef struct { int *data; // 动态数组指针 int MaxSize; // 最大容量 int length; // 当前长度 } SeqList; // ✅ 修正C语言用指针传参加了malloc空判断 void InitList(SeqList *L) { // 申请初始内存 L-data (int *)malloc(InitSize * sizeof(int)); if (L-data NULL) { // 必须判断防止申请失败崩溃 printf(初始化失败内存不足\n); exit(1);//程序异常退出 } L-length 0; L-MaxSize InitSize; printf(顺序表初始化完成初始容量%d\n, L-MaxSize); } // ✅ 修正指针传参空判断安全扩容 void IncreaseSize(SeqList *L, int len) { if (len 0) { // 防止无效扩容 printf(扩容长度必须大于0\n); return; } int *p L-data; // 保存旧数组地址 // 申请更大的内存 int newSize L-MaxSize len; L-data (int *)malloc(newSize * sizeof(int)); if (L-data NULL) { // 申请失败恢复原指针不崩溃 printf(扩容失败内存不足\n); L-data p; // 把原指针还回去不丢数据 return; } // 复制旧数据到新数组 for (int i 0; i L-length; i) { L-data[i] p[i]; } free(p); // 释放旧内存 L-MaxSize newSize; // 更新最大容量 printf(顺序表扩容完成新容量%d\n, L-MaxSize); } // ✅ 新增插入元素函数 bool ListInsert(SeqList *L, int pos, int val) { // 位置合法性判断1~length1 if (pos 1 || pos L-length 1) { printf(插入位置不合法\n); return false; } // 容量满了就扩容这里自动扩5也可以手动调 if (L-length L-MaxSize) { IncreaseSize(L, 5); } // 从后往前移动元素给新元素腾位置 for (int i L-length; i pos; i--) { L-data[i] L-data[i - 1]; } L-data[pos - 1] val; // 插入新元素 L-length; return true; } // ✅ 新增打印顺序表函数看运行结果 void PrintList(SeqList *L) { printf(当前顺序表元素); for (int i 0; i L-length; i) { printf(%d , L-data[i]); } printf(\n当前长度%d最大容量%d\n, L-length, L-MaxSize); } int main() { SeqList L; // 声明顺序表 InitList(L); // 初始化传指针 // 插入元素补全原代码的注释 ListInsert(L, 1, 10); ListInsert(L, 2, 20); ListInsert(L, 3, 30); PrintList(L); // 手动扩容5 IncreaseSize(L, 5); PrintList(L); // 继续插入触发自动扩容 for (int i 4; i 15; i) { ListInsert(L, i, i * 10); } PrintList(L); // ✅ 规范手动释放内存 free(L.data); L.data NULL; return 0; }效果图1.5 顺序表的特点随机访问即可以在O(1)时间内找到第i个元素顺序表当中的各个元素的存放位置是连续存放的只要知道第一个元素的存放地址那么后面这些元素的存放地址就可以马上算出来。比如数组只要给一个数组的下标就可以直接找到后面的元素存储密度高每个节点只存储数据元素本身如果是链式存储除了本身还要耗费一定的空间存储指针拓展容量不方便(即便采用动态分配的方式实现拓展长度的时间复杂度也比较高数据要复制到新区域)插入、删除操作不方便需要移动大量元素总结1.6 顺序表的插入和删除1.6.1 插入操作ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e.注意点代码中的int jL.length。类似于int i等于零一个从0往后加一个从length往前减逐步把前面的数移到后一个位置1.6.2 插入操作的时间复杂度1.6.3 删除操作我们在进行删除的操作时把元素依次往前移动一位先移动前面的元素再移动后面的元素而当我们进行插入操作时需要把元素依次往后移动一位先移动后面的再去移动前面的int e-1是为了给e一个无效初始值方便判断删除是否成功这是一个不可能出现在正常顺序表元素里的「标记值」假设顺序表存的都是正整数如果删除失败函数不会修改 e e 就还是 -1 你一眼就能看出来如果删除成功函数会把被删元素的值赋给e就变成了被删的那个数比如 3 元素前移逻辑从第i个位置后的元素依次向前覆盖填补被删元素的空位1.6.4 删除操作的时间复杂度总结1.7 顺序表的查找GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素1.7.1 静态分配数组的按位查找注意第i个元素所对应的数组下标为i-1位序从1开始而数组下标从0开始如果想让代码健壮性更强可以加一个判断i的值是否合法if (i 1 || i L-length 1) {printf(插入位置不合法\n);return false;}1.7.2 动态分配数组的按位查找注意data这个变量是个指针指向顺序表中的第一个数据元素也就是malloc函数申请的一整片的连续内存空间的起始地址1.7.3 按位查找的时间复杂度时间复杂度O(1)的意思是不管数据量n有多大执行这个操作需要的时间都是固定的不会随着n变大而变长。按位查找的时候不需要从头遍历数组那是O(n)的做法只需要做一次简单的地址计算然后直接访问对应内存位置不管顺序表里有10个元素还是10000个元素这个步骤都只做1次时间完全一样1.7.4 动态分配数组的按值查找如果是结构类型如何查找比较是否相等1.7.5 按值查找的时间复杂度总结