《數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)》實(shí)驗(yàn)指導(dǎo)書（合集）

1、上機(jī)實(shí)驗(yàn)1多項(xiàng)式的數(shù)組表示及運(yùn)算【實(shí)驗(yàn)?zāi)康摹浚?）學(xué)會(huì)用簡(jiǎn)單數(shù)據(jù)類型描述復(fù)合數(shù)據(jù)類型。（2）學(xué)會(huì)用數(shù)組來(lái)表示多項(xiàng)式。（3）學(xué)會(huì)建立新的數(shù)據(jù)結(jié)構(gòu)?！緦?shí)驗(yàn)內(nèi)容】用數(shù)組來(lái)表示多項(xiàng)式，多項(xiàng)式表示為：Pn（X）= piXel + p2Xe2 + pmXemo其中，Pi是指數(shù)為ei的項(xiàng)的非零系數(shù)，且滿足OW eie2 em= no為了方便計(jì)算 機(jī)實(shí)現(xiàn)多項(xiàng)式的存取，有多項(xiàng)式：F（x）=9x9+x8-7x6+4x3-25x+2將F（x）存入數(shù)組中，并在控制臺(tái)顯示。【實(shí)驗(yàn)步驟】（1）建立多項(xiàng)式項(xiàng)的數(shù)據(jù)結(jié)構(gòu)，使用結(jié)構(gòu)體來(lái)表示多項(xiàng)式的每一項(xiàng)。（2）定義多項(xiàng)式的數(shù)組，完成多項(xiàng)式的輸入與輸出。（3）代碼實(shí)現(xiàn)。【參考源代

2、碼】項(xiàng)的表示系數(shù)指數(shù)項(xiàng)的表示系數(shù)指數(shù)typedef struct int coef; int expn; polynomial;#include#define MAX 100多項(xiàng)式輸入函數(shù)的聲明多項(xiàng)式輸出函數(shù)的聲明void InputPolyO;void OutputPoIy(polynomial aPoly);polynomial aPolyMAX;void main()(InputPolyO;OutputPoly(aPoly);)void InputPolyO上機(jī)實(shí)驗(yàn)4二叉樹的遍歷【實(shí)驗(yàn)?zāi)康摹?1)掌握指針變量的含義及使用方法。(2)熟悉二叉樹結(jié)點(diǎn)的結(jié)構(gòu)。(3)掌握二叉樹每一種操作具體實(shí)現(xiàn)

3、的方法。(4)學(xué)會(huì)利用遞歸的方法實(shí)現(xiàn)二叉樹的遍歷算法。【實(shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)對(duì)二叉樹的如下操作：(1)創(chuàng)立二叉樹。(2)先序遍歷二叉樹。(3)中序遍歷二叉樹。(4)后序遍歷二叉樹。(5)按層遍歷二叉樹。要求能夠從鍵盤上輸入建樹的結(jié)點(diǎn)內(nèi)容，并且將遍歷的結(jié)果輸出在屏幕上。【實(shí)驗(yàn)步驟】(1)在Microsoft Visual C+中創(chuàng)立應(yīng)用程序L4。(2)在程序中創(chuàng)立二叉樹的存儲(chǔ)結(jié)構(gòu)BiTNode,以鏈表作為存儲(chǔ)結(jié)構(gòu)。(3)創(chuàng)立CreateBiTree()函數(shù)，實(shí)現(xiàn)創(chuàng)立二叉樹的操作，能夠按先序次序從鍵盤輸入結(jié) 點(diǎn)內(nèi)容，空格表示空樹。(4)創(chuàng)立PreOrderTraverse。函數(shù)，用遞歸的方法實(shí)現(xiàn)先序遍歷

4、二叉樹的操作。(5)創(chuàng)立InOrdeiTraverse。函數(shù)，用遞歸的方法實(shí)現(xiàn)中序遍歷二叉樹的操作。(6)創(chuàng)立PostOrdeiTraverse()函數(shù)，用遞歸的方法實(shí)現(xiàn)后序遍歷二叉樹的操作。(7)創(chuàng)立LevelOrderTraverse。函數(shù)，實(shí)現(xiàn)按層遍歷二叉樹的操作。(8)創(chuàng)立主函數(shù)，用switch語(yǔ)句實(shí)現(xiàn)從鍵盤上輸入字符，選擇要執(zhí)行的操作。(9)編譯連接程序，執(zhí)行并觀察程序的運(yùn)行效果?！緟⒖荚创a】#include stdlib.h#include nstdio.hntypedef struct BiTNodechar data;struct BiTNode *lchild,*rchil

