数据结构题集-第二章-线性表-连接链表并安全释放

🕗 发布于 2024-11-06 20:31 数据结构 算法

说明

本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

2.15 已知指针ha和hb分别指向两个单链表的头结点

并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，
即令其中一个表的首元结点连在另一个表的最后一个结点之后，
假设指针hc指向连接后链表的头结点，并要求算法以尽可能短的时间完成连接运算。
请分析你算法的时间复杂度。

解：
根据给定的两个链表的长度选择较合适的链表并找到其尾结点；注意为了释放后面链表的头结点，需要做特殊处理：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define MAX_TEST_LENGTH 20
#define MAX_TEST_ELEM 1000
typedef int ElemType;

typedef struct SLNode{ // 结点类型
ElemType data;
struct LNode *next;
} LNode, *Link;

typedef struct{ // 链表类型
Link head,tail; // 分别指向线性链表中的头结点和最后一个结点
int len; // 指示线性链表中数据元素的个数
} LinkList;

Status MakeNode(Link *pp,ElemType e){
// 分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
*pp=(Link)malloc(sizeof(LNode));
if(!*pp) return ERROR;
(*pp)->data=e;
(*pp)->next=NULL;
return OK;
}

void FreeNode(Link p){
// 释放p所指结点
if(NULL!=p){
//printf("\nvalue of adddress:%lld\n",(long long)p);
free(p);
}
}

Status InitList(LinkList *pL){
// 构造一个空的线性链表L
Link p;
if(ERROR==MakeNode(&p,0)) return ERROR;
(*pL).head=p;
(*pL).tail=NULL;
(*pL).len=0;
return OK;
}

Status ClearList(LinkList *pL){
// 将线性表L重置为空表，并释放原链表的结点空间
Link p;
if(NULL==pL) return ERROR;
if(NULL!=(*pL).head) p=((*pL).head)->next;
while(p){
((*pL).head)->next=p->next;
printf("free [%lld]=%d\n",(long long)p,p->data);
FreeNode(p);
p=((*pL).head)->next;
}
(*pL).tail=NULL;
(*pL).len=0;
return OK;
}

Status DestroyList(LinkList *pL){
// 销毁线性链表L
if(ERROR==ClearList(pL)) return ERROR;
if(NULL!=(*pL).head) FreeNode((*pL).head);
(*pL).head=NULL;
return OK;
}

Status InsFirst(LinkList *pL,Link s){
// 已知h指向线性链表的头结点，将s所指结点插入到第一个结点之前
// 线性链表的尾指针没有变化，线性链表的元素个数加1
Link p;
if(NULL==pL||NULL==s) return ERROR;
p=(*pL).head;
s->next=p->next;
if(NULL==p->next) (*pL).tail=s; // 插入前链表为空时，记录表尾
p->next=s;
(*pL).len+=1;
return OK;
}

Status rand_init_two_list(LinkList *pL,LinkList*qL){
// 在测试范围内，随机初始化两个链表
int c;
Link p;
time_t t;

if(ERROR==InitList(pL)) return ERROR;
if(ERROR==InitList(qL)) return ERROR;

srand((unsigned)time(&t)); // 初始化随机数发生器

c=rand()%MAX_TEST_LENGTH;
while(c--){
p=NULL;
if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
if(ERROR==InsFirst(pL,p)) return ERROR;
}

c=rand()%MAX_TEST_LENGTH;
// c=30000000; 开辟较大空间看销毁时是否能释放
while(c--){
p=NULL;
if(ERROR==MakeNode(&p,rand()%MAX_TEST_ELEM)) return ERROR;
if(ERROR==InsFirst(qL,p)) return ERROR;
}
return OK;
}

void print_list(LinkList L){
// 显示链表的内容
int c=0;
Link p=(L.head)->next;
while(p){
printf("->[%d].%d",++c,p->data);
p=p->next;
}
printf("\n%d elements\n",L.len);
}

