計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)指導(dǎo)書

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí) 驗(yàn) 指 導(dǎo) 書編寫：張霖 邱述威適用專業(yè)：電器工程與自動(dòng)化 通 訊 工 程 電 子 信 息 工 程安徽建筑工業(yè)學(xué)院 電子與信息工程學(xué)院2007年9月1實(shí)驗(yàn)一：線性鏈表的建立、查找、插入、刪除實(shí)驗(yàn)實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：驗(yàn)證 實(shí)驗(yàn)要求：必修 一、實(shí)驗(yàn)?zāi)康?通過(guò)本實(shí)驗(yàn)的學(xué)習(xí)，要求學(xué)生能夠通過(guò)單鏈表的存儲(chǔ)結(jié)構(gòu)，掌握單鏈表的基本操作，包括單鏈表的建立、查找、插入、刪除、輸出等操作。通過(guò)本實(shí)驗(yàn)可以鞏固學(xué)生所學(xué)的線性表知識(shí)，提高編程能力，為后繼課程的學(xué)習(xí)奠定基礎(chǔ)。 二、實(shí)驗(yàn)內(nèi)容 1、 為線性表10，30，20，50，40，70，60，90，80，100創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表；2、

2、在該鏈表上查找值為50，65的結(jié)點(diǎn)，并返回查找結(jié)果（找到：返回在縣新鏈表中的位置）；3、 在該鏈表上值為50的結(jié)點(diǎn)后，插入一個(gè)值為120的結(jié)點(diǎn)；4、 刪除該鏈表上值為70的結(jié)點(diǎn)。寫出各操作的實(shí)現(xiàn)函數(shù)，并上機(jī)驗(yàn)證。 三、實(shí)驗(yàn)原理、方法和手段 使用帶頭結(jié)點(diǎn)的單鏈表的表示線性表，通過(guò)實(shí)驗(yàn)，熟悉鏈表的創(chuàng)建、查找、插入、刪除、輸出等是鏈表的基本操作。具體如下： （1）首先定義單鏈表的節(jié)點(diǎn)結(jié)構(gòu)；（2）在單鏈表創(chuàng)建過(guò)程中，首先初始化一個(gè)帶頭結(jié)點(diǎn)的空鏈表，對(duì)線性表中的各元素依次通過(guò)鍵盤輸入、建立該元素結(jié)點(diǎn)、插入到單鏈表中，實(shí)現(xiàn)單鏈表的創(chuàng)建過(guò)程；結(jié)點(diǎn)的插入有頭插入和尾插入兩種方法，采用不同方法時(shí)應(yīng)注意元素的輸入

3、順序。（3）查找過(guò)程可以從頭結(jié)點(diǎn)開(kāi)始，將待查找的數(shù)據(jù)依次與每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域比較，匹配及查找成功，弱鏈表訪問(wèn)完未找到匹配的元素，則查找不成功。為能夠返回查找成功的結(jié)點(diǎn)位置，在鏈表的搜索過(guò)程中，應(yīng)設(shè)置一個(gè)計(jì)數(shù)器，記錄搜索結(jié)點(diǎn)的序號(hào)； （4）插入結(jié)點(diǎn)時(shí)，首先要通過(guò)查找算法，找到帶插入結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后為帶插入元素建立結(jié)點(diǎn)，通過(guò)指針的修改，將結(jié)點(diǎn)插入。（5）刪除結(jié)點(diǎn)時(shí)，首先要通過(guò)查找算法，找到待刪除結(jié)點(diǎn)的前驅(qū)，然后通過(guò)指針的修改，將待刪除結(jié)點(diǎn)從鏈表中卸下，釋放該結(jié)點(diǎn)。（6）以上操作的正確性，均可以通過(guò)鏈表的輸出結(jié)果來(lái)驗(yàn)證。因此，可以統(tǒng)一寫一個(gè)單鏈表的輸出函數(shù)。四、實(shí)驗(yàn)組織運(yùn)行要求 采用以學(xué)生自主訓(xùn)練

4、為主的開(kāi)放模式組織教學(xué)，教師予以答疑與指導(dǎo)。 五、實(shí)驗(yàn)條件 PC機(jī)一臺(tái)、Windows操作系統(tǒng)、 C+ Builder軟件或Turbo C環(huán)境 六、實(shí)驗(yàn)步驟 (1)、將提前準(zhǔn)備好的源程序錄入計(jì)算機(jī)； (2)、調(diào)試源程序，修正錯(cuò)誤，記錄實(shí)驗(yàn)數(shù)據(jù)； (3)、分析運(yùn)行結(jié)果，驗(yàn)證所編程序是否正確。 七、思考題 (1)、線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的區(qū)別？ (2)、采用頭插入和尾插入方法，建立單鏈表有何區(qū)別？ 八、實(shí)驗(yàn)報(bào)告 (1)、實(shí)驗(yàn)預(yù)習(xí)：仔細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書，復(fù)習(xí)教材關(guān)于線性表部分的內(nèi)容和C語(yǔ)言中關(guān)于指針的內(nèi)容。 (2)、實(shí)驗(yàn)記錄的內(nèi)容應(yīng)包括源程序、實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行結(jié)果。 (3)、實(shí)驗(yàn)結(jié)論部分的內(nèi)容應(yīng)包括

