《算法與數據結構(實踐)》new

PAGEPAGE36遼寧省高等教育自學考試軟件技術（應用本科）專業(yè)課程設計報告書課程名稱算法與數據結構（實踐）助學單位信息技術學院姓名劉佳旭準考證號060111300227成績二Ｏ一一年四月實驗1順序表的應用實訓目的

1、掌握順序表的定義及操作的C語言實現方法2、掌握相關操作的基本思想及其算法。實驗要求1、線性表的基本概念和基本運算。2、順序表的存儲結構和查找、插入、刪除等基本運算。3、單鏈表的存儲結構以及單鏈表的建立、查找、插入刪除等操作。4、雙向鏈表的存儲結構以及插入、刪除操作。5、靜態(tài)鏈表的存儲結構和基本運算。6、利用線性表的基本運算解決復雜問題。實驗步聚1.創(chuàng)建和銷毀順序表存儲結構。創(chuàng)建一個順序表在順序表的指定位置插入一個元素；在順序表的指定位置刪除一個元素；將兩個有序順序表合并成一個新的有序順序表-Linearsequenceofstorage,saidtable(structure)andrealizethecreationofachronologicaltable(datafromtheproposed)intheorderoftableelementstoinsertaspecifiedlocationinorderoftableelementstodeleteaspecifiedlocationwillmergetwotablesinanorderlysequenceintoanewtableinanorderlysequence銷毀線性表voidDestroy_SeqList(PSeqListSeqListPoint){/*銷毀順序表，入口參數：為要銷毀的順序表指針地址，無返回值*/if(SeqListPoint)//SeqListPoint=NULL;return;}設調用函數為主函數，主函數對初始化函數和銷毀函數的調用如下：main(){PSeqListSeqListPoint;SeqListPoint=Init_SeqList();……Destroy_SeqList(SeqListPoint);}2.實現順序表的基本操作，如插入、刪除、查找和遍歷等。具體插入算法描述如下：

InsertList(SeqList*L,inti,DataTypex)

{//在順序表L中第i個位置之前插入一個新結點x

if(i<1||i>L->length+1)

{printf("positionerror");return;}

if(L->length>=ListSize)

{printf("overflow");return;}

for(j=L-length-1;j>=i-1;j--)

L->data[j+1]=L->data[j];

//從最后一個結點開始逐一后移

L->data[i-1]=x;//插入新結點x

L->length++;//實際表長加1

}從上述的算法以及插入過程圖中可以看出，一般情況下，在第i(1≤i≤n)個結點之前插入一個新結點時，需要進行n-i+1次移動。而該算法的執(zhí)行時間花在for循環(huán)的結點后移上，因此，該算法的時間復雜度不僅依賴于表的長度n，而且還與結點的插入位置i有關。當i=n+1時，for循環(huán)不執(zhí)行，無需移動結點，屬于最好情況，其時間復雜度為O(1)；當i=1，循環(huán)需要執(zhí)行n次，即需要移動表中所有結點，屬于最壞情況，算法時間復雜度為O(n)。由于插入結點可在表的任何位置上進行，因此需要分析討論算法的平均移動次數。

假設pi是在第i個結點之前插入一個結點概率，則在長度為n的線性表中插入一個結點時所需要移動結點次數的期望值(平均次數)為:不失一般性，我們假定在線性表的任何位置上插入結點的機會是相等的，即是等概率的，則有：

p1=p2=…=pn+1=1/(n+1)

因此，在等概率情況下插入需要移動結點的平均次數為：

恰好是表長的一半，當表長n較大時，該算法的效率是相當低的。因為Eis(n)是取決于問題規(guī)模n的，它是線性階的，因此算法的平均時間復雜度是O(n)。

例如，假定一個有序表A=(23,31,46,54,58,67,72,88)，表長n=8。當向其中插入56時，此時的i等于5，因此應插入到第i-1個位置上，從而需要將第i-1個元素及之后的所有元素都向后移動一位，將第i-1個元素位置空出來，插入新元素。插入后的有序表為(23,31,46,54,56,58,67,72,88)。按上述移動次數的計算公式，可知本插入操作需要移動n-i+1=8-5+1=4次。刪除結點運算的算法如下：

DataTypeDeleteList(SeqList*L,inti)

{//在順序表L中刪除第個結點，并返回刪除結點的值

if(i<1||i>L->length)

{printf("positionerror");

returnError;

}

x=L->data[i];//保存結點值

for(j=i;j<=L->length;j++)

L->data[j-1]=L->data[j];//結點前移

L->length--;//表長減1

returnx;

}該算法的時間復雜度分析與插入算法類似，刪除一個結點也需要移動結點，移動的次數取決于表長n和位置i。當i=1時，則前移n-1次，當i=n時不需要移動，因此算法的時間復雜度為O(n)；由于算法中刪除第i個結點是將從第i+1至第n個結點依次向前移動一個位置，共需要移動n-i個結點。同插入類似，假設在順序表上刪除任何位置上結點的機會相等，qi為刪除第i個結點的概率，則刪除一個結點的平均移動次數為：

由此可以看出，在順序表上做刪除運算，平均移動結點次數約為表長的一半，因此，該算法的平均時間復雜度為O(n)。7、順序表查找

順序表是指線性表的順序存儲結構。假定在本章的討論中，順序表采用一維數組來表示，其元素類型為NodeType，它含有關鍵字key域和其它數據域data，key域的類型假定用標識符KeyType(int)表示，具體表的類型定義如下：

typedefstruct{

KeyTypekey；

InfoTypedata；

}NodeType；

typedefNodeTypeSeqList[n+1]；

//0號單元用作哨兵

在順序表上的查找方法有多種，這里只介紹最常用的、最主要的兩種方法，即順序查找和二分查找。。

順序查找(SequentialSearch)又稱線性查找，它是一種最簡單和最基本的查找方法。其基本思想是：從表的一端開始，順序掃描線性表，依次把掃描到的記錄關鍵字與給定的值k相比較；若某個記錄的關鍵字等于k，則表明查找成功，返回該記錄所在的下標，若直到所有記錄都比較完，仍未找到關鍵字與k相等的記錄，則表明查找失敗，返回0值。因此，順序查找的算法描述如下：

intSeqSearch(SeqListR,KeyTypek,intn)

{//從順序表R中順序查找記錄關鍵字為k的記錄，

//查找成功返回其下標，否則返回0；R[0]作為哨兵，

//用R[0].key==k作為循環(huán)下界的終結條件。

R[0].key=k；//設置哨兵

i=n；//從后向前掃描

while(R[i].key!=k)

i--；

returni；//返回其下標,若找不到，返回0

}

由于這個算法省略了對下標越界的檢查，查找速度有了很大的提高，其哨兵也可設在高端，其算法留給讀者自己設計。盡管如此，順序查找的速度仍然是比較慢的，查找最多需要比較n+1次。若整個表R[1..n]已掃描完，還未找到與k相等的記錄，則循環(huán)必定終止于R[0].key==k，返回值為0，表示查找失敗，總共比較了n+1次；若循環(huán)終止于i>0,則說明查找成功，此時，若i=n，則比較次數Cn=1；若i=1，則比較次數C1=n；一般情況下Ci=n-i+1。因此，查找成功時平均查找長度為：

即順序查找成功時的平均查找長度約為表長的一半(假定查找某個記錄是等概率)。如果查找成功和不成功機會相等，那么順序查找的平均查找長度：

((n+1)/2+(n+1))/2=3(n+1)/4

順序查找的優(yōu)點是簡單的，且對表的結構無任何要求，無論是順序存儲還是鏈式存儲，無論是否有序，都同樣適用，缺點是效率低。順序表的簡單應用有序表的合并#include<iostream>usingnamespacestd;int*init(int*x,int&n){cout<<"輸入順序表的大小：";cin>>n;x=(int*)malloc(sizeof(int)*n);cout<<"輸入"<<n<<"個數據："<<endl;for(inti=0;i<n;i++)cin>>x[i];returnx;}int*hebing(int*a,int*b,intna,intnb){int*c=(int*)malloc(sizeof(int)*(na+nb));inti=0,j=0,k=0;while(i<na&&j<nb){if(a[i]<b[j]){c[k]=a[i];i++;}else{c[k]=b[j];j++;}k++;}if(i==na)while(j<nb)c[k++]=b[j++];elsewhile(i<na)c[k++]=a[i++];returnc;}intmain(){int*a,*b,*sum,na,nb;a=init(a,na);b=init(b,nb);sum=hebing(a,b,na,nb);for(inti=0;i<na+nb;i++)cout<<sum[i]<<"";cout<<endl;return0;}二分法檢索又稱折半檢索，二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組中，首先將給定值key與字典中間位置上元素的關鍵碼比較，如果相等，則檢索成功；否則，若key小，則在字典前半部分中繼續(xù)進行二分法檢索，若key大，則在字典后半部分中繼續(xù)進行二分法檢索。這樣，經過一次比較就縮小一半的檢索區(qū)間，如此進行下去，直到檢索成功或檢索失敗。二分法檢索是一種效率較高的檢索方法，要求字典在順序表中按關鍵碼排序。實驗2鏈表的應用實驗目的1、熟悉C語言的上機環(huán)境，掌握C語言的基本結構。

2、會定義線性表的鏈式存儲結構。

3、熟悉對鏈表的一些基本操作和具體的函數定義。

4、本章的主要任務是使用有關單鏈表的操作來實現通訊錄信息系統(tǒng)的管理。實驗要求1.創(chuàng)建和銷毀鏈表存儲結構。2.實現鏈表的基本操作，如插入、刪除、查找和遍歷等。3.鏈表的簡單應用，如約瑟夫環(huán)、集合求并、一元多項式相加等。實驗步驟1.創(chuàng)建和銷毀鏈表存儲結構。創(chuàng)建鏈表

一般將鏈表中的每個數據對象稱為節(jié)點（Node）。創(chuàng)建鏈表的基本步驟如下:

第一步，創(chuàng)建第一個節(jié)點，并將此節(jié)點的內存地址保存

第二步，創(chuàng)建第二個節(jié)點，將第二個節(jié)點的首地址保存在第一個節(jié)點的成員變量中。

第三步，以此類推，創(chuàng)建第n個節(jié)點，并將此節(jié)點的地址存儲到第n-1節(jié)點的成員變量中。銷毀一個鏈表在鏈表使用完畢后建議銷毀它，因為鏈表本身會占用內存空間。如果一個系統(tǒng)中使用很多的鏈表，而使用完畢后又不及時地銷毀它，那么這些垃圾空間積累過多，最終可能導致內存的泄漏甚至程序的崩潰。因此應當養(yǎng)成及時銷毀不用的鏈表的習慣。函數destroyLinkList()的作用是銷毀一個鏈表list，它包括以下步驟。（1）首先將*list的內容賦值給p，這樣p也指向鏈表的第一個結點，成為了鏈表的表頭。（2）然后判斷只要p不為空（NULL），就將p指向的下一個結點的指針（地址）賦值給q，并應用函數free()釋放掉p所指向的結點，p再指向下一個結點。如此循環(huán)，直到鏈表為空為止。（3）最后將*list的內容置為NULL，這樣主函數中的鏈表list就為空了，防止了list變?yōu)橐爸羔槨６益湵碓趦却嬷幸脖煌耆蒯尫诺袅恕?.實現鏈表的基本操作，如插入、刪除、查找和遍歷等。鏈表的插入

