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

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

1、ttinclude 件include using namespace std;函数结果状态代码Mefine OK 14define ERROR 0/define OVERFLOW -2/Status是函数的返回值类型，其值是函数结果状态代码typedefint Status;typedef typedeftypedef typedefint ElemType; struct LNodeintintdata;struct LNode *next;LNode, LinkList;LNode的指针类型结点的数据域结点的指针域/LinkList为指向结构体初始化销毁链表后插法创立单链表求交集输出链表生

2、成新结点作为头结点，用头指针L指向头结点 头结点的指针域置空Status InitList(LinkList &L);Status DestroyList(LinkList &L);void CreateList_R(LinkList &L,int L_Data,int n);void Intersection(LinkList iLa,LinkList &Lb,LinkList &Lc); void PrintList(LinkList L);int main()int laData = 3,5,8,11);int lbData1=12,6,8,9,11,15,20);LinkList la

3、, lb;InitList(la);InitList(lb);CreateList_R(lazlaData,sizeof(laData)/sizeof(laData0);CreateList_R(lb,IbData,sizeof(IbData)/sizeof(IbData0);LinkList 1c；InitList(1c);Intersection(la,lb,1c);coutnext=NULL;return OK;销毁链表Status DestroyList(LinkList &L)while(L)LNode *p=L; L=L-next; delete p; return OK;释放空间

4、后插法创立单链表void CreateList_R(LinkList &L,int L_Data,int n)(正位序输入n个元素的值，建立带表头结点M单链表LLNode *r = L;/尾指针r指向头结点for (int i=0;idata=L_Datai; p-next=NULL; r-next=p; r=p;输出能表void PrintList(LinkList L)(LNode *p=L; coutNone;p=p-next;while(p)(cout p-data; p=p-next;coutendl;生成新结点初始化p的数据域为L_Data i将新结点*P插入尾结点*r之后 指向新

5、的尾结点*p求交集void Intersection(LinkList &La,LinkList &Lb,LinkList &Lc) 求两个递增的有序链表La和Lb的交集，使用头指针Lc指向LNode *pa=La-next;LNode *pbLb-next;Lc=La; LNode *pc=La; while(pa&pb) (if (pa-data=pb-data)/pa是链表La的工作指针，初始化为首元结点 pb是链表Lb的工作指针，初始化为首元结点 用La的头结点作为Lc的头结点 两个鞋表La和Lb均未到达表尾结点相等，交集并入结果表中pc-next=pa; pc=pa; pa=pa-n

6、ext;取La中的元素,将pa链接在pc的后面,pa指针后移LNode *u=pb; pb=pb-next; delete u;删除Lb中的对应的相等元素 )else if (pa-datadata)/删除较小者 La 中的元素LNode *upa;pa=pa-next;delete u;) else删除较小者Lb中的元素LNode *u=pb; pb=pb-next;delete u; ) while(pa)(LNode *u=pa; pa=pa-next; delete u;while(pb)(LNode *u=pb; pb=pb-next; delete u;pc-next=NULL; delete Lb;/Lb为空，删除非空表La中的所有元素La为空，删除非空表Lb中的所有元素/置桂表Lc尾标记 释放Lb的头结点输出结果:取交集后的线性表为：None - 8 - 11