5、對(duì)實(shí)驗(yàn)結(jié)果的分析和總結(jié)，回答思考題。 參考程序#include <stdio.h>typedef struct node int info; /*每個(gè)元素?cái)?shù)據(jù)信息*/ struct node *next; /*存放后繼元素的地址*/linknode,*pointer;void createlink(pointer *list) pointer p; int x,n,i; *list=(pointer)malloc(sizeof(linknode); (*list)->next=NULL; printf("nInput the Number of node:"

6、;); scanf("%d",&n);/*輸入結(jié)點(diǎn)個(gè)數(shù)*/ printf("nInput the datas of node:n"); for(i=1;i<=n;i+)/*前插入法創(chuàng)建鏈表*/ scanf("%d",&x); p=(pointer)malloc(sizeof(linknode); p->info=x; p->next=(*list)->next; (*list)->next=p; void print(pointer h) pointer p; p=h->next;

7、while(p) printf("%6d",p->info); p=p->next; int index(pointer list,int x,pointer *pos)/*在鏈表list中，查找值為x的結(jié)點(diǎn)，成功返回結(jié)點(diǎn)位置i及結(jié)點(diǎn)指針pos，不成功返回0*/ pointer p; int i=0; p=list->next; while(p) i+; if(p->info!=x) p=p->next; else *pos=p; return(i);/*查找成功，返回結(jié)點(diǎn)位置i*/ return(0);/*查找不成功，返回0*/int ins

8、ertlink(pointer list,int item,int x)/*在單鏈表list中,值為item的結(jié)點(diǎn)后，插入一個(gè)值為x的結(jié)點(diǎn)*/ pointer p,q; int k; k=index(list,item,&q);/*在鏈表h中查找值為50的結(jié)點(diǎn),結(jié)點(diǎn)指針存入q中*/ if(k!=0) /*找到值為item的結(jié)點(diǎn)，完成插入,并返回1*/ p=(pointer)malloc(sizeof(linknode); p->info=x; p->next=q->next; q->next=p; return(1); else /*未找到值為item的結(jié)點(diǎn)，并

9、返回0*/ return(0);int deletelink(pointer list, int x)/*刪除值為x的結(jié)點(diǎn)*/ pointer p,q; p=list->next; while(p&&p->info!=x) q=p; p=p->next; if(!p) printf("Delete fail!"); else q->next=p->next; free(p); printf("Delete success!"); main() pointer h,p; int x,k; /*建立鏈表*/ cr

10、eatelink(&h); printf("The linklist is:"); print(h);/*通過(guò)鏈表輸出，檢查鏈表建立的情況*/ /*查找*/ printf("nInput the data of index:"); scanf("%d",&x);/*輸入待查找的結(jié)點(diǎn)值*/ k=index(h,x,&p);/*在鏈表h中查找值為x的結(jié)點(diǎn)*/ if(k!=0) printf("Success!position=%d",k); else printf("Unsuccess

11、!"); /*插入*/ printf("nNow well insert 120 after 50.n"); k=insertlink(h,50,120);/*下面在鏈表中值為50的結(jié)點(diǎn)后，插入一個(gè)值為120的結(jié)點(diǎn)*/ if(k!=0) printf("nAfter of insert,the list is:n"); print(h);/*檢查插入后的鏈表*/ else printf("nNot fount node of 50!"); /*刪除*/ printf("nInput the data that yo

12、u want to delete:"); scanf("%d",&x); deletelink(h,x); printf("nNow the list is:"); print(h);/*檢查刪除后的鏈表*/ getch();/*暫停，以便查看結(jié)果*/參考程序運(yùn)行結(jié)果：實(shí)驗(yàn)二：二叉樹的創(chuàng)建與遍歷實(shí)驗(yàn) 實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：驗(yàn)證 實(shí)驗(yàn)要求：必修 一、實(shí)驗(yàn)?zāi)康?通過(guò)本實(shí)驗(yàn)的學(xué)習(xí)，使學(xué)生主要練習(xí)二叉樹的鏈表存儲(chǔ)的實(shí)現(xiàn)及二叉樹的基本操作，為繼續(xù)學(xué)習(xí)后續(xù)章節(jié)圖的內(nèi)容奠定基礎(chǔ)。 二、實(shí)驗(yàn)內(nèi)容 (1)、二叉樹的二叉鏈表結(jié)構(gòu)的建立； (2)、寫一個(gè)二

13、叉鏈表的創(chuàng)建算法，以此建立給定二叉樹的二叉鏈表；(3)、用遞歸方式寫出二叉樹的先序、中序、后序遍歷算法，對(duì)上面建立的二叉鏈表進(jìn)行遍歷。 三、實(shí)驗(yàn)原理、方法和手段 鏈表存儲(chǔ)二叉樹通常具有兩個(gè)指針域的鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域Data、左指針域和右指針域組成。兩個(gè)指針域分別指向該結(jié)點(diǎn)的左、右孩子。若某結(jié)點(diǎn)沒(méi)有左孩子或右孩子，則對(duì)應(yīng)的指針域?yàn)榭铡Ｗ詈?，還需要一個(gè)鏈表的頭指針指向根結(jié)點(diǎn)。 二叉樹是非線性結(jié)構(gòu)，遍歷時(shí)是先訪問(wèn)根結(jié)點(diǎn)還是先訪問(wèn)子樹，是先訪問(wèn)左子樹還是先訪問(wèn)右子樹必須有所規(guī)定，這就是遍歷規(guī)則。采用不同的遍歷規(guī)則會(huì)產(chǎn)生不同的遍歷結(jié)果，因此對(duì)二叉樹進(jìn)行遍歷時(shí)，必須設(shè)定遍歷規(guī)則

14、。根據(jù)遍歷規(guī)則采用遞歸或者非遞歸的方式實(shí)現(xiàn)二叉樹的遍歷。 本實(shí)驗(yàn)通過(guò)創(chuàng)建算法，首先創(chuàng)建一個(gè)二叉鏈表，再采用遞歸方法對(duì)所創(chuàng)建鏈表進(jìn)行先序、中序、后序遍歷。并以下面二叉樹為例，對(duì)所設(shè)計(jì)算法進(jìn)行驗(yàn)證。四、實(shí)驗(yàn)組織運(yùn)行要求 采用以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)，教師予以答疑與指導(dǎo)。 五、實(shí)驗(yàn)條件 PC機(jī)一臺(tái)、Windows操作系統(tǒng)、C+ Builder軟件或Turbo C環(huán)境 六、實(shí)驗(yàn)步驟 (1)、將提前準(zhǔn)備好的源程序錄入計(jì)算機(jī)； (2)、調(diào)試源程序，修正錯(cuò)誤，記錄實(shí)驗(yàn)數(shù)據(jù)； (3)、分析運(yùn)行結(jié)果，驗(yàn)證所編程序是否正確 七、思考題 (1)、結(jié)合二叉樹的遍歷，請(qǐng)考慮實(shí)現(xiàn)統(tǒng)計(jì)一棵二叉樹的結(jié)點(diǎn)數(shù)的函數(shù)。

15、 八、實(shí)驗(yàn)報(bào)告 (1)、實(shí)驗(yàn)預(yù)習(xí)：仔細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書和教材中二叉樹遍歷的相關(guān)內(nèi)容。 (2)、實(shí)驗(yàn)記錄的內(nèi)容應(yīng)包括實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行結(jié)果。 (3)、實(shí)驗(yàn)結(jié)論部分的內(nèi)容包括對(duì)實(shí)驗(yàn)結(jié)果的分析和總結(jié)，回答思考題。 參考程序：#include "stdio.h"typedef struct bnode char data;/* 設(shè)結(jié)點(diǎn)內(nèi)容的數(shù)據(jù)類型為字符型 */ struct bnode *lchild, *rchild; Bnode, *BTree;BTree CreateBinTree(BTree t)/* 以加入空結(jié)點(diǎn)的先序序列輸入，構(gòu)造二叉鏈表 */ char ch; ch=ge

16、tchar(); if (ch='0')t=NULL; /*讀入0時(shí)，將相應(yīng)結(jié)點(diǎn)指針置空*/ else t=(Bnode *)malloc(sizeof(Bnode); /* 生成結(jié)點(diǎn)空間 */ t->data=ch; t->lchild=CreateBinTree(t->lchild); /*構(gòu)造二叉樹的左子樹 */ t->rchild=CreateBinTree(t->rchild); /*構(gòu)造二叉樹的右子樹 */ return(t);void InOrder(BTree t) /*中序遍歷二叉樹的遞歸算法*/ if (t) InOrder(t

17、->lchild); printf("%c",t->data); InOrder(t->rchild); void PostOrder(BTree t)/*后序遍歷二叉樹的遞歸算法*/ if (t) PostOrder(t->lchild); PostOrder(t->rchild); printf("%c",t->data); main() BTree t; printf("Input the tree,eg:AB0D00CE00F00:n"); t=(Bnode *)malloc(sizeof(

18、Bnode); t=CreateBinTree(t); printf("InOrder:n"); InOrder(t); printf("nPostOrder:n"); PostOrder(t); printf("n"); getch();參考程序運(yùn)行結(jié)果：實(shí)驗(yàn)三：圖的鄰接矩陣結(jié)構(gòu)的創(chuàng)建和圖的遍歷實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：驗(yàn)證實(shí)驗(yàn)要求：必修 一、實(shí)驗(yàn)?zāi)康?通過(guò)本實(shí)驗(yàn)，使學(xué)生掌握?qǐng)D的基本存儲(chǔ)方法，特別是圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)圖的鄰接矩陣結(jié)構(gòu)的創(chuàng)建。掌握?qǐng)D的遍歷算法，并在圖的鄰接矩陣結(jié)構(gòu)下用高級(jí)語(yǔ)言實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容 1、 使用圖的鄰接