鏈表能夠方便地實現結點的插入和刪除操作，這也是鏈表結構具有動態(tài)分配存儲空間的體現，也是它優(yōu)于數組的地方之一。還是舉小朋友排隊的例子來說明鏈表的插入和刪除是怎樣實現的。在這個比喻里面，每一個小朋友相當于一個結點，一個小朋友的手拉著另一個小朋友的手，相當于一個結點的指針域指向下一個結點。假設現有一對按大小個排好隊的小朋友，又來一個小朋友需要加入該隊列。這時候，就需要從原來隊列里面的第一個小朋友開始，按照他們的身高找到新來小朋友應該站的位置（前一個小朋友的身高比他矮，后一個小朋友的身高比他高）。然后，把這兩個小朋友的手分開，讓前一個小朋友的手該拉著新來小朋友的一只手，新來小朋友的另一只手拉著后一個小朋友的一只手。這樣，新來的小朋友就被插入到這個隊伍里面了，并且這個隊伍的小朋友還是按照身高順序排列的。特別地，如果新來小朋友最矮，他只需要站在隊伍的開頭，并且讓他的一只手拉著原來站在對頭的小朋友的手就行了。實際鏈表的插入操作也就可以類似地實現。鏈表的刪除在鏈表中刪除一個節(jié)點，用圖7-4描述如下：[例7-6]創(chuàng)建一個學生學號及姓名的單鏈表，即節(jié)點包括學生學號、姓名及指向下一個節(jié)點的指針，鏈表按學生的學號排列。再從鍵盤輸入某一學生姓名，將其從鏈表中刪除。首先定義鏈表的結構：struct從圖7-4中看到，從鏈表中刪除一個節(jié)點有三種情況，即刪除鏈表頭節(jié)點、刪除鏈表的中間節(jié)點、刪除鏈表的尾節(jié)點。題目給出的是學生姓名，則應在鏈表中從頭到尾依此查找各節(jié)點，并與各節(jié)點的學生姓名比較，若相同，則查找成功，否則，找不到節(jié)點。由于刪除的節(jié)點可能在鏈表的頭，會對鏈表的頭指針造成丟失，所以定義刪除節(jié)點的函數的返回值定義為返回結構體類型的指針。鏈表的遍歷和查找

