数据结构——线性关系
数据结构——线性关系
- 🍃线性关系
- 🌿线性关系的顺序存储
- 🍀顺序表的定义
- 🍀创建动态顺序表
- 🍀插入元素
- 🍀显示元素
- 🍀删除元素
- 🍀销毁顺序表
- 🍀导入导出
- 🌿线性关系的链式存储
- 🍀单链表
- ☘️单链表的定义
- ☘️单链表的创建
- ☘️插入元素
- ☘️显示元素
- ☘️删除元素
- ☘️销毁单链表
- 🍀双链表
- ☘️双链表的定义
- ☘️双链表的其他操作
- 🌿顺序表、��表、线性表的区别
🍃线性关系
两个变量之间存在一次方函数关系，就称它们之间存在线性关系。
🌿线性关系的顺序存储
顺序表：（以学生管理系统为例子）
特点：
- 元素是一对一的
- 在逻辑上相邻的元素，在物理空间上也相邻
- 大小固定
- 对于静态顺序表：表满不能存、表空不能取
🍀顺序表的定义
typedef struct student { char name[20]; char add[20]; }data_type; typedef struct list { data_type (*Data)[]; //指向数组的指针,存储空间 int size； //当前顺序表的存储能力 int count; //表示当前表实际有效元素的个数 }List;🍀创建动态顺序表
//函数功能：创建顺序表
//函数形式参数的作用：传递信息
//函数参数：void
//函数返回值：地址，指向创建的顺序表
//定义函数：函数返回值数据类型 函数名(形参列表)
List *CreatList(void) { int mysize = 0; List *pList = NULL; puts("请输入要创建的大小:"); scanf("%d", &mysize); //创建顺序表 pList = (List *)malloc(sizeof(List)); if(NULL == pList) { perror("Creat error"); return NULL; } memset(pList, 0, sizeof(List)); //创建顺序表的存储空间 pList->Data = (data_type *)malloc(mysize * sizeof(data_type)); //void *malloc(size); if(NULL == pList->Data) { perror("Creat error"); return NULL; } memset(pList->Data, 0, mysize * sizeof(data_type)); //给大小赋值 pList->size = mysize; return pList; }🍀插入元素
//函数功能：插入元素
//函数参数1：被插入的表
//函数参数2：插入元素的位置
//函数参数3：插入的值
//函数返回值：成功返回OK，失败返回原因
int InserItem(List *pList, int pos, date_type item) { //入参判断 if(!pList) { return LIST_NULL; } //位置判断 if(pos pList->count) { return POS_ERROR; } //空满判断 if(pList->count == pList->size) { return LIST_FULL; } //移出插入空间 for(int i=pList->count; i>pos; i--) { //将当前位置的元素后移 pList->Data[i] = pList->Data[i-1]; } //插入元素 pList->Data[pos] = item; //总数增加 pList->count++; return OK; }🍀显示元素
//函数功能：显示元素
//函数参数：要显示的表
//函数返回值：成功返回OK，失败返回原因
int ShowList(List *pList) { //入参判断 if(!pList) { return LIST_NULL; } //空表判断 if(pList->count == 0) { return LIST_EMPTY; } //打印元素 for(int i=0; icount; i++) { printf("%d ",pList->Data[i]); } printf("\n"); return OK; }🍀删除元素
//函数功能：删除元素
//函数参数1：要删除元素的表
//函数参数2：删除的位置
//函数参数3：删除的值
//函数返回值：成功返回OK，失败返回原因
int DeleteItem(List *pList, int pos, data_type *item) { //入参判断 if(!pList) { return LIST_NULL; } //空表判断 if(pList->count == 0) { return LIST_EMPTY; } //位置判断 if(pos = pList->count) { return POS_ERROR; } //移动元素 for(int i=pos; icount-1; i++) { pList->Data[i] = pList->Data[i+1]; } //总数减少 pList->count--; return OK; }🍀销毁顺序表
//函数功能：销毁顺序表
//函数参数：要销毁的表
//函数返回值：成功返回OK，失败返回原因
int Destory(List **pList) { //入参判断 if(!pList) { return LIST_NULL; } //销毁存储空间 free((*pList)->Data); //销毁表 free(*pList); //重置 *pList = NULL; return OK; }🍀导入导出
使用 read 导入
1.打开文件
2.read
3.关闭文件
使用 write 导出
1.打开文件
2.wirte
3.关闭文件
关于read，write详见《关于linux下c语言的文件IO》←”点我直达“中对文件的读和写案例
🌿线性关系的链式存储
🍀单链表
- 单链表的每个节点包含两个部分：数据域和指针域。
- 数据域存储节点的值或数据。
- 指针域存储指向下一个节点的指针，即单链表的指针指向下一个节点。
- 单链表只能从头节点开始顺序访问，通过指针域进行节点之间的连接。
- 单链表只能单向遍历，即只能从头节点开始，沿着指针域逐个访问下一个节点。
- 无法逆向检索，有时候不太方便
☘️单链表的定义
typedef struct student { char name[20]; char add[20]; }data_type; //定义单链表节点 typedef struct link_node { data_type Data; //存放数据的数据域 struct link_node *Next;//存放指向下一个节点的地址的指针域 }LNode;☘️单链表的创建
//函数功能：创建表节点
//函数参数：void
//函数返回值：成功返回地址，失败返回NULL
LNode *CreatNode(void) { LNode *pHead = NULL; //申请空间 pHead = (LNode *)malloc(sizeof(LNode)); //判断是否成功 if(!pHead) { perror("malloc error"); return NULL; } //空间清零 memset(pHead, 0, sizeof(LNode)); //返回创建的地址 return pHead; }☘️插入元素
头插法：
顾名思义，头插法是将新的元素插入到头结点的后面。先将头结点与首节点联系断开，将首节点的地址（存放在头结点的指针域）赋给要插入的新节点的指针域，这样子新节点就和后面的所有节点连接了起来，起到了保护后面所有节点的作用
然后将新节点的地址赋值给头结点的指针域，覆盖掉原本存放的首节点的地址，这样操作就完成了对链表的头结点插入元素
尾插法
顾名思义，尾插法就是将新的节点插入到链表的的最后面，也就是尾节点之后。它的做法和头插法一样，只是要如何才能找到尾结点首先，我们定义一个指针变量，并将其初始化为头结点;然后我们可以发现，只有尾结点的指针域为NULL，则可以执行循环，每当我们所定义的指向头节点的指针变量的指针域不为NULL的时候，就让其后移一位，直到循环结束，找到了指针域为NULL的尾结点，然后将新节点插入到之后，并将新节点的指针域置为NULL
中间插入法
中间插入就是将数据元素插入到链表的中间位置
首先，定义一个指针变量，初始化为头结点，需要找到插入节点的前一个节点因为，要插入的位置的前一个节点保存了要插入位置的后一个节点的地址知道了后面节点的地址才能对其进行操作
//函数功能：插入元素
//函数参数1：要插入的表
//函数参数2：要插入的位置
TATL表示尾插 HEAD表示头插 直接输入位置则是中间插入
//函数参数3：要插入的值
//函数返回值：成功返回OK，失败返回原因
int InstertItem(LNode *pHead, int pos, data_type item) { LNode *pNew = NULL; LNode *pTmp = pHead; int i = 0; //入参判断 if(!pHead) { return LINK_NULL; } //创建节点 pNew = CreatNode(); //赋值 pNew->Data = item; //插入位置判断 switch(pos) { case TATL://尾插 //找尾节点 while(pTmp->Next != NULL) { pTmp = pTmp->Next; } //插入 pTmp->Next = pNew; return OK; case HEAD://头插 //保护后续节点 pNew->Next = pHead->Next; //插入 pHead->Next = pNew; return OK; default://中间插入 //找插入位置 while(i Next; i++ } //错误判断 if(!pTmp) { return POS_ERROR; } //保护后续节点 pNew->Next = pHead->Next; //插入 pTmp->Next = pNew; return OK; } }☘️显示元素
//函数功能：显示元素
//函数参数：要显示的元素
//函数返回值：成功返回OK，失败返回原因
int ShowLink(LNode *pHead) { LNode *pTmp = NULL; //入参判断 if(!pHead) { return LINK_NULL; } //空表判断 if(!pHead->Next) { return LINK_EMPTY; } pTmp = pHead->Next; //显示链表 while(pTmp) { printf("%d",pTmp->Data); pTmp = pTmp->Next; } printf("\n"); return OK; }☘️删除元素
//函数功能：删除元素
//函数参数1：被删除节点的表
//函数参数2：删除的位置
//函数参数3：删除的值
//函数返回值：成功返回OK，失败返回原因
int DeleteNode(LNode *pHead, int pos, data_type item) { LNode *pDel_Pre = NULL; LNode *pDel = NULL; int i = 0; //入参判断 if(!pHead) { return LINK_NULL; } //空表判断 if(!pHead->Next) { return LINK_EMPTY; } //将pDel_Pre设置成头节点 pDel_Pre = pHead; //将pDel设置成首节点 pDel = pHead->Next; //位置判断 switch(pos) { case TATL://尾删 //找尾节点 while(pDel->Next != NULL) { pDel_Pre = pDel_Pre->Next; pDel = pDel->Next; } //保存元素 *item = pDel->Data; //删除节点 pDel_Pre->Next = pDel->Next; //释放空间 free(pDel); return OK; case HEAD://头删 //保存元素 *item = pDel->Data; //删除节点 pDel_Pre->Next = pDel->Next; //释放空间 free(pDel); return OK; default://中间删 //寻找删除位置 while(i Next; pDel = pDel->Next; i++; } //错误判断 if(!pDel) { return POS_ERROR; } //保存元素 *item = pDel->Data; //删除节点 pDel_Pre->Next = pDel->Next; //释放空间 free(pDel); return OK; } }☘️销毁单链表
采用头删法删除所有的数据节点，之后再free头节点。
🍀双链表
- 双链表的每个节点包含三个部分：数据域、指向前一个节点的指针和指向下一个节点的指针。
- 数据域存储节点的值或数据。
- 前驱指针指向前一个节点，后继指针指向下一个节点。
- 双链表可以双向遍历，既能从头节点顺序遍历，也可以从尾节点逆序遍历。
- 双链表相较于单链表需要额外存储指向前一个节点的指针，因此会在空间上占用更多的内存。
- 可进可退，存储密度更低一点
☘️双链表的定义
typedef struct student { char name[20]; char add[20]; }data_type; typedef struct doublelinknode { struct doublelinknode *Pre;//前驱指针 data_type Data;//存放数据的数据域 struct doublelinknode *Next;//后继指针 }DbNode;☘️双链表的其他操作
双链表的其他操作与单链表类似不多赘述
🌿顺序表、链表、线性表的区别
线性表是一种逻辑结构，表示的是1对1的线性关系
顺序表和链表是线性表在不同的存储下的不同体现
顺序表：
- 逻辑上相邻的元素，在物理空间上也相邻
- 插入删除不方便，查询方便
- 空间的存储效率最大可达到1
- 对于静态的顺序表来说，表满不能存，表空不能取
- 顺序表对空间的要求比较高
- 容易有空间碎片的产生
链表：
- 逻辑上相邻的元素，在物理空间上不一定相邻
- 插入删除方便，查询不方便
- 空间的存储效率