19、矩陣存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)圖的創(chuàng)建算法，并對(duì)給定的圖，上機(jī)驗(yàn)證；2、 設(shè)計(jì)圖的遍歷算法，并用上面創(chuàng)建的圖上機(jī)驗(yàn)證。三、實(shí)驗(yàn)原理、方法和手段 圖是一種非線性結(jié)構(gòu)，圖中任意兩個(gè)頂點(diǎn)之間均可能存在關(guān)系。鄰接矩陣是圖常用的一種存儲(chǔ)結(jié)構(gòu)，在這種存儲(chǔ)結(jié)構(gòu)中，我們用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用一個(gè)二維數(shù)組表示圖中各頂點(diǎn)之間的鄰接關(guān)系信息。 由于圖的非線性結(jié)構(gòu)自身的復(fù)雜性，在圖中，沒(méi)有一個(gè)“自然”的首結(jié)點(diǎn)，圖中任意一個(gè)頂點(diǎn)都可作為第一個(gè)被訪問(wèn)的結(jié)點(diǎn)。在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能夠訪問(wèn)它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何選取下一個(gè)出發(fā)點(diǎn)以訪問(wèn)圖中其余的連通分量。如果圖中存在回路，那么一個(gè)頂點(diǎn)被訪問(wèn)之