我們可以用與Length()函數類似的方法查找鏈表中的某一個結點。

//給定鏈表的頭指針和待查結點數據，返回查到的結點的指針

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL)

if(current->data==data)break;

elsecurrent=current->next;

returncurrent;

}

Find()函數的功能是：輸入鏈表頭結點head和待查結點數據data，如果某一個結點的數據與data相等，則返回該結點的指針；如果查完每一個結點也沒有找到數據與data相等的結點，則返回空指針。

需要注意的是：Find函數也可以寫成下面的形式。

//給定鏈表的頭指針和待查結點數據，返回查到的結點的指針

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL&¤t->data==data)

current=current->next;

returncurrent;

}

但把while的條件"current!=NULL&¤t->data==data"寫成"current->data==data&¤t!=NULL"的形式，則Find函數可能會出現運行錯誤。這是因為：如果鏈表的最后一個結點，仍然不是要找的結點，則到下一次循環(huán)時current為NULL，再進行條件判斷時，前者current!=NULL為真，而不再作current->data==data的判斷，循環(huán)便結束；而后者在作current->data==data判斷時就會導致程序崩潰。3.鏈表的簡單應用，如約瑟夫環(huán)、集合求并、一元多項式相加等。鏈表的約瑟夫環(huán)#include<iostream>usingnamespacestd;intmark[1005];//數組來做表,方便快速高效intcur;//表的main(){intn,m;//n個人,數到第m個出列scanf("%d%d",&n,&m);//輸入信息intcnt,on=n;cur=1;inti;while(on--)//出列n次{cnt=0;for(;cnt<m;++cur){if(cur==n+1)cur=1;if(mark[cur])continue;++cnt;}mark[cur-1]=1;//標記，出隊printf("%d\n",cur-1);}return0;}實驗3棧和隊列的應用實驗目的理解棧和隊列的工程原理，掌握棧和隊列在計算機程序設計中的應用。實驗要求1.創(chuàng)建和銷毀棧和隊列的存儲結構，要求達到“熟練掌握”層次。2.實現棧和隊列的基本操作，要求達到“熟練掌握”層次。3.棧和隊列的簡單應用，要求達到“基本掌握”層次。實驗步驟1.創(chuàng)建和銷毀棧和隊列的存儲結構。//*HeaderFile#ifndef__STACK_H__#define__STACK_H__structNode;typedefstructNode*PtrToNode;typedefPtrToNodeStack;intIsEmpty(StackS);StackCreateStack(void);voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(StackS);#endif////*ImplementationFile//節(jié)點結構structNode{ElementTypeElement;PtrToNodeNext;};////測試堆棧是否為空intIsEmpty(StackS){returnS->Next==NULL;}////創(chuàng)建一個空棧StackCreateStack(void){StackS;S=(Node*)malloc(sizeof(structNode));//分配一個節(jié)點的空間給棧Sif(S==NULL)exit(1);//分配失敗S->Next=NULL;MakeEmpty(S);returnS;}////將棧清空voidMakeEmpty(StackS){if(S==NULL)exit(1);else{while(!IsEmpty(S))Pop(S);}}////進棧PushvoidPush(ElementTypeX,StackS){PtrToNodeTmpCell;TmpCell=malloc(sizeof(structNode));if(TmpCell==NULL)exit(1);else{TmpCell->Element=X;TmpCell->Next=S->next;S->next=TmpCell;}}//實驗4樹和二叉樹的應用實驗目的（1）熟練掌握樹的基本概念、二叉樹的基本操作及在鏈式存儲結構上的實現；

