計算機軟件技術(shù)基礎(chǔ)實驗指導(dǎo)書

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

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

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

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

5、對實驗結(jié)果的分析和總結(jié)，回答思考題。 參考程序#include <stdio.h>typedef struct node int info; /*每個元素數(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é)點個數(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é)點，成功返回結(jié)點位置i及結(jié)點指針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é)點位置i*/ return(0);/*查找不成功，返回0*/int ins

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

9、返回0*/ return(0);int deletelink(pointer list, int x)/*刪除值為x的結(jié)點*/ 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);/*通過鏈表輸出，檢查鏈表建立的情況*/ /*查找*/ printf("nInput the data of index:"); scanf("%d",&x);/*輸入待查找的結(jié)點值*/ k=index(h,x,&p);/*在鏈表h中查找值為x的結(jié)點*/ 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é)點后，插入一個值為120的結(jié)點*/ 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é)果*/參考程序運行結(jié)果：實驗二：二叉樹的創(chuàng)建與遍歷實驗 實驗學(xué)時：2 實驗類型：驗證 實驗要求：必修 一、實驗?zāi)康?通過本實驗的學(xué)習(xí)，使學(xué)生主要練習(xí)二叉樹的鏈表存儲的實現(xiàn)及二叉樹的基本操作，為繼續(xù)學(xué)習(xí)后續(xù)章節(jié)圖的內(nèi)容奠定基礎(chǔ)。 二、實驗內(nèi)容 (1)、二叉樹的二叉鏈表結(jié)構(gòu)的建立； (2)、寫一個二

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

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

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

16、tchar(); if (ch='0')t=NULL; /*讀入0時，將相應(yīng)結(jié)點指針置空*/ else t=(Bnode *)malloc(sizeof(Bnode); /* 生成結(jié)點空間 */ 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();參考程序運行結(jié)果：實驗三：圖的鄰接矩陣結(jié)構(gòu)的創(chuàng)建和圖的遍歷實驗學(xué)時：2 實驗類型：驗證實驗要求：必修 一、實驗?zāi)康?通過本實驗，使學(xué)生掌握圖的基本存儲方法，特別是圖的鄰接矩陣存儲結(jié)構(gòu)，學(xué)會圖的鄰接矩陣結(jié)構(gòu)的創(chuàng)建。掌握圖的遍歷算法，并在圖的鄰接矩陣結(jié)構(gòu)下用高級語言實現(xiàn)。二、實驗內(nèi)容 1、 使用圖的鄰接

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

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

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

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

23、存儲 */ int i,j,k; printf("Input vexters number & edges number:"); scanf("%d,%d",&(G->n),&(G->e); /* 輸入頂點數(shù)和邊數(shù) */ printf("Input vexters information:"); getchar(); /*此句接收掉上一個輸入的尾字符，保證下面輸入的正確執(zhí)行*/ for(i=0;i<(G->n);i+) /* 輸入頂點信息，建立頂點表 */ 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(); /*此句接收掉上一個輸入的尾字符，保證下面輸入的正確執(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個頂點出發(fā)深度優(yōu)先遍歷圖G */ int w; printf("%c->",G.vexsv); visitedv=True; /* 訪問第v個頂點 */ /*下面對v

26、尚未訪問的鄰接頂點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();以下圖為例的測試結(jié)果：實驗四：查找與排序?qū)嶒瀸嶒瀸W(xué)時：2 實驗類型：驗證實驗要求：必修 一、實驗?zāi)康?查找與排序是計算機最頻繁的操作，而排序與查找又是兩個密切相關(guān)的技術(shù)，有效的數(shù)據(jù)組織可以提高查找的效率。通過本實驗，使學(xué)生加深對查找操作的基本概念、性質(zhì)，內(nèi)部排序操作的方法、特點的理解，培養(yǎng)學(xué)生利用查找和排序方

27、面知識解決問題的能力，為后繼課程的學(xué)習(xí)奠定基礎(chǔ)。 二、實驗內(nèi)容 5、 試編寫一程序，用快速分類算法對下面數(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，并輸出查找信息。寫出各操作的實現(xiàn)函數(shù)，并上機驗證。 三、實驗原理、方法和手段 順序查找的基本方法是從表的一端開始，順序掃描數(shù)據(jù)表，依次將掃描到的結(jié)點關(guān)鍵字和給定值K相比較。若當(dāng)前掃描到的結(jié)點關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點，則查找失敗。但順序查找效率底，如果順序表中的數(shù)據(jù)元素按關(guān)鍵字

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

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

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

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

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

33、while(low<high && S->rlow.key<=pivotkey) low+; if(low<high) S->rhigh-.key=S->rlow.key; /*將比支點（軸值）記錄大的交換到高端*/ S->rlow.key=S->r0.key; /*支點（軸值）記錄到位*/ pivotloc=low; /*將待排序序列一分為二*/ QuickSort(S,left,pivotloc-1); /*對小于軸值序列實現(xiàn)遞歸排序*/ QuickSort(S,pivotloc+1,right); /*對大于軸值序列實現(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ū)間中點 */ 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"); /*下面對排序?qū)ο筮M行快速排序*/ 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();參考程序運行結(jié)果：實驗五：LINUX 下C語言使用、編譯與調(diào)試實驗實驗學(xué)時：2 實驗類型：演示 實驗要求：必修 一、實驗?zāi)康?1、復(fù)習(xí)C語言程序基本知識2

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

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

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

41、一個字符L右移一個字符0移至該行的首$移至該行的末移至該行的第一個字符處H移至窗口的第一列M移至窗口中間那一列L移至窗口的最后一列G移至該文件的最后一列W, W下一個單詞 (W 忽略標(biāo)點)B, B 上一個單詞 (B 忽略標(biāo)點)+移至下一列的第一個字符處-移至上一列的第一個字符處(移至該句首)移至該句末移至該段首移至該段末NG移至該文件的第n列N+移至光標(biāo)所在位置之后第n列n-移至光標(biāo)所在位置之前第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離開輸入模式更多用法見 info vi3、GNU C編譯器LINUX上可用的C編譯器是GNU C編譯器，它建立在自由軟件基金會編程許可證的基礎(chǔ)上，因此可以自由發(fā)布。LINUX 上的GNU C編譯器（GCC）是一個全功能的ANCI C兼容編譯器，而一般UNIX（如SCO UNIX）用的編譯器是CC。下面介紹G

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

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

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

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

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