说明
- 本文参照严蔚敏《数据结构(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){// 构造一个空的线性链表LLink 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){// 销毁线性链表Lif(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所指结点插入到第一个结点之前// 线性链表的尾指针没有变化，线性链表的元素个数加1Link 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;
}//ListConcatint 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;
}//InsLastStatus 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;
}// HalfListConcatWithMakeLongerListNullint 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语言相对于其他高级语言的尴尬，也是对算法设计者的考验。