数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-2.docx
include <iostream>include <cstdlib> using namespace std;/函数结果状态代码define OK 1define ERROR 0define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;/结点的数据域/结点的指针域/LinkList为指向结构体LNode的指/初始化/销毁链表/后插法创立单链表/合并/输出链表typedef struct LNode int data;struct LNode *next;LNode, *LinkList; 针类型Status InitList(LinkList &L);Status DestroyList(LinkList &L);void CreateList_R(LinkList &L,int L_Data,int n);void MergeList(LinkList &LA,LinkList &LB,LinkList &LC);void PrintList(LinkList L);int main() ( int laData=3,5,8,11; int 1bData=2,6,8,9,11,15,20; LinkList la, lb;InitList(la);InitList(lb);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);CreateList_R(lb,IbData,sizeof(IbData)/sizeof(IbData0);LinkList 1c;InitList(lc);MergeList(la,lb,lc); 合并后的线性表为：n; PrintList(lc);DestroyList(lc);return 0; /初始化 Status InitList (LinkList &L) /构造一个空的单链表LL=new LNode;/生成新结点作为头结点，用头指针L指向头结点L->next=NULL;/头结点的指针域置空return OK; ) /销毁链表 Status DestroyList(LinkList &L) ( while(L)LNode *p=L;L=L->next; delete p;) return OK;)/释放空间/后插法创立单链表void CreateList_R(LinkList &L,int L_Data,int n) /正位序输入n个元素的值，建立带表头结点M单链表LLNode *r = L;for (int i=0;i<n;+i) LNode *p=new LNode; p->data=L_Datai; p->next=NULL; r->next=p; r=p;)/输出链表void PrintList(LinkList L) LNode *p=L;cout«HNonen;p=p->next;while(p) cout«n -> n<<p->data; p=p->next; cout«endl;)/尾指针r指向头结点/生成新结点/初始化p的数据域为L_Datai/将新结点*P插入尾结点"之后/r指向新的尾结点*p/合并void MergeList(LinkList &Laz LinkList &Lbz LinkList &Lc) /将两个非递减的有序链表La和Lb合并为一个非递增的有序链表LcLNode *pa=La->next; LNode *pb=Lb->next; Lc=La; LNode *pc=La; Lc->next=NULL;LNode *q;while(pa|pb) (if(!pa) (q=pb; pb=pb->next;)else if(!pb)/pa是链表La的工作指针，初始化为首元结点/pb是链表Lb的工作指针，初始化为首元结点/用La的头结点作为Lc的头结点/只要有一个表未到达表尾结点，用q指向待摘取的元素/La表为空，用q指向pb, pb指针后移/Lb表为空，用q指向pa, pa指针后移q=pa；pa=pa->next;)else if (pa->data<=pb->data)/取较小者La中的元素，用q指向pa, pa指针后移q=pa； pa=pa->next;else/取较小者Lb中的元素，用q指向pb, pb指针后移q=pb;pb=pb->next;q->next=Lc->next; Lc->next=q; /将q指向的结点插在Lc的表头结点之后delete Lb;delete Lb;/释放Lb的头结点输出结果：合并后的线性表为：None > 20 > 15 > 11 > 11 > 9 > 8 > 8 > 6 > 5 > 3 > 2
