数据结构基础代码study log

线性表顺序表创建表静态表代码#include stdio.h #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int length; }SqList;//静态表 void InitList(SqList * L) { /*for(int i0;iMAXSIZE;i) L.data[i]0; */L-length0; } int main() { SqList L; InitList(L); for(int i0;iMAXSIZE;i) printf(data[%d]%d\n,i,L.data[i]); return 0; }动态表代码#include stdio.h #include stdlib.h #define InitSize 10//顺序表初始长度 typedef struct { int *data; //指示动态分配数组的指针 int MaxSize; int length; } SeqList; void InitList(SeqList *L) { L-data (int *)malloc(InitSize * sizeof(int)); if (!L-data) { printf(内存分配失败\n); exit(1); } L-MaxSize InitSize; L-length 0; } void IncreaseSize(SeqList *L, int len) { int *pL-data; L-data(int *)malloc((L-MaxSizelen)*sizeof(int)); for(int i0;iL-length;i) L-data[i]p[i]; L-MaxSizelen; free(p); } int main() { SeqList L; InitList(L); printf(Size of SeqList: %zu bytes\n, sizeof(L)); printf(MaxSize: %d, length: %d\n, L.MaxSize, L.length); IncreaseSize(L, 5); printf(After increasing size:\n); printf(MaxSize: %d, length: %d\n, L.MaxSize, L.length); free(L.data); // 释放动态分配的内存 return 0; }free第一次申请空间不需要释放第二次扩展空间需要释放掉旧空间如果不释放容易内存泄漏。后果// 如果 IncreaseSize 不写 free(p) // 每次扩容都丢一块旧内存 // 程序运行久了内存被占光系统变慢甚至崩溃这是 C 语言手动管理内存的核心谁申请谁释放不用了就释放。插入操作代码#include stdio.h #include stdbool.h #define MaxSize 10 typedef struct { int data[MaxSize]; int length; }SqList; bool ListInsert(SqList *L,int i,int e){ if(i1||iL-length1)//判断i的范围是否有效 return false; if(L-lengthMaxSize)//当前存储空间已满不能插入 return false; for(int jL-length;ji;j--) L-data[j]L-data[j-1]; L-data[i-1]e; L-length; return true; } int main() { SqList L; ListInsert(L,3,3); return 0; }时间复杂度O(n)健壮性怎么让别人调用我的代码爽并且还不容易出错❗f(i1||iL-length1)必须是length1才能在尾部追加数据初始顺序表数据法一初始化表后逐个插入int main() { SqList L; InitList(L); // 逐个插入6个数据 ListInsert(L, 1, 3); ListInsert(L, 2, 1); ListInsert(L, 3, 4); ListInsert(L, 4, 1); ListInsert(L, 5, 5); ListInsert(L, 6, 9); // 打印验证 for (int i 0; i L.length; i) printf(%d , L.data[i]); // 输出: 3 1 4 1 5 9 return 0; }法二直接赋值初始化更快void InitListWithData(SqList *L) { // 直接给数组赋值再设置长度 int initData[] {3, 1, 4, 1, 5, 9}; for (int i 0; i 6; i) { L-data[i] initData[i]; } L-length 6; } int main() { SqList L; InitListWithData(L); // 一步搞定 for (int i 0; i L.length; i) printf(%d , L.data[i]); // 3 1 4 1 5 9 return 0; }法三封装成通用函数// 从数组批量初始化 void InitListFromArray(SqList *L, int arr[], int n) { for (int i 0; i n; i) { L-data[i] arr[i]; } L-length n; } int main() { SqList L; int arr[] {3, 1, 4, 1, 5, 9}; InitListFromArray(L, arr, 6); for (int i 0; i L.length; i) printf(%d , L.data[i]); return 0; }enum枚举typedef enum { false, true } bool;替代stdbool.h //C99才有删除操作代码#include stdio.h #include stdbool.h #define MaxSize 10 typedef struct { int data[MaxSize]; int length; }SqList; void InitList(SqList *L){ L-length0; } bool ListInsert(SqList *L,int i,int e){ if(i1||iL-length1) return false; if(L-lengthMaxSize) return false; for(int jL-length;ji;j--) L-data[j]L-data[j-1]; L-data[i-1]e; L-length; } bool ListDelete(SqList *L,int i,int *e){ if(i1||iL-length) return false; *eL-data[i-1]; for(int ji;jL-length;j) L-data[j-1]L-data[j]; L-length--; return true; } int main() { SqList L; InitList(L); ListInsert(L,1,3); ListInsert(L,2,3); ListInsert(L,3,7); ListInsert(L,4,3); ListInsert(L,5,3); ListInsert(L,6,9); int e-1; if(ListDelete(L,3,e)) printf(已删除第3个元素删除元素值为%d\n,e); else printf(位序L不合法删除失败\n); return 0; }时间复杂度O(n)位序从1开始数组下标从0开始为什么插入操作传的是int e而删除操作传的是int *e?因为ListDelete(L,3,e)是需要打印出删除的数据所以不能直接用int e。查找操作按位查找一个典型的错误#includestdio.h #includestdbool.h #define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList *L,int InitData[],int n){ for(int i0;in;i) L-data[i]InitData[i]; L-lengthn; } bool GetElem(SqList *L,int i,int *e){ if(i1||iL-length)//判断i的1范围是否有效 return false; *eL-data[i-1]; return true; } int main(){ SqList L; int InitData[]{3,4,1,3,2,5,5}; InitList(L,InitData,7); int *value; if(GetElem(L,3,value)) printf(第三个元素是%d\n,value); else printf(查询失败\n); return 0; }错误一野指针int *value未初始化就传进去了int *value; // ❌ 野指针指向随机地址 GetElem(L, 3, value); // ❌ 传的是未初始化的指针会崩溃或乱码 printf(%d\n, value); // ❌ 打印的是指针变量的地址不是值错误二printf用了value写法含义结果value变量本身的值✅ 正确value变量的地址❌ 打印出来是一串奇怪的数字*value指针解引用只有指针才能用用普通变量 取地址int value; // ✅ 普通变量有实际内存 GetElem(L, 3, value); // ✅ 传地址让函数能写入 printf(%d\n, value); // ✅ 打印值不是地址是取地址运算符你有普通变量函数要指针→ 加你已经有指针了 → 直接传不加函数要指针的指针**→ 加取指针的地址常见的错误int value; int *p value; GetElem(L, 3, value); // ✅ value 是普通变量加 GetElem(L, 3, p); // ✅ p 已经是指针直接传 GetElem(L, 3, p); // ❌ 多加了传的是 int**类型不匹配 GetElem(L, 3, value); // ❌ 忘加了传的是 int类型不匹配完整代码静态表#includestdio.h #includestdbool.h #define MaxSize 10 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList *L,int InitData[],int n){ for(int i0;in;i) L-data[i]InitData[i]; L-lengthn; } bool GetElem(SqList *L,int i,int *e){ if(i1||iL-length)//判断i的1范围是否有效 return false; *eL-data[i-1]; return true; } int main(){ SqList L; int InitData[]{3,4,1,3,2,5,5}; InitList(L,InitData,7); int value; if(GetElem(L,3,value)) printf(第三个元素是%d\n,value); else printf(查询失败\n); return 0; }动态表所以malloc函数申请连续空间前要强转(int *),使其返回的存储空间起始地址要转换为与数据元素的数据类型相对应的指针。时间复杂度O(1)按值查找代码#includestdio.h #includestdlib.h #define InitSize 10 typedef struct{ int *data; int MaxSize; int length; }SeqList; void InitList(SeqList *L){ L-data(int*)malloc(InitSize*sizeof(int)); if(!L-data){ printf(内存分配失败\n); exit(1); } L-MaxSizeInitSize; int arr[]{1,8,9,3,4,2}; for(int i0;i6;i) L-data[i]arr[i]; L-length6; } int LocateElem(SeqList *L,int e){ for(int i0;iL-length;i) if(L-data[i]e) return i1; return 0; } int main(){ SeqList L; InitList(L); if(LocateElem(L,9)) printf(数值为9的位序为:%d\n,LocateElem(L,9)); else printf(此顺序表中无此数值); return 0; }Tip:链表链式存储单链表不带头结点的单链表typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ return (LNULL); //空表防止脏数据 } void test(){ LinkList L;//声明一个指向单链表的指针 IniteList(L); //.... }带头结点的单链表typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LinkList) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有节点 return true; } void test(){ LinkList L;//声明一个指向单链表的指针 IniteList(L); //.... }//声明一个指向单链表第一个结点的指针 LNode * L; LinkList L;指针的注意事项1. 指针本身是值只读不改指向void PrintList(LinkList L) { // L 是 LNode* 类型 LNode *p L-next; while (p) { printf(%d , p-data); p p-next; } } int main() { LinkList L; InitList(L); // ... PrintList(L); // ✅ 直接传 L不需要 }2. 要修改指针本身的指向如初始化、头插bool InitList(LinkList *L) { // L 是 LNode** 类型指针的指针 *L (LinkList)malloc(sizeof(LNode)); (*L)-next NULL; return true; } int main() { LinkList L; // L 目前是未初始化的野指针 InitList(L); // ✅ 传 L让函数能修改 L 的指向 }3. 要修改指针指向的内容如修改节点的 datavoid SetData(LNode *p, int e) { // p 是 LNode* 类型 p-data e; // 修改 p 指向的节点的数据 } int main() { LinkList L; InitList(L); LNode *p L-next; SetData(p, 99); // ✅ 直接传 p不需要 }指针指向的内容如 data、next LNode *p 、SetData(p)指针本身的指向如让 L 指向新节点 LinkList *L 、InitList(L)改内容→ 传指针改指向→ 传指针的地址指针和解指针int a 10; int *p a; // 指针本身 printf(%p, p); // 输出地址0x7ffd5c printf(%p, p); // p 自己的地址0x7ffd50 // 解指针 printf(%d, *p); // 输出内容10 *p 20; // 修改 a 的值插入操作按位序插入#includestdio.h #includestdlib.h #includestdbool.h typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LNode*) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有结点 return true; } //在第I个位置插入元素e bool ListInsert(LinkList L, int i,int e) { if(i1) return false; LNode *p; //指针p指向当前扫描到的节点 int j0; //当前p指向的是第几个结点 pL; //L指向头结点头结点是第0个结点不存数据 while(p!NULLji-1){//循环找到i-1个结点 pp-next; j; } if(pNULL) //i值不合法 return false; LNode *s(LNode *)malloc(sizeof(LNode)); s-data e; s-nextp-next; p-nexts; return true; }不带头结点的话需要修改头指针的指向。指定结点后插#includestdio.h #includestdlib.h #includestdbool.h typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LNode*) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有结点 return true; } bool InsertNextNode(LNode *p,int e){ if(pNULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if(sNULL) //有可能发生内存满了 return false; s-data e; s-nextp-next; p-nexts; } //在第I个位置插入元素e bool ListInsert(LinkList L, int i,int e) { if(i1) return false; LNode *p; //指针p指向当前扫描到的节点 int j0; //当前p指向的是第几个结点 pL; //L指向头结点头结点是第0个结点不存数据 while(p!NULLji-1){//循环找到i-1个结点 pp-next; j; } return InsertNextNode(p,e); }指定结点前插法一法二#includestdio.h #includestdlib.h #includestdbool.h typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LNode*) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有结点 return true; } bool InsertPriorNode(LNode *p,LNode *s){ if(pNULL||sNULL) return false; s-nextp-next; p-nexts; int tempp-data; p-datas-data; s-datatemp; return true; } /删除操作按位序删除带头结点#includestdio.h #includestdlib.h #includestdbool.h typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LNode*) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有结点 return true; } bool ListDelete(LinkList L,int i,int *e){ if(i1) return false; LNode *p; int j0; pL; while (p!NULLji-1) { pp-next; j; } if(pNULL) return false; if(p-next NULL) return false; LNode *qp-next; *eq-data; p-nextq-next; free(q); return true; }按指定结点的删除#includestdio.h #includestdlib.h #includestdbool.h typedef struct LNode{//定义单链表节点类型 int data; //定义每个结点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList *L){ *L(LNode*) malloc(sizeof(LNode));//分配头结点 if (*LNULL)//内存不足分配失败 return false; (*L)-nextNULL; //头结点之后暂时还没有结点 return true; } bool DeleteLNode(LNode *p){ if(pNULL) return false; LNode *qp-next;//但如果是尾结点这就会报错就只能从表头进行遍历查找然后删除。 p-nextq-next; free(q); return true; }