20、后，有可能沿回路又回到該頂點(diǎn)。圖中一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連等問(wèn)題。確定了圖的遍歷操作的復(fù)雜性，圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種方式。圖的深度優(yōu)先遍歷的基本思想是從圖中某個(gè)V0出發(fā)，訪問(wèn)此結(jié)點(diǎn)，再依次訪問(wèn)所有與V0有路徑的結(jié)點(diǎn)。完成后再另選圖中一個(gè)未被訪問(wèn)的結(jié)點(diǎn)作始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有結(jié)點(diǎn)都被訪問(wèn)到為止。 本實(shí)驗(yàn)通過(guò)創(chuàng)建算法，采用圖的鄰接矩陣結(jié)構(gòu)首先創(chuàng)建一個(gè)圖，再采用遞歸方法對(duì)所創(chuàng)建的圖進(jìn)行深度優(yōu)先遍歷。四、實(shí)驗(yàn)組織運(yùn)行要求 采用以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)，教師予以答疑與指導(dǎo)。 五、實(shí)驗(yàn)條件 PC機(jī)一臺(tái)、Windows操作系統(tǒng)、C+ Builder軟件或Tu

21、rbo C環(huán)境六、實(shí)驗(yàn)步驟 (1)、將提前準(zhǔn)備好的源程序錄入計(jì)算機(jī)； (2)、調(diào)試源程序，修正錯(cuò)誤，記錄實(shí)驗(yàn)數(shù)據(jù)； (3)、分析運(yùn)行結(jié)果，驗(yàn)證所編程序是否正確。 七、思考題 (1)、圖的鄰接矩陣表示法和圖的鄰接表的表示法的區(qū)別是什么？(2)、圖的廣度優(yōu)先遍歷方法的實(shí)現(xiàn)是怎么樣的？八、實(shí)驗(yàn)報(bào)告 (1)、實(shí)驗(yàn)預(yù)習(xí)：仔細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書和教材中圖的相關(guān)內(nèi)容，(2)、實(shí)驗(yàn)記錄的內(nèi)容應(yīng)包括源程序、實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行結(jié)果。 (3)、實(shí)驗(yàn)結(jié)論部分的內(nèi)容應(yīng)包括對(duì)實(shí)驗(yàn)結(jié)果的分析和總結(jié)，回答思考題。 參考程序：#include <stdio.h>/*鄰接矩陣存儲(chǔ)結(jié)構(gòu)的定義*/#define MaxVerNu

22、m 30 /* 最大頂點(diǎn)個(gè)數(shù) */typedef struct char vexsMaxVerNum; /* 頂點(diǎn)表 */ int edgesMaxVerNumMaxVerNum; /* 鄰接矩陣，即邊表 */ int n,e; /* 頂點(diǎn)數(shù)和邊數(shù) */MGraph; /* MGragh是以鄰接矩陣存儲(chǔ)的圖類型 */typedef enumFalse,Trueboolean;boolean visitedMaxVerNum; /*輔助變量，用于標(biāo)記頂點(diǎn)是否被訪問(wèn)過(guò)信息*/*建立一個(gè)無(wú)向網(wǎng)圖的鄰接矩陣存儲(chǔ)的算法*/void CreatGraph(MGraph *G) /* 建立有向圖G的鄰接矩陣

23、存儲(chǔ) */ int i,j,k; printf("Input vexters number & edges number:"); scanf("%d,%d",&(G->n),&(G->e); /* 輸入頂點(diǎn)數(shù)和邊數(shù) */ printf("Input vexters information:"); getchar(); /*此句接收掉上一個(gè)輸入的尾字符，保證下面輸入的正確執(zhí)行*/ for(i=0;i<(G->n);i+) /* 輸入頂點(diǎn)信息，建立頂點(diǎn)表 */ G->vexsi=get

24、char(); for(i=0;i<G->n;i+) /* 初始化鄰接矩陣 */ for(j=0;j<G->n;j+) G->edgesij=0; printf("Input edges information(i,j):n"); getchar(); /*此句接收掉上一個(gè)輸入的尾字符，保證下面輸入的正確執(zhí)行*/ for(k=0;k<G->e;k+) /* 輸入e條邊，建立鄰接矩陣 */ scanf("%d,%d",&i,&j); G->edgesij=1; G->edgesji=1;

25、 /*深度優(yōu)先遍歷算法*/void DFStraverse(MGraph G) int i,v; for(v=0;v<G.n;v+) visitedv=False; /*標(biāo)志向量初始化*/ for(i=0;i<G.n;i+) if(!visitedi)DFS(G,i); printf("Endn");/*DFS*/int DFS(MGraph G,int v) /* 從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G */ int w; printf("%c->",G.vexsv); visitedv=True; /* 訪問(wèn)第v個(gè)頂點(diǎn) */ /*下面對(duì)v

26、尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS*/ for(w=0;w<G.n;w+) if (G.edgesvw&&!visitedw)DFS(G,w); main() MGraph G; CreatGraph(&G); DFStraverse(G); getch();以下圖為例的測(cè)試結(jié)果：實(shí)驗(yàn)四：查找與排序?qū)嶒?yàn)實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：驗(yàn)證實(shí)驗(yàn)要求：必修 一、實(shí)驗(yàn)?zāi)康?查找與排序是計(jì)算機(jī)最頻繁的操作，而排序與查找又是兩個(gè)密切相關(guān)的技術(shù)，有效的數(shù)據(jù)組織可以提高查找的效率。通過(guò)本實(shí)驗(yàn)，使學(xué)生加深對(duì)查找操作的基本概念、性質(zhì)，內(nèi)部排序操作的方法、特點(diǎn)的理解，培養(yǎng)學(xué)生利用查找和排序方