LinkList* ListConcat(LinkList *pha,LinkList *phb){
// 最快连接两个链表，但是需要改变原有两个链表
// 由于事先维护了尾指针，这里也就不需要比较表长，直接相连
// 注意考虑空表的情况
if(NULL==pha->tail) pha->head->next=phb->head->next;
else pha->tail->next=phb->head->next;
// 如果数据没有复制出去，不做特殊处理，销毁或改原来的链表会损坏整个内容
pha->tail=phb->tail;
pha->len+=phb->len;
// 将后面链表做如下处理，在需要销毁时，一个头结点malloc都不能被忽略
phb->head->next=phb->tail=NULL;
phb->len=0;
return pha;
}//ListConcat

int main(){
LinkList La,Lb,Lc;
LinkList *phc;

if(OK==rand_init_two_list(&La,&Lb)){
printf("La:\n");
print_list(La);
printf("Lb:\n");
print_list(Lb);
}
phc=ListConcat(&La,&Lb);
printf("Concat La and Lb:\n");
print_list(*phc);
if(OK==DestroyList(phc)) printf("\nFree a part of them success\n");
if(OK==DestroyList(&Lb)) printf("Free them all success\n");

//if(OK==DestroyList(&La)) printf("\nFree La success\n");
//if(OK==DestroyList(&Lb)) printf("Free Lb success\n");
//getchar();
return 0;
}

以上算法由于前期维护了尾指针，所以连接链表的时间复杂度为O(1)
也可以新建一个链表，不改变已有链表，而是复制一份，这本来也不用考虑比较链表大小，
但是为了遵照原书的意思，可以比较之后，只复制较短的链表到新链表，
接着直接连较长链表，并且暂时保持原有链表的结构，新链表也可以访问较长链表，
为了保持元素原来的次序，还需要实现一个从表尾插入结点的算法，
至于InsAfter更普适一些，用到这里有些过犹不及，留到以后再实现，
还有原书中提到的Append，需要计算链接到尾部的未知链表长，不如直接让已知长度的链表直接链接；
链接完成之后，还要注意修改较长链表结构，让它成为空表，以方便完事之后可以销毁：

Status InsLast(LinkList *pL,Link s){
// 已知线性链表的尾结点，将s所指结点插入到最后结点之后
// 尾指针发生变化，若非空，线性链表的头结点指针域没有变化，线性链表的元素个数加1
// 注意这里提供s的时候，需要先从较短链表中复制一份再传进来
if(NULL==pL||NULL==s) return ERROR;
if(NULL==pL->head->next){
pL->head->next=s;
}else{
pL->tail->next=s;
}
pL->tail=s;
pL->len+=1;
return OK;
}//InsLast

Status HalfListConcatWithMakeLongerListNull(LinkList *pha,LinkList *phb,LinkList *phc){
// 复制较短链表，并链接较长链表
// 为了避免释放时产生混乱，需要修改较长链表结构为空表，
// 且不能调用释放其所有内容的已知释放函数，以提供给phc来释放。
// 由于调用前不确定哪个链表较短，所以它们的地址都应该传入以改变其值
Link p,q;
LinkList *hp,*hq;
if(NULL==pha||NULL==phb||NULL==phc) return ERROR;
if(NULL==pha->head||NULL==phb->head||NULL==phc->head) return ERROR;
if((pha->len)<(phb->len)){
hp=pha;
hq=phb;
}else{
hp=phb;
hq=pha;
}
p=hp->head->next;
while(p){
MakeNode(&q,p->data);
InsLast(phc,q);
p=p->next;
}
if(NULL==phc->tail) phc->head->next=hq->head->next;
else phc->tail->next=hq->head->next;
phc->tail=hq->tail;
phc->len=hp->len+hq->len;
// 将较长链表做如下处理
hq->head->next=hq->tail=NULL;
hq->len=0;
return OK;
}// HalfListConcatWithMakeLongerListNull

