您的位置：首页 > 科技 > 能源 > 【线性表】内容总结

【线性表】内容总结

2024/12/22 22:54:38 来源：https://blog.csdn.net/2401_82676816/article/details/141194176  浏览:  次   关键词：【线性表】内容总结

1.单链表，循环链表，双向链表的循环效率

在这里插入图片描述

2.顺序表和链表的比较

1.什么是存储密度

1.定义：

存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量 之比，即:
在这里插入图片描述

2.实例

比如在32位系统上，一个12字节的结点中 存储8个字节的数据 和 4个字节的指针
其存储密度就不高 在这里插入图片描述
在这里插入图片描述

2.链式存储结构的优点

  • 结点空间可以动态申请和释放;
  • 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。

3.链式存储结构的缺点

  • 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
  • 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链査找到该结点，这增加了算法的复杂度。

4.顺序表和链表的差异性

在这里插入图片描述

3.线性表的应用（链式存储实现）

1.线性表的合并

1.问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB

2.核心：
  • 去掉重复元素，取两个集合的并集

比如：
在这里插入图片描述

3.算法核心思路：

依次取出Lb 中的每个元素，执行以下操作:在La中查找该元素；如果找不到，则将其插入La的最后

4.链式存储需要用到的基本操作：
求表长
int LinkLength(LinkList L);尾插建立新表
bool CreateLinkList(LinkList* L, int n);按位查找元素e并获得对应值
bool GetElem(LinkList L, int i, Elem* e);按值查找并返回位序（用到非0为真，0为假）
int LocateElem(LinkList L, Elem e);按位插入（插入到i-1和i之间）
bool InsertElem(LinkList L, int i, Elem e);
5.链式存储的算法步骤：

（0）判断要合并的两个线性表头结点是否存在
（1）分别求La，Lb的表长
（2）定义变量e，用于存储要插入的元素值
（3）合并线性表La,Lb;将Lb中与La不重复的元素插入到La中
<1>依次取出Lb 中的每个元素
<2>在La中查找该元素,如果找不到，则将其插入La的表尾

bool unionLinkList(LinkList La, LinkList Lb)

int LinkLength(LinkList L);
bool CreateLinkList(LinkList* L, int n);
bool GetElem(LinkList L, int i, Elem* e);
int LocateElem(LinkList L, Elem e);
bool InsertElem(LinkList L, int i, Elem e);
//两个线性表的合并（带头结点的单链表的实现）
bool unionLinkList(LinkList La, LinkList Lb)
{//[0]判断要合并的两个线性表头结点是否存在if (!La && !Lb) {return false;}//[1]分别求La，Lb的表长int La_Len = LinkLength(La);int Lb_Len = LinkLength(Lb);//[2]定义变量e，用于存储要插入的元素值Elem e;//[3]合并线性表La,Lb;将Lb中与La不重复的元素插入到La中for (int i = 1; i <=Lb_Len; i++)//注意:循环条件i<=Lb_Len，而不是i<Lb_Len；若为i<Lb_Len，合并时Lb会忽略判断最后一个元素。{//<1>依次取出Lb 中的每个元素:GetElem(Lb, i, &e);//<2>在La中查找该元素,如果找不到，则将其插入La的表尾if (!LocateElem((La), e)){InsertElem(La,++La_Len,e);//注意：插入位置为La_Len+1,使用 ++La_Len 而不是 La_Len++ //是为了确保在插入元素时，La_Len 的值已经自增，插入位置已更新。}}return true;
}
6.小结：
  • 传入线性表若为不带头结点的两个链表，需要传入待合并线性表的头指针二级指针
bool unionLinkList(LinkList* La, LinkList Lb)
  • 注意循环条件i<=Lb_Len，而不是i<Lb_Len；若为i<Lb_Len，合并时Lb会忽略判断最后一个元素。
  • 注意插入位置为La_Len+1,使用 ++La_Len 而不是 La_Len++；先更新插入位置，再插入