27、面知識(shí)解決問(wèn)題的能力，為后繼課程的學(xué)習(xí)奠定基礎(chǔ)。 二、實(shí)驗(yàn)內(nèi)容 5、 試編寫一程序，用快速分類算法對(duì)下面數(shù)據(jù)表，按遞增排序輸出。49,2,19,25,36,5,72,60,41,52,28,10,44,37,14,32,8,76,816、 用二分法在分類后數(shù)據(jù)表中查找19和26，并輸出查找信息。寫出各操作的實(shí)現(xiàn)函數(shù)，并上機(jī)驗(yàn)證。 三、實(shí)驗(yàn)原理、方法和手段 順序查找的基本方法是從表的一端開(kāi)始，順序掃描數(shù)據(jù)表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。但順序查找效率底，如果順序表中的數(shù)據(jù)元素按關(guān)鍵字

28、有序排列，則可進(jìn)行二分查找。在二分查找中，首先將待查值k和表中間位置上的結(jié)點(diǎn)關(guān)鍵字進(jìn)行比較，若兩者相等，則查找成功；否則，若k值小，則在表的前半部分中繼續(xù)利用二分查找法查找，若k值大，則在表的后半部分中繼續(xù)利用二分查找法查找。這樣，經(jīng)過(guò)一次關(guān)鍵字比較就縮小一半的查找區(qū)間，如此進(jìn)行下去，直到查找到該關(guān)鍵字或查找失敗。二分查找可以用遞歸方式和非遞歸方式來(lái)實(shí)現(xiàn)。排序是將一個(gè)數(shù)據(jù)元素集合或序列重新排列成一個(gè)按數(shù)據(jù)元素某個(gè)項(xiàng)值有序的序列，通常是按照某種規(guī)則把數(shù)據(jù)的順序重新整理。排序方法各種各樣，主要有插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等。交換排序的方法是通過(guò)兩兩比較待排序記錄的關(guān)鍵字，若不

29、滿足排序要求，則交換，不斷重復(fù)比較和交換過(guò)程，直到待排序記錄滿足排序要求為止。在交換排序中較為典型的是快速排序，其基本方法是在待排序列中任取一個(gè)記錄，以它為基準(zhǔn)用交換的方法將所有記錄分成兩部分，關(guān)鍵碼值比它小的在一部分，關(guān)鍵碼值比它大的在另一部分。再分別對(duì)這兩部分實(shí)施上述過(guò)程，一直重復(fù)到排序完成。四、實(shí)驗(yàn)組織運(yùn)行要求 采用以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)，教師予以答疑與指導(dǎo)。 五、實(shí)驗(yàn)條件 PC機(jī)一臺(tái)、Windows操作系統(tǒng)、 C+ Builder軟件或Turbo C環(huán)境 六、實(shí)驗(yàn)步驟 (1)、將提前準(zhǔn)備好的源程序錄入計(jì)算機(jī)； (2)、調(diào)試源程序，修正錯(cuò)誤，記錄實(shí)驗(yàn)數(shù)據(jù)； (3)、分析運(yùn)行

30、結(jié)果，驗(yàn)證所編程序是否正確。 七、思考題 (1)、試考慮折半查找的遞歸形式的算法。 (2)、如何改進(jìn)快速分類算法，使得當(dāng)分出的子數(shù)組已經(jīng)排好序則不必再做。 八、實(shí)驗(yàn)報(bào)告 (1)、實(shí)驗(yàn)預(yù)習(xí)：仔細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書，復(fù)習(xí)教材關(guān)于線性表部分的內(nèi)容和C語(yǔ)言中關(guān)于指針的內(nèi)容。 (2)、實(shí)驗(yàn)記錄的內(nèi)容應(yīng)包括源程序、實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行結(jié)果。 (3)、實(shí)驗(yàn)結(jié)論部分的內(nèi)容應(yīng)包括對(duì)實(shí)驗(yàn)結(jié)果的分析和總結(jié)，回答思考題。 參考程序:#include <stdio.h>#include <stdlib.h>#define MAXSIZE 20 /* 順序表的最大長(zhǎng)度，假定順序表的長(zhǎng)度為20 */typed

