数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码 习题集-算法2-5.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 t int n) ;/后插法创立单链表void Decompose (LinkList &AZ LinkList &B, LinkList &C);/分解链表void PrintList (LinkList L) ;/输出链表int main() ( int A_Data=2,-6,8,9,-11,15,-20; LinkList A; InitList(A);CreateList_R(Af A_Dataz sizeof(A_Data)/sizeof(A_Data0);LinkList B,C;Decompose(A,B,C);分解后的有序表分别为：，Y <endl;PrintList(B); PrintList (C);DestroyList(A);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;/后插法创立单链表/尾指针r指向头结点/生成新结点/初始化p的数据域为L_Datai /将新结点*P插入尾结1%之后 /r指向新的尾结点*pvoid CreateList_R(LinkList &L,int L_Data, int n) /正位序输入n个元素的值，建立带表头结点而单链表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<<nNoneH;p=p->next;while(p) cout<<n -> n<<p->data; p=p->next;cout«endl;/分解链表void Decompose(LinkList LinkList &Bf LinkList &C) /单链表A分解为两个具有相同结构的链表B和CB=A;LNode *p=A->next;B->next=NULL;C=new LNode;C->next=NULL;/p为工作指针/B表初始化/为C申请结点空间/C初始化为空表while(p!=NULL) (LNode *r=p->next;if(p->data<0)(p->next=B->next; B->next=p;else(p->next=C->next; C->next=p;p=r;/表A未到达表尾结点/暂存p的后继/将小于0的结点链入B表，前插法/将大于0的结点链入C表，前插法/P指向新的待处理结点输出结果：分解后的有序表分别为：None > 2 0 > -11 > -6None > 15 > 9 > 8 > 2