課程設計--算法設計與實踐

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：38 大?。?72.50KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩37頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　題目：算法設計與實踐 　　院系：信息學院 　　專業(yè)：計算機科學與技術專

2、業(yè)（軟件方向） 　　學號： 　　姓名： 　　指導教師：

3、 　　完成日期： 2013年7月14日 　　目錄　　實驗一：順序表操作…………………………………………………..3　　抽象數據數據類型…………................

4、.........................3　　源代碼……………….....................................................4　　測試結果.........................................................................9</p&

5、gt;　　實驗小結……………………………………………….9　　實驗二：二叉排序樹的操作……………………………………………10　　抽象數據數據類型………….........................................10　　源代碼………………................

6、.....................................11　　測試結果.........................................................................17　　實驗小結……………………………………………….17　　實驗三：無向圖的

7、操作………………………………………………..18　　抽象數據數據類型………….........................................18　　源代碼……………….....................................................19　　測試結果....

8、.....................................................................26　　實驗小結……………………………………………….26　　實驗四：有向圖的操作………………………………………………..27　　抽象數據數據類型…………...........

9、..............................27　　源代碼……………….....................................................27　　測試結果.........................................................................3

10、4　　實驗小結……………………………………………….34　　實驗五：哈希表的操作………………………………………………..35　　抽象數據數據類型………….........................................35　　源代碼………………......

11、...............................................35　　測試結果.........................................................................37　　實驗小結……………………………………………….37

12、　　參考文獻…………………………………………………………………38　　[一] 順序表操作　?。?）創(chuàng)建順序表；　?。?）順序表進行順序查找； 　?。?）順序表進行排序（排序的方法可以是簡單的，也可

13、以是先進的）；　　（4）順序表進行折半查找。　　設計方案（抽象數據類型）　　ADT StaticSearchTable　　{　　數據對象D：銷售單集合

14、　　數據關系R：線性表　　基本操作P：　　CreateTable(&T,n)　　操作結果：構造一個含n個數據元素的靜態(tài)查找表　　DestroyTable（&T）

15、　　初始條件：靜態(tài)查找表T存在　　操作結果：銷毀表T　　int SearchTable(T,key)　　初始條件：靜態(tài)查找表T存在，key為和查找表中元素的關鍵字類型相同的給定值。　　操作結果：若T中存在其關鍵字

16、等于key的數據元素，則函數值返回其在表中的位置，否則為0。　　void SortTable(&T)　　初始條件：靜態(tài)查找表T存在；　　操作結果：對T實施直接插入排序（非遞減的）。　　int SearchBin(T ,key)<p&g

17、t;　　初始條件：靜態(tài)查找表T存在。　　操作結果：折半查找，在查找表中查關鍵字等于key的記錄的位序，如果沒有，則返回0。　　}　　源代碼：　　#include"stdio.h"

18、;　　#include"stdlib.h"　　#define OK 1　　#define ERROR -1　　typedef struct　　{&l

19、t;p>　　int key;　　char name[30];　　}SDate;　　typedef struct　　{<p&

20、gt;　　SDate *elem;　　int length;　　}STable;　　int CreatTable(STable *L,int n)　　{&

21、lt;b>　　int i;　　if(n<1)　　return ERROR;　　L->elem=(SDate *)malloc((n+1)*sizeof(SDate));　　L->length

22、=n;　　for(i=1;i<=n;i++)　　{　　printf("售單號和售貨員\n");　　scanf("%d",&L->elem[i].key);

23、　　getchar();　　gets(L->elem[i].name);　　}　　return OK;　　}　　void De

24、stroyTable(STable *L)　　{　　if(L->elem=NULL)　　return;　　free(L->elem);　　pr

25、intf("\n成功釋放靜態(tài)查找表\n");　　}　　int SearchTable(STable L,int key)　　{　　int i;</b&g

26、t;　　L.elem[0].key=key;　　for(i=L.length;L.elem[i].key!=key;i--)　　;　　return i;&

27、lt;b>　　}　　void SortTable(STable *L)　　{　　int i,j;　　for(i=2;i<=L->length;i++)<

28、/p>　　{　　if(L->elem[i].key<L->elem[i-1].key)　　{　　L->elem[0]=L->elem[i];

29、;　　L->elem[i]=L->elem[i-1];　　for(j=i-2;L->elem[0].key<L->elem[j].key;j--)　　{　　L->elem[j+1]=L->elem[j];<

30、;p>　　}　　L->elem[j+1]=L->elem[0];　　}　　}　　}