5、d;BiTNode,* BiTree;void CreateB iTree(B iTree &T)/按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T,空格表示空樹char ch;scanf(H%cn,&ch);if(ch=p T=NULL;elseif (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(-l);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);)/CreateBiTreevoid PreOrderTraverse(B iTree T) 先序遍歷if(T)printfC%c n,T-dat

6、a);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);)/PreOrderTra versevoid InOrderTraverse(BiTree T) 中序遍歷if(T)InOrderTraverse(T-lchild);printf(u%c n,T-data);InOrderTraverse(T-rchild);) /InOrderTraversevoid PostOrderTraverse(BiTree T) 后序遍歷if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rch

7、ild);printf(n%c n,T-data);) /PostOrderTraversevoid LevelOrderTraverse(B iTree T) 按層遍歷const int MaxLength=100;BiTree QMaxLength|;QO=T；int front=0,rear=l; while(frontdata); Q rear+=Q front -lchild; Q rear+=Q front -rchild; front+4-;) else front+;) /Level OrderTraversevoid main()(BiTree T=NULL;char sel

8、ect;while(l)printf(請(qǐng)選擇要執(zhí)行的操作：nn);printf(l .創(chuàng)立二叉樹 n)printf(“2.二叉樹的遞歸遍歷算法(前、中、后)n”)；printf(3.二叉樹的層序遍歷算法n);printf(0 .退出 n); fflush(stdin);scanf(n%cn,&select);fflush(stdin); switch(select) (case *0*:return;case T:printf(”請(qǐng)按先序次序輸入各結(jié)點(diǎn)的值，以空格表示空樹(輸入時(shí)可連續(xù)輸入)：nn);CreateBiTree(T);printf(nnM);break;case 2:printf

9、(先序遍歷PreOrderTraverse(T);printf(n 中序遍歷:)；InOrderTraverse(T);printf(n 后序遍歷PostOrderTraverse(T);printf(HnnH);break;case 3:printf(層序遍歷LevelOrderTraverse(T);printf(Hnnn);break;default:printf(請(qǐng)確認(rèn)選擇項(xiàng)八nn);/end switch/end while/end main【實(shí)驗(yàn)結(jié)果】運(yùn)行例如：構(gòu)建如下二叉樹，并且將其遍歷的結(jié)果輸出在屏幕上。步驟1：輸入1,按Enter鍵，等待創(chuàng)立二叉樹。步驟2：按先序方式構(gòu)建二叉

10、樹，輸入：abd(空兩格)e(空兩格)c(空兩格)，按Enter鍵確認(rèn) 輸入。步驟3：輸入2,按Enter鍵，觀察顯示結(jié)果。步驟4：輸入3,按Enter鍵，觀察顯示結(jié)果。步驟5：輸入0,退出循環(huán)程序。運(yùn)行結(jié)果如附圖4所示。要執(zhí)行的操作二叉2愧序遍歷:a b d e c 中任遍歷:d b e a c 后序遍歷:d e b c a精選岑 k .創(chuàng)缸 卡.二叉機(jī)的遞歸遍歷 5 .二叉樹的層序遍歷1(刖、禮后)中、后)cr C:INDOSsyste-32cd. exe附圖4上機(jī)實(shí)驗(yàn)4運(yùn)行結(jié)果作 操 的一tW層 執(zhí)見的的 要二M g叉叉出 選創(chuàng)二二退 f - - - L 二12303后中一層 執(zhí)叉的的

11、要二作 操 的g叉叉出 選創(chuàng)二二退 請(qǐng)1.B.3.S;歷歷 遍遍 歸序常選接要執(zhí)丘的操作：k創(chuàng)硅二叉樹，,二叉狗的襦歸遍歷篡花(前、中、后)藤叉樹的層序遍歷算法按先序次序輸入各結(jié)點(diǎn)的值，以空格表示空樹輸入時(shí)可連續(xù)輸入)： abd e c(前、歷歷 遍遍【實(shí)驗(yàn)總結(jié)】在創(chuàng)立二叉樹時(shí)應(yīng)注意程序的編寫，在參考程序中，使用空格來(lái)表示空樹、所以在創(chuàng)立 時(shí)，如果結(jié)點(diǎn)的子樹為空時(shí)，一定要輸入空格，方能成功創(chuàng)立二叉樹。當(dāng)然，也可用其他的 字符(如“肥)代替空格表示空樹，但是一定要在程序中進(jìn)行相應(yīng)的編寫與說(shuō)明。參考程序中，在主程序中先創(chuàng)立了一個(gè)空樹T,然后調(diào)用CreateBiTree()創(chuàng)立二叉樹，由 于T需要在

12、后面進(jìn)行遍歷，它的內(nèi)容要求是可以返回的，所以必須使用引用調(diào)用，在創(chuàng)立 CreateBiTree。時(shí)應(yīng)注意形參的設(shè)置。編程時(shí)尤其應(yīng)注意scanf()函數(shù)的c “格式帶來(lái)的緩沖區(qū)的問(wèn)題，因?yàn)槭褂?c “格式接收 的是字符，空格和轉(zhuǎn)義字符都為有效字符。而創(chuàng)立二叉樹時(shí)，完成輸入后有一個(gè)回車操作表 示結(jié)束輸入、創(chuàng)立完成，這個(gè)時(shí)候一定不要忘了使用“fflush(stdin)； ”語(yǔ)句來(lái)清空緩沖區(qū)，否 那么會(huì)將回車符作為一個(gè)字符接收，這樣可能會(huì)造成后續(xù)程序出問(wèn)題。建議使用scanf()函數(shù)的 “c”格式接收一個(gè)字符時(shí)，要在其后加上“fflush(stdin)； ”語(yǔ)句，這樣能防止問(wèn)題的出現(xiàn)。但 在參考程序中

13、，CreateBiTree。函數(shù)中的scanf()后并沒(méi)有“fflush(stdin)； ，這樣做是為了能連 續(xù)從鍵盤獲取字符，并且把空格也作為字符接收，但是在完成創(chuàng)立后，后面的scanf()函數(shù)在 接收字符前必須使用“fflush(stdin)； ”完成緩沖區(qū)的清空操作。上機(jī)實(shí)驗(yàn)6哈夫曼編碼【實(shí)驗(yàn)?zāi)康摹?1)熟悉哈夫曼樹的存儲(chǔ)結(jié)構(gòu)。(2)掌握哈夫曼樹構(gòu)建的算法。(3)掌握哈夫曼樹的遍歷方法。(4)掌握哈夫曼編碼算法?！緦?shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)哈夫曼編碼算法：根據(jù)給定的權(quán)值數(shù)組，構(gòu)建帶權(quán)路徑長(zhǎng)度最小的哈夫曼樹，然后 輸出對(duì)應(yīng)的哈夫曼編碼?！緦?shí)驗(yàn)步驟】(1)在Microsoft Visual C+中創(chuàng)立應(yīng)