7.带头结点单链表合并的实际操作：
//用单链表来实现：
#include<stdio.h>
#include<stdlib.h>typedef int Elem;#define bool int 
#define true 1
#define false 0typedef struct Node
{Elem data;struct Node* next;
}Node,*LinkList;//求表长
int LinkLength(LinkList L)
{if (!L){return 0;}Node* p = L->next;int count = 0;while (p){count++;p = p->next;}return count;
}//尾插建立整表
bool CreateLinkList(LinkList *L,int n)
{//头结点*L = (LinkList)malloc(sizeof(Node));if (!(*L)){return false;}(*L)->next = NULL;//初始化尾指针LinkList Tail = *L;Node* p;//尾插建立for (int i = 0; i < n; i++){p = (Node*)malloc(sizeof(Node));if (!p){return false;}scanf_s("%d", &p->data);Tail->next = p;p->next = NULL;Tail = p;}return true;
}//按位查找
bool GetElem(LinkList L, int i, Elem* e)
{//头结点，首元结点不存在if (!L||!(L->next)){return false;}Node* p = L->next;int j = 1;while (p && j < i){p = p->next;j++;}if (!p){return false;}//返回对应元素值*e = p->data;return true;
}//按值查找(返回位序，非0为真，0为假)
int LocateElem(LinkList L,Elem e)
{//头结点，首元结点不存在if (!L || !(L->next)){return 0;}Node* p = L->next;int count = 1;while (p&&p->data!=e){p = p->next;count++;}if (!p){return 0;}return count;
}//按位插入
bool InsertElem(LinkList L, int i, Elem e)
{//保证头结点存在if (!L){return false;}Node* p = L;int j = 0;//找第i-1个元素while (p&&j<i-1){p = p->next;j++;}if (!p){return false;}//建立并初始化新结点Node* s = (Node*)malloc(sizeof(Node));if(!s){return false;}s->data = e;//插入到对应位置s->next = p->next;p->next = s;return true;
}//整表输出
bool printLinkList(LinkList L)
{if (!L || !L->next){return false;}Node* p = L->next;while (p){printf("%d-->", p->data);p = p->next;}printf("end\n");return true;
}int LinkLength(LinkList L);
bool CreateLinkList(LinkList* L, int n);
bool GetElem(LinkList L, int i, Elem* e);
int LocateElem(LinkList L, Elem e);
bool InsertElem(LinkList L, int i, Elem e);//两个线性表的合并（带头结点）
bool unionLinkList(LinkList La, LinkList Lb)
{//[0]判断要合并的两个线性表头结点是否存在if (!La && !Lb) {return false;}//[1]分别求La，Lb的表长int La_Len = LinkLength(La);int Lb_Len = LinkLength(Lb);//[2]定义变量e，用于存储要插入的元素值Elem e;//[3]合并线性表La,Lb;将Lb中与La不重复的元素插入到La中for (int i = 1; i <=Lb_Len; i++)//注意1:循环条件i<=Lb_Len，而不是i<Lb_Len；若为i<Lb_Len，合并时Lb会忽略判断最后一个元素。{//<1>依次取出Lb 中的每个元素:GetElem(Lb, i, &e);//<2>在La中查找该元素,如果找不到，则将其插入La的表尾if (!LocateElem((La), e)){InsertElem(La,++La_Len,e);//注意4：插入位置为La_Len+1,使用 ++La_Len 而不是 La_Len++ //是为了确保在插入元素时，La_Len 的值已经自增，插入位置已更新。}}return true;
}
int main()
{LinkList La;LinkList Lb;CreateLinkList(&La, 4);printf("La:\n");printLinkList(La);printf("\n");CreateLinkList(&Lb, 3);printf("Lb:\n");printLinkList(Lb);unionLinkList(La, Lb);printf("\n");printf("合并后：\n");printLinkList(La);return 0;
}

在这里插入图片描述

2.有序表的合并

1.问题描述：

已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。

2.核心：
  • 取两个集合中的所有元素
  • 非递减有序排列：即每个元素都大于或等于它前面的元素；
    比如：
    在这里插入图片描述
3.算法核心思路：创建一个空表Lc；依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止；继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后
4. 链式存储的算法步骤：

（1） 定义三个临时指针：
//pa用来遍历La
//pb用来遍历Lb
//pc用来遍历新链表Lc的每个结点
（2）初始化pa,pb分别指向La,Lb的首元结点，pc指向新链表的头结点
//新链表的头结点可以是La的头结点，也可以是Lb的头结点
（3）依次从 La 或 Lb 中摘取元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
（4）插入剩余段（注意释放没用的头结点）
pc->next = pa ? pa : pb;
等价于
if(pa!=NULL)
{
pc->next=pa;
}
else
{
pc->next=pb;
}