31、ef int KeyType; /* 關(guān)鍵碼類型為整數(shù)類型 */typedef struct KeyType key; /* 關(guān)鍵碼項(xiàng) */DataType; /* 數(shù)據(jù)元素類型 */typedef struct DataType rMAXSIZE +1; /* r0閑置或充當(dāng)哨兵 */ int length; /* 順序表長(zhǎng)度 */SqList; /* 順序表類型 */void QuickSort(SqList *S,int low,int high) /*對(duì)順序表S中的序列r1length作快速排序*/ int pivotkey; int left,pivotloc,right; left

32、=low;right=high; if(low<high) S->r0.key=S->rlow.key; /*以子表的第一個(gè)記錄作為支點(diǎn)（軸值）記錄*/ pivotkey=S->rlow.key; /*取支點(diǎn)（軸值）記錄關(guān)鍵字*/ while(low!=high) /*從表的兩端交替地向中間掃描*/ while(low<high && S->rhigh.key>=pivotkey) high-; if(low<high) S->rlow+.key=S->rhigh.key; /*將比支點(diǎn)（軸值）記錄小的交換到低端*/

33、while(low<high && S->rlow.key<=pivotkey) low+; if(low<high) S->rhigh-.key=S->rlow.key; /*將比支點(diǎn)（軸值）記錄大的交換到高端*/ S->rlow.key=S->r0.key; /*支點(diǎn)（軸值）記錄到位*/ pivotloc=low; /*將待排序序列一分為二*/ QuickSort(S,left,pivotloc-1); /*對(duì)小于軸值序列實(shí)現(xiàn)遞歸排序*/ QuickSort(S,pivotloc+1,right); /*對(duì)大于軸值序列實(shí)現(xiàn)遞歸

34、排序*/ int BinSearch(SqList *S,KeyType k) /* 在表S中用折半查找法查找關(guān)鍵字k，若查找成功，則函數(shù)值為該元素在表中的位置，若查找失敗，返回0。*/ int low,mid,high; low=1;high=S->length; while(low<=high) mid=(low+high)/2; /* 取區(qū)間中點(diǎn) */ if (S->rmid.key=k)return(mid); /* 查找成功 */ else if (S->rmid.key>k)high=mid-1; /* 在左區(qū)間中查找 */ else low=mid+