14、用程序L6。(2)在程序中定義哈夫曼樹的存儲(chǔ)結(jié)構(gòu)tnodepointer。(3)編寫函數(shù)select。,實(shí)現(xiàn)在給定的n個(gè)元素的結(jié)點(diǎn)數(shù)組中，找出權(quán)值最小的兩個(gè)元素， 返回其下標(biāo)。(4)編寫huffmancoding。，實(shí)現(xiàn)構(gòu)建哈夫曼樹，并返回哈夫曼編碼。(5)編寫哈夫曼編碼的輸出函數(shù)output。(6)編寫主函數(shù)，初始化結(jié)點(diǎn)的權(quán)值數(shù)組，調(diào)用huffmancoding()函數(shù)，輸出哈夫曼編碼。(7)編譯連接程序，執(zhí)行并觀察程序的運(yùn)行效果?！緟⒖荚创a】#include #include #include typedef struct哈夫曼樹結(jié)點(diǎn)的類型int weight,parent,lchild

15、,rchild; tnode,tnodepointer;void select(tnodepointer HT,int n,int &sl,int &s2)在數(shù)組HT的前n個(gè)parents的元素中，找出權(quán)最小的兩個(gè)元素并將其下標(biāo)分別賦給si、 s2int i;sl=0;for(i=0;in&HTi.parent !=0;i+)略過(guò)已經(jīng)加入樹的結(jié)點(diǎn)sl=i+l;for(i=0;in;i+)用s 1保存權(quán)最小的元素的下標(biāo)if(HTi. weightHTs 1. weight&HTi .parent=0)sl=i;s2=0;for(i=0;in&(s2=sl |HTi,parent !=0);i+)