bool MergeList(LinkList* La, LinkList* Lb, LinkList* Lc)

bool MergeList(LinkList* La, LinkList* Lb, LinkList* Lc)
{//[1]定义三个临时指针：//pa用来遍历La//pb用来遍历Lb//pc用来遍历新链表Lc的每个结点	Node* pa, * pb, * pc;//[2]初始化pa,pb分别指向La,Lb的首元结点，pc指向新链表的头结点pa = (*La)->next;pb = (*Lb)->next;(*Lc) = (*La);//用La的头结点作为新链表Lc的头结点(当然也可以使用Lb的头结点)pc = (*Lc);//实际上pc指向的是La的头结点//[3]依次从 La 或 Lb 中摘取元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止while (pa && pb){if (pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb;pc = pb;pb = pb->next;}}//[4]插入剩余段pc->next = pa ? pa : pb;//若pa不为空，链接pa;否则链接pb//释放Lb的头结点free(*Lb);return true;
}
5.思路图解
    • 1
      在这里插入图片描述
    • 2
      在这里插入图片描述
    • 3
      在这里插入图片描述
    • 4
      在这里插入图片描述
    • 5
      在这里插入图片描述
    • 6
      在这里插入图片描述
6.小结：
  • 新表的头结点可以选择任意一个表的头结点，示实际情况灵活运用
  • 当传入不带头结点的两个表时，可以自己建立一个虚拟头结点，方便进行操作
7.带头结点有序单链表合并的实际操作：
#include<stdio.h>
#include<stdlib.h>typedef int Elem;#define bool int 
#define true 1
#define false 0typedef struct Node
{Elem data;struct Node* next;
}Node, * LinkList;//尾插建立整表
bool CreateLinkList(LinkList* L, int n)
{//头结点*L = (LinkList)malloc(sizeof(Node));if (!(*L)){return false;}(*L)->next = NULL;//初始化尾指针LinkList Tail = *L;Node* p;//尾插建立for (int i = 0; i < n; i++){p = (Node*)malloc(sizeof(Node));if (!p){return false;}scanf_s("%d", &p->data);Tail->next = p;p->next = NULL;Tail = p;}return true;
}//整表输出
bool printLinkList(LinkList L)
{if (!L || !L->next){return false;}Node* p = L->next;while (p){printf("%d-->", p->data);p = p->next;}printf("end\n");return true;
}bool MergeList(LinkList* La, LinkList* Lb, LinkList* Lc)
{//[1]定义三个临时指针：//pa用来遍历La//pb用来遍历Lb//pc用来遍历新链表Lc的每个结点	Node* pa, * pb, * pc;//[2]初始化pa,pb分别指向La,Lb的首元结点，pc指向新链表的头结点pa = (*La)->next;pb = (*Lb)->next;(*Lc) = (*La);//用La的头结点作为新链表Lc的头结点(当然也可以使用Lb的头结点)pc = (*Lc);//实际上pc指向的是La的头结点//[3]依次从 La 或 Lb 中摘取元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止while (pa && pb){if (pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb;pc = pb;pb = pb->next;}}//[4]插入剩余段pc->next = pa ? pa : pb;//释放Lb的头结点free(*Lb);return true;
}int main()
{LinkList La, Lb, Lc;//这里的Lc并不需要未初始化,用来新链表的头指针，它可以指向La和Lb中任意一个表中的头结点CreateLinkList(&La, 3);printf("La:\n");printLinkList(La);printf("\n");CreateLinkList(&Lb, 6);printf("Lb:\n");printLinkList(Lb);MergeList(&La, &Lb, &Lc);printf("Lc:\n");printLinkList(Lc);return 0;
}

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

《网络运维服务合同》 【JAVA开源】基于Vue和SpringBoot甘肃非物质文化网站 生成随机数 【系统开发】携程从零构建多端一致的设计研发体系实践 一岁将终，易碎江中 Python 潮流周刊#82：美国 CIA 如何使用 Python？（摘要）

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989