（2）重點掌握二叉樹的生成、遍歷及求深度等算法；

（3）掌握二叉樹的線索化及線索二叉樹的遍歷算法；掌握赫夫曼樹的含義及其應用；

（4）掌握運用遞歸方式描述算法及編寫遞歸C程序的方法，提高算法分析和程序設計能力。實驗要求1.創(chuàng)建和銷毀二叉樹的存儲結構。2.實現二叉樹的基本操作，如查找和遍歷等。3.二叉樹的簡單應用，如線索二叉樹、哈夫曼樹和表達式樹等。4.樹轉化為二叉樹的存儲結構的創(chuàng)建和銷毀。5.樹與森林的遍歷算法。6.樹的簡單應用，如因特網查詢等。實驗步驟1.創(chuàng)建和銷毀二叉樹的存儲結構。二叉樹的存儲結構有多種，最常用的有兩種：是順序存儲結構和鏈表存儲結構。順序存儲結構二叉樹可以存放在一維數組之中，這是一種簡單的順序存儲結構。請看如下語句：constintMAXSIZE20

typedefcharElemType;

ElemTypebt[MAXSIZE];其中Bt就是一維數組（向量），用它來存儲一棵二叉樹，每個數組元素存儲樹的一個結點的數據信息。假設讓bt[0]閑置，讓bt[1]存放根結點信息。假設按照自上而下、自左至右的順序將圖6.4(a)的滿二叉樹存入一維數組bt，可以發(fā)現圖6.4(a)中結的編號恰好與數組元素的下標號相對應，詳見6.5圖。根據二叉樹性質5，在bt數組中可以方便地由某結點bt[i]的下標i，找到它的雙親結點bt[i/2]或者它的左、右孩子結點bt[2i]、bt[2i+1]。例如bt[2]結點值為B，它的雙親結點是bt[1]值為A，左孩子結點是bt[4]值為D，右孩子結點是bt[5]值為E。鏈式存儲結構用于二叉樹存儲的鏈表結構，常見的有二叉鏈表和三叉鏈表。二叉鏈表的每個結點有一個數據域和兩個指針域，一個指針指向左孩子，另一個指針指向右孩子。2.實現二叉樹的基本操作，如查找和遍歷等。二叉樹的一般操作，實現了下：主要練習了二叉樹的非遞歸遍歷，利用棧，和隊列來完成。代碼#include"stdio.h"#include"malloc.h"#define

MAXSIZE20//二叉樹結點的結構體表示形式typedefstructnode{char

data;structnode*left,*right;}BTree;//棧的結構體表示形式typedefstructstackelem{BTree*a[MAXSIZE];inttop;}Stack;//隊列的結構體的表示形式typedefstructqueueelem{BTree*b[MAXSIZE];intfront,rear;}Queue;//前序遍歷，遞歸的方法voidPreorder(BTree*bt){if(NULL!=bt){printf("%c",bt->data);Preorder(bt->left);Preorder(bt->right);}}3.二叉樹的簡單應用，如線索二叉樹、哈夫曼樹和表達式樹等。線索二叉樹：n個結點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前趨和后繼結點的指針（這種附加的指針稱為"線索"）。

這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded

BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。

線索鏈表解決了二叉鏈表找左、右孩子困難的問題，出現了無法直接找到該結點在某種遍歷序列中的前趨和后繼結點的問題。哈夫曼樹：哈夫曼樹（Huffman）又稱最優(yōu)二叉樹，是一類帶權路徑長度最短的樹，有著廣泛的應用。

在討論哈夫曼樹之前首先需要弄清楚關于路徑和路徑長度的概念。樹中兩個結點之間的路徑由一個結點到另一結點的分支構成。兩結點之間的路徑長度是路徑上分支的數目。樹的路徑長度是從根結點到每一個結點的路徑長度之和。4.樹轉化為二叉樹的存儲結構的創(chuàng)建和銷毀。完全二叉樹結點編號

在一棵n個結點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結點編號，能得到一個反映整個二叉樹結構的線性序列。完全二叉樹的順序存儲

將完全二叉樹中所有結點按編號順序依次存儲在一個向量bt[0..n]中。

其中：

bt[1．．n]用來存儲結點

bt[0]不用或用來存儲結點數目。一般二叉樹的順序存儲

①將一般二叉樹添上一些"虛結點"，成為"完全二叉樹"

②為了用結點在向量中的相對位置來表示結點之間的邏輯關系，按完全二叉樹形式給結點編號

③將結點按編號存入向量對應分量，其中"虛結點"用"∮"表示5.樹與森林的遍歷算法。前序遍歷樹

步驟：

(1)訪問根結點；

(2)按從左至右的次序前序遍歷根的各棵子樹。