16、 s2 = i+1;for(i=0;in;i+)用s2保存權(quán)次小的元素的下標(biāo)if(HTi.weightweight =*w;TEMP-parent = 0;TEMP-lchild = 0;TEMP-rchild = 0; ) for(intm=2*n-l;TEMPparent =0;for(int i=n;i2*n-l;i+)/設(shè)置各個(gè)結(jié)點(diǎn)的值，構(gòu)建哈夫曼樹( int sl,s2; select(HT,i,sl,s2); /在數(shù)組HT的前n個(gè)parent=0的元素中，找出權(quán)最小的兩個(gè) 元素并將其下標(biāo)分別賦給si、s2HTsl.parent =i;HTs2.parent =i;HTi.lchil

17、d =sl;HTi.rchild =s2;HTi.weight =HTsl.weight +HTs2.weight;)char *str=(char *)malloc(n*sizeof(char);/str用于臨時(shí)存放哈夫曼編碼char *huffmancode=(char *)maUoc(n*sizeof(char *);for(int i=0;in;i+)構(gòu)建哈夫曼編碼int start=n-1;strstart=,O,;int c=i,temp=HTc.parent;t em p=0表示該結(jié)點(diǎn)為根結(jié)點(diǎn)t em p=0表示該結(jié)點(diǎn)為根結(jié)點(diǎn)while(temp!=O)if(HTtemp.lch

18、ild =c)str-start=O；elsestr-start-T;c=temp;temp=HTc.parent;huffmancodei=(char*)malloc(n-start)*sizeof(char); strcpy(huffmancodei,&strstart);)free (HT);free(str);return huffmancode;void output(char *p,int n)void output(char *p,int n)輸出數(shù)組p中各元素指向的字符串for(int i=0;in;i+)printf(n%s n,pi);printf(nnn);void ma

19、in()/測(cè)試int w卜5,29,7,8,14,23,3,11;char *p=huffmancoding(w,8);printf(與權(quán)值對(duì)應(yīng)的huffman編碼為：n);output(p,8);)【運(yùn)行結(jié)果】參考源碼中設(shè)置的權(quán)值為w=5,29,7,8,14,23,3,11程序運(yùn)行結(jié)果如附圖7所示。c、C: I!0)0TSsyst e32cd. exe與權(quán)值對(duì)應(yīng)的huf f man編科 為:0001 10 1110 1111 110 01 0000 001請(qǐng)按任意鍵繼續(xù). . 附圖7上機(jī)實(shí)驗(yàn)6運(yùn)行結(jié)果【實(shí)驗(yàn)總結(jié)】該算法的關(guān)鍵之一是select。函數(shù)的實(shí)現(xiàn)，即如何在給定的n個(gè)元素的結(jié)點(diǎn)數(shù)組中，

20、找出 權(quán)值最小的兩個(gè)元素，返回其下標(biāo)。構(gòu)建哈夫曼樹時(shí)，利用了哈夫曼樹的鏈接表來(lái)保存樹的左右孩子信息和父結(jié)點(diǎn)信息。在返回哈夫曼編碼時(shí)，從樹根遍歷到樹的葉子結(jié)點(diǎn)，這樣逆向構(gòu)建哈夫曼編碼。上機(jī)實(shí)驗(yàn)7快速排序【實(shí)驗(yàn)?zāi)康摹?1) 了解內(nèi)部排序的方法。(2)掌握快速排序的基本思想。(3)學(xué)會(huì)用快速排序?qū)崿F(xiàn)對(duì)無(wú)序數(shù)組的排序。(4)比照不同排序方法的優(yōu)劣?！緦?shí)驗(yàn)內(nèi)容】(1)使用快速排序算法將無(wú)序數(shù)列(10,168,23,7,67,5,4,45,0,97)按由小到大順序排列， 并在屏幕顯示。(2)在上述實(shí)驗(yàn)的基礎(chǔ)上，統(tǒng)計(jì)排序的次數(shù)并比擬快速排序與其他排序的優(yōu)劣?！緦?shí)驗(yàn)步驟】(1)分析快速排序的基本思想，通過(guò)一趟

