数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-2.docx

《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-2.docx》由会员分享，可在线阅读，更多相关《数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-2.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、include include 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);St

2、atus 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(laDat

3、a)/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 D

4、estroyList(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;idata=L_Datai; p-next=NULL; r-next=p; r=p;)/输出链表void PrintList(LinkList L) LNode *p=L;coutHNonen;p=p-next;whil

5、e(p) coutn - ndata; p=p-next; coutendl;)/尾指针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;

6、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-datadata)/取较小者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