前序遍歷樹和前序遍歷與該樹相對應的二叉樹具有相同的遍歷結果，即它們的前序遍歷是相同的。后序遍歷樹

步驟：

(1)按從左至右的次序后序遍歷根的各棵子樹；

(2)訪問根結點。

后序遍歷樹和中序遍歷與該樹相對應的二叉樹具有相同的遍歷結果。森林的遍歷前序遍歷森林

步驟：

(1)訪問森林中第一棵樹的根結點；

(2)前序遍歷森林中第一棵樹的根結點的各子樹；

(3)前序遍歷森林中除第一棵樹外其余各樹所構成的森林。

前序遍歷森林和前序遍歷與該森林相對應的二叉樹具有相同的遍歷結果。

后序遍歷森林

步驟：

(1)后序遍歷森林中第一棵樹的根結點的各子樹；

(2)訪問森林中第一棵樹的根結點；

(3)后序遍歷森林中除第一棵樹外其余各樹所構成的森林。

后序遍歷森林和中序遍歷與該樹相對應的二叉樹具有相同的遍歷結果。6.樹的簡單應用，如因特網查詢等。哈夫曼編碼(HuffmanEncoding)是最古老，以及最優(yōu)雅的數據壓縮方法之一。它是以最小冗余編碼為基礎的，即如果我們知道數據中的不同符號在數據中的出現頻率，我們就可以對它用一種占用空間最少的編碼方式進行編碼，這種方法是，對于最頻繁出現的符號制定最短長度的編碼，而對于較少出現的符號給較長長度的編碼。哈夫曼編碼可以對各種類型的數據進行壓縮，如應用在JPEG圖像的算法很多領域.

在這里我們采用一個文本文件來演示哈夫曼編碼的.為了說明問題,這個文本文件是高度簡化,這樣程序會變得相對簡單,比較好理解.

1.文件內容只會出現ASCII字符.即字符集里的字符總數不超過255.

2.用一串兩進制數比如10,110,1110,0來代表文件里字符.每個字符有一個獨立編碼.而且是一種特殊前綴的編碼,即任一個編碼都不是另外一個編碼的前綴.

3.統(tǒng)計文本文件中各個字符出現頻率,出現頻率最高的字符分配最短的號碼.