35、1; /* 在右區(qū)間中查找 */ return(0); /* 查找失敗 */main() int i,key,res; SqList SortObject=0,49,2,19,25,36,5,72,60,41,52,28,10,44,37,14,32,8,76,81,19; printf("Before sort:n"); for(i=1;i<=19;i+) /*輸出原表*/ printf("%4d",SortObject.ri); printf("n"); /*下面對(duì)排序?qū)ο筮M(jìn)行快速排序*/ QuickSort(&So

36、rtObject,1,SortObject.length); printf("After sort:n"); for(i=1;i<=19;i+) /*輸出排序后的表*/ printf("%4d",SortObject.ri); printf("n"); /*下面在排序后的表中用二分查找法查找19和26*/ key=19; printf("scarch %d:",key); res=BinSearch(&SortObject,key); if(res)printf("success!loc=%

37、dn",res); else printf("no found"); key=26; printf("scarch %d:",key); res=BinSearch(&SortObject,key); if(res)printf("success!loc=%dn",res); else printf("no found!n"); getch();參考程序運(yùn)行結(jié)果：實(shí)驗(yàn)五：LINUX 下C語(yǔ)言使用、編譯與調(diào)試實(shí)驗(yàn)實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：演示 實(shí)驗(yàn)要求：必修 一、實(shí)驗(yàn)?zāi)康?1、復(fù)習(xí)C語(yǔ)言程序基本知識(shí)2

38、、練習(xí)并掌握UNIX提供的vi編輯器來(lái)編譯C程序3、學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序二、實(shí)驗(yàn)內(nèi)容 1、用vi編寫一個(gè)簡(jiǎn)單的、顯示"Hello,World!"的C程序，用gcc編譯并觀察編譯后的結(jié)果2、利用gdb調(diào)試該程序3、運(yùn)行生成的可執(zhí)行文件三、實(shí)驗(yàn)原理、方法和手段1、C語(yǔ)言使用簡(jiǎn)介L(zhǎng)INUX中包含了很多軟件開(kāi)發(fā)工具。它們中的很多是用于C和C+應(yīng)用程序開(kāi)發(fā)的。 C是一種能在UNIX的早期就被廣泛使用的通用編程語(yǔ)言。它最早是由Bell實(shí)驗(yàn)室的Dennis Ritchie為了UNIX的輔助開(kāi)發(fā)而寫的，從此C就成為世界上使用最廣泛的計(jì)算機(jī)語(yǔ)言。C能在編程領(lǐng)域里得到如此廣泛

39、支持的原因有：（1）它是一種非常通用的語(yǔ)言，并且它的語(yǔ)法和函數(shù)庫(kù)在不同的平臺(tái)上都是統(tǒng)一的，對(duì)開(kāi)發(fā)者非常有吸引力；（2）用C寫的程序執(zhí)行速度很快；（3）C是所有版本UNIX上的系統(tǒng)語(yǔ)言；2、文件編輯器vi vi是在UNIX 上被廣泛使用的中英文編輯軟件。vi是visual editor的縮寫，是UNIX提供給用戶的一個(gè)窗口化編輯環(huán)境。進(jìn)入vi，直接執(zhí)行vi編輯程序即可。例：$vi test.c顯示器出現(xiàn)vi的編輯窗口，同時(shí)vi會(huì)將文件復(fù)制一份至緩沖區(qū)（buffer）。vi先對(duì)緩沖區(qū)的文件進(jìn)行編輯，保留在磁盤中的文件則不變。編輯完成后，使用者可決定是否要取代原來(lái)舊有的文件。（1）vi的工作模式vi

40、提供二種工作模式：輸入模式（insert mode）和命令模式（command mode）。使用者進(jìn)入vi后，即處在命令模式下，此刻鍵入的任何字符皆被視為命令，可進(jìn)行刪除、修改、存盤等操作。要輸入信息，應(yīng)轉(zhuǎn)換到輸入模式。命令模式在輸入模式下，按ESC可切換到命令模式。命令模式下，可選用下列指令離開(kāi)vi：q!離開(kāi)vi，并放棄剛在緩沖區(qū)內(nèi)編輯的內(nèi)容：wq將緩沖區(qū)內(nèi)的資料寫入磁盤中，并離開(kāi)vi：ZZ同wq：x同wq：w將緩沖區(qū)內(nèi)的資料寫入磁盤中，但并不離開(kāi)vi：q離開(kāi)vi，若文件被修改過(guò)，則要被要求確認(rèn)是否放棄修改的內(nèi)容，此指令可與：w配合使用命令模式下光標(biāo)的移動(dòng) H左移一個(gè)字符J下移一個(gè)字符K上移

41、一個(gè)字符L右移一個(gè)字符0移至該行的首$移至該行的末移至該行的第一個(gè)字符處H移至窗口的第一列M移至窗口中間那一列L移至窗口的最后一列G移至該文件的最后一列W, W下一個(gè)單詞 (W 忽略標(biāo)點(diǎn))B, B 上一個(gè)單詞 (B 忽略標(biāo)點(diǎn))+移至下一列的第一個(gè)字符處-移至上一列的第一個(gè)字符處(移至該句首)移至該句末移至該段首移至該段末NG移至該文件的第n列N+移至光標(biāo)所在位置之后第n列n-移至光標(biāo)所在位置之前第n列輸入模式輸入以下命令即可進(jìn)入vi輸入模式：a(append) 在光標(biāo)之后加入資料A 在該行之末加入資料i(insert)在光標(biāo)之前加入資料I 在該行之首加入資料o(open)新增一行于該行之下，供

42、輸入資料用O新增一行于該行之上，供輸入資料用Dd刪除當(dāng)前光標(biāo)所在行X刪除當(dāng)前光標(biāo)字符X刪除當(dāng)前光標(biāo)之前字符U撤消·重做F查找s 替換,例如:將文件中的所有"FOX"換成"duck",用":%s/FOX/duck/g"ESC離開(kāi)輸入模式更多用法見(jiàn) info vi3、GNU C編譯器LINUX上可用的C編譯器是GNU C編譯器，它建立在自由軟件基金會(huì)編程許可證的基礎(chǔ)上，因此可以自由發(fā)布。LINUX 上的GNU C編譯器（GCC）是一個(gè)全功能的ANCI C兼容編譯器，而一般UNIX（如SCO UNIX）用的編譯器是CC。下面介紹G

43、CC和一些GCC編譯器最常用的選項(xiàng)。(1)、使用GCC通常后跟一些選項(xiàng)和文件名來(lái)使用GCC編譯器。GCC命令的基本用法如下： gcc options filenames命令行選項(xiàng)指定的編譯過(guò)程中的具體操作(2)、GCC常用選項(xiàng)GCC有超過(guò)100個(gè)的編譯選項(xiàng)可用，這些選項(xiàng)中的許多可能永遠(yuǎn)都不會(huì)用到，但一些主要的選項(xiàng)將會(huì)頻繁使用。很多的GCC選項(xiàng)包括一個(gè)以上的字符，因此必須為每個(gè)選項(xiàng)指定各自的連字符，并且就像大多數(shù)LINUX 命令一樣不能在一個(gè)單獨(dú)的連字符后跟一組選項(xiàng)。例如，下面的命令是不同的：gcc -p-g test.cgcc -pg test.c第一條命令告訴GCC編譯test.c時(shí)為pro

44、f命令建立剖析（profile）信息并且把調(diào)試信息加入到可執(zhí)行文件里。第二條命令告訴GCC只為gprof命令建立剖析信息。當(dāng)不用任何選項(xiàng)編譯一個(gè)程序時(shí)，GCC將建立（假定編譯成功）一個(gè)名為a.out的可執(zhí)行文件。例如， gcc test.c編譯成功后，當(dāng)前目錄下就產(chǎn)生了一個(gè)a.out文件。也可用-o選項(xiàng)來(lái)為即將產(chǎn)生的可執(zhí)行文件指定一個(gè)文件名來(lái)代替a.out。例如：gcc -o count count.c此時(shí)得到的可執(zhí)行文件就不再是a.out，而是count。GCC也可以指定編譯器處理步驟多少。-c選項(xiàng)告訴GCC僅把源代碼編譯為目標(biāo)代碼而跳過(guò)匯編和連接步驟。這個(gè)選項(xiàng)使用得非常頻繁因?yàn)樗幾g多個(gè)C

