数据结构:第一章 - 线性表 579次阅读 数据结构 2022-07-18 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、基本概念 ## (一)线性表 线性表是具有**相同特性**数据元素的一个**有限序列**。 * 相同特性:把同类事物归类,方便批量处理 * 有限:表中元素个数为 n,n ∈ [ 0 , +∞ ] * 序列:表中元素排成一列,体现了一对一的逻辑特性(每个元素有且仅有一个前驱和一个后继) ## (二)顺序存储结构和链式存储结构 1、顺序存储结构(顺序表):将数据**依次存储**在连续的整块物理空间中; 2、链式存储结构(链表):数据**分散存储**在物理空间中,通过一根线保存着它们之间的逻辑关系; ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%281.2_1%29.png) ## (三)线性表常用术语 数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。 对于具有“一对一”逻辑关系的数据, * 某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素都统称为“前驱元素”; * 某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素都统称为“后继元素”; ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%281.3_1%29.png) ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、顺序表 ## (一)基本知识 顺序表存储数据时,会**提前申请一整块足够大小的物理空间,然后将数据依次存储起来**,存储时做到数据元素之间不留一丝缝隙。 顺序表存储数据使用的就是**数组**。 ## (二)初始化 使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,顺序表还需要实时记录以下 2 项数据: 1. 顺序表申请的**存储容量**; 2. 顺序表的**长度**,也就是表中存储的**数据元素个数**; ### 1、结点定义 ```c typedef struct { int data[maxsize];//存放元素的数组 int length;//顺序表长度 }Sqlist; /*常用形式:*/ int A[maxsize]; int n; ``` ### 2、建表(初始化) #### (1)表中带元素 ```c int creatList(int A[],int &length) { scanf("%d",&length);//输入表长 if(length > maxsize) return 0;//长度大于表的最大值,无法建表,返回0 for(int i=0;i 通过遍历,找到数据元素要插入的位置,将要插入位置元素以及后续的元素整体向后移动一个位置,将元素放到腾出来的位置上; ```c int insertElem(Sqlist &L;int p;int e)//p:插入位置;e:插入元素;L:表长 { int i; if(p<0||p.length||L.lentgh==maxsize)//位置错误或表长达到表的最大值,返回0,表插入不成功 return 0; for(i=L.length-1;i>=p;--i) L.data[i+1]=L.data[i];//从后往前循环p,并逐个将元素后移一位(包括p位置元素) L.data[p]=e;//将e放在p上 ++(L.length);//表长+1 return 1;//插入成功,返回1 } ``` ## (四)删除元素 删除顺序表 L 中下标为 p 的元素,并将被删除元素赋值给 e。 > 找到目标元素,并将其后续所有元素整体前移 1 个位置即可。 ```c int deleteElem(Sqlist &L,int p,int &e) { int i; if(p<0||p.length-1) return 0;//位置不对返回0,代表删除不成功 e=L.data[a];//将被删除元素赋值给e for(i=p;iL.length)//p值越界错误,返回0 return 0; e=L.data[p];//制定位置元素 return 1; } ``` ### 2、查找表中元素 顺序表中查找目标元素,可以使用多种查找算法实现,详情看第九章。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、链表基本知识 链表,别名链式存储结构或单链表,用于存储逻辑关系为 "一对一" 的数据。 链表不限制数据的物理存储状态 。(即,使用链表存储的数据元素,其物理存储位置是随机的) ## (一)结点 链表中每个数据的存储都由以下两部分组成: 1. 数据元素本身,其所在的区域称为数据域。 2. 指向直接后继元素的指针,所在的区域称为指针域。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%283.1_1%29.png) 链表实际存储的是一个一个的结点,真正的数据元素包含在这些结点中。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%283.1_2%29.png) ## (二)头结点、头指针和首元结点 1. 头指针:一个普通的指针,它的特点是永远指向链表第一个结点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据。 2. 结点:链表中的结点又细分为头结点、首元结点和其他结点 * 头结点:其实就是一个不存任何数据的空结点,通常作为链表的第一个结点。 对于链表来说,头结点不是必须的,它的作用只是为了方便解决某些实际问题。 * 首元结点:由于头结点(也就是空结点)的缘故,链表中称第一个存有数据的结点为首元结点。 首元结点只是对链表中第一个存有数据结点的一个称谓,没有实际意义。 * 其他结点:链表中其他的结点。 > 链表中有头结点时,头指针指向头结点;反之,若链表中没有头结点,则头指针指向首元结点。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%283.2_1%29.png) ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、单链表 ## (一)基本知识 ### 1、带头结点的单链表 头指针 head 指向头结点,头结点的值域不含任何信息,从头结点的后继结点开始存储数据信息。 头指针 head 始终不等于 NULL,head->next 等于 NULL 的时候链表为空。即, ```c head->next==NULL; ``` ### 2、不带头结点的单链表 头指针 head 直接指向开始结点,当 head 等于 NULL 的时候,链表为空。 ```c head==NULL; ``` 两者最明显的区别是, * ① 有一个结点不存储信息,只作为标志。(仅存储一些描述链表属性的信息) * ② 的所有结点都存储信息。 ## (二)结点定义 ```c typedef struct LNode { int data;//data中存放结点数据域 struct LNode *next;//指向后继结点的指针 }LNode;//定义单链表结点类型 ``` ## (三)初始化(带头结点) ### 1、尾插法 ```c void creatLinkListR(LNode *&head) { head=(LNode *)malloc(sizeof(LNode));//动态分配头结点空间 head->next=NULL;//头结点下个结点为空 LNode *P=NULL,*r=head;//p指针接收新结点,r始终指向尾部结点 int n; scanf("%d",&n);//人工定义数据结点个数 for(int i=0;inext=NULL; scanf("%d",&(p->data));//接收元素到数据域 p->next=r->next;//将p的后继结点设置为r的后继结点 r->next=p;//r的后继结点为p r=p;//将r指向尾部 } } ``` ### 2、头插法 ```c void creatLinkListH(LNode *&head)//除注释部分,其余部分与尾插法相同 { head=(LNode*)malloc(sizeof(LNode)); head->next = NULL; LNode *p = NULL; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { p=(LNode*)malloc(sizeof(LNode)); p->next=NULL; scanf("%d", &(p->data)); p->next = head->next;//p所指新结点的后继结点指向head的开始结点 head->next = p;//头结点的后继结点指向p,使其称为新的开始结点 } } ``` ## (四)插入结点 链表插入元素的思想是固定的,只需做以下两步操作,即可将新元素插入到指定的位置: 1. 将新结点的 next 指针指向插入位置后的结点。 2. 将插入位置前结点的 next 指针指向插入结点。 > 链表插入元素的操作必须是先步骤 1,再步骤 2;反之,若先执行步骤 2,会导致插入位置后续的部分链表丢失,无法再实现步骤 1。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%284.4_1%29.png) ### 1、普通情况 ```c /*p指向某结点并在其后插入结点s*/ s->next=p->next; p->next=s; ``` ### 2、在头部进行插入(未含有头结点) ```c s->next=head->next; head->next; //head->data+=1;//若带有头结点需进行本步 ``` ## (五)删除结点 从链表中删除指定数据元素时,实则就是将存有该数据元素的结点从链表中摘除,并对不再利用的存储空间要及时释放。 从链表中删除数据元素需要进行以下 2 步操作: 1. 将结点从链表中摘下来。 2. 手动释放掉结点,回收被结点占用的存储空间。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%284.5_1%29.png) ### 1、普通情况 ```c /*p位置:删除结点q的前一个结点*/ q=p->next;//将删除结点放进q p->next=p->next->next;//p的下一个指针域结点为下下个结点 free(q);//释放q所指结点的内存空间 ``` ### 2、在头部进行删除 ```c head=head->next; free(q); ``` ## (六)查找元素 在链表中查找指定数据元素,最常用的方法是:从表头依次遍历表中结点,用被查找元素与各结点数据域中存储的数据元素进行比对,直至比对成功或遍历至链表最末端的 NULL(比对失败的标志)。 ```c int findAndDelete(LNode *C,int x) { LNode *p,*q; p=C; /*查找部分*/ while(p->next!=NULL) { if(p->next->data==x) break; p=p->next; } if(p->next==NULL) return 0; else{ //各类操作(插入、删除、访问等) } } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、静态链表 静态链表,也是线性存储结构的一种,它兼顾了顺序表和链表的优点于一身,可以看做是顺序表和链表的升级版。 使用静态链表存储数据,数据全部存储在**数组**中(和顺序表一样),但**存储位置是随机的**,数据之间"一对一"的逻辑关系通过一个**整形变量**(称为"**游标**",和指针功能类似)维持(和链表类似)。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%285_1%29.png) ## (一)结点定义 * 数据域:用于存储数据元素的值。 * 游标:其实就是数组下标,表示直接后继元素所在数组中的位置。 ```c typedef struct { int data;//数据域 int next;//游标 }SLNode; ``` ## (二)各类操作 ```c int p=ado;//定义一个指针 SLink[p].data;//取p指针指向的结点值,类比:p->data; SLink[p].next;//取p后继结点指针,类比:p->next; /*在p后插入结点q*/ SLink[q].next=SLink[p].next;//类比:q->next=p->next; SLink[p].next=q;//类比:p->next=q; ``` ## (三)静态链表和动态链表区别 ### 1、静态链表 使用静态链表存储数据,需要预先申请足够大的一整块内存空间,也就是说,静态链表存储数据元素的个数从其创建的那一刻就已经确定,后期无法更改。 > 比如,如果创建静态链表时只申请存储 10 个数据元素的空间,那么在使用静态链表时,数据的存储个数就不能超过 10 个,否则程序就会发生错误。 不仅如此,静态链表是在固定大小的存储空间内随机存储各个数据元素,这就造成了静态链表中需要使用另一条链表(通常称为"备用链表")来记录空间存储空间的位置,以便后期分配给新添加元素使用。 这意味着,如果你选择使用静态链表存储数据,你需要通过操控两条链表,一条是存储数据,另一条是记录空闲空间的位置。 ### 2、动态链表 使用动态链表存储数据,不需要预先申请内存空间,而是在需要的时候才向内存申请。也就是说,动态链表存储数据元素的个数是不限的,想存多少就存多少。 同时,使用动态链表的整个过程,你也只需操控一条存储数据的链表。当表中添加或删除数据元素时,你只需要通过 malloc 或 free 函数来申请或释放空间即可,实现起来比较简单。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、双链表 ## (一)基本知识 双向链表,简称双链表。从名字上理解双向链表,即链表是 "双向" 的。 > 所谓双向,指的是各结点之间的逻辑关系是双向的,但通常头指针只设置一个,除非实际情况需要,可以为最后一个结点再设置一个“头指针”。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.1_1%29.png) ## (二)结点定义 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.2_1%29.png) 1. 指针域:用于指向当前结点的直接前驱结点。 2. 数据域:用于存储数据元素。 3. 指针域:用于指向当前结点的直接后继结点。 ```c typedef struct DLNode { int data;//data中存放结点数据域 struct DLNode *prior;//指向前驱结点的指针 struct DLNode *next;//指向后驱结点的指针 }DLNode; ``` ## (三)初始化 采用尾插法建立双链表。 ```c void createDlistR(DLNode *&L,int a[],int n) { DLNode *s,*r; int i; L=(DLNode*)malloce(sizeof(DLNode)); L->prior=NULL; L->next=NULL; r=L; for(i=0;idata=a[i]; r->next=s;//原尾结点下个结点指向s s->prior=r;//新结点指向前驱 r=s;//使尾指针指向s } r->next=NULL; } ``` ## (四)插入结点 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.4_1%29.png) ### 1、插入至表头 将新数据元素添加到表头,只需要将该元素与表头元素建立双层逻辑关系即可。 假设新元素结点为 s,表头结点为 head,头指针为 L,则: ```c s->next=L->next; s->prior=L; L->next=s; head->prior=s; ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.4.1_1%29.png) > **将新元素 7 添加至双链表的表头。** ### 2、插入至表的中间位置 在 p 所指结点之后插入一个结点 s。 ```c s->next=p->next; s->prior=p; p->next=s; s->next->prior=s; ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.4.2_1%29.png) ### 3、插入至表尾 与添加至表的中间位置大致相同: 1. 找到双链表中最后一个节点。 2. 让新节点与最后一个节点进行双层逻辑关系。 > 此句话可省略:s->next->prior=s; > ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.4.3_1%29.png) ## (五)删除结点 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.5_1%29.png) ```c q=p->next; p->next=q->next; q->next->prior=p; free(q); ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%286.5_2%29.png) ## (六)查找 从表头依次遍历表中元素。 ```c DLNode* findNode(DLNode *C,int x) { DLNode *p=C->next; while(p!=NULL) { if(p->data==x) break; p=p->next; } return p;//若找到,则p中是结点地址;反之,则p中是NULL(同时因 //此结束) } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 七、循环链表 把链表的两头连接,使其成为了一个环状链表,通常称为循环链表。 > * 需要注意的是,虽然循环链表成环状,但本质上还是链表,因此在循环链表中,依然能够找到头指针和首元结点等。 > * 循环链表和普通链表相比,唯一的不同就是循环链表首尾相连,其他都完全一样。 ## (一)循环单链表 表中最后一个结点的指针不是 NULL,而改为指向头结点,是整个链表形成环。 表尾结点 *r 的 next 域指向 L,故表中没有指针域为 NULL 的结点。循环单链表判空条件是头结点的指针是否等于头指针。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%287.1_1%29.png) 循环单链表可以实现从任一个结点出发访问链表中的任何结点,单链表只能从任一结点出发访问这个结点本身及其以后的所有结点。 带头结点的循环单链表,当 head 等于 head->next 时,链表为空。即, ```c head->next==head; ``` 带头结点的循环单链表,当 head 等于 NULL 时,链表为空。即, ```c head==NULL; ``` ## (二)循环双链表 与双链表不同的是,循环双链表的头结点 prior 指针需要指向表尾结点。 * 在循环双链表 L 中,某结点 *p 为尾结点时,p->next==L。 * 当循环双链表为空表时,其头结点的 prior 和 next 都等于 L。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%287.2_1%29.png) 以下四句中的任意一句为真,都可判断循环双链表为空。 ```c head->next==head; head->prior==head; head->next==head&&head->prior==head; head->next==head||head->prior==head; ``` ## (三)如何判断链表中有环? 需注意,有环链表并不一定就是循环链表。 * 循环链表指的是“首尾相连”的单链表。 * 有环链表则指的是单链表中存在一个循环子链表。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit1/DS.Unit1.%287.3_1%29.png) > 此图是一个有环链表,但并不是循环链表。 ### 1、最直接的实现算法思想 从给定链表的第一个结点开始遍历,每遍历至一个结点,都将其和所有的前驱结点进行比对, * 如果为同一个结点,则表明当前链表中有环。 * 反之,如果遍历至链表最后一个结点,仍未找到相同的结点,则证明该链表中无环。 > 如果一个单链表为有环链表,基于单链表中各结点有且仅有 1 个指针域的特性,则势必该链表是没有尾结点的。 > > 即,有环链表的遍历过程是无法自行结束的,需要使用 break 语句手动结束遍历。 ### 2、时间复杂度为 O(n) 的算法思想 在一个链表中,如果 2 个指针(假设为 H1 和 H2)都从表头开始遍历链表,其中 H1 每次移动 2 个结点的长度(H1 = H1->next->next),而 H2 每次移动 1 个结点的长度(H2 =H2->next), * 如果该链表为有环链表,则 H1、H2 最终必定会相等。 * 反之,如果该链表中无环,则 H1、H2 永远不会相遇。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 八、划分顺序表 以某个元素为标准,把顺序表中的元素分为两个部分(左边:小于数轴;右边:大于数轴)。 ## (一)以第一个元素为数轴 ```c void partition(int arr[], int n) { int temp; int i = 0, j = n-1; temp = arr[i]; while(i < j) { while(i < j && arr[j] >= temp) --j; if(i < j) { arr[i] = arr[j]; ++i; } while(i < j && arr[i] < temp) ++i; if(i < j) { arr[j] = arr[i]; --j; } } arr[i] = temp; } ``` ## (二)以任意值 x 为数轴 ```c void partition(int arr[], int n, int comp)//增加参数:int comp; { int temp; int i = 0, j = n-1; temp = arr[i]; while(i < j){ while(i < j && arr[j] >= comp) //更改判断条件为comp --j; if(i < j) { arr[i] = arr[j]; ++i; } while(i < j && arr[i] < comp) //更改判断条件为comp ++i; if(i < j) { arr[j] = arr[i]; --j; } } arr[i] = temp; } ``` ## (三)以表中任意位置的元素为数轴 ```c void partition(int arr[], int n, int k)//增加参数 { int temp; int i = 0, j = n-1; temp = arr[0];//增加Code1 arr[0] = arr[k];//增加Code2 arr[k] = temp;//增加Code3 temp = arr[i]; while(i < j) { while(i < j && arr[j] >= temp) --j; if(i < j) { arr[i] = arr[j]; ++i; } while(i < j && arr[i] < temp) ++i; if(i < j) { arr[j] = arr[i]; --j; } } arr[i] = temp; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 九、归并 ## (一)顺序表归并 ```c void mergearray(int a[], int m, int b[], int n, int c[]) { int i = 0, j = 0; int k = 0; while (i < m && j < n) { if (a[i] < b[j]) c[k++] = a[i++];//c[k] = a[i];k++;i++; else c[k++] = b[j++]; } while (i < m) c[k++] = a[i++]; while (j < n) c[k++] = b[j++]; } ``` ## (二)链表归并 ### 1、尾插法(升序) ```c void merge(LNode *A, LNode *B, LNode *&C) { LNode *p = A->next; LNode *q = B->next; LNode *r; C = A; C->next = NULL; free(B); r = C; while(p != NULL && q!= NULL) { if(p->data <= q->data) { r->next = p; p = p->next; r = r->next; } else { r->next = q; q = q->next; r = r->next; } } if(p!=NULL) r->next = p; if(q!=NULL) r->next = q; } ``` ### 2、头插法(降序) ```c void mergeR(LNode *A, LNode *B, LNode *&C) { LNode *p = A->next; LNode *q = B->next; C = A; C->next = NULL; free(B); while(p != NULL && q!= NULL) { if(p->data <= q->data) { s = p; p = p->next; s->next = C->next; C->next = s; } else { s = q; q = q->next; s->next = C->next; C->next = s; } } while(p!=NULL) { s = p; p = p->next; s->next = C->next; C->next = s; } while(q!=NULL) { s = q; q = q->next; s->next = C->next; C->next = s; } } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 十、逆置 ## (一)顺序表 ```c for(int i = left, j = right; i < j; ++i, --j) { temp = a[i]; a[i] = a[j]; a[j] = temp; } ``` ## (二)链表(逆置 p->nxet 到 q 结点) ```c while(p->next != q) { t = p->next; p->next = t->next; t->next = q->next; q->next = t; } ``` ## (三)将一长度为 n 的数组的前端 k(k ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 十一、取最值 ## (一)顺序表 ### 1、最大值 ```c int max = a[0]; int maxIdx = 0; for (int i = 0; i < n; ++i) { if (max < a[i]) { max = a[i]; maxIdx = i; } } ``` ### 2、最小值 ```c int max = a[0]; int maxIdx = 0; for (int i = 0; i < n; ++i) { if (max < a[i]) { max = a[i]; maxIdx = i; } } ``` ## (二)链表 ### 1、最大值 ```c LNode *p, *q; int max = head->next->data; q = p = head->next; while (p != NULL) { if (max < p->data) { max = p->data; q = p; } p = p->next; } ``` ### 2、最小值 ```c LNode *p, *q; int min = head->next->data; q = p = head->next; while (p != NULL) { if (min > p->data) { min = p->data; q = p; } p = p->next; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 十二、移动次数计算(顺序表) ## (一)插入元素 1、在任一位置插入元素的概率:p=1/(n+1)。 2、在 i 位置(0<=i<=n)前插入元素,需移动:n-i 个元素。 3、插入元素平均要移动的元素个数:n/2 。 4、总移动次数:[n(n+1)]/2 。 ## (二)删除元素 1、任一位置删除元素的概率:p=1/n。 2、在 i 位置(0<=i<=n)前删除元素,需移动:n-1-i 个元素。 3、删除元素要移动的元素的个数:(n-1)/2。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 十三、顺序表和链表的优缺点(区别、特点) ## (一)基于时间的比较 ### 1、存取(读写)方式 * 顺序表:可以顺序存取、随机存取。 * 链表:只能从表头顺序存取元素。 ### 2、查找、插入、删除操作 * 顺序表: * 查找:对于按值查找,无序时为 O( n );有序时,可采用折半查找,为 O( log ~2~ n )。对于按序号查找,顺序表支持随机访问,为 O( 1 )。 * 插入、删除:平均需要移动半个表长的元素。 * 链表: * 查找:对于按序号查找,需要遍历整个表,为 O( n )。 * 插入、删除:只需修改相关结点的指针域。 ## (二)基于空间的比较 ### 1、存储分配的方式 * 顺序表:一次性分配 * 静态存储分配:需要预先分配最足够大的存储空间,一旦存储空间装满就不能扩充,若再加入新元素,则会出现内存溢出。 * 分配过大,会导致顺序表后部大量闲置。 * 分配过小,则会溢出。 * 动态存储分配:虽然存储空间可以扩充,但需要移动大量元素,导致操作效率低,若内存中没有更大块的连续存储空间,则会导致分配失败。 * 链表:多次分配 * 只需在需要时申请分配,只要内存有空间就可以分配,操作灵活、高效。 ### 2、存储密度 * 存储密度 = 结点值域所占的存储量 / 结点结构所占的存储总量。 * 顺序表的存储密度 = 1。 * 链表的存储密度 < 1。 ### 3、逻辑结构与物理结构 * 顺序表:逻辑上相邻的元素,对应物理存储位置也相邻。 * 链表:逻辑上相邻的元素,物理存储位置不一定相邻,是通过指针链接表示的。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 十四、为什么在单链表中设置尾指针比设置头指针好? 尾指针是指向终端结点的指针,用它来表示单循环链表可使查找链表的开始结点和终端结点更方便。 设一个带头结点的单循环链表,其尾指针是 rear,则开始结点和终端结点分别为指针 rear 所指结点的后继节点的后继节点和指针 rear 所指的结点,即: * rear->next-next * rear 查找时间均为 O( 1 )。 若用头指针来表示该链表,则查找开始结点为 O( 1 ),终端结点为 O( n )。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 2 最后一次更新于2022-10-23 数据结构
0 条评论