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

数据结构习题集(李冬梅第2版)C语言版源程序汇总 include <iostream> include <cstdlib> using namespace std;/函数结果状态代码Idefine OK 1铲define ERROR 04define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;结点的数据域/结点的指针域/LinkList为指向结构体LNode的指结点的数据域/结点的指针域/LinkList为指向结构体LNode的指typedef struct LNode (int data;struct LNode *next;LNode, *LinkList;针类型Status InitList (LinkList &L);/初始化Status DestroyList (LinkList SL);销毁链表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 lbData = 2,6,8,9,11,15,20;LinkList la, lb;InitList(la);InitList(lb);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);CreateList_R(lbzlbData,sizeof(IbData)/sizeof(IbData0);LinkList 1c;InitList(1c);MergeList(la,lb,1c); coutcc"合并后的线性表为：”;PrintList(lc);DestroyList(lc);return 0;/初始化生成新结点作为头结点，用头指针L指向头结点 /头结点的指针域置空Status InitList(LinkList &L) /构造一个空的单链表LL=new LNode;L->next=NULL; return OK; 销毁链表Status DestroyList(LinkList &L)while(L)while(pa)(n+；pa=pa->next;输出结果：差运算后的线性表为：None > 3 -> 5 该集合的元素个数为：2 才include <iostream> 4include <cstdlib> using namespace std;/函数结果状态代码define OK 1Idefine ERROR 0define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;/结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类/结点的数据域结点的指针域/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 Decompose (LinkList &A, LinkList SB, LinkList &C);分解锥表void PrintList (LinkList L);输出链表int main() (int A_Data=2z-6,8,9,-llz15,-20;LinkList A;InitList(A);CreateList_R(A,A_Data,sizeof(A_Data)/sizeof(A_Data(0);LinkList B,C； Decompose(ArB,C);cout<<”分解后的有序表分别为："<<endl;PrintList(B);PrintList(C);DestroyList(A);return 0;p=p->next;) return false;遍历下一个结点遍历下一个结点void Output()输出数据cout«i«" : ;LinkList p=HTi->next; while(p)输出散列地址/p初始化为链表的首元结点cout«p->data; p=p->next;if(p) cout<<") cout«endl;)void initHash()(for(int i=O;i<LENGTH;i+)HTi=new LNode；HT(i->next=NULL;int main()(initHash();int n;cin»n;for(int i=0;i<n;i+) Insert_K();Output ();Delete_K();Output ();return 0;输入输出0:71:1 82:23:34:45:56:60:71:82:23:34:45:5forfint i=0;i<LENGTH;i+)6:6include <iostream>#include <cstdlib> using namespace std;函数结果状态代码#define OK 1#define ERROR 0 /define OVERFLOW -2 /Status是函数的返回值类型，其他是函数结果状态代码 typedef int Status;结点的数据域结点的指针域/LinkList为指向结构体LNode的指结点的数据域结点的指针域/LinkList为指向结构体LNode的指初始化销毁链表/后插法创立单链表简单项选择择排序输出链表typedef struct LNode ( int data; struct LNode *next;LNode, *LinkList; 针类型Status InitList(LinkList &L);Status DestroyList(LinkList iL);void CreateList_R(LinkList SLf int L_Data, int n); void SelectSort(LinkList &L);void PrintList(LinkList L);int main() ( int n; cout<<”请输入锥表长度： cin»n;int *lData=new intn;cout<< “请输入关键字以空格隔开：”； for(int i»0;i<n;i+) (cin»lData (i; )LinkList 1;InitList(1);CreateList_R(lzIData,n);SelectSort(1);cout<<"排序结果：， PrintList(1);delete(IData);DestroyList(1);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个元素的值，建立带表头结点而单链表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;p-p->next;while(p)cout«p->data«" p=p->next;)cout«endl;简单项选择择排序void SelectSort(LinkList &L) 基于单链表的简单项选择择排序LNode *p=L->next;while(p!=NULL)(LNode *q«p->next;LNode *r=p;while(q!"NULL) if(q->data<r->data) r=q;/尾指针r指向头结点/生成新结点/初始化p的数据域为L_Data i 将新结点*P插入尾结5”之后 /r指向新的尾结点*p/p指向首元结点顺链域向后扫描，直到p为空/r是指向关键字最小的结点的指针q=q->next；)if (r!=p)交换r和p的数据域int temp=r->data;r->data=p->data;p->data«temp;)p=p->next;p指向下一个结点)输出结果请输入链表长度：6请输入关犍字以空格隔开：8 5 7 1 0 1 排序结果：0 115 7 8 4include <iostream> #include <cstdlib> using namespace std;/函数结果状态代码define OK 1#define ERROR 0#define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码双向链表双向链表初始化/销毁链表L_Data , int n);/后插法创立双向链表/双向冒泡排序输出链表typedef int Status;typedef struct DuLNode ( int data;struct DuLNode *prior,*next; DuLNode, *DuLinkList;Status InitList(DuLinkList &L);Status DestroyList(DuLinkList &L); void CreateList_R(DuLinkList &L,int void DuplexSort(DuLinkList &L); void PrintList(DuLinkList L);int main() ( int n; cout<<"请输入锥表长度：" cin»n;int *lData-new intn; cout<<“请输入关键字以空格隔开：'； for(int i»0;i<n;i+) cin»lData i;)DuLinkList 1;InitList(1);CreateList_R(l/IData,n);DuplexSort (1);cout<"排序结果：”；PrintList (1);delete(IData);DestroyList(1);return 0; 初始化Status InitList(DuLinkList &L) 构造一个空的双向链表LL=new DuLNode;/初始化链表L的头结点L->prior=L;L->next=L; return OK; 情毁链表Status DestroyList(DuLinkList &L) (while(L) DuLNode *p=L;L=L->next;delete p;糅放空间) return OK; 后插法创立双向链表void CreateList_R(DuLinkList &L,int L_Data(,int n) (正位序输入n个叁素的值，建立带表头结点的会向链表LDuLinkList p=new DuLNode;p->data=L_Data0;L->next=p;p->prior=L;p->next*NULL;for(int i=l;i<n;i+) (DuLinkList p=new DuLNode;p->data»L_Datai;p->prior=L;L->next->prior=p; p->next=L->next; L->next=p;/输出链表void PrintList(DuLinkList L)依次输出链表中的数据DuLinkList p=L->next; while(p!=NULL) (cout<<p->data<<M " p=p->next;)cout«endl;双向冒泡排序是否发生交换的标记双向链表头，向下冒泡的开始结点 /双向链表尾，向上冒泡的开始结点p是工作指针，指向当前结点假定本趟无交换向卜冒泡，每一趟使一最大元素沉底交换两结点指针，涉及6条锌/有交换先将结点从倦表上摘卜./将temp插到结点*p前无交换，指针后移准备向上起泡交换两结点指针，涉及6条健有交换先将temp结点从链表上摘下/将temp插到p结点后(右)无交换，指针前移准备向下起泡/while(exchange)void DuplexSort(DuLinkList &L)(对存储在带头结点的双向链表L中的元素进行双向冒泡排序int exchange=l;DuLinkList head,tail,p,temp;head=L;tail=NULL;while(exchange)if(head->next=tail)break;p=head->next;exchange=O;while(p->next!=tail)if(p->data > p->next->data)(temp=p->next;exchanger；p->next=temp->next;if(temp->next!=NULL)temp->next->prior=p;temp->next=p;p->prior->next=temp;temp->prior=p->prior; p->prior=temp;else p=p->next;)tail=p;p=tail->prior;while(exchange && p->prior!=head)if(p->data < p->prior->data)(temp=p->prior;exchanged;p->prior=temp->prior; temp->prior->next=p; temp->prior=p;p->next->prior=temp;temp->next=p->next; p->next=temp;else p=p->prior;)head=p;输出结果请输入链表长度：5请输入关健字以空格隔开：8 6 16-4排序结果：-4 16 6 8 ilinclude<iostream> using namespace std;void Process(int az int n)对数组a中的n个关键字进行整理/使所有关键字为负值的记录排在关键字为非负值的记录之前 int low=Orhigh=n-l;while(low<high)while(low<high&&alow<0) low+；while(low<high&&ahigh>=0) high-;if(low<high)(int temp=alow;alow«ahigh;ahigh=temp;low+;high-;找到从左到右的非负值记业找到从右到左的负值记录如果需要交换，即low<high/交换记录继续向后找void PrintA(int a,int n) 输出数据for(int i=0;i<n-l;i+) cout«ai«"cout<<an-1<<endl;int main ()int n;cout«"请输入数组长度:"cin»n;int *a=new intn;cout<<”请输入关键字以空格隔开："for(int i=0;i<n;i+)cin»a i;Process (a, n);/数组的正负排序cout<<"排序结果："；PrintA(a,n);输出数据return 0;输出结果请输入数组长度：5请输入关键字以空格隔开：-1 9 7 2 -4排序结果：-1 -4 7 2 9/基于快排思想的查找#include <iostream>using namespace std;int Search (int r,int low,int high,int key)1/在数组r low. .high中台找关键字值等于key的记录 while(low<high)if(rlow>key&&rhigh<key)1OW+； high-; ) while(low<»high && rhigh>key) high-; /从右侧开始找到第一个不大于关键字的记录，其位置为high if (r high=key)查找成功返回其位置return high; while(low<=high && rlow<key)low+； /从左侧开始找到第一个不小于关键字的记录，其位置为low if (r low=key)查找成功返回其位置return low; ) cout«HNot find"<<endl;/查找失败return -1; int main() ( int n; cout<<”请输入数组长度：， cin>>n; int rn; coutc(”请输入数组元素："； for(int i=0;i<n;i+) cin»r i;int key; cout<< ”请输入要查找的元素：， cin>>key;int p=Search (r, 0, n-1, key); 查找 if(p!«-l) cout<<"该元素在数组中的位置为："<<p+l,<<endl;return 0; 输出结果 请输入数组长度：6 请输入数组元素：9 5 1 3 8 2 请输入要查找的元素：9 该元素在数组中的位置为：1#include<iostream>using namespace std;void CountSort(int a z int bz int n)计数排序，将包括n个数据的数组a中的记录排序存入到数组b中 intfor(i=0;i<n;i+)/针对数组中的每个关键字(for(j=0zc=0;j<n;j+)/统计关键字比当前关键字小的元素个数if(a(j<ai) C+;b(c=ai;根据比当前关键字小的元素个数将当前关键字存放在数组b中)int main()int n;cout<<"请输入数组长度：， cin>>n;int iza100,b100;cout<< “请输入关键字以空格隔开：”;for (i=0;i<n;i+) cin»a i;Countsort (a,bzn);/计数排序cout<”排序结果：”； for(i=0;i<n-l;i+) cout«bi«"cout«bn-l «endl;输出结果请输入数组长度：6请输入关健字以空格隔开：8 4 9 1 7 5排序结果：1 4 5 7 8 9#include<iostream> using namespace std;int Partition(int az int n)将正整数构成的集合划分为两个不相交的子集A1和A2int low=0,high-n-1;int low0=0,highO=n-l;int sl=0,s2=0;int flag»l;int k=n/2;分别指向表的下界和上界 分别指向新的子表的卜界和上界 /分别记录A1和R2中元素的和 /标记划分是否成功记录表的中间位宣while(flag) (int pivotkey=alow;while(low<high) while (low<high && ahigh>=pivotkey) -high;if(low!=high)a lov; =a high;while(low<high && alow<=pivotkey)+1OW；while(flag) (int pivotkey=alow;while(low<high) while (low<high && ahigh>=pivotkey) -high;if(low!=high)a lov; =a high;while(low<high && alow<=pivotkey)+1OW；循环进行划分选择枢轴从两端交替地向中间扫描从最右侧位置依次向左搜索/将比枢轴记录小的记录移到低端从最左侧位置依次向右搜索if(low!=high)ahigh=alow； )alow=pivotkey;if(low=*k-l)flag=0;else/将比枢轴记录大的记录移到高端枢轴记录到位满足条件，枢轴的位置是n/2的前一位置.划分成功，卜次循环将退出划分继续划分/满足条件，枢轴low及之前的所有元素均属于A11ow0=+1qw;high=highO;1ow0=+1qw;high=highO;维续对low之后的元素进行划分else/满足条件，枢轴low及之后的所有元素均属于A2highO=high;继续对low之前的元素进行划分lov/=lowO; ) COUt«”Al中的元素：”； for(int i=0;i<k;i+) (cout«ai«"sl+=ai;求解子集Al中元素的和 cout<<endl;cout«"A2中的元素：" for(int i=k;i<n;i+) cout«ai«"s2+=ai;求解子集A2中元素的和)cout«endl;cout«" IS1-S2 | 的值为：H«s2-sl«erKil; return s2-sl;int main() (int n;cout<<”请输入数组长度：， cin>>n;int an;cout<<”请输入数组元素：， for(int i=0;i<n;i+)cin»a i;Partition(a,n);return 0;输出结果请输入数组长度：5请输入数组元素：6 1 2 8 4A1中的元素：1 2A2中的元素：4 6 8IS1-S2I 的值为：15/初始化/生成新结点作为头结点，用头指针L指向头结点 头结点的指针域置空/生成新结点作为头结点，用头指针L指向头结点 头结点的指针域置空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 &LZ 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_Data i;/初始化 p 的数据域为 L_Data ip->next=NULL; r->next=p; 将新结点*p插入尾结点*r之后 r=p;指向新的尾结点) 输出链表void PrintList(LinkList L) ( LNode *p=L;cout«"None"p=p->next;while(p) (cout«,r -> "«p->data;p=p->next;cout«endl;/分解链表void Decompose(LinkList &A,LinkList &B/LinkList &C) /单链表A分解为两个具有相同结构的链表B和CB=A;LNode *p=A->next;B->next=NULL;C=new LNode;C->next=NULL;B=A;LNode *p=A->next;B->next=NULL;C=new LNode;C->next=NULL;p为工作指针B表初始化为C申请结点空间C初始化为空表while(p!=NULL)while(p!=NULL)表A未到达表尾结点LNode *r=p->next;暂存p的后继if (p->data<0)/将小于0的结点链入B表，前插法 p->next»B->next; B->next=p; ) else将大于0的结点链入C表,前插法( p->next=C->next; C->next=p; ) p=r;/p指向新的待处理结点|输出结果：分解后的有序表分别为：None -> -20 > -11 > -6 None -> 15 -> 9 -> 8 > 2 #include <iostream> dinclude <cstdlib> using namespace std;函数结果状态代码#define OK 1#define ERROR 04define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类初始化梢毁链表后插法创立单链表求最大值输出链表typedef struct LNode (int data;struct LNode *next;LNode, *LinkList; 型Status InitList(LinkList &L);Status DestroyList(LinkList &L);void CreateList_R(LinkList iL,int L_Data, int n); int Max(LinkList L);void PrintList(LinkList L);int main() (int laData=2,-6,8,9,-11,15,-201;LinkList la;InitList(la);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);int lamax=Max(la);cout<<"琏表 la 中的最大值为："<<lamax<<endl;DestroyList(la);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 I ,int n)/正位序输入n个元素的值，建立带表头结点初单链表LLNode *r = L;尾指针r指向头结点for (int i=0;i<n;+i) (LNode *p=new LNode;生成新结点p->data=L_Data i;初始化 p 的数据域为 L_Dataip->next=NULL; r->next=p; /将新结点*p插入尾结点*r之后 r=p;r指向新的尾结点*p) 输出链表void PrintList(LinkList L) (LNode *p=L;cout«"None"p=p->next;while(p) (cout«n -> "«p->data;p=p->next;)cout«endl; 求最大值int Max(LinkList L) 确定单链表中值最大的结点 if(L->next»»NULL) return NULL; LNode *pmax=L->next;pmax 指向首元结点LNode *p=L->next->next;指向第二个结点while (p!=NULL)遍历链表，如果下一个结点存在if(p->data>pmax->data)pmax=p;pmax指向数值大的结点p-p->next;p指向下一个结点，继续遍历) return pmax->data; 输出结果:链表la中的最大值为：15 #include <iostream> #include <cstdlib> using namespace std;/函数结果状态代码 #define OK 1 define ERROR 0 金define 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 5L, int L_Data , int n);/后插法创立单链表void Inverse (LinkList &L);逆转链表void PrintList (LinkList L);输出链表int main() (int laData=2,-6,8,9f-llz15,-20;LinkList la;InitList(la);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);Inverse(la);cout<"链表la逆置后为："；PrintList(la);DestroyList(la);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 iLz int L_Data,int n) (正位序输入n个元素的值，建立带表头结点初单链表LLNode *r - L;/尾指针r指向头结点for (int i=0;i<n;+i) ( LNode *p«new LNode;生成新结点p->data=L_Data i;/初始化 p 的数据域为 L_Data ip->next=NULL; r->next=p; /将新结点*p插入尾结点*r之后 r-p;/r指向新的尾结点/输出鞋表void PrintList(LinkList L) (LNode *p=L;cout«"None"p=p->next;while(p) (cout«n -> M«p->data; p=p->next;)cout«endl;逆转链表void Inverse(LinkList &L) 逆置带头结点的单链表L LNode *p=L->next;L->next=NULL;while(p!=NULL)LNode *q=p->next; p->next=L->next; L->next=p;pq；p指向首元结点头结点的指针域置为空遍历链表，如果卜一个结点存在/q指向*p的后继 /p插入在头结点之后输出结果：链表 la 逆置后为：None -> -20 > 15 > -11 > 9 -> 8 > -6 -> 2#include <iostream>#include <cstdlib> using namespace std;函数结果状态代码4define OK 1Idefine ERROR 0#define OVERFLOW -2/Status是函数的返回值类型，其值是函数结果状态代码 typ