21、排序?qū)⒋庞涗浄指畛瑟?dú)立的兩個(gè)局部，其 中一局部記錄的關(guān)鍵字均比另一局部記錄的關(guān)鍵字小，那么可分別對(duì)這兩局部記錄繼續(xù)進(jìn)行排 序，以使整個(gè)序列有序。(2)選取數(shù)組中的一個(gè)記錄作為樞軸(或支點(diǎn))，建議選擇數(shù)組元素的中間數(shù)。(3)代碼實(shí)現(xiàn)?！緟⒖荚创a】#include #define N 10int count=0;int Partition(int a,int low,int high)(int privotlndex = (low+high)/2; 中間數(shù)int temp=aprivotlndex;count+;printf(第(1次中間數(shù):%dnn,count,temp);aprivotTn

22、dex=ahigh;ahigh=temp;int pivotkey=temp;while(lowhigh)(while(lowhigh&alow=pivotkey)+low;ahigh=alow;while(low=pivotkey)-high;printf(多項(xiàng)式的建立11輸入一元多項(xiàng)式(以0, 0標(biāo)志結(jié)束)n)；prints系數(shù)與指數(shù)之間用空格，輸完后按回車。n)int i=0;do (printf(第d項(xiàng)系數(shù)和指數(shù)：”,i+l);scanf(,%d%d,&aPolyi.coef,&aPolyi.expn);if(aPolyi.coef=0&aPolyi.expn=0) break;i+；

23、while (i0)printf(n%d%s%dn,aItem0.coef,nxAn,aItem0.expn);else if(aItem0.expn=0) printf(n %dn,aItem0 .coef);elseprintf(d%s%c%d%c”,altem0.coefjx/v?(,altem0.expn,);)for(int i = 1; i != MAX; i+) (if(altemi.coef0)(if(aItemi.expn0)printf(n%c%d%s%dn/+aItemi.coef,nxA，aItemi.expn);else if(altemi.expn=0)printf

24、(,%c%d7+altemi.coef);elseprintf(”c%d%s%c%d%c,altemi.coefjx 八 altemi.expn,); )else if(altemi.coef0)alow=ahigh;)ahigh=pivotkey;printf(第 d 次排序結(jié)果:,count);for(int i=0;iN;+i)printf(n%d n,ai);printf(nnn);return high;)void QuickSort(int a| ,int low,int high)int pivotloc;if(lowhigh)(pivotloc=Partition(a,low,

25、high);QuickSort(a,low,pivotloc-1);QuickSort(a,pivotloc+1 ,high);)void main()int dataN= 10,168,23,7,67,5,4,45,0,97;printf(原始的無(wú)序數(shù)組：”)；for(int i=0;iN;+i)printf(u%d n,datai);printf(nnn);QuickSort(data,0,N-1);printf(由小到大的有序數(shù)組：”)；for(int i=0;i:184組.。數(shù).168234 75 75 75 75 7：023 7 677 45 5 445 23 1045 23 104

26、5 23 1010 23 4510 23 454 5 7 105 4 45 0 9767 97 16867 97 16867 97 16867 97 16867 97 16867 97 16823 45 67 97 1682d附圖8上機(jī)實(shí)驗(yàn)7運(yùn)行結(jié)果【實(shí)驗(yàn)總結(jié)】快速排序是交換排序的另一種方法，是對(duì)冒泡排序的一種改進(jìn)。通過(guò)對(duì)快速排序算法的 實(shí)現(xiàn)，進(jìn)一步學(xué)習(xí)了交換排序算法的基本思想?？焖倥判虻钠骄鶗r(shí)間為Aver(n)=nlog2n,其 中n為待排序列中記錄的個(gè)數(shù)。實(shí)驗(yàn)證明，在同數(shù)量級(jí)的排序中，就平均時(shí)間而言，快速排序是目前被認(rèn)為最好的一種 內(nèi)部排序方法。上機(jī)實(shí)驗(yàn)8折半查找【實(shí)驗(yàn)?zāi)康摹?1)熟悉順序