31、　　void ShowTable(STable L)　　{　　int i;　　for(i=1;i<=L.length;i++)　　{

32、;　　printf(“銷售單號:%d,銷售員是:　　%s\n",L.elem[i].key,L.elem[i].name);　　}　　}　　in

33、t SearchBin(STable L,int key)　　{　　int low,high,mid;　　low=1;　　high=L.length;

34、while(low<=high)　　{　　mid=(low+high)/2;　　if(L.elem[mid].key=key)　　return mid;　　else&l

35、t;/b>　　if(key<L.elem[mid].key)　　high=mid-1;　　else　　low=mid+1;　　}</p&

36、gt;　　return 0;　　}　　void main()　　{　　STable L;</

37、p>　　int i,key,n;　　printf("輸入銷售單的個數:");　　scanf("%d",&n);　　if(CreatTable(&L,n)==ERROR)

38、　return;　　ShowTable(L);　　printf("輸入要查找的銷售單號:");　　scanf("%d",&key);　　i=SearchTable(L,key);&

39、lt;p>　　if(i!=0)　　{　　printf("找到:%d \n",key);　　printf("在銷售表中的位置是%d,銷售員是%s\n",i,L.elem[i].name);<

40、;/p>　　}　　else 　　printf("未找到:%d\n",key);　　SortTable(&L);　　ShowTable(L);

41、　　i=SearchBin(L,key);　　if(i!=0)　　{ printf("找到:%d \n",key);　　printf("在銷售表中的位置是%d,銷售員是%s\n",i,L.e

42、lem[i].name);　　}　　else 　　printf("未找到:%d\n",key);　　DestroyTable(&L);<p

43、>　　}　　測試結果：　　實驗小結：　　沒遇到太大的問題，在=和== 功能上會有失誤的時候不過在將key==…時就會解決這個問題。　　[二] 二叉排序

44、樹的操作　?。?）創(chuàng)建一棵二叉排序樹；　?。?）二叉排序樹上的查找操作；　?。?）二叉排序樹上的刪除操作；　　ADT StaticSortBST　　{

45、　　數據對象D：數據集合　　數據關系R：二叉樹　　基本操作T：　　int SearchBST(T, key ,f ,&p)　　初始條件：二叉排序樹存在<p&g

46、t;　　操作結果：若T中存在其關鍵字等于key的數據元素，則函數值返回其在表中的位置，否則為0。　　int InsertBST(&T,int n)　　操作結果：以二叉排序樹的規(guī)則插入結點，成功返回1，否則返回0　　void DestroyBST(& T)

47、　初始條件：二叉排序樹T存在　　操作結果：銷毀樹T　　void Preorder(T)　　操作結果：先序遍歷二叉排序樹，并輸出各節(jié)點信息　　void Inorder(T)　　操作結果：中序遍歷

48、二叉排序樹，并輸出各節(jié)點信息　　}　　源代碼：　　#include"stdio.h"　　#include"stdlib.h"<

49、p>　　#include"string.h"　　typedef struct BiTNode　　{　　int data;　　struct BiTNode *lchild,

50、*rchild;　　}*BiTree,BiTNode;　　int SearchBST(BiTree T,int key,BiTree f,BiTree *p)　　{　　if(!T)</p&g

51、t;　　{　　*p=f;　　return 0;　　}　　else </b&

52、gt;　　if(key==T->data)　　{　　*p=T;　　return 1;　　}&

53、lt;/b>　　else 　　if(key<T->data)　　return SearchBST(T->lchild,key,T,p);　　else return SearchBST(T->rchild,

54、key,T,p);　　}　　int InsertBST(BiTree *T,int n)　　{　　BiTree s=NULL,p=NULL;　　if(!S

55、earchBST(*T,n,NULL,&p))　　{　　s=(BiTree)malloc(sizeof(BiTNode));　　s->data=n;　　s->lchild=NULL;<

56、p>　　s->rchild=NULL;　　if(!p)　　*T=s;　　else　　if(n<p->data)

57、　　p->lchild=s;　　else　　p->rchild=s;　　return 1;　　}<

58、p>　　else return 0;　　}　　void DestroyBST(BiTree T)//采用后序遍歷的方法釋放空間　　{　　if(T!=NULL)<

59、p>　　{　　DestroyBST(T->lchild);　　DestroyBST(T->rchild);　　free(T);　　}<

60、/p>　　}　　void Preorder(BiTree T)//先序遍歷二叉樹　　{　　if(T)　　{<

61、;/b>　　printf("%d",T->data);　　Preorder(T->lchild);　　Preorder(T->rchild);　　}

62、　　}　　void Inorder(BiTree T)//中序遍歷二叉樹　　{　　if(T)　　{