實驗5圖的應用實驗目的（1）掌握線性結構、樹形結構和圖形結構等基本數據結構及算法的應用；（2）掌握分治技術、貪心技術、回溯和分支限界等經典算法設計技術應用；（3）熟練掌握搜索算法和排序算法的應用；（4）具備應用算法與數據結構開發(fā)簡單應用軟件的能力。實驗要求（1）圖的鄰接表和鄰接矩陣存儲結構的創(chuàng)建和銷毀，要求達到“熟練掌握”層次。（2）實現圖的基本操作，要求達到“熟練掌握”層次。實驗步驟1.圖的鄰接表和鄰接矩陣存儲結構的創(chuàng)建和銷毀。2．實現圖的基本操作，如查找和遍歷等。3．圖的應用，如最小生成樹、單源最短路徑、拓撲排序等。（1）.圖的鄰接表和鄰接矩陣存儲結構的創(chuàng)建和銷毀。////////////////////////////////////////////////////////////////////圖是通過文件建立的//數據元素為char類型//存儲結構為鄰接表//文件中第一行為圖的類型//第二行為節(jié)點元素，以#結束//下邊每一行為邊，和邊的權值//下邊是文件的示例/*2ABCD#AB3AC4BC2CD4DA1##*///////////////////////////////////////////////////////////////////#include<iostream>#include<fstream>usingnamespacestd;constintMaxNum=20;constintInfinity=-1;typedefcharVexType;typedefintArcType;typedefstructQNode//定義隊列節(jié)點{intdata;QNode*next;}*LQueuePtr;structLQueue//定義隊列結構體LQueuePtrfront,rear;};oidQueueInit(LQueue&Q)//隊列初始化{Q.front=newQNode;Q.front->next=0;Q.rear=Q.front;}voidEnqueue(LQueue&Q,inte){LQueuePtrs;s=newQNode;s->data=e;s->next=0;Q.rear->next=s;Q.rear=s;}boolDequeue(LQueue&Q,int&e){LQueuePtrp;if(Q.front==Q.rear)returnfalse;p=Q.front;Q.front=p->next;e=Q.front->data;deletep;returntrue;}pedefstructArcNode//定義邊的結構體{intadjvex;ArcTypeinfo;ArcNode*nextarc;}*ArcPtr;structVexNode//定義節(jié)點的結構體{VexTypedata;ArcPtrfirstarc;};structALGraph//定義圖的結構體{VexNodevexs[MaxNum+1];intkind,vexnum,arcnum;};intLocateVex(ALGraph&G,VexTypev)//在圖中找到某一個元素{inti;for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);returni;}voidCreateGraph(ALGraph&G,charfn[])//創(chuàng)建圖{inti,j;VexTypeu,v;ArcPtrp;ifstreamf;ArcTypew;f.open(fn);//打開文件失敗if(!f){G.vexnum=0;return;}//讀入圖的種類f>>G.kind;//先設置邊數為0G.arcnum=0;i=0;while(true)//向節(jié)點數組中添加節(jié)點{f>>u;if('#'==u)break;i++;G.vexs[i].data=u;G.vexs[i].firstarc=0;}G.vexnum=i;while(true)//讀入各條邊{f>>u>>v;if('#'==u||'#'==v)break;i=LocateVex(G,u);if(0==i)continue;j=LocateVex(G,v);if(0==j||j==i)continue;if(1==G.kind||3==G.kind)w=1;elsef>>w;G.arcnum++;p=newArcNode;p->adjvex=j;p->info=w;p->nextarc=G.vexs[i].firstarc;G.vexs[i].firstarc=p;if(G.kind<=2)continue;p=newArcNode;p->adjvex=i;p->info=w;p->nextarc=G.vexs[j].firstarc;G.vexs[j].firstarc=p;}f.close();}voidOutputGraph(ALGraph&G)//輸出圖voidDFS(ALGraph&G,inti,boolvisited[],voidvisit(VexType))//圖的名稱，當前節(jié)點位置，標記數組，訪問函數{intj;ArcPtrp;//訪問當前節(jié)點visit(G.vexs[i].data);//修改標記值visited[i]=true;for(p=G.vexs[i].firstarc;p;p=p->nextarc){j=p->adjvex;if(!visited[j])//對下一個節(jié)點遞歸DFS(G,j,visited,visit);}}voidDFSTraverse(ALGraph&G,voidvisit(VexType)){inti;boolvisited[MaxNum+1];for(i=1;i<=G.vexnum;i++)//初始化標記數組{visited[i]=false;}for(i=1;i<=G.vexnum;i++){if(!visited[i]){DFS(G,i,visited,visit);}}}voidBFSTraverse(ALGraph&G,voidvisit(VexType)){//訪問節(jié)點visit(G.vexs[v].data);visited[v]=true;//將訪問的節(jié)點入隊Enqueue(q,v);while(Dequeue(q,u))//出隊并訪問{for(p=G.vexs[u].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w]){visit(G.vexs[w].data);visited[w]=true;Enqueue(q,w);}}}}}intmain(){ALGraphG;CreateGraph(G,"aaa.txt");cout<<"創(chuàng)建的圖為:";OutputGraph(G);cout<<"深度優(yōu)先遍歷："<<endl;DFSTraverse(G,visit);cout<<endl<<"廣度優(yōu)先遍歷"<<endl;BFSTraverse(G,visit);cout<<endl;return0;}2．實現圖的基本操作，如查找和遍歷等#include<stdio.h>#include<iostream.h>structgraph{chartnode;charhnode;doublequanzhi;}gr[100];charnode[50]="";doublegraphshu[50][50];intmini(intt,intn)printf("用普里姆算法得出的結果是:\n");printf("路徑為：");intt2=0;for(k=0;k<n-1;k++){intt1=mini(t2,n);sum=sum+graphshu[t2][t1];for(inti=0;i<n;i++)graphshu[i][t2]=30000;graphshu[t2][t1]=30000;for(i=0;i<n;i++)graphshu[t1][i]=minval(graphshu[t2][i],graphshu[t1][i]);printf("(%c,%c)",node[t2],node[t1]);t2=t1;}printf("\n最小生成樹的總耗費為:%f\n",sum);}voidKruscal(intk,intn)value=gr[0].quanzhi;for(i=1;i<k;i++)//tt為最小權的下標if(value>=gr[i].quanzhi){tt=i;value=gr[i].quanzhi;}///////for(i=0;i<n;i++){if(gr[tt].tnode==node[i])ii=i;if(gr[tt].hnode==node[i])jj=i;}if(nod[ii]==nod[jj]){gr[tt].quanzhi=30000;continue;}else{if(nod[ii]>=nod[jj]){for(i=0;i<n;i++)if(nod[i]==nod[ii])nod[i]=nod[jj];}else{for(i=0;i<n;i++)if(nod[i]==nod[jj])nod[i]=nod[ii];{cin>>gr[k].hnode;cin>>gr[k].quanzhi;}}intp,o=1;for(intj=0;j<k;j++)//n為頂點數{for(intt=0;t<o;t++)if(gr[j].tnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].tnode;n++;o++;}}for(j=0;j<k;j++){for(intt=0;t<o;t++)if(gr[j].hnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].hnode;n++;o++;}}for(inti=0;i<n;i++)for(intj=0;j<n;j++)graphshu[i][j]=30000;for(i=0;i<k;i++)//構造數組{for(intj=0;j<n;j++)if(gr[i].tnode==node[j]){ii=j;break;}for(j=0;j<n;j++)if(gr[i].hnode==node[j]){jj=j;break;}graphshu[ii][jj]=gr[i].quanzhi;}for(i=0;i<n;i++)for(intj=i;j<n;j++)graphshu[j][i]=graphshu[i][j];//prim(k,n);charoption;intx;for(x=1;x<=4;x++){cout<<"求給定網的最小生成樹"<<endl;cout<<"1.普里姆（Prim）算法"<<endl;cout<<"2.克魯斯卡爾（Kruskal）算法"<<endl;cout<<"3.退出"<<endl;cout<<"請選擇:";cin>>option;switch(option){case'1':Prim(n,k);break;case'2':Kruscal(n,k);break;case'3':return;}}}輸入文件：如果該數字序列不是度序列，只需在第一行輸出“No！”;如果該數字序列是一個度序列，首先在第一行輸出“Yes！”；然后在接下來的若干行里輸出一個符合該度序列的圖所有邊，每行一條邊。我們默認一個圖的頂點編號為1至T，如果頂點i與j之間有一條邊，我們表示為“ij”。例如圖一就可以表示為：13243435輸入樣例1：532111輸出樣例1：Yes!13243435輸入樣例2：No!說明：若連接結點之間的邊可以不止一條，這樣的圖稱為多重圖。一個結點如果有指向自己的邊，這條邊被稱為自環(huán)。無向簡單圖是指無自環(huán)的非多重圖。3．圖的應用，如最小生成樹、單源最短路徑、拓撲排序等/*已調試成功前半部分(yes/no)*/#include<stdio.h>#defineNMAX100intmain(){statica[NMAX][NMAX];inttop[NMAX];inttops,i,temp,s=0,s1=0;scanf("%d",&tops);if(tops>NMAX){fprintf(stderr,"toomanyvertax...\n");return-1;}for(i=0;i<tops;++i){scanf("%d",&temp);s+=top[i]=temp;if(temp%2)++s1;}if(s%2||s1%2){printf("No!\n");return1;}printf("Yes!\n");/*waiting...*/return0;}實驗6散列表的應用實驗目的(1)掌握散列查找的基本思想；(2)掌握閉散列表的構造方法；(3)掌握線性探測處理沖突的方法；(4)掌握散列技術的查找性能。實驗要求(1)了解散列表存儲結構的創(chuàng)建和銷毀。(2)了解實現散列表的基本操作，如插入、刪除和查找等。(3)解決散列沖突方法的應用，如開放地址法和鏈地址法等。實驗步驟散列表由固定數目的散列表元組成。散列表元或是空，或是包含有與某個關鍵字相關聯的數據。為了找到某個關鍵字值的數據，就要通過散列函數作用于關鍵字值來計算出散列表元數。對于某一個給定關鍵字的值，散列函數總是產生出相同的散列表元數。

