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

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

1、数据结构习题集(李冬梅第2版)C语言版源程序汇总 include include 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, *LinkLis

2、t;针类型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;LinkLis

3、t 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(Lin

4、kList &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 4include using namespace std;/函数结果状态代码define OK 1Idefine ERROR 0define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Statu

5、s;/结点的数据域结点的指针域/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 (LinkLi

6、st &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”分解后的有序表分别为：next;) return false;遍历下一个结点遍历下一个结点void Output()输出数据couti : ;Link

7、List p=HTi-next; while(p)输出散列地址/p初始化为链表的首元结点coutp-data; p=p-next;if(p) cout) coutendl;)void initHash()(for(int i=O;inext=NULL;int main()(initHash();int n;cinn;for(int i=0;in;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;iLENGTH;i+)6:6

8、include #include 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, *Lin

9、kList; 针类型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”请输入锥表长度： cinn;int *lData=new intn;cout “请输入关键字以空格隔开：”； for(int i0;in;i+) (cinlData (i; )LinkList

10、1;InitList(1);CreateList_R(lzIData,n);SelectSort(1);coutnext-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 i0;idata=L_Da

11、tai; p-next=NULL; r-nextp; r=p;输出链表void PrintList(LinkList L) (LNode *p=L;p-p-next;while(p)coutp-data p=p-next;)coutendl;简单项选择择排序void SelectSort(LinkList &L) 基于单链表的简单项选择择排序LNode *p=L-next;while(p!=NULL)(LNode *qp-next;LNode *r=p;while(q!NULL) if(q-datadata) r=q;/尾指针r指向头结点/生成新结点/初始化p的数据域为L_Data i 将新结

12、点*P插入尾结5”之后 /r指向新的尾结点*p/p指向首元结点顺链域向后扫描，直到p为空/r是指向关键字最小的结点的指针q=q-next；)if (r!=p)交换r和p的数据域int temp=r-data;r-data=p-data;p-datatemp;)p=p-next;p指向下一个结点)输出结果请输入链表长度：6请输入关犍字以空格隔开：8 5 7 1 0 1 排序结果：0 115 7 8 4include #include using namespace std;/函数结果状态代码define OK 1#define ERROR 0#define OVERFLOW -2 /Status

13、是函数的返回值类型，其值是函数结果状态代码双向链表双向链表初始化/销毁链表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(DuLin

14、kList &L); void PrintList(DuLinkList L);int main() ( int n; cout请输入锥表长度：; cinn;int *lData-new intn; cout“请输入关键字以空格隔开：； for(int i0;in;i+) cinlData i;)DuLinkList 1;InitList(1);CreateList_R(l/IData,n);DuplexSort (1);coutprior=L;L-next=L; return OK; 情毁链表Status DestroyList(DuLinkList &L) (while(L) DuLNod

15、e *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;idataL_Datai;p-prior=L;L-next-prior=p; p-next=L-next; L-next=p;/输出链表void PrintList(DuLink

16、List L)依次输出链表中的数据DuLinkList p=L-next; while(p!=NULL) (coutdatanext;)coutendl;双向冒泡排序是否发生交换的标记双向链表头，向下冒泡的开始结点 /双向链表尾，向上冒泡的开始结点p是工作指针，指向当前结点假定本趟无交换向卜冒泡，每一趟使一最大元素沉底交换两结点指针，涉及6条锌/有交换先将结点从倦表上摘卜./将temp插到结点*p前无交换，指针后移准备向上起泡交换两结点指针，涉及6条健有交换先将temp结点从链表上摘下/将temp插到p结点后(右)无交换，指针前移准备向下起泡/while(exchange)void Duple

17、xSort(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

18、-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 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请输入

19、关健字以空格隔开：8 6 16-4排序结果：-4 16 6 8 ilinclude using namespace std;void Process(int az int n)对数组a中的n个关键字进行整理/使所有关键字为负值的记录排在关键字为非负值的记录之前 int low=Orhigh=n-l;while(lowhigh)while(lowhigh&alow0) low+；while(low=0) high-;if(lowhigh)(int temp=alow;alowahigh;ahigh=temp;low+;high-;找到从左到右的非负值记业找到从右到左的负值记录如果需要交换，即lo

20、whigh/交换记录继续向后找void PrintA(int a,int n) 输出数据for(int i=0;in-l;i+) coutaicoutan-1endl;int main ()int n;cout请输入数组长度:;cinn;int *a=new intn;cout”请输入关键字以空格隔开：;for(int i=0;in;i+)cina i;Process (a, n);/数组的正负排序cout排序结果：；PrintA(a,n);输出数据return 0;输出结果请输入数组长度：5请输入关键字以空格隔开：-1 9 7 2 -4排序结果：-1 -4 7 2 9/基于快排思想的查找#i

21、nclude using namespace std;int Search (int r,int low,int high,int key)1/在数组r low. .high中台找关键字值等于key的记录 while(lowkey&rhighkey)1OW+； high-; ) while(lowkey) high-; /从右侧开始找到第一个不大于关键字的记录，其位置为high if (r high=key)查找成功返回其位置return high; while(low=high & rlowkey)low+； /从左侧开始找到第一个不小于关键字的记录，其位置为low if (r low=ke

22、y)查找成功返回其位置return low; ) coutHNot findendl;/查找失败return -1; int main() ( int n; coutn; int rn; coutc(”请输入数组元素：； for(int i=0;in;i+) cinr i;int key; coutkey;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

23、using namespace std;void CountSort(int a z int bz int n)计数排序，将包括n个数据的数组a中的记录排序存入到数组b中 intfor(i=0;in;i+)/针对数组中的每个关键字(for(j=0zc=0;jn;j+)/统计关键字比当前关键字小的元素个数if(a(jai) C+;b(c=ai;根据比当前关键字小的元素个数将当前关键字存放在数组b中)int main()int n;coutn;int iza100,b100;cout “请输入关键字以空格隔开：”;for (i=0;in;i+) cina i;Countsort (a,bzn);/

24、计数排序cout”排序结果：”； for(i=0;in-l;i+) coutbicoutbn-l endl;输出结果请输入数组长度：6请输入关健字以空格隔开：8 4 9 1 7 5排序结果：1 4 5 7 8 9#include 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 flagl;int k=n/2;分别指向表的下界和上界 分别指向新的子表的卜界和上界 /分别记录A1和R2中元

25、素的和 /标记划分是否成功记录表的中间位宣while(flag) (int pivotkey=alow;while(lowhigh) while (low=pivotkey) -high;if(low!=high)a lov; =a high;while(lowhigh & alow=pivotkey)+1OW；while(flag) (int pivotkey=alow;while(lowhigh) while (low=pivotkey) -high;if(low!=high)a lov; =a high;while(lowhigh & alow=pivotkey)+1OW；循环进行划分选

26、择枢轴从两端交替地向中间扫描从最右侧位置依次向左搜索/将比枢轴记录小的记录移到低端从最左侧位置依次向右搜索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;继续对lo

27、w之前的元素进行划分lov/=lowO; ) COUt”Al中的元素：”； for(int i=0;ik;i+) (coutaisl+=ai;求解子集Al中元素的和 coutendl;coutA2中的元素：; for(int i=k;in;i+) coutais2+=ai;求解子集A2中元素的和)coutendl;cout IS1-S2 | 的值为：Hs2-slerKil; return s2-sl;int main() (int n;coutn;int an;cout”请输入数组元素：， for(int i=0;inext=NULL;return OK;情毁链表Status DestroyL

28、ist(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;idata=L_Data i;/初始化 p 的数据域为 L_Data ip-next=NULL; r-next=p; 将新结点*p插入尾结点*r之后 r=p;指向新的尾结点) 输出链表void PrintList

29、(LinkList L) ( LNode *p=L;coutNone;p=p-next;while(p) (cout,r - p-data;p=p-next;coutendl;/分解链表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初

30、始化为空表while(p!=NULL)while(p!=NULL)表A未到达表尾结点LNode *r=p-next;暂存p的后继if (p-datanextB-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 dinclude using namespace std;函数结果状态代码#define OK 1#define ERROR 04define OVE

31、RFLOW -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(

32、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 中的最大值为：lamaxnext=NULL;头结点的指针域置空return OK; /销毁链表 Status DestroyList(Lin

33、kList &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;idata=L_Data i;初始化 p 的数据域为 L_Dataip-next=NULL; r-next=p; /将新结点*p插入尾结点*r之后 r=p;r指向新的尾结点*p) 输出链表void PrintList(LinkLi

34、st L) (LNode *p=L;coutNone;p=p-next;while(p) (coutn - p-data;p=p-next;)coutendl; 求最大值int Max(LinkList L) 确定单链表中值最大的结点 if(L-nextNULL) return NULL; LNode *pmax=L-next;pmax 指向首元结点LNode *p=L-next-next;指向第二个结点while (p!=NULL)遍历链表，如果下一个结点存在if(p-datapmax-data)pmax=p;pmax指向数值大的结点p-p-next;p指向下一个结点，继续遍历) retur

35、n pmax-data; 输出结果:链表la中的最大值为：15 #include #include 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 (L

36、inkList &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);I

37、nverse(la);coutnext=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;idata=L_Data i;/初始化 p 的数据域为 L_Data ip-next=

38、NULL; r-next=p; /将新结点*p插入尾结点*r之后 r-p;/r指向新的尾结点/输出鞋表void PrintList(LinkList L) (LNode *p=L;coutNone;p=p-next;while(p) (coutn - Mp-data; p=p-next;)coutendl;逆转链表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 #include using namespace std;函数结果状态代码4define OK 1Idefine ERROR 0#define OVERFLOW -2/Status是函数的返回值类型，其值是函数结果状态代码 typ