27、存儲(chǔ)結(jié)構(gòu)。(2)掌握查找的有關(guān)方法。(3)學(xué)會(huì)分析查找的性能。(4)掌握折半查找算法的實(shí)現(xiàn)方法?！緦?shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)折半查找算法：要求能夠?qū)崿F(xiàn)用戶從鍵盤輸入一個(gè)有序的整數(shù)數(shù)組，然后從鍵盤指 定一個(gè)整型的搜索值n,如果找到，那么在屏幕輸出該值的位置，否那么，輸出“沒(méi)有找到搜索值 n”?！緦?shí)驗(yàn)步驟】(1)在Microsoft Visual C+中創(chuàng)立應(yīng)用程序L8。(2)創(chuàng)立折半查找函數(shù)BinarySearch。，實(shí)現(xiàn)折半查找算法。(3)創(chuàng)立主函數(shù)，實(shí)現(xiàn)從鍵盤上輸入數(shù)據(jù)創(chuàng)立一個(gè)按從低到高排列的整型數(shù)組，并且 調(diào)用B inary Search。完成查找。(4)編譯連接程序，執(zhí)行并觀察程序的運(yùn)行結(jié)果?！緟⒖?/p>

28、源代碼】#include #include #define MAX 10int BinarySearch(int a,int key) 折半查找int low=0;int high=MAX;while(lowa|mid|) low=mid+l;else high二mid-1;)return -1;/Binary Searchvoid main()int found,value,aMAX;printf(”請(qǐng)按從低到高的順序輸入10個(gè)整型數(shù)據(jù)，以空格分隔，回車結(jié)束：n) for(int i=0;i32d. eze-|口316 ，布 9 8 3 5 0 0 X - 0空 91T4-220F- 蜘期珈

29、如期蜘江短 TH僅匕日匕日匕日匕日匕日匕日匕日7分一 立項(xiàng)之繼 如系系系系系系普 貯需瑞瑞喘酸附圖1上機(jī)實(shí)驗(yàn)1運(yùn)行結(jié)果【實(shí)驗(yàn)總結(jié)】通過(guò)多項(xiàng)式的數(shù)組表示及運(yùn)算的實(shí)驗(yàn),讀者應(yīng)初步學(xué)會(huì)用簡(jiǎn)單數(shù)據(jù)類型描述復(fù)合數(shù)據(jù)類 型。作為數(shù)據(jù)結(jié)構(gòu)的第一個(gè)實(shí)驗(yàn)，認(rèn)真掌握實(shí)驗(yàn)的開發(fā)環(huán)境，為后續(xù)實(shí)驗(yàn)打下基礎(chǔ)。上機(jī)實(shí)驗(yàn)2串的匹配算法及實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹?1) 了解串的相關(guān)概念。(2)掌握串的有關(guān)存儲(chǔ)方法。(3)熟悉串的基本操作。(4)通過(guò)串匹配算法的實(shí)現(xiàn)，掌握樸素的模式匹配算法。【實(shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)樸素的模式匹配算法：要求能夠?qū)崿F(xiàn)從鍵盤輸入主串S和子串T,并且能夠從鍵盤指 定S的第pos位為開始匹配的位置，如果匹配成功，那么在屏

30、幕輸出S中符合匹配的位置，即S中 與T匹配的子序列第一個(gè)字符的序號(hào)，否那么，返回0。【實(shí)驗(yàn)步驟】(1)在Microsoft Visual C+中創(chuàng)立應(yīng)用程序L2。(2)在程序中創(chuàng)立字符串的存儲(chǔ)函數(shù)InitStr。，使用數(shù)組的0號(hào)單元存儲(chǔ)字符串的長(zhǎng)度。(3)創(chuàng)立字符串的匹配函數(shù)Index。(4)創(chuàng)立主函數(shù)，實(shí)現(xiàn)從鍵盤上輸入主串S、子串T,并能夠指定開始匹配的位置。(5)編譯連接程序，執(zhí)行并觀察程序的運(yùn)行效果?！緟⒖荚创a】#include #include #define MAXSIZE 100/字符串的最大存儲(chǔ)長(zhǎng)度typedef char SStringMAXSIZE+l; / 使用0號(hào)單元存