沖突和重復

當散列表元的數目少于關鍵字值的數目時，兩個或者兩個以上的關鍵字值就有可能被散列到同一個散列表元上，這被稱作沖突。當發(fā)生沖突的時候，有兩種選擇，一種是擴展散列表元，使它可以含有多個表項；另一種是不能有多重散列表項。

后種方法不是一個好的解決方案，這使我們構造巨大的散列表以避免沖突。在大多數情況下，可以讓散列表元包含多個散列表項，而這些散列表項都是被散列到該散列表元的。

散列表元可以是一個包含簡單表項的鏈表，空的散列表元含有一個空的鏈表，散列表元的新表項被附加到該散列表元的表項鏈表的尾部。

FrankAn(WindSor,Ontario,Canada)寫了一個簡單的算法，代碼如下：#include<iostream>

#include<stdlib.h>usingnamespacestd;enumHashKeyType

{

KEY_STRING,

KEY_INT,

KEY_LONG,

KEY_USER1,

KEY_USER2,

KEY_USER3,

KEY_USER4

};//定義1

structHashEntryBase

{

HashEntryBase*Prev;

HashEntryBase*Next;

HashEntryBase();

virtualHashKeyTypeGetKeyType()const=0;

virtualsize_tHash(size_tbuckets)const=0;

virtualintKeyEquals(constHashEntryBase*entry)const=0;

};//定義2

structHashEntryInt:publicHashEntryBase

{

intKey;

HashEntryInt(constint&k);

HashEntryInt(constHashEntryInt&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryInt();

};

structHashEntryIntDB:publicHashEntryInt

{

intdata;

HashEntryIntDB(constint&k,constint&db):HashEntryInt(k)

{

data=db;

}

};

structHashEntryStr:publicHashEntryBase

{

stringKey;

HashEntryStr(conststring&k);

HashEntryStr(constHashEntryStr&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryStr();

};

structHashEntryStrDB:publicHashEntryStr

{

stringdata;

HashEntryStrDB(conststring&k,conststring&db):HashEntryStr(k)

{

data=db;

}

};//定義3

classHashBucker;//定義4

classHashTableBase

{

public:

HashTableBase(size_tbuckets);

~HashTableBase();

protected:

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

virtualboolTravCallback(constHashEntryBase*e)const=0;

boolTraverse();

size_tNoOfBuckets;

HashBucker**Table;

};typedefbool(HashTableBase::*HashTravFunc)(constHashEntryBase*e)const;//定義3

classHashBucker

{

public:

HashBucker();

~HashBucker();

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

boolTraverse(constHashTableBase&table,HashTravFuncfunc);

protected:

HashEntryBase*First;

};//定義5

typedefbool(*HashEnumFuncIntDB)(constint&k,constint&db);

classHashTableIntDB:privateHashTableBase

{

public:

HashTableIntDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(constint&key,constint&db);

boolDelete(constint&dele);

intLookUp(constint&key);

boolEnumerate(HashEnumFuncIntDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncIntDBEnumCallBack;

};typedefbool(*HashEnumFuncStrDB)(conststring&k,conststring&db);

classHashTableStrDB:privateHashTableBase

{

public:

HashTableStrDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(conststring&key,conststring&db);

boolDelete(conststring&dele);

stringLookUp(conststring&key);

boolEnumerate(HashEnumFuncStrDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncStrDBEnumCallBack;

};

//實現1

inlineHashEntryBase::HashEntryBase()

{

Prev=NULL;

Next=NULL;

}//實現2

inlineHashEntryInt::HashEntryInt()

{

}

inlineHashEntryInt::HashEntryInt(constint&k):Key(k)

{

}

inlineHashEntryInt::HashEntryInt(constHashEntryInt&e):Key(e.Key)

{

}

HashKeyTypeHashEntryInt::GetKeyType()const

{

returnKEY_INT;

}

intHashEntryInt::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_INT!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryInt*)entry)->Key);

}

