数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-3.docx
ttinclude <iostream> 件include <cstdlib> 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为指向结构体初始化销毁链表后插法创立单链表求交集输出链表生成新结点作为头结点，用头指针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, 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);cout<<”取交集后的线性表为：， PrintList(lc);DestroyList(1c);return 0;初始化Status InitList(LinkList &L) /构造一个空的单链表LL=new LNode;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;/尾指针r指向头结点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«"None"p=p->next;while(p)(cout«" > "«p->data; p=p->next;cout«endl;生成新结点初始化p的数据域为L_Data i将新结点*P插入尾结点*r之后 指向新的尾结点*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->next;取La中的元素,将pa链接在pc的后面,pa指针后移LNode *u=pb; pb=pb->next; delete u;删除Lb中的对应的相等元素 )else if (pa->data<pb->data)/删除较小者 La 中的元素LNode *u»pa;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
