概念
对于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;//寻找尾节点,默认头节点为尾节点,并创建临时变量qNODE *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 1int 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 777slist_addHead(&head, 555); // 运行效果:555 999 222 666 777slist_insert(&head, 555, 1024); // 运行效果:1024 555 999 222 666 777slist_insert(&head, 222, 1080); // 运行效果:1024 555 999 1080 222 666 777slist_showAll(head);DATA data;while (1){ #ifdef DELETEprintf("请输入要删除的数据:");scanf("%d", &data);if (data == -1)break;if (slist_delete(&head, data) < 0){puts("删除失败,请重试");continue;}slist_showAll(head); #elseNODE *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); #elseDATA 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; }
链表优缺点
-
优点
-
插入删除数据仅需调整几个指针,较为便捷;
-
数据节点较多时,无需整片连续空间,可利用离散内存;
-
节点变化剧烈时,内存的分配和释放灵活、速度快;
-
-
缺点
-
不支持立即随机访问任意随机数据;
-
需要多余指针记录节点间的关联关系;
-