【正文】 并完成問題：查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35查找key=41的比較次數(shù)：查找key=35的比較次數(shù)：l 算法實(shí)現(xiàn)代碼哈希表的構(gòu)造與查找/* 采用開放地址法構(gòu)造哈希表*/includeincludedefine MAXSIZE 25define P 13define OK 1define ERROR 0define DUPLICATE 1define TRUE 1define FALSE 0typedef struct{ /*哈希表元素結(jié)構(gòu)*/ int key。學(xué)會(huì)哈希函數(shù)的構(gòu)造方法，處理沖突的機(jī)制以及哈希表的查找。理解圖的應(yīng)用方法四、教師評(píng)語實(shí)驗(yàn)六 查找一、實(shí)驗(yàn)?zāi)康恼莆詹檎冶?、?dòng)態(tài)查找表、靜態(tài)查找表和平均查找長(zhǎng)度的概念。ABCDEF0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,61,1,1ABCDEF0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,601,1,1167。 下面的輸入分別驗(yàn)證prim算法和dijstra算法。 /*dijstra算法演示*/ return 0。 /*prim算法演示*/getchar()。 dijkstra(ga,0)。 createGraph_w(amp。ga,0)。ga,1)。 } }}void showprim()/*最小生成樹prim算法演示*/{ graph ga。i!=j) printf(%c,[j])。j++) if(path[i][j]==1amp。 for(j=0。 else{ printf(%d ,dist[i])。i++){ printf(\n頂點(diǎn)%c頂點(diǎn)%c：,[v],[i])。 for(i=0。 path[j][j]=1。k。dist[u]+[u][j]dist[j]){ dist[j]=dist[u]+[u][j]。j++) if((s[j]==0)amp。 for(j=0。 mindis=dist[j]。j。i++){ mindis=INFIN。 for(i=0,u=1。 } } dist[v]=0。 if(dist[i]INF){ path[i][v]=1。j。 s[i]=0。i。 int mindis,i,j,u,k。 closest[j]=k。amp。jgvexnum。 /*輸出該邊*/ lowcost[k]=0。 k=j。amp。jgvexnum。i++) /*循環(huán)求最小生成樹中的各條邊*/ { min=INFIN。 for(i=1。 closest[i]=u。igvexnum。 }}void prim(graph *g,int u)/*出發(fā)頂點(diǎn)u*/{ int lowcost[N],closest[N],i,j,k,min。j,amp。 scanf(%d,%d,%d,amp。 /*讀入邊(i,j,w)*/ while(i!=1) /*讀入i為－1時(shí)結(jié)束*/ { garcs[i][j]=w。j,amp。 scanf(%d,%d,%d,amp。j++) garcs[i][j]=INF。i++) /*鄰接矩陣初始化*/ for(j=0。 for(i=0。 /*讀入頂點(diǎn)信息*/ i++。39。 printf(輸入頂點(diǎn)序列(以結(jié)束)：\n)。 garum=0。 char v。void showdij()。void dijkstra(graph g,int v)。void createGraph_w(graph *g,int flag)。 int arcs[N][N]。includedefine N 20define TRUE 1define INF 32766 /*鄰接矩陣中的無窮大元素*/define INFIN 32767 /*比無窮大元素大的數(shù)*/typedef struct{ /*圖的鄰接矩陣*/ int vexnum,arum。輸入:ABCDEF0,11,22,34,14,51,1167。 根據(jù)輸入，輸出有向圖的拓?fù)渑判蛐蛄小? return 0。n。 int n,*p。i)。 while(! IsEmpty(s)) { Pap(amp。i++) if(indegree[i]==0) Push(amp。 for(i=0。 InitStack(amp。 AreNode *p。 int indegree[MAX_VERTEX_NUM]。 s=snext。 s=adjlist[i].link。in。 } printf(鄰接表:)。i,amp。 /*頂點(diǎn)j的入度加1*/ e++。 adjlist[i].link=s。 sadjvex=j。j)。 scanf(%d,%d,amp。 *p=n。 i++。 /*讀入頂點(diǎn)信息*/ adjlist[i].link=NULL。39。 printf(輸入頂點(diǎn)序列(以結(jié)束)：\n)。n=0。 edgenode *s。void createGraph_list(vnode adjlist[],int *p)； /*建立有向圖的鄰接表*/void topSort(vnode g[],int n)； /*拓?fù)渑判?/void createGraph_list(vnode adjlist[],int *p){ /*建立有向圖的鄰接表*/ int i,j,n,e。 /*頂點(diǎn)入度*/ struct edgenode *link。typedef struct vnode{ /*圖的鄰接表：鄰接表*/ char data。 /*頂點(diǎn)序號(hào)*/ struct edgenode *next。 運(yùn)行結(jié)果：閱讀并運(yùn)行下面程序，補(bǔ)充拓?fù)渑判蛩惴?。}167。ga)。 init_visit()。 tdfs(amp。 printf(\n)。j。i。 printf(無向圖的鄰接矩陣：\n)。 createGraph(amp。}int main(){ graph ga。iN。}void init_visit() /*初始化訪問標(biāo)識(shí)數(shù)組*/{ int i。igvexnum。 printf(\n從頂點(diǎn)%C開始廣度優(yōu)先搜索序列：,gvexs[0])。 qrear=(qrear+1)%N。 visited[j]=TRUE。amp。jgvexnum。 qfront=(qfront+1)%N。 qrear=(qrear+1)%N。 visited[k]=TRUE。 qfront=0。qlist。 queue qlist,*q。i++) if(visited[i]!=TRUE) dfs(i,g)。 for(i=0。}void tdfs(graph *g) /*深度優(yōu)先搜索整個(gè)圖*/{ int i。amp。jgvexnum。 visited[i]=TRUE。 }}void dfs(int i,graph *g) /*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/{ int j。i,amp。 garcs[j][i]=1。j)。 scanf(%d,%d,amp。j++) garcs[i][j]=0。i++) /*鄰接矩陣初始化*/ for(j=0。 /*頂點(diǎn)數(shù)目*/ for(i=0。 /*讀入頂點(diǎn)信息*/ i++。39。 printf(輸入頂點(diǎn)序列(以結(jié)束)：\n)。 garum=0。 char v。 /*廣度優(yōu)先搜索整個(gè)圖*/void init_visit()。 /*深度優(yōu)先搜索整個(gè)圖*/void bfs(int k,graph *g)。 /*建立一個(gè)無向圖的鄰接矩陣*/void dfs(int i,graph *g)。}graph。 char vexs[N]。}queue。 typedef struct /*隊(duì)列的定義*/{ int data[N]。四、教師評(píng)語實(shí)驗(yàn)五 圖的表示與遍歷一、實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的鄰接矩陣和鄰接表表示掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法 理解圖的應(yīng)用方法二、實(shí)驗(yàn)內(nèi)容和要求閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果。三、實(shí)驗(yàn)小結(jié)掌握二叉樹的基本特性，以及對(duì)遞歸和非遞歸的了解。 }}選做實(shí)驗(yàn)：（代碼可另附紙）補(bǔ)充二叉樹層次遍歷算法。 rchilddep=BTNodeDepth(prchild)。 if(p==NULL) return 0。 }在上題中補(bǔ)充求二叉樹深度算法，并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。 rchilddep=BTNodeDepth(prchild)。 if(p==NULL) return 0。}在上題中補(bǔ)充求二叉樹中求葉子結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計(jì)遍歷的葉子結(jié)點(diǎn)數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。 else q=NULL。 if(qlchild!=NULL) q=qlchild。 while(q!=NULL){ j++。i++) stack[i]=NULL。 for(i=0。 BiTree stack[MAX],q。}l 運(yùn)行程序輸入：ABCDEGF運(yùn)行結(jié)果：在上題中補(bǔ)充求二叉樹中求結(jié)點(diǎn)總數(shù)算法（提示：可在某種遍歷過程中統(tǒng)計(jì)遍歷的結(jié)點(diǎn)數(shù)），并在主函數(shù)中補(bǔ)充相應(yīng)的調(diào)用驗(yàn)證正確性。 release(t)。 printf(\n\n先序遍歷序列（非遞歸）:)。 printf(\n\nPostOrder the tree is:)。 printf(\n\nInOrder the tree is:)。 printf(\n\nPreOrder the tree is:)。 createBiTree(amp。 free(t)。 }}void release(BiTree t){ /*釋放二叉樹空間*/ if(t!=NULL){ release(tlchild)。 else if(top0) q=stack[top]。 if(qrchild!=NULL) stack[top++]=qrchild。/*初始化棧*/ q=p。iMAX。 int top=0,i。 printf(%c, pdata)。 }}void PostOrder(