int main(){
LinkList La,Lb,Lc;
LinkList *phc;

if(OK==rand_init_two_list(&La,&Lb)){
printf("La:\n");
print_list(La);
printf("Lb:\n");
print_list(Lb);
}
/*
phc=ListConcat(&La,&Lb);
printf("Concat La and Lb:\n");
print_list(*phc);
if(OK==DestroyList(phc)) printf("\nFree a part of them success\n");
if(OK==DestroyList(&Lb)) printf("Free them all success\n");
*/

if(OK==InitList(&Lc)){
if(OK==HalfListConcatWithMakeLongerListNull(&La,&Lb,&Lc)){
printf("Lc:\n");
print_list(Lc);
}
if(OK==DestroyList(&Lc)) printf("\nFree Lc and Longer L success\n");
}
if(OK==DestroyList(&La)) printf("\nFree La success\n");
if(OK==DestroyList(&Lb)) printf("Free Lb success\n");

//getchar();
return 0;
}

这个算法时间复杂度为O(m+n)。
这里还要注意，在上一个算法代码里，MakeNode获取一个新分配的空间给List类型的p时，
就算形参是指针，也改变不了作为的实参的指针变量，
所以需要传入指针变量的地址作为实参，也就是指针的指针，才能把内存分配出去。
除此之外，在释放空间时，就不需要传指针的地址了，
在归还空间时，只需要将那些已开辟地址的值传入销毁函数，就可以正常释放。
经过测试，大规模空间的释放，是可以察觉的，但是我们仍然不能确保所有空间都在管理的范围内。
也就是说，仍不能保证程序中没有一个野指针，这也许是C语言相对于其他高级语言的尴尬，也是对算法设计者的考验。

原文地址：https://blog.csdn.net/georangel/article/details/143455968

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【华为云-云驻共创】UCS跨云多活容灾：让业务高可用不再是难题
下一篇：【VQAScore 文本生成质量评估测试代码】

Linux 使用中的问题
Linux 使用中的问题。
阅读更多2024-11-08
标识符的规范命名及建议
标识符(identtifier)：在编程中，用来表示类，方法，变量等名称的自定义字符，都是标识符。
阅读更多2024-11-08
python-23-一篇文章帮你理解Python推导式
在 Python 中，推导式（Comprehensions）是一个简洁的语法，用于通过某种可迭代对象快速生成新的对象（如列表、字典、集合等！来开始我们今天的日拱一卒！
阅读更多2024-11-08
leetcode 633. 平方数之和中等
你要判断是否存在两个整数。
阅读更多2024-11-08
C++游戏开发前景讨论
为什么「多数」游戏服务端是用 C++ 来写呢，我觉得这个「多数」很可能是错的，没有任何数据支撑C++写的游戏服务器占大多数。但是我自己进鹅厂以后一直是用C++写游戏服务器，而且是纯C++，我了解的不少
阅读更多2024-11-08
Wecom酱搭建企业微信发送消息
获取企业微信应用id、secret。设置可信域名和可信ip。
阅读更多2024-11-08
鹧鸪云光伏小程序上线啦
为了适应市场的发展需求，现推出了手机端SaaS版的光伏小程序，里面包含很多免费的小工具，供给我们业务人员、施工人员方便手机上操作，省去了带着电脑的笨重。投融资测算：能根据提供的详细数据快速的计算出，投
阅读更多2024-11-08
批量压缩tif文件到指定物理宽度mm，同时保持DPI大于300
【代码】批量压缩tif文件到指定物理宽度mm，同时保持DPI大于300。
阅读更多2024-11-08
Java 集合框架
本文主要介绍 Java 中 Collection 和 Map 的相关知识体系，结合源码进行学习。
阅读更多2024-11-08
代码随想录算法训练营第二十二天|回溯法模板、77组合、216组合总和III、17电话号码的字母组合
【代码】代码随想录算法训练营第二十二天|回溯法模板、77组合、216组合总和III、17电话号码的字母组合。
阅读更多2024-11-08

数据结构题集-第二章-线性表-连接链表并安全释放

说明

2.15 已知指针ha和hb分别指向两个单链表的头结点

相关文章