第一篇：南航計算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)上機(jī)實踐報告
數(shù)據(jù)結(jié)構(gòu)實踐報告整理 031040102 劉玉 ? 簡述每一部分的對象、目的和要求；
? 畫出程序流程圖；另附A4紙手繪； ? 附源程序清單； ? 實驗的收獲：遇到的問題以及解決的辦法、方法的優(yōu)缺點。
實驗一 單鏈表的基本操作與運算
題目一：單鏈表的定義、創(chuàng)建、插入和刪除操作，將數(shù)據(jù)元素顯示出來。
本題目針對單鏈表。聯(lián)表示通過一組任意的存儲單元來存儲線性表格中的數(shù)據(jù)元素。為了建立起數(shù)據(jù)元素之間的存儲關(guān)系，設(shè)置每一個結(jié)點，結(jié)點既存放數(shù)據(jù)data，又存放其后繼地址的部分next。而每個結(jié)點中只有一個指向后繼的指針，所以稱其為單鏈表。本題目的要求是創(chuàng)建一個新的鏈表，并且完成鏈表的創(chuàng)建定義。鏈表是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每一個結(jié)點所占用的空間是根據(jù)運行是的實際需要的空間生成的。因此建立單鏈表是從空鏈表開始的，每次讀入一個數(shù)據(jù)元素就申請一個結(jié)點鏈表的一段。在單鏈表中插入一個結(jié)點不需要移動元素指針的指向。而刪除則需要找到木比啊偶元素的前驅(qū)結(jié)點，并且修改指針的指向。題目一需要的操作就是，對于一個新建的空鏈表，以其為對象進(jìn)行具體的數(shù)據(jù)的插入填寫。待鏈表中存有數(shù)據(jù)后，再進(jìn)行數(shù)據(jù)的整理查找，然后刪除目標(biāo)數(shù)據(jù)。
//031040102單鏈表 #include
//定義一個鏈表 { int data;SLNODE *next;};void CREATE_SL(SLNODE *h)//創(chuàng)建一個單鏈表 { SLNODE *p,*s;int x;h->next=NULL;
cout<<“輸入以-1結(jié)尾的一組數(shù)”< cin>>x; //開始輸入數(shù)據(jù) while(x!=-1) { s=new SLNODE[sizeof(SLNODE)]; //申請一個動態(tài)新空間 s->data=x; if(h->next==NULL) h->next=s; else p->next=s; p=s; cin>>x; } p->next=NULL; //鏈表最后指向空 };int Insert_LinkList(SLNODE *h,int i,int x) //在單鏈表第i個位置插入x { SLNODE *p,*s;int j=0; p=h;while(p->next!=NULL&&j { p=p->next; j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;} else { s=new SLNODE[sizeof(SLNODE)]; s->data=x; s->next=p->next; p->next=s; return 1; } };int Del_LinkList(SLNODE *h,int i) //刪除單鏈表上第i個結(jié)點 { SLNODE *p,*s;int j=0;p=h;while(p->next!=NULL&&j p=p->next;j++; } if(j!=i-1){ cout<<“i is invalid!”< return 0;4 6 8 9 7 2 6 9 7 5-1 } 鏈表數(shù)據(jù)如下 else 4 6 8 9 7 2 6 9 7 5 { 輸入需插入的數(shù)據(jù)8 if(p->next==NULL)輸入需插入的結(jié)點3 { 插入成功 cout<<“第i個結(jié)點不存在鏈表數(shù)據(jù)如下 ”< return 0;輸入需刪除的結(jié)點 4 } 刪除成功 else 鏈表數(shù)據(jù)如下 {s=p->next;p->next=s->next; 7 2 6 9 7 */ //刪除結(jié)點 Deletes; //釋放結(jié)點空間 return 1; } } };void Print_LinkList(SLNODE *h)//輸出鏈表中所有元素 { SLNODE *p;p=h->next;cout<<“鏈表數(shù)據(jù)如下”< cout< data<<'t';} cout< data< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< 實驗一的收獲 實驗一讓我對于鏈表的創(chuàng)建于定義有了更多的接觸與認(rèn)識。之前的學(xué)習(xí)經(jīng)驗里主要是 扎實，VC++，涉及鏈表的內(nèi)容，我學(xué)的不夠所以這次在軟件基礎(chǔ)時間里重新再次 學(xué)習(xí)。題目一比較簡單，設(shè)僅是創(chuàng)建和插入以及刪除的基本操作。實驗一的困難較小，我也是比較順利參照課本，完成體題目一，也讓我對于進(jìn)一步學(xué)習(xí)鏈表有了興趣和動力。由淺入深，我會一點點開展學(xué)習(xí)。在圖書館借閱一本《數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實驗指 導(dǎo)》，里面對于實驗的指導(dǎo)比較全面而且有很多實例可以參考。 上機(jī)實踐二 題目二：棧、隊列的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義、創(chuàng)建、插入和刪除操作，將數(shù)據(jù)元素顯示出來。本題目要求掌握棧和列隊。棧和列隊是 兩種常見的數(shù)據(jù)結(jié)構(gòu)。它們的邏輯結(jié)構(gòu)和線性表相同。其特點是，插入和刪除等運算的位置有所限制：棧是按照先進(jìn)后出的規(guī)則進(jìn)行操作，而是按照先進(jìn)先出的規(guī)則進(jìn)行操作。堆棧技術(shù)現(xiàn)在的應(yīng)用非常廣泛，不管是編譯軟件還是程序設(shè)計，在操作系統(tǒng)和事務(wù)管理中則是廣泛應(yīng)用了隊列技術(shù)。棧是限制在一段進(jìn)行插入和刪除的線性表，允許插入刪除的這一端稱為棧頂，固定端稱為棧底。棧是運算受到限制的一種線 性表，采用順序存儲的是順序棧，采用鏈?zhǔn)酱鎯Φ氖擎湕！ｎ}目要求對于兩種存儲結(jié)構(gòu) 的棧進(jìn)行定義創(chuàng)建。對于順序棧，首先需要申請共享的一位數(shù)組空間。即為先置空棧，然后入棧插入元素（特別要注意棧滿不能插入），刪除出棧（特別要注意?？詹荒艹鰲＃?。對于鏈棧，采用帶頭指針的單鏈表來實現(xiàn).隊列操作的順序隊列，插入在表的隊尾一端，刪除在表的另外的隊頭一端。隊的隊頭和隊尾都是活動的，特別地需要設(shè)置隊頭和隊尾兩個指針。需要實現(xiàn)置空隊、入隊、出對、以及判別隊列是否為空的運算。對于鏈?zhǔn)疥犃?，通常是用帶頭結(jié)點的單鏈表實現(xiàn)的，并且設(shè)置一個隊頭指針（始終指向頭結(jié)點）和一個隊尾指針（指向當(dāng)前的最后一個元素），特別地，當(dāng)隊列為空時隊頭和隊尾指針均指向頭結(jié)點。顯示創(chuàng)建一個帶頭結(jié)點的空隊，申請頭尾結(jié)點，然后進(jìn)行如對操作不斷申請新的結(jié)點，還需要進(jìn)行隊列是否為空的判斷操作，隊空則出隊失敗。 //031040102 順序棧 #include return 1;else return 0;};int Push_SeqStack(SqStack *s,ElemType x)//入棧 { if(s->top==MaxSize-1) return 0;else { s->top++; s->data[s->top]=x; return 1; } };int Pop_SeqStack(SqStack *s,ElemType x) //出棧 { if(IsEmpty_SeqStack(s)) return 0;else { x=s->data[s->top]; s->top--; return 1; } }; ElemType Top_SeqStack(SqStack *s) //取出棧頂元素 { if(IsEmpty_SeqStack(s)) return 0; else return(s->data[s->top]); };void Print(SqStack *s) //輸出棧內(nèi)所有元素 { if(IsEmpty_SeqStack(s)) cout<<“ 此棧為空 ”< cout<<“棧內(nèi)元素為”< for(int i=s->top;i>-1;i--) cout< } };void main(){ SqStack *s;int x; s=Init_SeqStack();cout<<“ 輸入一組以-1結(jié)尾的數(shù)”< s->top++; s->data[s->top]=x; cin>>x;} Print(s);cout<<“輸入需插入的數(shù)”< cout<<“插入成功”< cout<<“插入失敗”< Print(s); delete p;if(Pop_SeqStack(s,x)) return top; cout<<“刪除成功”< cout<<“刪除失敗”< Print(s);} 輸入一組以-1結(jié)尾的數(shù) 5 8 9 7 3 6 2 1 8-1 棧內(nèi)元素為 8 1 2 6 3 7 9 8 5 輸入需插入的數(shù)4 插入成功 棧內(nèi)元素為 4 8 1 2 6 3 7 9 8 5 刪除成功 棧內(nèi)元素為 8 1 2 6 3 7 9 8 5 //031040102 鏈棧 #include //定義一個鏈棧 { elemtype data;LinkStack *next;};LinkStack *Init_LinkStack()//鏈棧的初始化 { LinkStack *top;top=new LinkStack[sizeof(LinkStack)];top=NULL;return top;};LinkStack *Push_LinkStack(LinkStack *top,elemtype x) //數(shù)據(jù)入棧 { LinkStack *s;s=new LinkStack[sizeof(LinkStack)];s->data=x;s->next=top;top=s;return top;};LinkStack *Pop_LinkStack(LinkStack *top,elemtype x) //數(shù)據(jù)出棧 { LinkStack *p;if(top==NULL) return NULL;else { x=top->data; p=top; top=top->next;//輸出棧內(nèi)所有元素 { LinkStack *p;p=top;if(p==NULL) cout<<“此棧為空”< cout<<“棧內(nèi)元素為”< for(;p->next!=NULL;p=p->next) cout< data<<'t'; cout< data< s=new LinkStack[sizeof(LinkStack)]; s->data=x; s->next=top; top=s; cin>>x;} Print(top);cout<<“輸入需插入的數(shù)”< 輸入需插入的數(shù)15 棧內(nèi)元素為 15 65 23 1 6 3 4 8 9 7 棧內(nèi)元素為 65 23 1 6 3 4 8 9 7 //031040102 順序隊列 #include typedef struct queue //定義一個順序隊列 { ElemType data[MaxSize];int rear,front;}SeQueue;SeQueue*Init_Queue()//隊列的初始化 { SeQueue *sq;sq=new SeQueue[sizeof(SeQueue)];sq->front=sq->rear=-1;return sq;};int IsEmpty_Queue(SeQueue *sq)//判空隊列 { if(sq->rear==-1) return 1;else return 0;};int In_Queue(SeQueue *sq,ElemType x) //入隊 { if(sq->rear==MaxSize-1) return 0;else { sq->rear++; sq->data[sq->rear]=x; return 1;} };int Out_Queue(SeQueue*sq) //出隊 { if(IsEmpty_Queue(sq)) return 0;else { sq->front++; return(sq->data[sq->front]);} };int Front_Queue(SeQueue *sq)//讀隊頭元素 { if(IsEmpty_Queue(sq)) return 0;else { return(sq->data[sq->front+1]);} };void Print(SeQueue *sq)//輸出隊列所有元素 { if(IsEmpty_Queue(sq)) cout<<“此隊列為空”< cout<<“隊列內(nèi)元素為”< for(int i=sq->front+1;i<=sq->rear;i++) cout< cout< cin>>x;while(x!=-1){ sq->rear++; sq->data[sq->rear]=x; cin>>x;} Print(sq);cout<<“輸入需插入的數(shù)”< cout<<“插入成功”< cout<<“插入失敗”< cout<<“刪除成功”< cout<<“刪除失敗”< //定義鏈隊的結(jié)點類型 { ElemType data;QNODE *next;}; typedef struct linkqueue p=q->front->next; //封裝頭尾指針 if(IsEmpty_LQueue(q)){ cout<<“此棧為空”< cout<<“ 隊列內(nèi)元素為 ”< { for(;p->next!=q->rear->next;p=p->next)LinkQueue *q; cout< data<<'t';QNODE *p; cout< data< } //申請頭尾節(jié)點 p=new QNODE[sizeof(QNODE)];//申請鏈隊頭結(jié)點 p->next=NULL;q->front=q->rear=p;return q;};void In_LQueue(LinkQueue *q,ElemType x)//入隊操作 { QNODE *p;p=new QNODE[sizeof(QNODE)];//申請新結(jié)點 p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;};int IsEmpty_LQueue(LinkQueue *q)//判隊空 { if(q->front==q->rear) return 1;else return 0;};int Out_LQueue(LinkQueue *q,ElemType x)//出隊操作 { QNODE *p;if(IsEmpty_LQueue(q)) return 0;else { p=q->front->next; q->front->next=p->next; x=p->data; delete p; if(q->front->next==NULL) //一個元素時，出隊后隊空還要改隊尾指針 q->rear=q->front; return 1;} };void Print(LinkQueue *q){ QNODE *p;}; void main(){ LinkQueue *q;QNODE *s;int x; q=Init_LQueue();cout<<“輸入一組以-1結(jié)尾的數(shù)”< { s=new QNODE[sizeof(QNODE)]; s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; cin>>x; } Print(q);cout<<“輸入需插入的數(shù)”< cout<<“刪除成功”< else cout<<“刪除失敗”< 隊列內(nèi)元素為 8 9 4 5 3 2 1 實驗二的收獲 實驗二是全新的知識需要理解。在之前的學(xué)習(xí)經(jīng)歷中沒有接觸到棧和隊列。所以這 次是從概念開始學(xué)習(xí)的。在具體程序的學(xué)習(xí)應(yīng)用時候，我對于書上提到的，首先需要的是為棧申請共享空間，有了理解和認(rèn)識。特別地，在?？盏臅r候有s->top[0]==-1;s->top[1]==Maxsize。再有就是棧滿的時候不可以入棧操作，未滿的入棧操作則是先移動再賦入值。例如語句(兩句的順序不可以顛倒)s->top++;s->data[s->top]=x;由于棧的主要運算是在棧頂插入、刪除。因此我在鏈表的頭部作為棧頂，這樣方便了程序，而且不需要像單鏈表一樣為了運算方便附加一個頭結(jié)點。在聯(lián)系隊列的相關(guān)程序時候，我理解了，列隊單向空間無法利用，即為前面的已經(jīng)被指針制動過的空間不能釋放也無法利用。除此，隊列的操作里面。有可能出現(xiàn)“隊滿”“隊空”的條件相同，front==rear;需要具體區(qū)分。 上機(jī)實踐三 題目三：二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)定義、創(chuàng)建、先序和后序遍歷，并將結(jié)果序列輸出。 二叉樹是有限個元素的集合，該集合或者為空、或者由一個稱為根的元素以及兩個不相交的、被稱為左子樹右子樹的二叉樹組成。二叉樹的臉是存儲結(jié)構(gòu)是指，用鏈表來表示一顆二叉樹，即用鏈表來表示元素的邏輯關(guān)系。二叉樹的鏈表存儲的結(jié)點有三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來指向該節(jié)點的左子結(jié)點和右子結(jié)點的存儲地址。當(dāng)左子結(jié)點或者右子結(jié)點不存在的時候，相應(yīng)的指針值域為空。二叉樹的遍歷是指按照某種順序結(jié)構(gòu)訪問二叉樹的每個結(jié)點，使每個結(jié)點僅被訪問一次。限定先左后右，只有三種方式即為先序遍歷、中序遍歷、后序遍歷。遍歷其實是一個遞歸的過程，若二叉樹為空，則遍歷結(jié)束，不然就按照順序依次訪問根結(jié)點、左結(jié)點、右結(jié)點。 //031040102 二叉樹 #include //定義二叉樹結(jié)點 { elemtype data; BiTNode *lchild,*rchild;//兩結(jié)點指針 }BiTree; BiTree *Create()//二叉樹的創(chuàng)建,遞歸算法 { BiTree *bt;elemtype ch;cin>>ch;if(ch=='0'){ bt=NULL;} else { bt=new BiTNode[sizeof(BiTNode)]; bt->data=ch; bt->lchild=Create(); bt->rchild=Create();} return bt;}; void PreOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;cout< void PostOrder(BiTree *bt) //先序遍歷二叉樹，遞歸算法 { if(bt==NULL) return;PostOrder(bt->lchild);PostOrder(bt->rchild);cout< void main(){ BiTree *bt;cout<<“輸入所需字符（空結(jié)點以零代替）”< 輸入所需字符（空結(jié)點以零代替）frt0e000qj00m00 先序遍歷可得二叉樹元素為 f r t e q j m 后序遍歷可得二叉樹元素為 e t r j m q f 實驗三的收獲 二叉樹可以用計算機(jī)語言來讀取，通過遍歷可以恢復(fù)二叉樹。通過這次試驗更加深刻理解二叉樹。本體操作不斷調(diào)用函數(shù)，遞歸實現(xiàn)遍歷。實際需要的時候?qū)τ谝阎亩鏄涞拿總€結(jié)點逐一訪問。一次完整的便利科室的一個二叉樹的結(jié)點信息由非線性排列轉(zhuǎn)變?yōu)橐饬x上的線性排列。在二叉樹的鏈表中無法根據(jù)結(jié)點找到其父結(jié)點。不過，二叉樹的鏈表結(jié)構(gòu)靈巧簡便、操作方便。特別地還節(jié)省空間。對于一個龐大的工程型程序的話，空間與簡便十分重要。同樣的目的，同樣的結(jié)果，需要比較選擇，肯定是精巧簡單操作性強(qiáng)等等優(yōu)勢作為判斷取舍。 上機(jī)實踐四 題目四：查找：順序查找、二分查找 查找是許多程序中最為耗費時間的部分。因此需要方法提高運行的速度和效率。順序查找又稱為線性查找，也是最為基本的查找方法之一。具體實現(xiàn)為：從表的一端開始，依次將關(guān)鍵碼與給定的值比較，若找到查找成功，并且給出數(shù)據(jù)元素在表中的位置，若整個表查找完成仍未找到相同的關(guān)鍵碼，則查找失敗給出失敗信息。 二分法查找只適用于順序存儲的有序表。有序表即是表中數(shù)據(jù)元素按照關(guān)鍵碼的升序或者降序排列。去中間元素作為比較對象，若給定值與中間元素的關(guān)鍵碼相等，則為查找成功；若給定值小于中間元素的關(guān)鍵碼，則在中間元素的左半?yún)^(qū)繼續(xù)查找，若給定值大于中間元素的關(guān)鍵碼，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述的查找過程直到查找成功，或者所查找的區(qū)域，沒有該元素查找失敗。 //031040102順序查找 #include #define MaxSize 1024 typedef struct { KeyType key; //定義關(guān)鍵碼字段 ElemType elem;//定義其他字段 }elemtype; typedef struct //順序存儲結(jié)構(gòu)定義 { elemtype elem[MaxSize];//定義數(shù)組 int length; //表長度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int s_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { tbl->elem[0].key=kx; //存放檢測 for(int i=tbl->length;tbl->elem[i].key!=kx;i--); //從表尾向前查找 return i;}; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“請輸入所需查找數(shù)的關(guān)鍵碼字段：”< { flag=mid; cout<<“查找成功”< break; cout<<“所查找的數(shù)為//查找成功，元素位置設(shè)置到flag中 ”< } } } else return flag; cout<<“查找失敗”< //定義關(guān)鍵碼字段 ElemType elem; //定義其他字段 }elemtype;typedef struct //順序存儲結(jié)構(gòu)定義 { elemtype elem[MaxSize];//定義數(shù)組 int length; //表長度 }S_TBL;S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;};int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { int mid,flag=0,low=1,high=tbl->length;//1.設(shè)置初始區(qū)間 while(low<=high) //2.表空測試 { //非空，進(jìn)行比較測試 mid=(low+high)/2; //3.得到中間點 if(kx high=mid-1; //調(diào)整到左半?yún)^(qū) else if(kx>tbl->elem[mid].key) low=mid+1; //調(diào)整到右半?yún)^(qū) else { //返回該元素在表中的位置，或返回0 };void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數(shù)的關(guān)鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數(shù)為”< } else cout<<“查找失敗”< -1結(jié)尾的數(shù)(數(shù)據(jù)元素)33 22 11 55 99 77 88 66 44-1 輸入所需查找數(shù)的關(guān)鍵碼字段3 查找成功 所查找的數(shù)為33 實驗四的收獲 查找的程序?qū)ξ襾碚f不陌生。兩種基本方法的比較和應(yīng)用里，我留意了最大查找次 數(shù)的不同。順序查找的進(jìn)行，如果查找不成功那么會議共比較N+1次。當(dāng)數(shù)據(jù)量很大的時候，平均查找長度過大，當(dāng)然順序查找對于數(shù)據(jù)的存貯方式?jīng)]有任何的要求。折半查找會有一個平均查找長度以及查找的最大長度。 我比較傾向于這本查找，其查找的效率明顯會高于順序查找。特別地，我還留意到對于單鏈表結(jié)構(gòu)，無法進(jìn)行二分法的查找，因為全部的元素的定位只能從指針開始。對于線性列表只能采取順序查找的方式。 上機(jī)實踐五 題目五：排序(插入排序選擇排序冒泡排序)排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要的運算，其目的就是將一組數(shù)據(jù)按照規(guī)定的順序進(jìn)行排列。排序的目的是便于查詢和處理。插入排序的基本思想是每一步將一個待排序的元素，按照其關(guān)鍵字嗎的大小，插入到前面已經(jīng)排序號的一組元素的適當(dāng)?shù)奈恢蒙?，知道所有的元素都插入為止。一般地認(rèn)為插入排序是一個穩(wěn)定的排序方法。選擇排序，每次從當(dāng)前待排序的記錄中，通過依次地進(jìn)行關(guān)鍵字媽的比較從中選擇一個關(guān)鍵字最小的記錄，并且把它與當(dāng)前待排序的第一個記錄進(jìn)行交換。直接選擇排序是一個不穩(wěn)定的排序方法。冒泡排序是一種簡單的交換排序的方法。一次地比較相鄰兩個記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個記錄的次序相反（即位前一個記錄的關(guān)鍵字大雨后有一個記錄的關(guān)鍵字），進(jìn)行記錄的交換一直到?jīng)]有反序為止。極端情況下，冒泡排序會有最短與最長時間，整個隊列越是接近有序，則冒泡排序的進(jìn)行次數(shù)越少。 //031040102 插入排序 #include //定義關(guān)鍵碼字段 ElemType elem; //定義其他字段 }elemtype; typedef struct //順序存儲結(jié)構(gòu)定義 { elemtype elem[MaxSize]; //定義數(shù)組 int length; //表長度 }S_TBL; S_TBL *Init_S_TBL() //順序表的初始化 { S_TBL *s;s=new S_TBL[sizeof(S_TBL)];s->length=-1;return s;}; int Binary_search(S_TBL *tbl,KeyType kx)//在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素 { int mid,flag=0,low=1,high=tbl->length;//1.設(shè)置初始區(qū)間 while(low<=high) //2.表空測試 { //非空，進(jìn)行比較測試 mid=(low+high)/2; //3.得到中間點 if(kx high=mid-1; //調(diào)整到左半?yún)^(qū) else if(kx>tbl->elem[mid].key) low=mid+1; //調(diào)整到右半?yún)^(qū) else { flag=mid; break; //查找成功，元素位置設(shè)置到flag中 } } Return flag;//返回該元素在表中的位置，或返回0 }; void main(){ S_TBL *tbl;tbl=Init_S_TBL();int i,k;cout<<“輸入一組以-1結(jié)尾的數(shù)(關(guān)鍵碼字段)”< tbl->length++; i=tbl->length+1; tbl->elem[i].key=k; cin>>k;} i=1;cout<<“輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)”< while(k!=-1)};{ void Print(RecType R[],int n) tbl->elem[i].elem=k; i++; cin>>k;} cout<<“輸入所需查找數(shù)的關(guān)鍵碼字段”< cout<<“查找成功”< cout<<“所查找的數(shù)為”< cout<<“查找失敗”< k=i; for(j=i+1;j<=n;j++) if(R[j].key k=j; if(k!=i) { R[0]=R[k]; R[k]=R[i]; R[i]=R[0]; } } //輸出數(shù)組內(nèi)所有元素 { cout<<“關(guān)鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)：”< R[++n].otherinfo=x; cin>>x;} cout<<“ 排序前 ”< Print(R,n);SelectSort(R,n);cout<<“排序后”< 請輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)： 33 22 11 44 55 66 99 88 77-1 排序前 關(guān)鍵字段為： 6 9 7 4 1 5 6 8 3 所有元素為： 33 22 11 44 55 66 99 88 排序后 關(guān)鍵字段為： 1 3 4 5 6 6 7 8 9 所有元素為： 55 44 66 33 99 11 88 22 //031040102 冒泡排序 #include #define MaxSize 50 cin>>x;typedef struct RecType } //定義排序記錄的形式 cout<<“排序前：”< 請輸入一組以 -1結(jié)尾的數(shù)(關(guān)鍵碼字段)： //選擇排序函數(shù) { int i,j,flag;for(i=1;i flag=1; for(j=1;j<=n-i;j++) if(R[j+1].key { flag=0; R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } if(flag==1) return;} };void Print(RecType R[],int n)//輸出數(shù)組內(nèi)所有元素 { cout<<“關(guān)鍵字段為：”< cout< cout< R[++n].key=x; cin>>x;} n=0;cout<<“請輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)：”< R[++n].otherinfo=x;9 8 7 4 1 5 6-1 請輸入一組以-1結(jié)尾的數(shù)(數(shù)據(jù)元素)： 11 22 33 44 66 55 77 88-1 排序前： 關(guān)鍵字段為： 6 9 8 7 4 1 5 6 所有元素為： 11 22 33 44 66 55 77 88 排序后： 關(guān)鍵字段為： 1 4 5 6 6 7 8 9 所有元素為： 55 66 77 11 88 44 33 22 實驗五的收獲 三種不同的排序方式，都是之前C++ 學(xué)習(xí)時候的重點掌握內(nèi)容。 直接插入排序的算法很簡潔，也很容易實現(xiàn)。從空間看，它只需要一個元素的輔助，從實踐看該算法的主程序運行次數(shù)只比元素的個數(shù)少一。當(dāng)然由于原列表的排序狀況未知，其總比較次數(shù)和總的移動次數(shù)也是未定的，取平均數(shù)約為0.25N^2。對于直接選擇排序，比較次數(shù)與原表元素的排列順序無關(guān)，移動次數(shù)有關(guān)。根據(jù)冒泡排序的思想，待排序的記錄有序之 后，則在下一趟的排序時候不會再有記錄的交換位置，由此，我增加了一個標(biāo)記flag，來直觀表示每一次的排序是否需要發(fā)生交換，無交換則已經(jīng)完成可以結(jié)束冒泡。特別地冒泡排序需要增加一個附加的單元來實現(xiàn)元素的交換。在交換時需要留意免得出錯。 · 數(shù)據(jù)結(jié)構(gòu)實驗報告 課程 數(shù)據(jù)結(jié)構(gòu) _ 院 系 專業(yè)班級 實驗地點 姓 名 學(xué) 號 實驗時間 指導(dǎo)老師 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告1 一﹑實驗名稱： 實驗一——鏈表 二﹑實驗?zāi)康模?/p> 1.了解線性表的邏輯結(jié)構(gòu)特性； 2.熟悉鏈表的基本運算在順序存儲結(jié)構(gòu)上的實現(xiàn)，熟練掌握鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述方法； 3.掌握鏈表的基本操作（建表、插入、刪除等）4.掌握循環(huán)鏈表的概念，加深對鏈表的本質(zhì)的理解。5.掌握運用上機(jī)調(diào)試鏈表的基本方法 三﹑實驗內(nèi)容： （1）（2）（3）（4）創(chuàng)建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“請輸入一個鏈表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//輸出鏈表L的數(shù)據(jù)元素 LinkList p; } void LinkListLengh(LinkList &L){//計算鏈表L的數(shù)據(jù)元素個數(shù)。int i=0;p=L->next;if(L->next==NULL){ } cout<<“鏈表的數(shù)據(jù)元素為:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“鏈表沒有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“鏈表的數(shù)據(jù)元素個數(shù)為:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//刪除鏈表L的第I個數(shù)據(jù)元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“刪除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//銷毀鏈表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“鏈表已經(jīng)被銷毀!”< LinkList L; int i,j,x;cout<<“第一次數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗—鏈表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第幾個元素前插入:”;cin>>i;cout<<“輸入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“輸入刪除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“銷毀程序后為:”< DestroyLinkList(L);} 五﹑實驗結(jié)果 六﹑實驗心得體會： 鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動態(tài)地進(jìn)行存儲分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表中每一個元素稱為“結(jié)點”，每個結(jié)點都應(yīng)包括兩個部分：一為用戶需要用的實際數(shù)據(jù)，二為下一個結(jié)點的地址。 實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）編寫鏈表創(chuàng)建子函數(shù)void CreatLinkList(L,j)（2）編寫鏈表插入子函數(shù) int InsertLinkList(LinkList &L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList &L)（4）編寫鏈表刪除子函數(shù) int DeleteLinkList(LinkList &L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList &L)（6）編寫主函數(shù)Main()，通過功能菜單調(diào)用子函數(shù)（7）編譯調(diào)試程序 經(jīng)過多次的調(diào)試，修改，實驗結(jié)果終于正確了，在這個過程中，經(jīng)歷了不知道怎么進(jìn)行聲明區(qū)的編寫如包含文件，宏定義，函數(shù)聲明，全局變量聲明，結(jié)構(gòu)體等的定義等的結(jié)合，到學(xué)會了使用先把程序主要規(guī)劃為四個部分來寫就簡單多了，第一，定義；第二，寫所要調(diào)用的子函數(shù)；第三，寫主函數(shù)，調(diào)用子函數(shù)；第四就是程序的編譯與調(diào)試，修改。數(shù)據(jù)結(jié)構(gòu)實驗需要我們對每個程序的算法有深刻的理解，才能應(yīng)用到實際中去，因此我們需要在做實驗之前要熟悉實驗的內(nèi)容，且先把所要實驗的程序?qū)懗鰜?，在實驗中就可以查找錯誤并加以改正，這是一個成長的過程。 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告一﹑實驗名稱： 實驗二—隊列 二﹑實驗?zāi)康模?1.掌握隊列這種抽象數(shù)據(jù)類型的特點, 掌握棧與隊列在實際問題中的應(yīng)用和基本編程技巧,并能在相應(yīng)的問題中選用它;2.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別是隊滿和隊空的描述方法； 3．掌握棧與隊列的數(shù)據(jù)類型描述及特點； 4.掌握棧的順序和鏈?zhǔn)酱鎯Υ姹硎九c基本算法的實現(xiàn)； 5.掌握隊列的鏈?zhǔn)酱鎯Ρ硎九c基本操作算法實現(xiàn);6.按照實驗題目要求，獨立完成實際程序的編寫編寫、調(diào)試和運行，并通過用例數(shù)據(jù)的運行過程抓獲相關(guān)屏面驗證程序設(shè)計的正確性； 7.認(rèn)真書寫實驗報告，并按時提交。 三﹑實驗內(nèi)容： 對順序循環(huán)隊列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對頭指針用于指示當(dāng)前的対頭位置下標(biāo)。現(xiàn)要求： （1）掌握棧和隊列的特點，即后進(jìn)先出和先進(jìn)先出的原則。（2）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空； （3）編寫主函數(shù)進(jìn)行測試。 四﹑實驗步驟與程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“該鏈隊為空:”);else printf(“該鏈隊不為空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入隊成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“隊首元素刪除成功”); } if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;printf(“隊首元素為:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“該鏈隊為空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“該隊列的長度為:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“該隊列的長度為:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************鏈隊列功能菜單***********************n”);printf(“1:初始化鏈隊列，2:判斷鏈隊列是否為空, 3:進(jìn)入隊列，4:取出隊首元素n”);printf(“5:輸出該隊列的所有元素,6:輸出該隊列的長度，7:結(jié)束程序，8:清屏n”); while(flag){ printf(“n請輸入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“請輸入隊列的長度:”);scanf(“%d”,&n);printf(“請輸入隊列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化鏈隊成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“請輸入要進(jìn)入隊列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“該隊列的元素為:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑實驗結(jié)果 六﹑實驗心得體會： 程序主要構(gòu)造了主函數(shù)main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等調(diào)用函數(shù)，實現(xiàn)了隊列的創(chuàng)立，隊列是否為空的判斷，入隊和出隊等功能。 通過此次實驗，加深了對隊列的存儲結(jié)構(gòu)的了解，同時也對程序設(shè)計能力有了提高，加深了對隊列先進(jìn)先出性質(zhì)的理解，它允許在表的一端進(jìn)行插入，在另一端刪除元素，這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌?，最早進(jìn)入隊列的元素最早離開。我們往往寫不出程序，這其中的原因我覺得是對程序的結(jié)構(gòu)不是很了解，對實驗的內(nèi)容也不熟練的結(jié)果，數(shù)據(jù)結(jié)構(gòu)給我們許多程序的算法和模型，對我們寫程序的思維有很大的鍛煉，我們應(yīng)珍惜每次上機(jī)實驗的機(jī)會去實踐課堂上所學(xué)的東西并從中發(fā)現(xiàn)問題，從而達(dá)到提升寫程序的能力。 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告一﹑實驗名稱： 實驗三—二叉樹的遍歷 二﹑實驗?zāi)康模?/p> 1、熟悉二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法； 2、掌握二叉樹的生成，掌握二叉樹的定義和存儲表示，學(xué)會建立一棵特定二叉樹的方法； 3、理解二叉樹的三種遍歷方法：先序遍歷、中序遍歷和后序遍歷； 4、學(xué)會編寫實現(xiàn)樹的各種操作的算法。 二、實驗內(nèi)容： 1、使用類定義實現(xiàn)二叉樹，補(bǔ)充完整所缺的函數(shù)，并實現(xiàn)創(chuàng)建和遍歷二叉樹的基本操作； 2、編程實現(xiàn)在二叉鏈表這種存儲方式下，實現(xiàn)二叉的遍歷，可采用遞歸或者非遞歸實現(xiàn)，遍歷算法為在先序、中序和后序遍歷算法。 三、實驗步驟與程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函數(shù) { printf(“------------二叉樹的遍歷-------------n”);printf(“請輸入要遍歷的數(shù)：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍歷:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍歷:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍歷:”);printf(“n”);PostOrder(Ta);} 五﹑實驗結(jié)果 六﹑實驗心得體會： 實驗的程序設(shè)計規(guī)劃（實現(xiàn)的功能、分幾個模塊、子函數(shù)）（1）先序遍歷遞歸算法函數(shù)：void PreOrder(BiTree T)（2）中序遍歷遞歸算法函數(shù)：void InOrder(BiTree T)（3）后續(xù)遍歷遞歸算法函數(shù)：void PostOrder(BiTree T)（4）主函數(shù)的實現(xiàn)：void main() 在實驗前我認(rèn)真閱讀關(guān)于二叉樹的實現(xiàn)的內(nèi)容，為編程實現(xiàn)第一步，本次實驗通過按上述的實驗步驟一步步實現(xiàn)的，實驗過程中出現(xiàn)了一些錯誤，經(jīng)過一步步的調(diào)試，修改錯誤，得到了二叉樹的遍歷用遞歸運算的方法的程序。通過這個實驗，我體會到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復(fù)雜，這使我更進(jìn)一步理解了函數(shù)遞歸調(diào)用并得到靈活運用；在實現(xiàn)算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。 總之，不管做什么實驗，我們在做實驗前都要先預(yù)習(xí)，對所做的實驗有較深的理解，在做實驗的時候需要很嚴(yán)謹(jǐn)，仔細(xì)的查找錯誤，從而能在實驗中收獲知識，提升自己。 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告4 一﹑實驗名稱： 實驗四—查找 二﹑實驗?zāi)康模?/p> 1、熟悉掌握順序表的查找方法； 2、熟練掌握二叉排序樹的構(gòu)造方法和查找算法 3、掌握描述查找過程的判定樹的構(gòu)造方法，以及按照定義計算各種查找方法在等概率情況下查找成功時的平均查找長度； 4、學(xué)會定義線性表的儲存類型，實現(xiàn)C++程序的基本結(jié)構(gòu)對線性表的一些基本操作和具體的函數(shù)定義； 5、掌握順序表的基本操作，實現(xiàn)順序表的查找的等基本運算； 6、掌握對于多函數(shù)程序的輸入，編輯，調(diào)試和運算過程。 二、實驗內(nèi)容： 1、實現(xiàn)順序表的查找算法 2、關(guān)于衡量查找的主要操作—查找的查找平均效率的平均長度的討論。 三、實驗步驟與程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------數(shù)據(jù)結(jié)構(gòu)查找實驗-------------n”);printf(“請輸入數(shù)據(jù)元素的個數(shù)：”);scanf(“%d”,&num);printf(“請輸入數(shù)據(jù)的元素：n”);for(i=0;i printf(“請輸入要查詢的數(shù)據(jù)元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查詢元素的下標(biāo)為：”);printf(“%dn”,k);} else printf(“查詢元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑實驗心得體會： 實驗的程序設(shè)計規(guī)劃為先寫一個主函數(shù)int main()，再寫一個查找的子函數(shù)int seqsearch(element list[],int searchnum,int num)，主函數(shù)通過調(diào)用子函數(shù)的方法實現(xiàn)程序的設(shè)計。 所謂“查找”即為在一個眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄），通過本次實驗，我更進(jìn)一步的了解數(shù)據(jù)結(jié)構(gòu)程序?qū)嶒炘O(shè)計實現(xiàn)算法的基本模型，和算法實現(xiàn)等基本內(nèi)容，學(xué)會了順序表的查找方法。 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告5 一﹑實驗名稱： 實驗五—內(nèi)部排序 二﹑實驗?zāi)康模?/p> 1、通過實現(xiàn)下述實驗內(nèi)容，學(xué)習(xí)、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應(yīng)用。 2、掌握各種排序時間復(fù)雜度的分析方法。 二、實驗內(nèi)容： 1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。 2、快速排序：首先選擇一個基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對兩部分重復(fù)上述過程，直至整個序列排序完成。 3、討論各種內(nèi)部排序方法的基本思路，算法特點，排序過程及它們的時間復(fù)雜度的分析。 三、實驗步驟與程序： #include } int x;void charu();void kuaisu();printf(“----------內(nèi)部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、選擇排序：n”);printf(“請根據(jù)序號選擇：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“請輸入個您想排序的數(shù)據(jù):n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“請輸入個您想排序的數(shù)據(jù):n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑實驗結(jié)果： 六﹑實驗心得體會： 排序的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，從新排成按關(guān)鍵字有序的序列；直接插入排序的穩(wěn)定性比快速排序高，且算法較簡單。本次實驗運用到的是插入排序和快速排序。 實習(xí)報告 題 目 : 實現(xiàn)一個約瑟夫環(huán)程序 班級：031021姓名：王帥學(xué)號：03102076 一、需求分析 1． 本演示程序中，利用單向循環(huán)鏈表存儲結(jié)構(gòu)存儲約瑟夫環(huán)數(shù)據(jù)（即n個人的編號和密碼）。 2． 演示程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運算結(jié)果顯示在其后。 3． 程序執(zhí)行的命令包括： 1)構(gòu)造單向循環(huán)鏈表；2）進(jìn)行數(shù)值的輸入，并作判斷分析；3）約瑟夫算法的實現(xiàn)與結(jié)果輸出；4）結(jié)束。 4． 測試數(shù)據(jù) m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序為6，1，4，7，2，1，3，5）。 二、概要設(shè)計 1．單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為： ADT List｛ 數(shù)據(jù)對象：D=｛ai | ai?正整數(shù)，I=1，2，......，n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛< ai-1，ai > |，ai-1，ai?D,I=1，2，......，n｝基本操作： Init List(&L) 操作結(jié)果：構(gòu)造一個空的線性表L。 List Insert(&L,i,e) 初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L長度加1。List Delete(&L,i,&e) 初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個元素，并用e返回其值，L長度減1。 2． 程序包含四個模塊： 1）主程序模塊： void main() { 初始化； for（;;） {} while（命令=開始） { 接受命令； 處理命令； } for（;;） { } } 2）有序表單元模塊——實現(xiàn)有序表的抽象數(shù)據(jù)類型； 3）節(jié)點結(jié)構(gòu)單元模塊——定義有序表的節(jié)點結(jié)構(gòu)； 4）數(shù)據(jù)輸入分析模塊——判斷輸入數(shù)據(jù)正確有效； 各模塊之間的調(diào)用關(guān)系如下： 主程序模塊 ↓ 有序表結(jié)構(gòu)模塊 ↓ 節(jié)點結(jié)構(gòu)單元模塊 ↓ 數(shù)據(jù)輸入分析模塊 三、詳細(xì)設(shè)計 1、結(jié)點類型，指針類型 TypedefstructLNode{ int code,date;//code 為人所在位置 date為人持有的密碼 struct LNode *next; };// 結(jié)點類型，指針類型 2、構(gòu)造單向循環(huán)鏈表 struct LNode *p,*head,*q;//定義頭節(jié)點，和指針 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新結(jié)點空間 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根據(jù)輸入的人數(shù)，進(jìn)行單項循環(huán)鏈表的創(chuàng)建，p指向最后一個結(jié)點，并與頭節(jié)點鏈接，形成單項循環(huán)鏈表 3、約瑟夫環(huán)的程序?qū)崿F(xiàn)部分 while(n!=1)//判斷輸入人數(shù)，如為1則直接輸出結(jié)果，不循環(huán) { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要刪除節(jié)點 p->next=q->next;//找到要刪除節(jié)點的后繼，并連接新環(huán)m=q->date;//找到下一個密碼 printf(“%d”,q->code); free(q);//釋放已刪除節(jié)點空間 n--;//鏈表長度減一 } printf(“%d”,p->code);//約瑟夫環(huán)的結(jié)果輸出 4、其他函數(shù)代碼 數(shù)值的輸入限制 int input() { int y,k,z=0; char c;//元素類型 char a[4];//數(shù)組初始化 if(!z)//輸入判斷，確定位數(shù)字或控制字符且位置和密碼不為零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//確定為輸入數(shù)字 {a[y]=c; putch(c); } else { y--; if(c=='r')//確定輸入為控制字符 即回車或者刪除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//確定最終輸入數(shù)字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 輸入為零，重新輸入 } return(k);//數(shù)值的返回 5、函數(shù)的調(diào)用關(guān)系圖反映程序?qū)哟谓Y(jié)構(gòu) Main→input 四、調(diào)試分析 1、早期程序只寫了約瑟夫環(huán)的實現(xiàn)部分，沒有對輸入數(shù)據(jù)進(jìn)行篩選，調(diào)試的時候會經(jīng)常出錯。比如是輸入字母，或者輸入0，大于32767溢出； 2、早期的循環(huán)過程中沒有進(jìn)行優(yōu)化，導(dǎo)致循環(huán)次數(shù)過多，浪費時間； 3、為了輸出時美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費了資源； 4、算法的時空分析 為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數(shù)字，但是做的是do……while循環(huán)，復(fù)雜度為o（1）; 當(dāng)n大于1時： 在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時間復(fù)雜度為o（n-1） 在約瑟夫環(huán)實現(xiàn)程序中，為for循環(huán)。時間復(fù)雜度為o（m%n-1） 當(dāng)n=1時，復(fù)雜度為o（1）。 五、用戶手冊 用戶根據(jù)提示，先輸入起始密碼m，然后輸入人數(shù)n，再根據(jù)人數(shù)，分別輸入每個人的密碼date，數(shù)值均不能為0，否則會提示重新輸入，輸入為字母則自動丟棄，輸入錯誤可用刪除鍵進(jìn)行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數(shù)字大于9999，則第五位自動轉(zhuǎn)換為下一個數(shù)字的起始位，依此類推）。 當(dāng)n個數(shù)字全部輸入完畢，則自動顯示結(jié)果，按任意鍵則退出本程序。 六、測試結(jié)果 第一組：m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，出列順序為6，1，4，7，2，1，3，5。 第二組： m 的初值為30；n=8，7個人的密碼依次為：5，1，6，9，4，7，2，3，出列順序為6，5，2，3，7，1，4，8。 第三組 : m 的初值為15；n=6，7個人的密碼依次為：5，3，4，7，6，9，出列順序為3，1，2，6，4，5。 七、附錄 源程序頭文件名清單： #include “malloc.h”//內(nèi)存空間分配頭文件 #include “stdio.h”//輸入輸出函數(shù)頭文件 #include “stdlib.h”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 #include “conio.h”//最后顯示結(jié)果、清屏函數(shù)頭文件 數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗六 實驗內(nèi)容:圖的基本操作 實驗要求: 1)圖的遍歷與基本操作要作為函數(shù)被調(diào)用.2)把自己使用的圖結(jié)構(gòu)明確的表達(dá)出來.3)基本上實現(xiàn)每個實驗題目的要求.分組要求：可單獨完成，也可兩人一組。 實驗?zāi)康? 1)熟悉C/C++基本編程,培養(yǎng)動手能力.2)通過實驗,加深對圖的理解.評分標(biāo)準(zhǔn)： 1)只完成第一和第二題，根據(jù)情況得4，5分； 2）完成前3題，根據(jù)情況得5至7分； 3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。 題目: 一)建立一個無向圖+遍歷+插入 (1)以數(shù)組表示法作為存儲結(jié)構(gòu)，從鍵盤依次輸入頂點數(shù)、弧數(shù)與各弧信息建立一個無向圖； (2)對（1）中生成的無向圖進(jìn)行廣度優(yōu)先遍歷并打印結(jié)果； (3)向（1）中生成的無向圖插入一條新弧并打印結(jié)果； 二)建立一個有向圖+遍歷+插入+刪除 (1)以鄰接表作為圖的存儲結(jié)構(gòu)，從鍵盤輸入圖的頂點與弧的信息建立一個有向圖； (2)對（1）中生成的有向圖進(jìn)行深度優(yōu)先遍歷并打印結(jié)果； (3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結(jié)果； (4)在（1）中生成的有向圖中，分別插入與刪除一個頂點并打印結(jié)果； (5)在（1）中生成的有向圖中,各頂點的入度與出度并打印結(jié)果； 三）基本應(yīng)用題 （1）編寫算法，判斷圖中指定的兩個頂點是否連通。 （2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個數(shù) （3）編寫算法，判斷圖中任意兩個頂點的連通性 （4）編寫算法，判斷圖中是否存在回路。 （5）實現(xiàn)圖的廣度優(yōu)先搜索算法。 四）高級應(yīng)用題 （1）實現(xiàn)Prim算法 （2）實現(xiàn)Kruskal算法 （3）實現(xiàn)迪杰斯特拉算法 （4）實現(xiàn)拓?fù)渑判蛩惴?/p> （5）實現(xiàn)關(guān)鍵路徑算法 實驗一 線性表 一、實驗題 線性表的應(yīng)用———多項式計算 二、程序設(shè)計思路 包括每個函數(shù)的功能說明，及一些重要函數(shù)的算法實現(xiàn)思路一鏈?zhǔn)酱鎯Γ?/p> 1.void InitPoly(LNode *&p)初始化多項式 2.void TraversePoly(LNode *&p)遍歷多項式 3.void ClearPoly(LNode *&p)清除多項式 4.void InsertPoly(LNode *&p, double a, int e)插入一項 5.void DeletetPoly(LNode *&p,int pos) 刪除一項 6.double PolySum(LNode *&p, double x) 多項式求值 7.LNode * PolyAdd(LNode *&p1,LNode *& p2) 多項式相加 順序存儲： 1.void InitPoly1(SeqList &L)初始化多項式 2.void ClearPoly1(SeqList &L)清除多項式 3.void TraversePoly1(SeqList L) 遍歷多項式 4.bool InsertPoly1(SeqList &L, ElemType item)插入一項 5.double PolySum1(SeqList L,double x) 多項式求值 6.bool DeleteList1(SeqList &L,int pos) 刪除一項 7.SeqList PolyAdd1(SeqList &L1,SeqList& L2) 多項式相加 三、源程序代碼 #include { if(pos>1||pos<-1)return false;NodeType *cp=p->next;NodeType *np=p;if(pos==0){ while(cp!=p){ if(cp->coef==a&&cp->exp==e)break;else{ np=cp;cp=cp->next;} } } else if(pos==-1)while(cp!=p){ 刪除np=cp;cp=cp->next;} np->next=cp->next;delete cp;return true;} double PolySum(NodeType *p, float x)//多項式求值 { int i;double sum=0,item;NodeType *cp=p->next;while(cp!=p){ item=1;for(i=1;i<=cp->exp;i++)item=item*x;sum=sum+item*cp->coef;cp=cp->next;} return sum;} NodeType *PolyAdd(NodeType *p1, NodeType *p2)//多項式相加 { float coef;NodeType *a=p1->next,*b=p2->next,*c,*pc;InitPoly(c);pc=c;while(a!=p1&&b!=p2){ if(a->exp==b->exp){ coef=a->coef+b->coef;if(coef!=0){ InsertPoly(pc, coef, a->exp);pc=pc->next;} a=a->next;b=b->next;} else if(a->exp 輸出多項式 } void ClearPoly1(ListType &p)//清除多項式 { if(p.list!=NULL){ delete []p.list;p.list=NULL;} p.size=0;} void InsertPoly1(ListType &p, float a, int e)//項 { p.list[e]=a;if(p.size { int i,n;if(p.size==0){ cout<<“多項式為空,刪除無效!”< 插入一if(p.list[e]==a)p.list[e]=0;else if(pos==-1)p.list[p.size]=0;return true;} double PolySum1(ListType p, float x)//值 { double sum=0,item;int i,j;for(i=0;i<=p.size;i++){ item=1;for(j=1;j<=i;j++)item=item*x;sum=sum+item*p.list[i];} return sum;} ListType PolyAdd1(ListType p1, ListType p2)//項式相加 { ListType p;InitPoly1(p);float coef; 多項式求多int i,j;for(i=0;i<=p1.size;i++){ coef=p1.list[i]+p2.list[i];InsertPoly1(p, coef, i);} if(i<=p1.size)for(j=i;j<=p1.size;j++)InsertPoly1(p, p1.list[j], j);if(i<=p2.size)for(j=i;j<=p2.size;j++)InsertPoly1(p, p2.list[j], j);return p;四實驗結(jié)果分析 五.心得體會 對于結(jié)構(gòu)體的認(rèn)識增加了，對于動態(tài)存儲也有了更多的認(rèn)識，也是在不知不覺中提高了。 實驗二 字符串的操作 一、實驗題目——字符串的操作 二、程序設(shè)計思路 采用定長順序存儲表示，由用戶創(chuàng)建串s和串t，實現(xiàn)在串s中下標(biāo)為pos的字符之前插入串t。 三、源程序代碼 #define MAXLEN 10 typedef struct { /*串結(jié)構(gòu)定義*/ char ch[MAXLEN]; int len;}SString;void createstring(SString *s) /*創(chuàng)建串s*/ { int i,j;char c;printf(“input the length of the string:”); scanf(“%d”,&j); for(i=0;i { printf(“input the %d:”,i+1); fflush(stdin); scanf(“%c”,&c); s->ch[i] = c; } s->len = j;} void output(SString *s) /*輸出串s*/ { int i;for(i=0;i printf(“%c ”,s->ch[i]); printf(“n”);} int StrInsert(SString *s, int pos, SString *t)/*在串s中下標(biāo)為pos的字符之前插入串t */ { int i;if(pos<0 || pos>s->len) /*插入位置不合法*/ return(0); if(s->len + t->len<=MAXLEN) /*插入后串長≤MAXLEN*/ { for(i=s->len + t->len-1;i>=t->len + pos;i--) s->ch[i]=s->ch[i-t->len];/*將下標(biāo)為pos的字符后的元素往后移動t->len個長度*/ for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標(biāo)為pos位置開始插入到串s*/ s->len=s->len+t->len;} else { if(pos+t->len<=MAXLEN)/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/ { for(i=MAXLEN-1;i>t->len+pos-1;i--) s->ch[i]=s->ch[i-t->len]; for(i=0;i s->ch[i+pos]=t->ch[i]; /*將串t從下標(biāo)為pos位置開始插入到串s*/ s->len=MAXLEN; } else /*插入后串長>MAXLEN,并且串t的部分字符也要舍棄*/ { for(i=0;i s->ch[i+pos]=t->ch[i]; /*直接從下標(biāo)為pos的位置按順序插入串t*/ s->len=MAXLEN; } return(1);} } void main(){ SString *str1;SString *str2;int i,j,k,pos;int flag=0;str1 =(SString *)malloc(sizeof(SString));str1->len = 0;printf(“creat the string 1:n”);createstring(str1);printf(“creat the string 2:n”);createstring(str2);printf(“input the insert local:”);scanf(“%d”,&pos);flag=StrInsert(str1,pos,str2);if(flag == 0) printf(“insert error!”);else { printf(“after insert:n”); output(str1);} } 四、實驗結(jié)果 五、實驗體會 通過本次實驗，我加深了對串?dāng)?shù)據(jù)結(jié)構(gòu)的理解。在串的定長順序存儲結(jié)構(gòu)中，按照預(yù)定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。在存儲方式中，結(jié)點大小的選擇和順序存儲方式的格式選擇一樣都很重要，它直接影響著串處理的效率。 實驗三 一、實驗題目——非遞歸算法對二叉樹進(jìn)行中前序遍歷 二、程序設(shè)計思路 創(chuàng)建一棵10個節(jié)點構(gòu)造的完全二叉樹，并對其進(jìn)行前、中、后序遍歷。 三、源程序代碼 #define STUDENT EType #define SType SType #define HeadEType int #include //定義數(shù)據(jù)結(jié)構(gòu)類型 struct STUDENT { char name[8];int age;char number[15];char address[20];}; struct BinaryTreeNode { EType data;BinaryTreeNode *LChild;BinaryTreeNode *RChild;};typedef BinaryTreeNode BinaryTree; typedef struct { BinaryTreeNode *ptr;bool status;}SType; typedef struct { SType *element;int top;int MaxSize;}Stack; void CreatStack(Stack &S, int MaxStackSize){// 構(gòu)造一個最大容量為MaxStackSize 的堆棧 S.MaxSize = MaxStackSize; S.element = new SType[S.MaxSize]; S.top =-1;} bool IsEmpty(Stack &S){// 判斷堆棧S是否為空 if(S.top ==-1) return true; return false;} bool IsFull(Stack &S){// 判斷堆棧S是否為空 if(S.top == MaxSize-1) return true; return false;} bool Push(Stack &S , SType &x){// x進(jìn)s棧，返回進(jìn)棧后的狀態(tài)值 if(IsFull(S)) return false; S.top++; S.element[S.top] = x; return true;} bool Pop(Stack &S , SType &x){// 將s棧頂?shù)闹等≈義中，返回出棧后的狀態(tài)值 if(IsEmpty(S)) return false; x = S.element[S.top]; S.top--; return true;} BinaryTreeNode *MakeNode(EType &x) {//構(gòu)造結(jié)點 BinaryTreeNode *ptr; ptr = new BinaryTreeNode; if(!ptr)return NULL; ptr->data = x; ptr-> LChild = NULL; ptr-> RChild = NULL; return ptr;} void MakeBinaryTree(BinaryTreeNode *root, BinaryTreeNode *left, BinaryTreeNode *right){// 聯(lián)接root，left, right所指的結(jié)點指針為二叉樹 root->LChild=left; root->RChild=right;} void PreOrderNoRecursive(BinaryTreeNode *BT){//二叉樹前序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧 while(q||!IsEmpty(S)){ if(q) { cout< ele.ptr=q; Push(S,ele);//節(jié)點指針進(jìn)棧，以后回溯時在退棧 q=q->LChild;//指針指向剛剛被訪問的“根”節(jié)點的左子樹 } else //當(dāng)左子樹為空時，利用堆棧回溯 if(!IsEmpty(S)) { Pop(S,ele);//退?；厮?/p> q=ele.ptr;//指針重新指向剛剛被訪問的“根”節(jié)點 q=q->RChild;//指針指向該回溯節(jié)點的右子樹 } } } void InOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的中序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧 while(q ||!IsEmpty(S)){ while(q)//找到最左邊的子樹 { ele.ptr=q; Push(S,ele);//指針非空時，將當(dāng)前的“根”節(jié)點指針進(jìn)棧，用于以后回溯 q=q->LChild;//指針繼續(xù)指向該“根”節(jié)點的左子樹 } if(!IsEmpty(S))//當(dāng)左子樹為空時，進(jìn)行退?；厮?/p> { Pop(S,ele);//從堆棧中回溯節(jié)點指針（節(jié)點還未訪問） q=ele.ptr; cout< q=q->RChild;//指針向回溯的節(jié)點右子樹推進(jìn) } } } void PostOrderNoRecursive(BinaryTreeNode *BT){//二叉樹的后序遍歷非遞歸的算法 Stack S;SType ele;BinaryTreeNode *q=BT;int MaxStackSize=50;//假設(shè)堆的空間足夠大，即MaxStackSize值足夠大 CreatStack(S,MaxStackSize);//產(chǎn)生一個空棧 while(q ||!IsEmpty(S)){ if(q)//找最左邊的子樹 { ele.ptr=q; ele.status=false;//進(jìn)棧前標(biāo)記為第一次進(jìn)棧 Push(S,ele); q=q->LChild;//指針繼續(xù)向左推進(jìn) } else if(!IsEmpty(S))//直到左子樹為空時，退?；厮?/p> { Pop(S,ele);//從堆棧中彈出回溯節(jié)點（還未訪問） q=ele.ptr;//q指向當(dāng)前回溯節(jié)點 if(ele.status)//判斷節(jié)點進(jìn)棧標(biāo)志，是否對其進(jìn)行訪問 { cout< q=NULL;//將q設(shè)為空，為了繼續(xù)退棧 } else { ele.status=true;//改變回溯節(jié)點的進(jìn)棧標(biāo)記，以便再次進(jìn)棧 Push(S,ele); q=q->RChild;//指針向該回溯節(jié)點的右孩子推進(jìn) } } } } //主函數(shù) void main(){ BinaryTreeNode *ptr[11]; char Name[][8]={“ ”,“A”,“B”,“C”,“D”,“E”,“F”,“G”,“H”,“I”,“J”};EType x[11];for(int i=1;i<11;i++){ strcpy(x[11-i].name,Name[11-i]); ptr[11-i]=MakeNode(x[11-i]);//構(gòu)造10個二叉樹節(jié)點 } //將節(jié)點鏈接域填值，構(gòu)造一個二叉樹 //這里構(gòu)造的是一棵有10個節(jié)點的完全二叉樹 for(int j=1;j<5;j++){ MakeBinaryTree(ptr[j],ptr[2*j],ptr[2*j+1]);} MakeBinaryTree(ptr[5],ptr[10],NULL);//該完全二叉樹構(gòu)造完畢 //***********對已構(gòu)造的完全二叉樹進(jìn)行前序非遞歸遍歷************// cout<<“對該二叉樹進(jìn)行前序遍歷結(jié)果：”< //***********對已構(gòu)造的完全二叉樹進(jìn)行中序非遞歸遍歷************// cout< //***********對已構(gòu)造的完全二叉樹進(jìn)行中序非遞歸遍歷************// cout< 四、實驗結(jié)果分析 五、實驗總結(jié) 二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就是遞歸定義，因此采用遞歸的方法去實現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現(xiàn)。在三種遍歷中，前序和中序遍歷的非遞歸算法都很容易實現(xiàn)，非遞歸后序遍歷實現(xiàn)起來相對來說要難一點。 實驗四 一、實驗題目——深度優(yōu)先算法實現(xiàn)圖的遍歷 二、程序設(shè)計思路 以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，以用戶指定的頂點為起始點，實現(xiàn)無向連通圖的深度優(yōu)先，并輸出遍歷的結(jié)點序列。首先，根據(jù)用戶輸入的頂點總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點為起始點，進(jìn)行深度優(yōu)先，并輸出遍歷的結(jié)果。 三、源程序代碼 #include };struct vexnode { char vertex;edgenode* edgelink;};struct Graph { vexnode adjlists[MaxVerNum];int vexnum;int arcnum;};//隊列的定義及相關(guān)函數(shù)的實現(xiàn) struct QueueNode { int nData;QueueNode* next;};struct QueueList { QueueNode* front;QueueNode* rear;};void EnQueue(QueueList* Q,int e){ QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q==NULL) return;if(Q->rear==NULL) Q->front=Q->rear=q;else { Q->rear->next=q; Q->rear=Q->rear->next;} } void DeQueue(QueueList* Q,int* e){ if(Q==NULL) return;if(Q->front==Q->rear){ *e=Q->front->nData; Q->front=Q->rear=NULL;} else { *e=Q->front->nData; Q->front=Q->front->next;} } //創(chuàng)建圖 void CreatAdjList(Graph* G){ int i,j,k;edgenode* p1;edgenode* p2;cout<<“請輸入頂點數(shù)和邊數(shù):”< cin>>G->adjlists[i].vertex; G->adjlists[i].edgelink=NULL;} cout<<“開始輸入邊表信息:”< cout<<“請輸入邊 cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlists[i].edgelink; G->adjlists[i].edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlists[j].edgelink; G->adjlists[j].edgelink=p2; //因為是無向圖，所以有兩次建立邊表的過程 } } //------------------------------深度優(yōu)先遍歷 void DFS(Graph *G,int i,int visit[]){ cout< DFS(G,p->endver,visit);} } void DFStraversal(Graph *G,char c)//深度優(yōu)先遍歷 { cout<<“該圖的深度優(yōu)先遍歷結(jié)果為:”< visit[i]=0;//全部初始化為0，即未訪問狀態(tài) } int m;for(i=0;i if(G->adjlists[i].vertex==c)//根據(jù)字符查找序號 { m=i; DFS(G,i,visit); break; } } //繼續(xù)訪問未被訪問的結(jié)點 for(i=0;i if(visit[i]==0) DFS(G,i,visit);} cout< int e=0; DeQueue(Q,&e); cout< visit[e]=1; edgenode* p=new edgenode; p=G->adjlists[e].edgelink; if(p) { int m=p->endver; if(m==0) { EnQueue(Q,m); while(visit[m]==0) { p=p->edgenext; if(p==NULL) break; m=p->endver; EnQueue(Q,m); } } } } } void BFStraversal(Graph *G,char c){ cout<<“該圖的廣度優(yōu)先遍歷結(jié)果為:”< visited[i]=0;} int m;for(i=0;i if(G->adjlists[i].vertex==c) { m=i; BFS(G,i,visited); break; } } //繼續(xù)訪問未被訪問的結(jié)點 for(i=0;i if(visited[i]==0) BFS(G,i,visited);} cout< 四、實驗結(jié)果及分析 五、實驗總結(jié) 本次試驗采用的是鄰接表的方式實現(xiàn)圖的深度優(yōu)先遍歷和。對于深度優(yōu)先遍歷，主要是采用遞歸的方式。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數(shù)據(jù)的輸入有問題，結(jié)果當(dāng)然也就不可能正確了。只有正確的輸入數(shù)據(jù)，建立圖，才能得出正確的遍歷結(jié)果。第二篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告
第三篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告
第四篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗--圖
第五篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)
點擊咨詢 