45、程序時(shí)速度更快且更易于管理。默認(rèn)時(shí)GCC建立的目標(biāo)代碼文件有一個(gè).o的擴(kuò)展名。3、執(zhí)行文件 格式：./可執(zhí)行文件名例：./a.out ./count4、gdb調(diào)試工具LINUX包含了一個(gè)叫g(shù)db的GNU調(diào)試程序。gdb是一個(gè)用來(lái)調(diào)試C和C+程序的強(qiáng)有力調(diào)試器。它使你能在程序運(yùn)行時(shí)觀察程序的內(nèi)部結(jié)構(gòu)和內(nèi)存的使用情況。它具有以下一些功能：·監(jiān)視程序中變量的值；·設(shè)置斷點(diǎn)以使程序在指定的代碼行上停止執(zhí)行；·一行行的執(zhí)行代碼。以下是利用gdb進(jìn)行調(diào)試的步驟：(1)、調(diào)試編譯代碼為了使gdb正常工作，必須使你的程序在編譯時(shí)包含調(diào)試信息。調(diào)試信息里包含你程序里的每個(gè)變量的類型

46、和在可執(zhí)行文件里的地址映射以及源代碼的行號(hào)。gdb利用這些信息使源代碼和機(jī)器碼相關(guān)聯(lián)。在編譯時(shí)用 -g 選項(xiàng)打開(kāi)調(diào)試選項(xiàng)。(2)、gdb基本命令命令描述file裝入欲調(diào)試的可執(zhí)行文件kill終止正在調(diào)試的程序list列出產(chǎn)生執(zhí)行文件的源代碼部分next執(zhí)行一行源代碼但不進(jìn)入函數(shù)內(nèi)部step執(zhí)行一行源代碼并進(jìn)入函數(shù)內(nèi)部run執(zhí)行當(dāng)前被調(diào)試的程序quit終止gdbwatch監(jiān)視一個(gè)變量的值而不管它何時(shí)被改變break在代碼里設(shè)置斷點(diǎn)，使程序執(zhí)行到這里時(shí)被掛起make不退出gdb就可以重新產(chǎn)生可執(zhí)行文件shell不離開(kāi)gdb就執(zhí)行UNIX shell 命令(3)、應(yīng)用舉例設(shè)有一源程序greet.c)

47、編譯，gcc -ggdb -o greet greet.c，出錯(cuò)gdb greet ，出現(xiàn)提示符(gdb)，此時(shí)可在提示符下輸入gdb的命令了，如：(gdb)run(gdb)list)退出調(diào)試狀態(tài)，返回系統(tǒng)提示符下， (gdb)quit4、參考程序main( ) printf("Hello,world!n");四、實(shí)驗(yàn)組織運(yùn)行要求 采用以學(xué)生自主訓(xùn)練為主的開(kāi)放模式組織教學(xué)，教師予以答疑與指導(dǎo)。 五、實(shí)驗(yàn)條件 PC機(jī)一臺(tái)、Linux環(huán)境、C語(yǔ)言環(huán)境 六、實(shí)驗(yàn)步驟 (1)、將提前準(zhǔn)備好的源程序錄入計(jì)算機(jī)； (2)、調(diào)試源程序，修正錯(cuò)誤，記錄實(shí)驗(yàn)數(shù)據(jù)； (3)、分析運(yùn)行結(jié)果，驗(yàn)證所編程序是否正確。 七、思考題 (1)、在Linux環(huán)境下如何創(chuàng)建一個(gè)新進(jìn)程？(2)、如何啟動(dòng)linux環(huán)境下telnet服務(wù)？ 八、實(shí)驗(yàn)報(bào)告 (1)、實(shí)驗(yàn)預(yù)習(xí)：仔細(xì)閱讀實(shí)驗(yàn)指導(dǎo)書，熟悉linux運(yùn)行環(huán)境和C語(yǔ)言中開(kāi)發(fā)環(huán)境內(nèi)容。 (2)、實(shí)驗(yàn)記錄的內(nèi)容應(yīng)包括源程序、實(shí)驗(yàn)數(shù)據(jù)和運(yùn)行結(jié)果。 (3)、實(shí)驗(yàn)結(jié)論部分的內(nèi)容應(yīng)包括對(duì)實(shí)驗(yàn)結(jié)果的分析和總結(jié)，回答思考題。 實(shí)驗(yàn)六 建立數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)數(shù)據(jù)編輯修改實(shí)驗(yàn)學(xué)時(shí)：2 實(shí)驗(yàn)類型：驗(yàn)證實(shí)驗(yàn)要求：必修 一、目的熟悉SQL Server2000數(shù)據(jù)庫(kù)開(kāi)發(fā)環(huán)境，了解