size_tHashEntryInt::Hash(size_tbuckets)const

{

returnsize_t(Key%(unsignedlong)buckets);

}

inlineHashEntryStr::HashEntryStr()

{

}

inlineHashEntryStr::HashEntryStr(conststring&k):Key(k)

{

}

inlineHashEntryStr::HashEntryStr(constHashEntryStr&e):Key(e.Key)

{

}

HashKeyTypeHashEntryStr::GetKeyType()const

{

returnKEY_STRING;

}

intHashEntryStr::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_STRING!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryStr*)entry)->Key);

}

size_tHashEntryStr::Hash(size_tbuckets)const

實驗7排序的應用實驗目的（1）掌握查找的不同方法，并能用高級語言實現查找算法。（2）熟練掌握順序表和有序表的順序查找和二分查找方法。（3）掌握排序的不同方法，并能用高級語言實現排序算法。（4）熟練掌握順序表的選擇排序、冒泡排序和直接插入排序算法的實現實驗要求(1）深化理解書本上的理論知識，將書本的知識變“活”（為已掌握，為已活用）；(2）理論和實踐相結合，學會將相關的數據結構和算法應用于解決實際問題，培養(yǎng)數據結構的應用能力和軟件工程所需要的實踐能力。實驗步驟輸入：一個包含n個正整數的文件，每個正整數小于n,n等于10的7次方（一千萬）。并且文件內的正整數沒有重復和關聯數據。

輸出:

輸入整數的升序排列

約束：限制在1M左右內存，充足的磁盤空間假設整數占32位，1M內存可以存儲大概250000個整數，第一個方法就是采用基于磁盤的合并排序算法，第二個辦法就是將0-9999999切割成40個區(qū)間，分40次掃描（10000000/250000)，每次讀入250000個在一個區(qū)間的整數，并在內存中使用快速排序。書中提出的第三個解決辦法是采用bitmap（或者稱為bitvector）來表示所有數據集合（注意到條件，數據沒有重復），這樣就可以一次性將數據讀入內存，減少了掃描次數。算法的偽代碼如下：

階段1：初始化一個空集合

fori=[0,n)

bit[i]=0;

階段2：讀入數據i，并設置bit[i]=1

foreachiintheinputfile

bit[i]=1;

階段3：輸出排序的結果

fori=[0,n)

ifbit[i]==1

writeiontheoutputfile算法的時間復雜度為O(N)

#include<stdio.h>

#defineWORD32

#defineSHIFT5

#defineMASK0x1F

#defineN10000000

intbitmap[1+N/WORD];

/*

*置位函數——用"|"操作符,i&MASK相當于mod操作

*mmodn運算，當n=2的X次冪的時候,mmodn=m&(n-1)

*/

void

set(inti)

{

bitmap[i>>SHIFT]|=(1<<(i&MASK));

}

/*清除位操作，用&~操作符*/

void

clear(inti)

{

bitmap[i>>SHIFT]&=~(1<<(i&MASK));

}

/*測試位操作用&操作符*/

int

test(inti)

{

returnbitmap[i>>SHIFT]&(1<<(i&MASK));

}

intmain()

{

inti=0;

printf("beforesort:\n");

while(scanf("%d",&i)!=EOF){

set(i);

}

printf("aftersort:\n");

for(i=0;i<N;i++){

if(test(i)){

printf("%d\n",i);

}

}

return0;

}======================基于位圖的整數序列合并算法=====================================搜索引擎檢索時，常常要將兩個結果進行組合處理，例如查詢“中國北京”，則需要將包含“中國”和“北京”的文檔編號序列進行合并的操作。常用的算法有歸并，先排序后去重等，但這些算法在大數據量的情況下，如對包含“中國”的10萬個文檔編號序列和包含“北京”的8萬個文檔編號序列進行組合時，效率比較低，無法滿足搜索引擎高速的檢索要求。我們引入了基于二進制數組的算法來解決這個問題。

基于二進制數組的整數序列合并算法是一種高速的多個整數序列組合的算法。它的基本原理是將各整數序列保存在一個二進制的數組當中，然后對這些二進制數組進行并，或的運算。

下面詳細介紹一下此算法的處理過程。

1．將整數序列轉為二進制數組。

先申請一個二進制數組，其大小為有可能出現的最大的整數值，如500萬，如圖所示。（圖1）

假設有5個整數組成的序列{2,3,200,7000,12000}，則我們可以將這個序列保存在二進制數組當中，如圖2所示，第n位如果為1，則表示n存在于這個序列中：（圖2）

2．對兩個序列進行位運算。

如果需要對兩個整數序列進行并的操作，那么只需要對它們對應的二進制數組進行“并”的位運算；如果需要對兩個整數序列進行或的操作，那么只需要對它們對應的二進制數組進行“或”的位運算；如果需要對兩個整數序列進行NOT的操作，那么只需要對它們對應的二進制數組先進行“并”的位運算，再進行“異或”的位運算。

計算機進行位運算的速度是最快的。在實際的程序中，我們可以以long類型為基本的位運算單位，相同位置的long型數據進行兩兩位運算，以提高速度。

3．將二進制數組轉為結果整數序列。

位運算結束后，需要將這個結果再轉為整數序列。這個轉換后的整數序列就是我們需要的最終結果。

下面是一次完整的運算過程，我們需要將{2,3,300}和{2,3,200,7000,12000}這兩個序列進行并的操作。如圖3所示。實驗八典型算法的應用實驗目的掌握順序查找（設置監(jiān)視哨）、折半查找等典型HYPERLI