《上海第二工业大学1011学期计算机学院实训数据结构习题参考.docx》由会员分享，可在线阅读，更多相关《上海第二工业大学1011学期计算机学院实训数据结构习题参考.docx（15页珍藏版）》请在三一办公上搜索。
1、上海第二工业大学1011学期计算机学院实训数据结构习题参考/*源文件名：P1.cpp功能：顺序表操作*/#include <iostream.h>#include <iomanip.h>#include <conio.h>#include <stdio.h>#include <process.h>#include <string.h>#include <math.h>#include <stdlib.h>#include <fstream.h>const max=10000;struct SqListint elemmax
2、; /存放元素的数组int length; /当前长度;void slowcout << nn请按任意键继续 << flush;getch;void init(SqList &list);void display(SqList &list);void insert(SqList &list);void search(SqList &list);void del(SqList &list);void simpleSort(SqList &list);void quickSort(SqList &list);void quicksort_cnt(void);void binaryS
3、earch(SqList &list);void nzlist(SqList &list);int Partion(SqList &list,int ,int );SqList list;void mainchar choice;while (1)system(cls);cout << nnnn;cout << tt 顺序表操作 n;cout << tt=;cout << nn;cout << tt 1：初始化 n;cout << tt 2：显示 n;cout << tt 3：单个插入 n;cout << tt 4：查找 n;co
4、ut << tt 5：删除 n;cout << tt 6：简单选择排序 n;cout << tt 7：快速排序 n;cout << tt 8：折半查找 n;cout << tt 9：逆置线性表 n;cout << n;cout << tt 0：退出 n;cout << n;cout << tt请选择： << flush;choice = getch;system(cls);switch(choice)case 1:init(list);break;case 2:display(list);break;case 3:
5、insert(list);break;case 4:search(list);break;case 5:del(list);break;case 6:simpleSort(list);break;case 7:quickSort(list);break;case 8:binarySearch(list);break;case 9:nzlist(list);break;case 0:exit(0);/屏幕提示后，从键盘输入线性表长度和随机数种子，生成指定长度的线性表listvoid init(SqList &list)int i;while (1)cout << 输入元素个数： <&
6、lt flush;cin >> list.length;if (list.length >= 0 & list.length <= max)break;cout << endl;while (1)cout << 输入随机数种子： << flush;cin >> i;if (i >= 0 & i <= 32767)break;cout << endl;srand(i); /指定随机数种子，相同的种子将产生相同的数据序列rand;for (i = 0; i < list.length; i+)list.elemi = rand %
7、 10000;for (i = list.length; i < max; i+)list.elemi = 0;/在屏幕上依次显示线性表list中的元素个数和全部元素/格式应便于观察/如果需要指定输出的宽度，可以使用 cout << setw(W) << X ，其中 X 是输出的数值，W 是占据的列数void display(SqList &list)cout<<共有<<list.length<<个元素<<分别是:;for(int i=0;i<list.length;i+)cout<<list.elemi<<,;/屏幕提示
8、后，从键盘输入一个元素值和一个插入位置值，然后把这个新元素插到线性表list的指定位置处/应有溢出判断和报告void insert(SqList &list) cout<<请输入要插入的值：<<endl;cout<<请输入要插入的位置<<endl;int x;int n;int i;cin>>x;cin>>n;if (list.length>=0 & list.length<=max)for (i=list.length-1;i>n;i-)list.elemi+1=list.elemi;list.elemn=x;list.length
9、+;elsecout<<插入失败<<endl;/屏幕提示后，从键盘输入一个元素值，在线性表list中搜索这个元素/屏幕显示搜索结果和搜索过程中的比较次数void search(SqList &list)int i=0,j;cout<<请输入要搜索的数据：;cin>>j;while(i<list.length&list.elemi!=j)i+;if(list.elemi=j)cout<<已找到,该元素位于第<<i+1<<位 , ;else cout<<sorry, ;cout<<共比较了<<i+1<<次;
10、cout<<endl;slow;/屏幕提示后，从键盘输入一个元素值，在线性表list中删除这个元素/屏幕显示删除成功与否的信息，并显示比较次数和移动次数void del(SqList &list)int i=0,j;cout<<请输入要删除的值：;cin>>j;while(i<list.length&list.elemi!=j)i+;if(list.elemi=j)for(int m=i;m<list.length-1;m+)list.elemm=list.elemm+1;list.length-;cout<<completed<<endl;el
11、se cout<<failed<<endl;cout<<比较次数:<<i+1<<,移动次数:<<list.length-i<<endl;slow;/对线性表list进行简单选择排序/屏幕显示比较次数和移动次数void simpleSort(SqList &list)int i,j,k,c=0,d=0;for(i=0;i<list.length-1;i+)for(j=i;j<list.length;j+) d+;if(list.elemj<list.elemi)c+;k=list.elemj;list.elemj=list.el
12、emi;list.elemi=k;cout<<比较次数：<<d<<,移动次数:<<c<<endl;slow;/对线性表list进行快速排序/屏幕显示比较次数和移动次数void QSort (SqList &list,int low,int high);void quickSort(SqList &list)int CPnum=0, QSnum=0; QSort(list,0,list.length-1);cout<<比较次数：<<CPnum<<endl;cout<<移动次数：<<QSnum<<endl;sl
13、ow;int Partition(SqList &list,int low,int high) int CPnum=0, QSnum=0;int pivotkey=list.elemlow;while(low<high)while(low<high&list.elemhigh>=pivotkey) -high;+CPnum;list.elemlow=list.elemhigh; +QSnum;while(low<high&list.elemlow<=pivotkey) +low;+CPnum;list.elemhigh=list.elemlow; +QSnum;list.e
14、lemlow=pivotkey;return low;void QSort (SqList &list,int low,int high)int pivotloc=0;if(low<high)pivotloc=Partition(list,low,high);QSort(list,low,pivotloc-1);QSort(list,pivotloc+1,high);/屏幕提示后，从键盘输入一个元素值，对经过排序的线性表list进行折半查找/屏幕显示查找结果，并显示比较次数void binarySearch(SqList &list)int i,low,high,mid,m=0,n=0;c
15、out<<请输入要查找的值：;cin>>i;low=0,high=list.length-1;while(low<=high)mid=(low+high)/2;if(i=list.elemmid)break;else if(i>list.elemmid)low=mid+1;m+;else high=mid-1;n+;if(i!=list.elemmid)cout<<查找失败<<endl;else cout<<位于第<<mid+1<<位<<，比较<<m+n+1<<次<<endl;/编程实现一个顺序表的
16、就地逆置，即利用原表的存储空间将顺序表逆置。void nzlist(SqList &list)int t,n=list.length;for(int i=0;i<n/2;i+)t=list.elemn-1-i;list.elemn-1-i=list.elemi;list.elemi=t; /*1、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素。2、编程实现将两个有序的顺序表进行合并，要求同样的数据元素只出现一次。3、编程实现shell排序。*/*选做题:* 有序插入，屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素；屏幕显示比较次数和移动次数，应有溢出判断和报告。*、编程实现堆排序算法。*/