63、　　Inorder(T->lchild);　　printf("%d",T->data);　　Inorder(T->rchild);　　}　　}</b&g

64、t;　　int SearchDeleteBST(BiTree T,int key,BiTree *f,BiTree *p)　　{　　if(!T)　　return 0;</

65、b>　　else　　if(key==T->data)　　{ *p=T;　　return 1;<b

66、>　　}　　else　　if(key<T->data)　　{ *f=T;　　return SearchDeleteBST(T->lchild,key

67、,f,p);　　}　　else 　　{ *f=T;　　return SearchDeleteBST(T->rchild,key,f,p);</

68、p>　　}　　}　　int DeleteBST(BiTree *T,int key)　　{　　BiTree p,f,s;</

69、p>　　if(SearchDeleteBST(*T,key,&f,&p)==0)　　return 0;　　if(!p->rchild)　　{　　f

70、->lchild=p->lchild;　　free(p);　　}　　else 　　if(!p->lchild)<

71、;p>　　{　　f->lchild=p->rchild;　　free(p);　　}　　else<

72、;/p>　　{　　f=p;　　s=p->lchild;　　while(s->rchild)　　{

73、　　p=s;　　s=s->rchild;　　}　　f->data=s->data;　　if(f!=p)</p&g

74、t;　　p->rchild=s->lchild;　　else　　p->lchild=s->lchild;　　free(s);　　}

75、　　return 1;　　}　　void main()　　{　　BiTree T=NULL,p=

76、NULL;　　int m_inum,m_icount,m_icin,m_ifeedback,m_ifind,m_idelete;　　printf("二叉樹結點的個數：");　　scanf("%d",&m_inum);　　pr

77、intf("創(chuàng)建一棵結點數為%d的二叉排序樹\n",m_inum);　　for(m_icount=0;m_icount<m_inum;m_icount++)　　{　　printf("輸入結點數據");<

78、;p>　　scanf("%d",&m_icin);　　m_ifeedback=InsertBST(&T,m_icin);　　if(m_ifeedback=1)　　printf("插入成功\n");　　if(m_

79、ifeedback=0)　　printf("也存在該關鍵字");　　}　　printf("\n先序遍歷的序列是：");　　Preorder(T);　　p

80、rintf("\n中序遍歷的序列是：");　　Inorder(T);　　putchar('\n');　　printf("輸入要查找的數據");　　scanf("%d",&m_ifind);

81、　　if(SearchBST(T,m_ifind,NULL,&p)==1)　　{　　printf("找到！%d\n",m_ifind);　　if(p->lchild&&p->rc

82、hild)　　printf("值為%d的結點的度為2\n",m_ifind);　　else　　if(!p->lchild&&!p->rchild)　　printf("值為%d的

83、結點的度為0\n",m_ifind);　　else printf("值為%d的結點的度為1\n",m_ifind);　　}　　else printf("未找到：%d",m_ifind);

84、;　　printf("輸入要刪除的數據:");　　scanf("%d",&m_idelete);　　if(DeleteBST(&T,m_idelete)==1)　　printf("刪除成功\n");

85、;　　else printf("刪除失敗");　　printf("\n先序遍歷的序列是：");　　Preorder(T);　　printf("\n中序遍歷的序列是");　　Inorder(T);

86、;　　printf("\n");　　DestroyBST(T);　　}　　測試結果：　　實驗小結：

87、;　　該實驗掌握的比較好，沒什么大問題，對于二叉排序樹理解還不錯。　　[三] 無向網的操作　?。?）創(chuàng)建一個連通的無向網（邊上的權都是正整數，表示某種代價）；　　（2）對這個無向網可以實施深度或廣度優(yōu)先遍歷；　　（3）求這個無向網的一棵最小生成樹。&

88、lt;/p>　　ADT UDNGraph　　{　　數據對象D：數據集合　　數據關系R：無向圖　　基本操作T：

89、　　void CreateUDN(&G)　　操作結果：創(chuàng)建一個含權值的無向圖。　　void DFSGraph(G)　　初始條件：無向圖G存在　　操作結果：深度優(yōu)先遍歷該無向圖。　　void BFSTra

90、verse(G)　　初始條件：無向圖G存在　　操作結果：廣度優(yōu)先遍歷該無向圖。　　long MiniSpanTree_PRIM(G, u)　　操作結果：用普利姆算法生成最小二叉樹，成功返回權值，失敗返回-1　　}

91、　　源代碼：//內含隊列的操作　　#include"stdio.h"　　#include"stdlib.h"　　#define MAXQSIZE 100　　#define

92、 INFINITY 9999　　#define MAX_VERTEX_NUM 20　　typedef enum {DG,DN,UDG,UDN} GraphKind;　　typedef struct ArcCell　　{</p&g

93、t;　　int adj;　　char *info;　　}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　typedef struct

94、{　　int vex[MAX_VERTEX_NUM];　　AdjMatrix arcs;　　int vexnum,arcnum;　　GraphKind kind;　　}MGraph;</

95、b>　　void CreateUDN(MGraph *G)　　{　　int i,j,k,w;　　G->kind=UDN;　　printf("輸入圖的頂點數和邊數:&quo

96、t;);　　scanf("%d%d",&G->vexnum,&G->arcnum);　　for(i=0;i<G->vexnum;i++)　　G->vex[i]=i;　　for(i=0;i<G->

97、vexnum;i++)　　for(j=0;j<G->vexnum;j++)　　{　　G->arcs[i][j].adj=INFINITY;　　G->arcs[i][j].info=NULL;

98、　　}　　printf("錄入 %d條邊，　　例如 0 1 5表示0 1之間有邊，權為5；\n",G->arcnum);　　for(k=0;k<G->arcnum;k++)&

99、lt;b>　　{　　scanf("%d%d%d",&i,&j,&w);　　G->arcs[i][j].adj=w;　　G->arcs[j][i].adj=G->arcs[i][j].adj;<p&

100、gt;　　}　　}　　int visited[MAX_VERTEX_NUM]={0};　　void DFS(MGraph G,int v)　　{</p&

101、gt;　　int w=0;　　visited[v]=1;　　printf("%3d",G.vex[v]);　　for(;w<G.vexnum;w++)　　if(G.arcs[v][w].

102、adj!=INFINITY&&!visited[w])　　DFS(G,w);　　}　　void DFSGraph(MGraph G)　　{&l

103、t;/p>　　int i;　　for(i=0;i<G.vexnum;i++)　　{　　if(!visited[i])　　{&

104、lt;/p>　　printf("\n從%d出發(fā)深度優(yōu)先遍歷的結果是:",i);　　DFS(G,i);　　}　　}

105、;　　}　　typedef struct　　{　　int *base;　　int front;　　int rear;

106、　　}SqQueue;　　void InitQueue(SqQueue *Q)　　{　　Q->base=(int *)malloc(MAXQSIZE *sizeof(int));</p

107、>　　if(NULL==Q->base)　　{　　printf("\n分配空間失??！");　　return;　　}</

108、b>　　Q->front=Q->rear=0;　　}　　void DestroyQueue(SqQueue *Q)　　{　　if(Q-&

109、gt;base!=NULL)　　free(Q->base);　　}　　int QueueLength(SqQueue Q)　　{　　return (

110、Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;　　}　　void EnQueue(SqQueue *Q,int e)　　{　　if((Q->rear+1)%MAXQSI

111、ZE==Q->front)　　return;　　Q->base[Q->rear]=e;　　Q->rear=(Q->rear+1)%MAXQSIZE;　　}</p

112、>　　void DeQueue(SqQueue *Q,int *e)　　{　　if(Q->front==Q->rear)　　return;　　*e=Q-&g

113、t;base[Q->front];　　Q->front=(Q->front+1)%MAXQSIZE;　　}　　int QueueEmpty(SqQueue Q)　　{</p

114、>　　return Q.front==Q.rear;　　}　　void BFSTraverse(MGraph G)　　{　　int v,w,u,visited[MAX_

115、VERTEX_NUM];　　SqQueue Q;　　for(v=0;v<G.vexnum;v++)　　visited[v]=0;　　InitQueue(&Q);　　for(v=0;v<G.vexnum;v++)

116、　　if(!visited[v])　　{　　visited[v]=1;　　printf("\n從%d出發(fā)廣度優(yōu)先遍歷的結果是： ",G.vex[v]);　　printf(&

117、quot;%3d",G.vex[v]);　　EnQueue(&Q,v);　　while(!QueueEmpty(Q))　　{　　DeQueue(&Q,&u);

118、　　for(w=0;w<G.vexnum;w++)　　{　　if(G.arcs[u][w].adj!=INFINITY)　　{　　if(!visited[w])<

119、;p>　　{　　visited[w]=1;　　printf("%3d",G.vex[w]);　　EnQueue(&Q,w);　　}<

120、p>　　}　　}　　}　　}　　DestroyQueue(&Q);

121、;　　}　　struct　　{　　int adjvex;　　int lowcost;　　}closedge[MAX_

122、VERTEX_NUM];　　int minnum(MGraph G)　　{　　int i,k,min=INFINITY;　　k=-1;　　for(i=0;

123、i<G.vexnum;i++)　　{　　if(closedge[i].lowcost>0&&closedge[i].lowcost<min)　　{　　min=cl

124、osedge[i].lowcost;　　k=i;　　}　　}　　return k;<p&g

125、t;　　}　　long MiniSpanTree_PRIM(MGraph G,int u)　　{　　int k,i,j;　　long sum=0;<

126、b>　　k=u;　　for(j=0;j<G.vexnum;j++)　　{　　if(j!=k)　　{&l

127、t;p>　　closedge[j].adjvex=u;　　closedge[j].lowcost=G.arcs[k][j].adj;　　}　　}　　closedge[k].lowcost=0

128、;　　for(i=1;i<G.vexnum;i++)　　{　　k=minnum(G);　　if(k==-1)　　{</b&g

129、t;　　printf("\n無邊可選，求最小生成樹算法非正常結束！");　　return -1;　　}　　printf("\n%d:(%d,%d)%d",

130、;　　i,closedge[k].adjvex,k,closedge[k].lowcost);　　sum+=closedge[k].lowcost;　　closedge[k].lowcost=0;　　for(j=0;j<G.vexnum;j++)

131、　{　　if(G.arcs[k][j].adj<closedge[j].lowcost)　　{　　closedge[j].adjvex=k;　　closedge[j].lowcost=G.arcs[k][j]

132、.adj;　　}　　}　　}　　return sum;　　}

133、;　　void main()　　{　　MGraph M;　　long sum;　　CreateUDN(&M);

134、;　　DFSGraph(M);　　BFSTraverse(M);　　printf("\n圖的最小生成樹依次選的邊:");　　sum=MiniSpanTree_PRIM(M,0);　　printf("\n圖的最小代價之和是

135、%ld\n",sum);　　}　　測試結果：　　實驗小結：　　普利姆算法實現時遇到困難，反復只選一條邊，經測試發(fā)現為一處判斷出現錯誤，導致錯誤。還想

136、實驗克魯斯卡爾算法。　　[四] 有向圖的操作　　（1）創(chuàng)建一個具有偏序關系有向圖；　?。?）對這個有向圖實施拓撲排序。　　ADT DGGraph　　{

137、　　void CreateDG(& G)　　操作結果：創(chuàng)建一個具有偏序關系的有向圖。　　void Display(G)　　操作結果：顯示有向圖。　　int TopologicalSort(G)　　操作結果：進行拓撲排序。&

138、lt;/p>　　}　　源代碼：//內含棧的操作　　#include <stdio.h>　　#include <stdlib.h>　　#include<string.h>&

139、lt;/p>　　#define INFINITY 32767　　#define MAX_VERTEX_NUM 26　　#define TRUE 1　　#define FALSE 0　　typedef struct<

140、p>　　{　　int adj;　　}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];　　typedef struct

141、　　{　　char vexs[MAX_VERTEX_NUM];　　AdjMatrix arcs;　　int vexnum, arcnum;　　}MGraph;　　int I

142、ndegree[MAX_VERTEX_NUM] = {0};//標記用　　typedef struct Stack_　　{　　char sta[MAX_VERTEX_NUM];　　int top;

143、　　}Stack;　　Stack stack;　　int LocateVex(MGraph G, char u)　　{　　int i;&

144、lt;/b>　　for(i = 0; i < G.vexnum;i++)　　{　　if(u == G.vexs[i])//字符可以直接相等　　return i;

145、　　}　　return -1;　　}　　char GetVex(MGraph G, int v)　　{<p&g

146、t;　　if(v >= G.vexnum || v < 0)　　exit(0);　　return G.vexs[v];　　}　　int FirstAdjVex(MGraph G, in

147、t v)　　{　　int i;　　int j = INFINITY;　　for(i = 0; i < G.vexnum;i++)　　if(G.arc

148、s[v][i].adj != j)　　return i;　　return -1;　　}　　int NextAdjVex(MGraph G, int v, int w)<

149、;p>　　{　　int i;　　int j = INFINITY;　　for(i = w+1; i < G.vexnum;i++)　　if(G.arcs[v][i].adj != j)

150、　　return i;　　return -1;　　}　　void CreateDG(MGraph * G)　　{&

151、lt;/p>　　int i, j, k;　　char v1, v2;　　printf("請輸入有向圖G的頂點數，邊數(例如:3 4)");　　scanf("%d%d", &G->vexnum, &G->arcnum)

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設計--算法設計與實踐

文檔簡介

溫馨提示

最新文檔

評論

課程設計--算法設計與實踐

文檔簡介

溫馨提示

最新文檔

評論

免費下載