實驗一 線性表的基本操作實現(xiàn)及其應用

實驗一線性表的基本操作實現(xiàn)及其應用實驗一線性表的基本操作實現(xiàn)及其應用實驗一線性表的基本操作實現(xiàn)及其應用資料僅供參考文件編號：2022年4月實驗一線性表的基本操作實現(xiàn)及其應用版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：實驗一線性表的基本操作實現(xiàn)及其應用一、實驗目的1、熟練掌握線性表的基本操作在兩種存儲結構上的實現(xiàn)。2、會用線性鏈表解決簡單的實際問題。二、實驗內容題目一、該程序的功能是實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結構類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。其中，程序中的單鏈表（帶頭結點）結點為結構類型，結點值為整型。單鏈表操作的選擇以菜單形式出現(xiàn)，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求鏈表長度4.檢查鏈表是否為空5.檢查鏈表是否為滿6.遍歷鏈表（設為輸出元素）7.從鏈表中查找元素8.從鏈表中查找與給定元素值相同的元素在表中的位置9.向鏈表中插入元素10.從鏈表中刪除元素其他鍵退出。。。。。其中黑體部分必做題目二、約瑟夫環(huán)問題：設編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設計一個程序模擬此過程，求出出列編號序列。structnodeMain函數(shù)Main函數(shù)初始化鏈表調用菜單函數(shù)1.清空2.求鏈表長度3.檢查鏈表是否為空4.遍歷鏈表5.按位置查找元素6.按值查找元素7.向鏈表中插入元素8.從鏈表中刪除元素9.退出等待選擇，等輸入1-9時，調用對應函數(shù)，否則退出程序結束輸入1-9輸入非1-9程序調試及運行結果分析1．進入選擇界面后，先選擇7，進行插入： 2.選擇4，進行遍歷，結果為：選擇2，得出當前鏈表長度.4.選擇3，得出當前鏈表為.選擇分別選擇5、6進行測試.選擇8，分別按位置和元素值刪除.選擇9，或非1-8的字符，程序結束.實驗總結 通過這次實驗，我對線性鏈表有了更深的理解，深入明白了線性存儲結構與鏈式存儲結構在內存存儲的不同特點，同時我還學會了用這些知識實際解決一些問題，能夠更加熟練地將算法轉化為實際程序。同時，在寫程序和調試程序的過程中，學會了一些書寫技巧和調試技巧，這對于自己能在短時間高效的寫出正確地程序有很大作用。四、主要算法流程圖及程序清單主要算法流程圖： (1)從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置p=p->nextp&&!(p->data==x)p=p->nextp&&!(p->data==x)true調用函數(shù)，傳入參數(shù)L，xp=L->nextfalse返回p調用函數(shù)，傳入參數(shù)調用函數(shù)，傳入參數(shù)L，i，x建立新結點s，令s->data=x;p=L->nexti==1p=nullfalseL->next=s;s->next=NULL;trueL->next=s;s->next=p;j=1j<i-1&&pp=p->nextj++trueq=p->next;p->next=s;s->next=q;P不為空返回對應值FalseFalse 程序清單：#include<iostream>usingnamespacestd;#include<>#include<>/*預處理命令*/#defineOK1;#defineERROR0;#defineOVERFLOW-1;/*單鏈表的結點類型*/typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkedList;/*初始化單鏈表*/LinkedListLinkedListInit(){ 空"<<endl; cout<<"\t\t\t"<<"2.求鏈表長度"<<endl; cout<<"\t\t\t"<<"3.檢查鏈表是否為空"<<endl; cout<<"\t\t\t"<<"4.遍歷鏈表"<<endl; cout<<"\t\t\t"<<"5.從鏈表中查找元素"<<endl; cout<<"\t\t\t"<<"6.從鏈表中查找與給定元素值相同的元素在表中的位置"<<endl; cout<<"\t\t\t"<<"7.向鏈表中插入元素"<<endl; cout<<"\t\t\t"<<"8.從鏈表中刪除元素"<<endl; cout<<"\t\t\t"<<"9.退出"<<endl;}/*主函數(shù)*/intmain(){ 鏈表長度 case2:{ cout<<"\t\t\t鏈表長度為："<<LinkedListLength(L)<<endl; getch(); } break; 查鏈表是否為空 case3:{ if(!LinkedListEmpty(L)) { cout<<"\t\t\t鏈表不為空！"<<endl; } else { cout<<"\t\t\t鏈表為空！"<<endl; } getch(); } break; 歷鏈表 case4:{ LinkedListTraverse(L); getch(); } break; 鏈表中查找元素 case5:{ cout<<"\t\t\t請輸入要查詢的位置i："; intj; cin>>j; if(LinkedListGet(L,j)) { cout<<"\t\t\t位置i的元素值為："<<LinkedListGet(L,j)->data<<endl; } else { cout<<"\t\t\ti大于鏈表長度！"<<endl; } getch(); } break; 鏈表中查找與給定元素值相同的元素在表中的位置 case6:{ cout<<"\t\t\t請輸入要查找的元素值："; intb; cin>>b; if(LinkedListGet1(L,b)) { cout<<"\t\t\t要查找的元素值位置為："<<LinkedListGet1(L,b)<<endl; cout<<"\t\t\t要查找的元素值內存地址為："<<LinkedListLocate(L,b)<<endl; } else { cout<<"\t\t\t該值不存在！"<<endl; } getch(); } break; 鏈表中插入元素 case7:{ cout<<"\t\t\t請輸入要插入的值：";intx;cin>>x; cout<<"\t\t\t請輸入要插入的位置：";intk;cin>>k; if(LinkedListInsert(L,k,x)) { cout<<"\t\t\t插入成功！"<<endl; } else { cout<<"\t\t\t插入失敗！"<<endl; } getch(); } break; 鏈表中刪除元素 case8:{ cout<<"\t\t\t1.按位置刪除"<<endl; cout<<"\t\t\t2.按元素刪除"<<endl; intd; cout<<"\t\t請選擇：";cin>>d; switch(d) { case1:{ cout<<"\t\t\t請輸入刪除位置："; cin>>d; inty; if(LinkedListDel(L,d,y)) { cout<<"\t\t\t"<<y<<"被刪除！"<<endl; } else { cout<<"\t\t\t刪除失??！"<<endl; } }break; case2:{ cout<<"\t\t\t請輸入刪除元素："; inty; cin>>y; if(LinkedListDel(L,y)) { cout<<"\t\t\t"<<y<<"被刪除！"<<endl; } else { cout<<"\t\t\t刪除失??！"<<endl; } } } getch(); } break; } } return1;}題二約瑟夫環(huán)問題算法、思想為了解決這一問題，可以先定義一個長度為30（人數(shù)）的數(shù)組作為線性存儲結構，并把該數(shù)組看成是一個首尾相接的環(huán)形結構，那么每次報m的人，就要在該數(shù)組的相應位置做一個刪除標記，該單元以后就不再作為計數(shù)單元。這樣做不僅算法較復雜，而且效率低，還要移動大量的元素。用單循環(huán)鏈表來解決這一問題，實現(xiàn)的方法相對要簡單得的多。首先定義鏈表結點，單循環(huán)鏈表的結點結構與一般單鏈表的結點結構完全相同，只是數(shù)據(jù)域用一個整數(shù)來表示位置；然后將它們組成一個具有n個結點的單循環(huán)鏈表。接下來從位置為1的結點開始數(shù)，數(shù)到第m個結點，就將此結點從循環(huán)鏈表中刪去，然后再從刪去結點的下一個結點開始數(shù)起，數(shù)到第m個結點，再將其刪去，如此進行下去，直至全部刪去為止。代碼分析創(chuàng)建單循環(huán)鏈表structLink{ intData; Link*next;};Link*Creat(intn){ Link*head,*s,*r; head=newLink; r=head; for(inti=0;i<n;i++) { s=newLink; cin>>s->Data; r->next=s; r=s; }r->next=head->next; returnhead;}“約瑟夫環(huán)”的操作模塊；Link*Jose(Link*p,intm){ ints=m; if(p==p->next) returnp;//遞歸出口即循環(huán)鏈表只剩下一個結點，將該結點指針返回 Link*q=NULL;//指針q用來保存刪除結點的前驅 for(intj=1;j<s;j++) { q=p; p=p->next; }//查找要刪除結點 q->next=p->next;//刪除節(jié)點 cout<<p->Data<<"";//輸出結點序號 Jose(p->next,s);//遞歸調用}主程序intmain(){ cout<<"請輸入Jose環(huán)中人數(shù)："; intn,m; cin>>n; cout<<"請輸入每個人手中的序號："<<endl; Link*head=Creat(n); cout<<"請輸入報數(shù)的數(shù)值"; cin>>m; Link*p=head->next; cout<<endl; cout<<"離開的序號依次是："; Link*Result=Jose(p,m); cout<<Result->Data<<endl; return0;}測試數(shù)據(jù)調試分析1、早期程序只寫了約瑟夫環(huán)的實現(xiàn)部分，沒有對輸入數(shù)據(jù)進行篩選，調試的時候會經常出錯。比如是輸入字母，或者輸入0，大于32767溢出；2、早期的循環(huán)過程中沒有進行優(yōu)化，導致循環(huán)次數(shù)過多，浪費時間；3、為了輸出時美觀，分別在input和main函數(shù)主體內做了兩次，輸入非零的判斷，浪費了資源；4、算法的時空分析為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數(shù)字，但是做的是do……whil