靜態(tài)線性表操作

靜態(tài)線性表操作表入逆間頁表入逆間頁化插表區(qū)兩a始一木找除曇并序t初顯畧刪瀑折順刪臺有耐Ig34:￡￡7-a69a:b:c:9:/*源文件名：Pl.cpp功能：靜態(tài)線性表操作*/#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>constmax=10000;structSqList{intelem[max];//存放元素的數(shù)組intlength;//當(dāng)前長度};SqListlist;intQSnum=O;/快速排序的移動次數(shù)intCPnum=O;/快速排序的比較次數(shù)voidwait();voidopentxt();voidinit(SqList&list);voiddisplay(SqList&list);voidinsert(SqList&list);voidsearch(SqList&list);voiddel(SqList&list);voidsimpleSort(SqList&list);voidquickSort(SqList&list);voidbs(SqList&list,intlow,inthigh);voidQSort(SqList&list,intlow,inthigh);voidnixu(SqList&list);intPartition(SqList&list,intlow,inthigh);voidshanchuqujian(SqList&list);voidhebin(SqList&list);voidsortInsert(SqList&list);voidmain(){charchoice;while(1){system("cls");cout<<"\n\n\n\n";cout<<"\t\t靜態(tài)線性表操作\n";cout<<"\t\t=========cout<<"\n\n";cout<<"\t\t1：初始化\n";cout<<"\t\t2：顯示\n";cout<<"\t\t3：單個插入\n";cout<<"\t\t4：查找\n";cout<<"\t\t5：刪除\n";cout<<"\t\t6：簡單排序\n";cout<<"\t\t7：快速排序\n";cout<<"\t\t8：折半查找\n";cout<<"\t\t9：順序表逆置\n";cout<<"\t\ta：刪除區(qū)間值\n";cout<<"\t\tb：合并兩有序表\n";cout<<"\t\tcout<<"\n";c：有序插入\n";cout<<"\t\t0：退出\n";cout<<"\n";cout<<"\t\t請選擇："<<flush;choice=getch();system("cls");switch(choice){case'1':init(list);break;case'2':display(list);break;case'3':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':bs(list,0,list.length-1);//zhebanchazhao;break;case'9':nixu(list);break;case'a':shanchuqujian(list);break;case'b':hebin(list);break;case'c':sortInsert(list);break;case'0':exit(0);//default:// cout<<"輸入有誤!"<<endl;}}}voidwait(){cout<<"\n\n請按任意鍵繼續(xù)"<<flush;getch();}//屏幕提示后，從鍵盤輸入線性表長度和隨機數(shù)種子，生成指長定度的線性表listvoidinit(SqList&list){inti;while(1){cout<<"輸入元素個數(shù)(0－"<<max<<")："<<flush;cin>>list.length;if(list.length>=0&&list.length<=max)break;cout<<endl;}while(1){cout<<"輸入隨機數(shù)種子(0－32767)："<<flush;cin>>i;if(i>=0&&i<=32767)break;cout<<endl;}001關(guān)于srand(i);//001關(guān)于rand();for(i=0;i<list.length;++i){list.elem[i]=rand()%10000;}for(i=list.length;i<max;++i)list.elem[i]=0;}//在屏幕上依次顯示線性表list中的元素個數(shù)和全部元素//格式應(yīng)便于觀察//如果需要指定輸出的寬度，可以使用cout<<setw(W)<<X,其中X是輸出的數(shù)值，W是占據(jù)的列數(shù)voiddisplay(SqList&list){cout<<"線性表的元素個數(shù)："<<list.length?endl;for(inti=0;i<list.length;++i){cout<<setw(6)<<list.elem[i];if(i%10==9)cout<<endl;}cout<<endl;wait();}//屏幕提示后，從鍵盤輸入一個元素值，然后把這個新元素插到線性表list的末尾//應(yīng)有溢出判斷和報告voidinsert(SqList&list){++list.length;if(list.length<=max){inti=0;cout<<"請輸入新元素值："<<flush;cin>>i;list.elem[list.length-1]=i;}else{cout<<"線性表已滿!不能添加!"<<endl;--list.length;002較次數(shù)002較次數(shù)//屏幕提示后，從鍵盤輸入一個元素值，在線性表002較次數(shù)002較次數(shù)//屏幕顯示搜索結(jié)果和搜索過程中的比沒考慮有重復(fù)隨機數(shù)出現(xiàn)//屏幕提示后，從鍵盤輸入一個元素值，在線性表list中搜索這個元素產(chǎn)生的大批的隨機數(shù)中是否有相同的//屏幕顯示搜索結(jié)果和搜索過程中的比沒考慮有重復(fù)隨機數(shù)出現(xiàn)voidsearch(SqList&list){inti=0;cout<<"請輸入查找的數(shù)值："<<flush;cin>>i;intj=0;while(list.elem[j]!=i&&j<list.length){++j;}if(j<list.length){cout<<"處于第"vvj+lvv"個位置"<<endl;cout<<"比較次數(shù)："<<j+1<<endl;}else{cout<<"未能找到!"<<endl;cout<<"比較次數(shù):"<<list.length?endl;}/*考慮了隨機數(shù)中有重復(fù)inti=0,j=0,k=0;for(j=0;j<list.length;++j){if(list.elem[j]==i){++k;cout<<"第："<<j+1<<"個元素為所查找值"<<endl;}}cout<<endl;cout<<"鏈表中包含"<<k<<"個所查找的元素"<<endl;cout<<endl;cout<<"共比較次數(shù)為："<<list.length?endl;*/wait();//屏幕提示后，從鍵盤輸入一個元素值，在線性表list中刪除這個元素//屏幕顯示刪除成功與否的信息，并顯示比較次數(shù)和移動次數(shù)voiddel(SqList&list){inta=0;cout<<"請輸入刪除的數(shù)值："<<flush;cin>>a;inti=0;while(list.elem[i]!=a&&i<list.length) 〃003while循環(huán)中i的數(shù)值：找不到元素時，i=list.length{i++;}if(i<list.length-1){for(intk=i;k<list.length;k++){list.elem[k]=list.elem[k+1];}list.length--;cout<<"刪除成功!"《endl;}else{if(i==list.length)cout<<"未找到要刪除的元素，刪除失敗!"<<endl;else{list.length--;cout<<"刪除成功!"《endl;}}if(i==list.length){cout<<"比較次數(shù)："<<list.length+1?endl;cout<<"移動次數(shù)："<<0<<endl;}else{cout<<"比較次數(shù)："<<i+1?endl;cout<<"移動次數(shù)："<<list.length-i?endl;}wait();}〃對線性表list進(jìn)行簡單排序//屏幕顯示比較次數(shù)和移動次數(shù)voidsimpleSort(SqList&list) //004此處才用的是冒泡，選擇方法也應(yīng)會,按從小到大排的序{inttemp=0;inta=0,s=0;for(inti=0;i<list.length-1;++i){for(intj=0;j<list.length-i-1;++j){++a;if(list.elem[j]>list.elem[j+1]){++s;temp=list.elem[j];list.elem[j]=list.elem[j+1];list.elem[j+1]=temp;}}}cout<<"比較次數(shù)："<<a<<endl;cout<<"移動次數(shù)："<<s<<endl;wait();}voidbs(SqList&list,intlow,inthigh){inta,mid,b=0;cout?'輸入要查找的數(shù):"；cin>>a;while(low<=high){mid=(low+high)/2;if(list.elem[mid]==a){b++;cout<<"查找成功!"<<endl;cout<<"所查元素位于第"<<mid+1<<"位"<<endl;cout<<"比較次數(shù):"<<b<<"次"<<endl;break;}elseif(a>list.elem[mid]){low=mid;low++;}else{high=mid;high--;}b++;}if(list.elem[mid]!=a){cout<<"未找到!"<<endl;cout<<"查找次數(shù)"<<b<<"次"<<endl;}wait();}〃對線性表list進(jìn)行快速排序//屏幕顯示比較次數(shù)和移動次數(shù)voidquickSort(SqList&list){CPnum=0;變量，故應(yīng)每次調(diào)用時應(yīng)對其置零QSnum=0;QSort(list,0,list.length-1);cout<<"比較次數(shù)："<<CPnum<<endl;cout<<"移動次數(shù)："<<QSnum<<endl;wait();}//快速排序使用的相關(guān)函數(shù)//no.1一趟快速排序intPartition(SqList&list,intlow,inthigh)自己動手寫出，才能真正的成功//注意：由于CPnum、QSnum為全局//否則CPnum、QSnum將不斷累加相關(guān)信息參見數(shù)據(jù)結(jié)構(gòu)與算法P274//不能照搬書上的程序，要在自己的理解上intpivotkey=list.elem[low];while(low<high){while(low<high&&list.elem[high]>=pivotkey){--high;++CPnum;}list.elem[low]=list.elem[high];++QSnum;while(low<high&&list.elem[low]<=pivotkey){++low;++CPnum;}list.elem[high]=list.elem[low];++QSnum;}list.elem[low]=pivotkey;returnlow;}//no.2快速排序遞歸函數(shù)voidQSort(SqList&list,intlow,inthigh){intpivotkey=0;if(low<high){pivotkey=Partition(list,low,high);QSort(list,low,pivotkey-1);QSort(list,pivotkey+1,high);}}voidnixu(SqList&list) //順序表逆置;{inti;for(i=list.length-1;i>=0;i--){cout<<list.elem[i]<<"";}wait();}voidshanchuqujian(SqList&list){inta,k=0,i=0,b;cout<<"輸入刪除元素的范圍<小值再前cin>>a;cout<<"輸入刪除元素的范圍<大值再前>:";cin>>b;for(k=0;k<list.length;k++)if(list.elem[k]<a||list.elem[k]>b){list.elem[i]=list.elem[k];i++;}}list.length=i;}voidhebin(SqList&list){intnum=O;〃用于溢出判斷l(xiāng)ist.length=0;SqListlist1;SqListIist2;〃待合并的表cout<<"構(gòu)建表1:"<<endl;init(Iist1);//cout<<"構(gòu)建表2:"<<endl;cout<<endl;init(list2);//QSort(list1,O,list1.length-1);QSort(list2,O,list2.length-1);//合并成有序表到listinti=O,j=O;intk=O;while(i<list1.length&&j<list2.length){if(list1.elem[i]<list2.elem[j]){list.elem[k]=list1.elem[i];++list.length;++k;if(k>max){cout<<"合并失敗!元素溢出!"<<endl;break;}++i;}else{if(list1.elem[i]==list2.elem[j]){list.elem[k]=list1.elem[i];++list.length;++k;if(k>max){cout<<"合并失敗!元素溢出!"<<endl;break;}++i;++j;}else{list.elem[k]=list2.elem[j];++list.length;++k;if(k>max){cout<<"合并失敗!元素溢出!"<<endl;break;}++j;}}}inta=0;if(k<=max){if(i<list1.length){for(a