c-数据结构（顺序表、链表）
概念
对于n各元素的线性表，严格数学定义：其中任意一个数据元素a[i]，有且仅有一个前驱a[i-1]，有且仅有一个后继a[i+1]；首元素a[0]无前驱，尾元素a[n-1]无后继。
顺序表
属于线性表，数据之间的空间是连续，如具名的栈数组，匿名的堆数组。
链表
属于线性表，数据之间的空间不连续（离散），如结构体。
单链表
-
顺序表设计
-
顺序表容量；
-
顺序表当前最末元素下标位置；
-
顺序表指针；
顺序表
-
-
顺序表的相关数据操作代码 //math文件夹 ------------------------------------------------------------------------------------------ seqlist.h ------------------------------------------------------------------------------------------ #ifndef __SEQLIST_H #define __SEQLIST_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> //定义顺序表的结构体 typedef struct { int capacity;//顺序表的容量（本质为数组）； int last;//末元素下标 int* data;//数据 } seqList; //创建顺序表 seqList *initList(int cap); //判断顺序表是否满了 bool isFull(seqList *list); //向顺序表表头插入新数据 bool insert(seqList *list, int data); //遍历顺序表元素 void show(seqList *list); //删除顺序表指定元素 bool removeNode(seqList *list, int data); //销毁顺序表 void destroy(seqList *list); #endif ------------------------------------------------------------------------------------------ seqlist.c ------------------------------------------------------------------------------------------ #include "seqlist.h" //初始化顺序表 seqList *initList(int cap) { //申请内存 seqList *list = malloc(sizeof(seqList)); //顺序表非空校验 if(list != NULL) { //给数据区分配空间 list->data = malloc(cap * sizeof(int)); if(list->data == NULL) { free(list); return NULL; } list->capacity = cap; list->last = -1; } } //判断顺序表是否满了 bool isFull(seqList *list) { return list->last == list->capacity - 1;//尾结点与下标的对应关系 } //向顺序表表头插入新数据 bool insert(seqList *list, int data) { //判断顺序表是否满了 if(isfull(list)) { return false; } //将原有数据全部向后移动一位，腾出空间 for(int i = list->last; i >= 0; i--) { list->data[i+1] = list->data[i]; } //将数据插入表头 list->data[0] = data; list->last++; return true; } //遍历顺序表元素 void show(seqList *list) { //判断是否为空 if(list->lats == -1) { return; } //遍历 for(int i = 0; i <= list->last; i++) { printf("%d ", list->data[i]); } printf("\n"); } //删除顺序表指定元素 bool removeNode(seqList *list, int data) { //判断顺序表是否为空 if(isFull(list)) { return false; } //找到要产出元素结点 int pos; for(int i = 0; i <= list->last; i++) { if(list->data[i] == data) { pos = i; break; } } //若找不到要删除的的节点 if(i > list->last) { return false; } //将截至到删除节点后所有元素前移 for(int i = pos; i < list->last; i++) { list->data[i] = list->data[i+1]; } list->last--; return true; } //销毁顺序表 void destroy(seqList *list) { if(list == NULL) { return; } free(list->data);//销毁顺序表中的是数据 free(list);//销毁顺序表 } ------------------------------------------------------------------------------------------ seqlist_main.c ------------------------------------------------------------------------------------------ #include "seqlist.h" int main() { //创建顺序表 seqList *list = initList(10); if(lits == NULL) { perror("初始化顺序表失败！"); //结束进程 exit(0); } else { printf("初始化顺序表成功！"); } int n;//键盘录入整数 printf("请输入人一个整数：\n"); while(true) { scanf("%d", &n); //控制循环跳出 if(n == 0) { printf("循环跳出\n"); break; } else if(n > 0) { //插入数据 if(!insert(list,n)) { printf("容量已满，插入失败！\n"); continue; } } else { //删除数据 if(!removeNode(list,-n)) { printf("查无此数，删除失败！\n"); continue; } } //遍历顺序表 show(list); } //销毁 destroy(list); }顺序表优缺点
-
优点
-
无需多余信息来记录数据间关系，数据存储密度高；
-
存储空间连续，随机访问速度快；
-
-
缺点
-
插入删除数据时，需要成片移动数据，很不方便；
-
数据节点较多时，需要一整片较大连续空间；
-
数据节点数量变化剧烈，内存的释放和分配不灵活；
-
-
单链表基本操作
-
节点设计；
-
初始化空链表；
-
增删节点；
-
链表遍历；
-
销毁链表；
-
-
单链表
单链表相关数据操作代码 //math1文件夹 ---------------------------------------------------------------------------------------------- slist.h ---------------------------------------------------------------------------------------------- #ifndef__SLIST_H #define __SLIST_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef int DATA; //创建单链表的结构体 typedef struct Node { DATA data;//存储数据 struct Node *next;//存储下一节点地址 }NODE; //初始化单链表结构体 int slist_create(NODE**, DATA); //向单链表插入一个数据（头插法） int slist_addHead(NODE**, DATA); //向单链表插入一个数据（尾插法） int slist_addTail(NODE**, DATA); //向单链表插入一个数据（中间插法） int slist_insert(NODE**, DATA, DATA); //删除单链表中的数据 int slist_delete(NODE**, DATA);参考中间插法 //查找链表中的数据 NODE* slist_find(const NODE*, DATA); //修改更新链表数据 int slist_update(const NODE*, DATA, DATA); //遍历链表 void slist_showAll(const NODE*); //销毁单链表 void slist_destroy(NODE**); #endif ---------------------------------------------------------------------------------------------- slist.c ---------------------------------------------------------------------------------------------- #include "slist.h" /* @function: int slist_create(NODE** head,DATA data); @berif: 创建单项链表 @argument: head: 指向头指针变量的地址，用来接收首节点地址 data: 存储在节点中的数据 @return : 成功返回 0 失败返回 -1 */ //初始化单链表结构体 int slist_create(NODE** head, DATA data) { NODE* p = (NODE*)malloc(sizeof(NODE)); //非空校验 if(!p) { return -1; } //单链表赋初值 p->data = data; p->next = NULL; *head = p; return 0; } /* @function: int slist_addHead(NODE** head,DATA data); @berif: 向链表头部插入一个节点数据 @argument: head: 指向头指针变量的地址，用来接收首节点地址 data: 存储在新节点中的数据 @return : 成功返回 0 失败返回 -1 */ //向单链表插入一个数据（头插法） int slist_addHead(NODE** head, DATA data) { NODE* p = (NODE*)malloc(sizeof(NODE)); if(!p) { return -1; } p->data = data; p->next = *head; *head = p; return 0; } /* @function: int slist_addTail(NODE** head,DATA data); @berif: 向链表尾部插入一个节点数据 @argument: head: 指向头指针变量的地址，用来接收首节点地址 data: 存储在新节点中的数据 @return : 成功返回 0 失败返回 -1 */ //向单链表插入一个数据（尾插法） int slist_addTail(NODE** head, DATA data) { NODE* pNew = (NODE*)malloc(sizeof(NODE)); if(!pNew) { return -1; } pNew->data = data; pNew->next = NULL; //寻找尾节点，默认头节点为尾节点，并创建临时变量q NODE *p = *head, *q = NULL; if(!p) { *head = pNew; return 0; } while(p) { q = p; p = p->next; } q->next = pNew;//将要插入的数放在原先尾节点的后面作为新的尾节点 return 0; } /* @function: int slist_insert(NODE** head,DATA pos ,DATA data); @berif: 向链表节点值为pos的位置插入一个节点数据data @argument: head: 指向头指针变量的地址 pos: 插入节点位置的节点数据 data: 存储在新节点中的数据 @return : 成功返回 0 失败返回 -1 */ //向单链表插入一个数据（中间插法） int slist_insert(NODE** head, DATA pos, DATA data) { //创建新节点 NODE *pNew = (NODE*)malloc(sizeof(NODE)); if(!pNew) { return -1; } //给新结点赋值 pNew->data = data; pNew->next = NULL; NODE *p = *head, *q = NULL; //第一种情况，若原链表无任何一个节点 if(!p) { *head = pNew;//新节点作为头节点 return 0; } //第二种情况，原链表只有一个头节点 if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0) { pNew->next = *head;//头插法 *head = pNew; return 0; } //第三种情况，原链表有多个节点 while(p) { //尾插法 if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0) { //两句顺序不可调换，否则会覆盖 pNew->next = p; q->next = pNew; return 0; } //此时，q为前驱，p为后继;依次往后走 q = p; p = p->next; } //第四种情况，要插入的位置pos不存在 q->next = pNew; return 0; } /* @function: int slist_delete(NODE** head,DATA data); @berif: 删除链表中节点值为data的节点 @argument: head: 指向头指针变量的地址 data: 删除节点中的数据 @return : 成功返回 0 失败返回 -1 */ //删除单链表中的数据 int slist_delete(NODE** head, DATA data) { NODE* p = *head, *q = NULL; //第一种情况，若原链表无任何一个节点 if(!p) { return -1; } //第二种情况，要删除的刚好是头节点 if(memcmp(&(p->data),&data,sizeof(DATA)) == 0) { *head = p->next; free(p); return 0; } //第三种情况，逐个查找要删除的节点 while(p) { if(memcmp(&(p->data),&data,sizeof(DATA)) == 0) { q->next = p->next; //这一步释放p并不影响数据的删除 free(p); return 0; } q = p; p = p->next; } return -1; } /* @function: NODE* slist_find(const NODE* head,DATA data); @berif: 查找链表数据data @argument: head: 指向头指针变量 data: 待查找的数据 @return : 成功返回节点的地址 失败返回NULL */ //查找链表中的数据 NODE* slist_find(const NODE* head, DATA data) { const NODE* p = head; while(p) { if(memcmp(&(p->data),&data,sizeof(DATA)) == 0) { return (NODE*)p; } p = p->next; } return NULL; } /* @function: int slist_update(const NODE* head,DATA old,DATA newdata); @berif: 更新链表数据old 为 newdata @argument: head: 指向头指针变量 old: 待更新的节点数据 newdata: 更新后的节点数据 @return : 成功返回 0 失败返回 -1 */ //修改更新链表数据 int slist_update(const NODE* head, DATA old_data, DATA new_data) { NODE* p = NULL; if( !(p = slist_find(head,old_data)) ) { return -1; } p->data = new_data; return 0; } /* @function: void slist_showAll(const NODE* head); @berif: 遍历链表数据 @argument: head: 指向头指针变量 @return : 无 */ //遍历链表 void slist_showAll(const NODE* head) { const NODE* p = head; while(p) { printf("%d ", p->data); p = p->next; } printf("\n"); } /* @function: void slist_destroy(NODE** head); @berif: 回收链表 @argument: head: 指向头指针变量的地址 @return : 无 */ //销毁单链表 void slist_destroy(NODE** head) { NODE* p = *head, *q = NULL; while(p)//逐个遍历回收 { q = p; p = p->next; free(q); } *head = NULL; } ---------------------------------------------------------------------------------------------- slist_main.c ---------------------------------------------------------------------------------------------- #include "slist.h" #define DELETE 1 int main() { NODE *head = NULL; if (slist_create(&head, 888) < 0) { perror("单链表创建失败！"); // exit(0); return -1; } printf("单链表创建成功！\n"); slist_addTail(&head, 999); slist_addTail(&head, 222); slist_addTail(&head, 666); slist_addTail(&head, 777);// 运行效果：999 222 666 777 slist_addHead(&head, 555);// 运行效果：555 999 222 666 777 slist_insert(&head, 555, 1024);// 运行效果：1024 555 999 222 666 777 slist_insert(&head, 222, 1080);// 运行效果：1024 555 999 1080 222 666 777 slist_showAll(head); DATA data; while (1) { #ifdef DELETE printf("请输入要删除的数据:"); scanf("%d", &data); if (data == -1) break; if (slist_delete(&head, data) < 0) { puts("删除失败,请重试"); continue; } slist_showAll(head); #else NODE *pFind = NULL; DATA newdata = 512; printf("请输入要查找的数据:"); scanf("%d", &data); if (data == -1) break; // if(!(pFind = slist_find(head,data))) if (slist_update(head, data, newdata) == -1) { puts("查找的数据不存在,请重试"); continue; } // printf("查找数据:%d 内存地址:%p\n",pFind -> data, &(pFind -> data)); slist_showAll(head); #endif } slist_destroy(&head); puts("====销毁后===="); slist_showAll(head); return 0; }双链表
双链表相关数据操作代码 //math2文件夹 ---------------------------------------------------------------------------------------------- dlist.h ---------------------------------------------------------------------------------------------- #ifndef __DLIST_H #define __DLIST_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef int DATA; //定义双向链表结构体 typedef struct node { DATA data; //数据 struct node *prev; //前驱指针 struct node *next; //后继指针 }NODE; //创建双向链表 int dlist_create(NODE**, DATA); //向双链表插入数据（头插法） int dlist_addHead(NODE**, DATA); //向双链表插入数据（尾插法） int dlist_addTail(NODE**, DATA); //向双链表插入数据（中间插法） int dlist_insert(NODE**, DATA, DATA); //链表数据查询 NODE* dlist_find(const NODE*, DATA); //链表数据更新 int dlist_update(const NODE*, DATA, DATA); //链表数据遍历 void dlist_showAll(const NODE*); //链表数据删除 int dlist_delete(NODE**, DATA); //销毁双链表 void dlist_destroy(NODE**); #endif ---------------------------------------------------------------------------------------------- dlist.c ---------------------------------------------------------------------------------------------- #include "dlist.h" //创建双向链表 int dlist_create(NODE** head, DATA data) { //创建新节点 NODE* pNew = (NODE*)malloc(sizeof(NODE)); //判断是否申请成功 if(!pNew) { return -1; } //给节点赋初值 pNew->data = data; //数据 pNew->prev = pNew->next = NULL; //前驱后继指向空 *head = pNew; //新节点作为头节点 return 0; } //向双链表插入数据（头插法） int dlist_addHead(NODE** head, DATA data) { //创建新节点，申请内存空间 NODE *pNew = (NODE*)malloc(sizeof(NODE)); //判断是否申请成功 if(!pNew) { return -1; } //给新节点赋值 pNew->data = data; pNew->prev = NULL; pNew->next = *head; //如果头节点存在 if(*head) { (*head)->prev = pNew; } *head = pNew; return 0; } //向双链表插入数据（尾插法） int dlist_addTail(NODE** head, DATA data) { //创建新节点，申请内存 NODE *pNew = (NODE*)malloc(sizeof(NODE)); //判断是否申请成功 if(!pNew) { return -1; } //给新节点赋初值 pNew->data = data; pNew->next = pNew->prev = NULL; NODE *p = *head; //第一种情况，头节点不存在 if(!p) { *head = pNew; return 0; } //第二种情况，有一个或多个结点 while (p->next) //循环来找到尾结点 { p = p->next; } //尾节点的后继指向新插入节点 p->next = pNew; //新插入节点的前驱指向尾节点 pNew->prev = p; return 0; } //向双链表插入数据（中间插法） int dlist_insert(NODE** head, DATA pos, DATA data) { //创建新节点，申请空间 NODE* pNew = (NODE*)malloc(sizeof(NODE)); //判断是否申请成功 if(!pNew) { return -1; } //给新节点赋初值 pNew->data = data; pNew->next = pNew->prev = NULL; NODE* p = *head, *q = NULL; //第一种情况，没有头节点 if(!p) { *head = pNew; return 0; } //第二种情况，只有一个头节点 if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0) { pNew->next = p; p->prev = pNew; *head = pNew; return 0; } //第三种情况，有多个节点 while (p) { if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0) { /* 顺序：先自己再别人，先后再前 */ pNew->next = p; pNew->prev = q; p->prev = pNew; q->next = pNew; return 0; } q = p; p = p->next; } //第四种情况，找不到要插入的位置(也就是找不到pos) q->next = pNew; pNew->prev = q; return 0; } //链表数据查询 NODE* dlist_find(const NODE* head, DATA data) { const NODE* p = head; while (p) { if (memcmp(&(p->data),&data,sizeof(DATA)) == 0) { return (NODE*)p; } //向后查询 p = p->next; //向前查询 //p = p->prev; } return NULL; } //链表数据更新 int dlist_update(const NODE* head, DATA old_data, DATA new_data) { NODE* p = NULL; if( !(p = dlist_find(head,old_data))) { return -1; } p->data = new_data; return 0; } //链表数据遍历 void dlist_showAll(const NODE* head) { const NODE* p = head; while(p) { //两种遍历方式不可同时使用 printf("%d ", p->data); //向后遍历 p = p->next; //向前遍历 //p = p->prev; } printf("\n"); } //链表数据删除 int dlist_delete(NODE** head, DATA data) { NODE* p = *head; //第一种情况，原链表没有节点 if(!p) { return -1; } //第二种情况，要删除的刚好是头节点 if(memcmp(&(p->data),&data,sizeof(DATA)) == 0) { //1.链表中只有一个节点 if(p->next == NULL) { free(p); *head = NULL; return 0; } //2.链表中有两个以上节点 *head = p->next; //此前head和p都指向头节点 p->next->prev = NULL; //解除p的引用关系 free(p); return 0; } //第三种情况，逐个查找要删除节点 while (p) { if(memcmp(&(p->data),&data,sizeof(DATA)) == 0) { p->prev->next = p->next; //解除上一个节点和被删节点的关系 //要删除的p刚好是尾节点 if(p->next == NULL) { p->prev->next = NULL; } else //要删除的p不是尾节点 { p->next->prev = p->prev; } free(p); return 0; } p = p->next; //改变循环条件 } return -1; } //销毁双链表 void dlist_destroy(NODE** head) { NODE* p = *head, *q = NULL; while (p) { //实现指针尾随 q = p; p = p->next; free(q); } *head = NULL; } ---------------------------------------------------------------------------------------------- dlist_main.c ---------------------------------------------------------------------------------------------- #include "dlist.h" #define OP 2 int main(void) { NODE* head = NULL; int a[] = {1,3,5,7,9}; int n = sizeof a / sizeof a[0]; register int i = 0; for(; i < n; i++) { dlist_addTail(&head,a[i]); } dlist_showAll(head); while(1) { #if (OP == 0) DATA data; NODE *pFind = NULL; printf("请输入要查找的数据(-1 退出):"); scanf("%d",&data); if(data == -1) break; if(!(pFind = dlist_find(head,data))) { puts("查找的数据不存在,请重试..."); continue; } printf("在内存地址为 %p 的内存空间中找到了 %d\n",&(pFind->data),pFind->data); #elif (OP == 1) DATA data; NODE *pFind = NULL; printf("请输入要插入位置的数据(-1 退出):"); scanf("%d",&data); if(data == -1) break; if(dlist_insert(&head,data,407)) { puts("插入失败,请重试..."); continue; } dlist_showAll(head); #else DATA data; NODE *pFind = NULL; printf("请输入要删除位置的数据(-1 退出):"); scanf("%d",&data); if(data == -1) break; if(dlist_delete(&head,data)) { puts("删除失败,请重试..."); continue; } dlist_showAll(head); #endif } dlist_destroy(&head); puts("=====回收后===="); dlist_showAll(head); return 0; }链表优缺点
-
优点
-
插入删除数据仅需调整几个指针，较为便捷；
-
数据节点较多时，无需整片连续空间，可利用离散内存；
-
节点变化剧烈时，内存的分配和释放灵活、速度快；
-
-
缺点
-
不支持立即随机访问任意随机数据；
-
需要多余指针记录节点间的关联关系；
-
原文地址：https://blog.csdn.net/LHB15173352347/article/details/141750495
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！