31、儲(chǔ)長(zhǎng)度void InitStr(SString rs)char stmpMAXSIZE;int i;gets(stmp);rsO=strlen(stmp);for (i=l;i=rs0;i+)rsi=stmpi-l;rsi 尸 0;int Index(SString S, SString T, int pos)/返回T在S中第pos個(gè)字符后首次出現(xiàn)的位置，假設(shè)不存在那么返回0int i = posj = 1;while(i = S0 &jT0)return i-T0J;/匹配成功返回T在S中第pos個(gè)字符后首次出現(xiàn)的位置else return 0; / Indexvoid main ()(SS

32、tring sstr;SString dstr;int pos;int n;printf(請(qǐng)輸入主串：”)； InitStr(sstr);printf(請(qǐng)輸入子串:)； InitStr(dstr);printf(”請(qǐng)輸入開始匹配的位置：”); scanf(n%dn,&pos);n=Index(sstr, dstr, pos); printf(n%dnn,n);)【運(yùn)行結(jié)果】運(yùn)行例如：主串輸入：sit please子串輸入：please匹配位置輸入：2運(yùn)行結(jié)果如附圖2所示。c. C:VI!TOOSsyste32cd. exe請(qǐng)施入主串：sit please 請(qǐng)輸入子串：please 請(qǐng)輸入開始匹

33、配的位置：2主11任意鍵繼續(xù).附圖2上機(jī)實(shí)驗(yàn)2運(yùn)行結(jié)果【實(shí)驗(yàn)總結(jié)】編程時(shí)應(yīng)注意，存儲(chǔ)字符串有一個(gè)轉(zhuǎn)換的過(guò)程，通過(guò)InitStr。函數(shù)，將鍵盤上獲取的字符 串轉(zhuǎn)換成符合要求的存儲(chǔ)結(jié)構(gòu)，使得存儲(chǔ)字符串?dāng)?shù)組的第一位為字符串的長(zhǎng)度，這樣方便了 Index。函數(shù)的編寫，在比擬時(shí)能夠更直觀地使用數(shù)組的下標(biāo)進(jìn)行操作，而不用再作相應(yīng)的考 慮與轉(zhuǎn)換。編寫程序時(shí)應(yīng)注意數(shù)組長(zhǎng)度的設(shè)置，在保證有足夠存儲(chǔ)空間的情況下不必定義過(guò)長(zhǎng)，參 考源代碼中指定的是100,編程者可根據(jù)實(shí)際情況自行設(shè)置其大小。在編寫Index。函數(shù)時(shí)， 應(yīng)注意回退指針的計(jì)算，以免造成匹配出錯(cuò)的情況。上機(jī)實(shí)驗(yàn)3八皇后問(wèn)題【實(shí)驗(yàn)?zāi)康摹?1) 了解回溯算法

34、的思路：從一條路往前走，能進(jìn)那么進(jìn)，不能進(jìn)那么退回來(lái)，換一條路 再試。(2)通過(guò)對(duì)八皇后問(wèn)題的解決，掌握回溯算法的應(yīng)用。【實(shí)驗(yàn)內(nèi)容】在8X8格的國(guó)際象棋上擺放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于 同一行、同一列或同一斜線上，問(wèn)有多少種擺法?！緦?shí)驗(yàn)步驟】(1)算法分析：數(shù)組a、b、c分別用來(lái)標(biāo)記沖突。數(shù)組a代表列沖突，a0ka代表第0列到第7列，如果某列上已經(jīng)有皇后，那么為1,否 那么為0。數(shù)組b代表主對(duì)角線沖突，為bi-j+7,即b0b14,如果某條主對(duì)角線上已經(jīng)有皇后， 那么為1,否那么為0。數(shù)組c代表從對(duì)角線沖突，為ci+j,即c0c14,如果某條從對(duì)角線上已經(jīng)有皇后, 那么為1，否那么