數(shù)據(jù)結(jié)構(gòu)試驗要求-信陽師范學(xué)院

1、數(shù)據(jù)結(jié)構(gòu)實驗手冊王淑禮熊炎 編信陽師范學(xué)院計算機與信息技術(shù)學(xué)院第一部分C語言基本知識一基本輸入和輸出3二函數(shù)與參數(shù)傳遞5三結(jié)構(gòu)體及運用 8四動態(tài)分配函數(shù) 9第二部分上機實驗習(xí)題上機實驗要求及規(guī)范11實驗一線性表13實驗二隊列17實驗三棧20實驗四二叉樹及應(yīng)用21實驗五圖23實驗六查找26實驗七排序27第三部分 課程設(shè)計題目28第一部分C語言基本知識數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)及相關(guān)專業(yè)的核心基礎(chǔ)課。上機實驗是對學(xué)生的一種全面 綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)。通常，實驗題 中的問題比平時的習(xí)題復(fù)雜得多，也更接近實際。實驗著眼于原理與應(yīng)用的結(jié)合點，使學(xué)生學(xué)會如何把書上學(xué)

2、到的知識用于解決實際問題，培養(yǎng)軟件工作所需要的動手能力；另一方面,能使書上的知識變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。目前各種“數(shù)據(jù)結(jié)構(gòu)”教材較為注重理論的敘述與介紹，算法描述不拘泥某種語言的語法細節(jié)。多年的教學(xué)實踐表明，學(xué)生的程序設(shè)計基礎(chǔ)并不一致，相當(dāng)一部分人基礎(chǔ)較為薄弱，對上機實驗感到非常困難。存在的主要問題是：不能正確的輸入數(shù)據(jù)，結(jié)構(gòu)體概念陌生，函數(shù)的傳址調(diào)用概念不清，有關(guān)指針的內(nèi)容理解不深。因此，有必要將數(shù)據(jù)結(jié)構(gòu)所必須使用的C語言語法在此做簡單介紹。如果學(xué)生基礎(chǔ)好，可以跳過這一部分內(nèi)容不看。一、基本輸入和輸出看起來簡單的輸入/輸出，往往是上機實驗最容易出錯的地方，尤其是輸入。

3、對于一個 算法程序，如果數(shù)據(jù)不能正確輸入，算法設(shè)計得再好也無法正常運行。1. 輸入C語言的輸入是由系統(tǒng)提供的 scanf()等函數(shù)實現(xiàn)，在程序的首部一般要求寫入：# in elude 因為標(biāo)準(zhǔn)輸入/輸出函數(shù)都存在于頭文件stdio.h之中，現(xiàn)將其包含進來方可使用這些常用的輸入/輸出函數(shù)。有的系統(tǒng)允許不使用上述包含語句，可以直接使用標(biāo)準(zhǔn)輸入/輸出函數(shù)。函數(shù)scanf()的功能很豐富，輸入格式也是多種多樣，這是大家較為熟悉的知識，這里不 做詳細介紹。在使用中需要注意以下幾個問題。(1) 一條seanf()語句有多個變量、并且都是數(shù)值型(int, float, double )時，在輸入數(shù) 據(jù)時應(yīng)該

4、在一行之內(nèi)鍵入多個數(shù)據(jù)，數(shù)據(jù)之間空格分隔。例如：intn; float x;scanf (“ %d %f ” , &n, &x);正確的輸入應(yīng)是：整數(shù)空格 實數(shù) 回車。例如：100 _3.14 /就是在兩個數(shù)據(jù)之間使用空格鍵為分隔符，最后打回車鍵。如果語句中在 %d和%f之間有一個逗號：scanf (“ d%f ”, &n, &x);正確的輸入應(yīng)是：整數(shù)逗號 實數(shù) 回車。例如：100, 3.14 /(2) 在需要字符型變量或字符串輸入時，要單獨寫一條輸入語句，這樣不易出錯。如果在同一條scanf()語句中將字符型和數(shù)值型混合輸入常常會出錯。因為鍵盤輸入時在數(shù)值型數(shù)據(jù)之間空格鍵起分隔符作用，但是

5、在字符或字符串之間，空格會被當(dāng)做一個字符，而不能起到分隔符的作用。所以將它們混在一起容易出錯。(3) 在scanf()語句中變量寫法應(yīng)該是該變量的地址，這一點常被忽視。例1請看下列程序:1:void mai n()2: char n ame10, ch ;3:int num; float x;4:printf( n 請輸入姓名：” );scanf(“ s” , name);5:printf( n 請輸入性別：” );scanf(“ c” , &ch);6:printf( n 請輸入學(xué)號和成績：”)；scanf( %d%f , &n, &x);為了方便說明問題程序中加了行號，運行時當(dāng)然不允許行號

6、。一般情況下在scanf()語句中的變量名之前要加上求地址符&，上述程序第5, 6行之中就是這樣。為什么第 4行的name前面不加&呢？因為name代表字符串，即是一維字符數(shù)組，一維數(shù)組名本身就是一個 地址，是該數(shù)組的首地址，所以name前面不加&。在本程序中把字符串、字符、數(shù)值型變量分別寫入不同的scanf()語句，輸入數(shù)據(jù)的具體形式如下：請輸入姓名：Zha ngHua請輸入性別：v請輸入學(xué)號和成績：101 90.5請考慮如果姓名輸入成：Zhang Hua，會出現(xiàn)什么現(xiàn)象？那樣只會讀入Zhang做姓名，而Hua被忽略，還會影響后面的輸入語句無法正確讀入數(shù)據(jù)。因此，應(yīng)該充分重視數(shù)據(jù)的輸入技術(shù)。

7、2. 輸出C語言的輸出是由系統(tǒng)提供的printf()等函數(shù)來實現(xiàn)，在程序的首部一般要求寫入：# in clude 因為標(biāo)準(zhǔn)輸入/輸出函數(shù)都存在于頭文件stdio.h之中，現(xiàn)將其包含進來方可使用這些常用的輸入/輸出函數(shù)。有的系統(tǒng)允許不使用上述包含語句，可以直接使用標(biāo)準(zhǔn)輸入/輸出函數(shù)。輸出函數(shù)printf()的語法一般容易掌握，這里強調(diào)的是怎樣合理巧妙的使用它。(1) 在連續(xù)輸出多個數(shù)據(jù)時，數(shù)據(jù)之間一定要有間隔，不能連在一起。int n=10, m=20, p=30;printf( n %d%d%d ,n,m,p);printf( n %6d%6d%6c” ,n,m,p);/提倡使用的語句第一行輸

8、出是：102030第二行輸出是：102030(2) 在輸入語句scanf()之前先使用printf()輸出提示信息，但是在printf()最后不 能使用換行符。int x;printf( n x=? ”)；/句尾不應(yīng)使用換行符scanf( “ d，&x);這樣使光標(biāo)與提示信息出現(xiàn)在同一行上，光標(biāo)停在問號后邊：X=? 。(3) 在該換行的地方，要及時換行。int i;printf(數(shù)據(jù)輸出如下：n”)；/需要換行for (i=0; i8 ; i+) printf(“ 6c” , i )/幾個數(shù)據(jù)在同一行輸出，不能換行（4）在調(diào)試程序時多加幾個輸出語句，以便監(jiān)視中間運行狀況。 程序調(diào)式成功后，再去

9、掉這些輔助輸出語句。、函數(shù)與參數(shù)傳遞C語言的源程序是由一個主函數(shù)和若干（或零個）子函數(shù)構(gòu)成，函數(shù)是組成 C語言程 序的基本單位。函數(shù)具有相對獨立的功能，可以被其他函數(shù)調(diào)用， 也可調(diào)用其他函數(shù)。當(dāng)函 數(shù)直接或間接的調(diào)用自身時，這樣的函數(shù)稱為遞歸函數(shù)。是否能夠熟練的設(shè)計和使用函數(shù)， 是體現(xiàn)一個人程序設(shè)計能力高低的基本條件。 因此有 必要回顧和復(fù)習(xí) C語言函數(shù)的基本概念。1函數(shù)的設(shè)計函數(shù)設(shè)計的一般格式是：類型名 函數(shù)名（形參表）函數(shù)體；因此函數(shù)可以具有返回值，上面的類型名int, float 等。例如：函數(shù)體；.void。例如：函數(shù)體；函數(shù)設(shè)計一般是處理一些數(shù)據(jù)獲得某個結(jié)果，就是函數(shù)返回值的類型，可

10、以是float funx（形參表）函數(shù)也可無返回值，此時類型是void funy（形參表）而函數(shù)體內(nèi)所需處理的數(shù)據(jù)往往通過形參表傳送，函數(shù)也可以不設(shè)形參表，此時寫為： 類型名 函數(shù)名（）函數(shù)體；例2設(shè)計一個函數(shù)計算三個整數(shù)之和，再設(shè)計一個函數(shù)僅輸出一條線。設(shè)計主函數(shù)調(diào) 用兩個函數(shù)。#in elude intsumx (int a, int b, int c) int s;s=a+b+c;return s;/*計算三個整數(shù)之和的函數(shù)*/voiddisplay() printf( ” voidmai n() int x,y, z ,sa; x=y=z=2; display();printf(pri

11、ntf(printf(/* 輸出一條線的函數(shù)*/n nsum=%d ”,sumx(x,y,z);n %6d%6d%6d ”x,y,z); n);/*畫一條線/*在輸出語句中直接調(diào)用函數(shù)*/sumx( ) */display();x=15; y=16; z=17; sa=sumx(x, y, z); printf( n printf( nsum=%d ”,sa); %6d%6d%6dn ”x,y,z);/*在賦值語句中調(diào)用函數(shù) sumx（）*/display( );/*程序結(jié)束 */運行結(jié)果:sum= 6222sum=481516172.關(guān)于函數(shù)的參數(shù)傳遞函數(shù)在被調(diào)用時，由主調(diào)程序提供實參，將信

12、息傳遞給形參。 在調(diào)用結(jié)束后，有時形參可以返回新的數(shù)據(jù)給主調(diào)程序。這就是所謂參數(shù)傳遞。各種算法語言實現(xiàn)參數(shù)傳遞的方法通 常分為傳值和傳址兩大類。在上例中函數(shù) sumx()的設(shè)計和主函數(shù)對它的調(diào)用，就是傳值調(diào)用。第一、第二次調(diào) 用，帶入的實參均是三個整型變量。調(diào)用函數(shù)返回后，在主程序中輸出實參的值仍與調(diào)用之前相同。傳值調(diào)用的主要特點是數(shù)據(jù)的單向傳遞，由實參通過形參將數(shù)據(jù)代入被調(diào)用函數(shù)， 不論在調(diào)用期間形參值是否改變，調(diào)用結(jié)束返回主調(diào)函數(shù)之后，實參值都不會改變。在不同的算法語言中，傳址調(diào)用的語法有所不同。在PASCAL語言中用變參實現(xiàn)傳址。在C語言中采用指針變量做形參來實現(xiàn)傳址。傳址調(diào)用的主要特點

13、是可以實現(xiàn)數(shù)據(jù)雙向傳 遞，在調(diào)用時實參將地址傳給形參，該地址中的數(shù)據(jù)代入被調(diào)用函數(shù)。如果在調(diào)用期間形參值被改變，也即該地址中的數(shù)據(jù)發(fā)生變化，調(diào)用結(jié)束返回主調(diào)函數(shù)之后，實參地址仍然不變， 但是該地址中的數(shù)據(jù)發(fā)生相應(yīng)改變。這就是數(shù)據(jù)的雙向傳遞。現(xiàn)看一例題：例3 設(shè)計一個函數(shù)實現(xiàn)兩個數(shù)據(jù)的交換，在主程序中調(diào)用。#in elude void swap( int *a, int *b) int c;c=*a; *a = *b;*b=c;voidmai n() int x=100, y=800;/*輸出原始數(shù)據(jù)*/*調(diào)用交換數(shù)據(jù)的函數(shù)swap () */*輸出交換后的數(shù)據(jù)*/prin tf(n%6d%6d

14、, x, y);swap( &x, &y);prin tf(n%6d%6d, x ,y);運行結(jié)果：100 800800 100實踐證明x,y的數(shù)據(jù)在調(diào)用函數(shù)前后發(fā)生了交換變化。形參是指向整形的指針變量a和b,在函數(shù)體內(nèi)需要交換的是指針?biāo)傅拇鎯卧膬?nèi)容，因此使用*a = *b ;這樣的寫法。在調(diào)用時，要求實參個數(shù)、類型位置與形參一致。因為實參應(yīng)該是指針地址，所以調(diào)用語句swap(&x, &y)中，實參&x,和& y代入的是整型變量 x,y的地址。在函數(shù)體內(nèi)交換的是實參地 址中的內(nèi)容，而作為主函數(shù)變量x,y的地址仍然沒有改變。從整數(shù)交換的角度看，本例題實現(xiàn)了雙向數(shù)據(jù)傳遞。若從指針地址角度看，

15、調(diào)用前后指針地址不變。在數(shù)據(jù)結(jié)構(gòu)教材中，很多函數(shù)的形參前帶有“& ”，如順序表的初始化函數(shù)的聲明：Status In itList_Sq( SqList &L)其中，形參前帶有“ &”，說明形參T是引用類型的。引用類型是 C+語言特有的。引用類 型的變量，其值若在函數(shù)中發(fā)生變化，則變化的值會帶回主調(diào)函數(shù)中。下面的例子說明了函數(shù)中引用類型的變量和非引用類型的變量的區(qū)別：例4#in cludevoid fa(int a)/函數(shù)中改變a,將不會帶回主調(diào)函數(shù)(主調(diào)函數(shù)中的a仍是原值) a+;printf(” 在函數(shù) fa 中：a=%dn,a);void fb(int &a)/由于a為引用類型，在函數(shù)中

16、改變a，其值將帶回主調(diào)函數(shù) a+;printf(在函數(shù) fb 中：a=%dn,a);void fc(int *a)/a為指針類型，數(shù)據(jù)雙向傳遞，在函數(shù)中改變*a的值，其結(jié)果將帶回主調(diào)函數(shù) (*a)+;printf(在函數(shù) fc 中：*a=%dn,*a);void main() int n=1,*p; p=&n;printf(在主程中，調(diào)用函數(shù) fa(n);printf(在主程中，調(diào)用函數(shù) fb( n);printf(在主程中，調(diào)用函數(shù) fc(p);printf(在主程中，調(diào)用函數(shù)fa 之前：n=%dn,n);fa之后，調(diào)用函數(shù) fb之前：n=%dn,n);fb之后，調(diào)用函數(shù) fc之前：n=%d

17、n,n);運行結(jié)果：在主程中，調(diào)用函數(shù)在函數(shù)fa中：a=2在主程中，調(diào)用函數(shù)在函數(shù)fb中：a=2在主程中，調(diào)用函數(shù)在函數(shù)fc中：*a=3在主程中，調(diào)用函數(shù)fc 之后：n=%dn,n);fa之前：n=1fa之后，調(diào)用函數(shù)fb之前：n=1fb之后，調(diào)用函數(shù)fa之前：n=2fc之后，n=3需要進一步說明的是，C語言的傳址調(diào)用比較復(fù)雜，不如C+的引用調(diào)用方便。因此建議大家采用Visual C+作為編譯環(huán)境，在此環(huán)境下可以兼容 C程序，并且可以直接使用引用 參數(shù)，算法變?yōu)槌绦虻倪^程就會容易很多。三、結(jié)構(gòu)體及運用數(shù)據(jù)結(jié)構(gòu)課程所研究的問題均運用到“結(jié)構(gòu)體”。在C語言中結(jié)構(gòu)體的定義、輸入 /輸出是數(shù)據(jù)結(jié)構(gòu)程序

18、設(shè)計的重要語法基礎(chǔ)。定義結(jié)構(gòu)體的一般格式：:結(jié)構(gòu)體類型名類型名1變量名1 ；數(shù)據(jù)子域類型名2變量名2；類型名n變量名n；其中struct是保留字。結(jié)構(gòu)體類型名由用戶自己命名。在使用時必須聲明一個具體的結(jié)構(gòu)體類型的變量，聲明創(chuàng)建一個結(jié)構(gòu)體變量的方法是：struct結(jié)構(gòu)體類型名結(jié)構(gòu)體變量名；例如： struct ElemType /*定義結(jié)構(gòu)體*/ int num; char n ame10; ;struct ElemType x ；/* 聲明結(jié)構(gòu)體變量 x */另外有一種方法使用 typedef語句定義結(jié)構(gòu)體，在聲明結(jié)構(gòu)體變量時可以不寫struct，使得書寫更加簡便。例如：typedef str

19、uct int num;char n ame10; ElemType ；ElemType就是一個新的類型名，并且是結(jié)構(gòu)體類型名。聲明變量x的語句是：ElemType x;一個結(jié)構(gòu)體中可以包含多個數(shù)據(jù)子域。數(shù)據(jù)子域的類型名一般指基本數(shù)據(jù)類型（int char等），也可是已經(jīng)定義的另一結(jié)構(gòu)體名。數(shù)據(jù)子域變量名可以是簡單變量，也可以是數(shù) 組。它們也可以稱為結(jié)構(gòu)體的數(shù)據(jù)成員。通過“結(jié)構(gòu)體變量名.數(shù)據(jù)子域”可以訪問數(shù)據(jù)子域。例5 設(shè)計Student結(jié)構(gòu)體，在主程序中運用。#i nclude定義結(jié)構(gòu)體Student */ longnum;/*學(xué)號*/intx;/*成績*/charn ame10;/*姓名*

20、/* Stude nt;void mai n()Stude nts1;s1. nu m=1001 ;s1. x=83;strcpy( s1. name, 李/*/*聲明創(chuàng)建一個結(jié)構(gòu)體變量 為s1的數(shù)據(jù)子域提供數(shù)據(jù)s1 */*/明”);#in clude typedef structprintf( “n 姓名：s”，); /* 輸出結(jié)構(gòu)體變量 si的內(nèi)容 */printf( “n 學(xué)號：d”，s1. nu m);printf( “n 成績： d”，s1.x);或者使用鍵盤輸入： scanf( %d”，si.num);scanf( %d ”，s1.x);scanf( %s”，si.n

21、ame);還可以通過“結(jié)構(gòu)體指針- 數(shù)據(jù)子域”來訪問數(shù)據(jù)域。在實際問題中還會使用到指向結(jié)構(gòu)體的指針，通過以下語句段可以說明結(jié)構(gòu)體指針的一般用法。 Student *p ;/* 聲明指針變量 p */p=( Student *)malloc(sizeof( Student);/* 分配存儲單元，首地址賦給p 指針 */p_num=101;p-x=83; strcpy( p_name, 李 明”);printf( n %10s%6d%6d ”,p- name,p- nu m,p-x);設(shè)計一個一維數(shù)組，每個數(shù)組元素是Stude nt結(jié)構(gòu)體類型，通過以下語句段可以說明結(jié)構(gòu)體數(shù)組的一般用法?？梢酝ㄟ^“

22、結(jié)構(gòu)體數(shù)組名下標(biāo).數(shù)據(jù)子域”訪問數(shù)據(jù)域。 Stude nt a5;/* 聲明創(chuàng)建一個結(jié)構(gòu)體數(shù)組a */int i ;for( i=0, i5, i+)printf(n學(xué)號：%d ”,ai. num);printf(n姓名：%s”,)；printf(n成績:%d ”,ai.x);四動態(tài)分配函數(shù)以數(shù)組為例，在我們聲明一個數(shù)組時，必須用一個常量指定數(shù)組的長度，但是常常這個數(shù)組的長度是未知的。一般采用的方法是聲明一個較大的數(shù)組，內(nèi)存利用率有可能不高且仍可能溢出。采用動態(tài)分配函數(shù)就可以較好地解決這個問題。在數(shù)據(jù)結(jié)構(gòu)實驗中，很多順序存儲結(jié)構(gòu)都采用的動態(tài)分配內(nèi)存的方式。不同的C編譯系統(tǒng)提供的動

23、態(tài)存儲分配函數(shù)不同。有的編譯系統(tǒng)放在malloc.h中，有的編譯系統(tǒng)放在 stdlib.h中。常用的有如下幾種：(1) malloc()函數(shù)其函數(shù)原型為：void *malloc( un sig ned int size);其功能是：分配一塊長度為size字節(jié)的連續(xù)空間，并將該空間的首地址作為函數(shù)的返回值。如果函數(shù)沒有成功執(zhí)行，返回值為空指針(NULL或0)。由于返回的指針的基類型為void，應(yīng)該通過強制類型轉(zhuǎn)換后才能存入其他基類型的指針變量中，否則會有警告提示。例如:p=(i nt *)malloc(sizeof( in t);sizeof運算符返回某類型所需的內(nèi)存字節(jié)數(shù)或某變量所分配的字節(jié)

24、數(shù)，該處返回一個整 型變量所需要的字節(jié)數(shù)2,它即為動態(tài)分配內(nèi)存空間的大小。返回的指針先要通過(int *)轉(zhuǎn)換成整型指針，然后才賦值給整型指針變量P。(2) realloc ()函數(shù)其函數(shù)原型為：void * realloc(void * ptr,unsigned int size)；其功能是：用來改變已分配的內(nèi)存空間的大小，如果重新分配成功，則該函數(shù)返回指向被分配內(nèi)存的指針，否則返回空指針NULL。其中，realloc是該函數(shù)的名字，ptr是指向已分配的內(nèi)存空間的指針，即為所要改變大小的內(nèi)存空間，size是改變后的內(nèi)存空間大小。 既可以將原來空間變大，也可以將原來空間變小。如果用于擴大一個內(nèi)

25、存塊，那么這塊內(nèi)存原先的內(nèi)容依然保留，新增的內(nèi)存添加到原先內(nèi)存塊的后面。相反如果用于縮小一個內(nèi)存塊，那么這個內(nèi)存原來尾部的內(nèi)存便被刪除，但是剩余部分內(nèi)存的原先內(nèi)容依然保留。如果原先內(nèi)存塊的大小是無法改變的那么realloc將重新分配另一塊指定大小的內(nèi)存塊，并把原先那塊內(nèi)存的內(nèi)容復(fù)制到新的內(nèi)存塊上面。所以在使用了realloc之后便不可以再使用原來指向那塊舊內(nèi)存的指針了，而應(yīng)該使用realloc所返回的新指針。否者很容易出錯！例如：p=(i nt *)malloc(p, 20*sizeof(i nt);作用是將原來分配給指針p的內(nèi)存變更為20個整型變量所需內(nèi)存空間。(3) free()函數(shù)其函數(shù)

26、原型為：void free(void *p);其功能是：釋放以前分配給指針變量p的動態(tài)空間(由函數(shù) malloc或realloc等分配的地址)。例如：free(p);作用就是將上例中malloc或realloc分配的空間釋放掉。第二部分上機實驗上機實驗要求及規(guī)范一、實驗步驟數(shù)據(jù)結(jié)構(gòu)課程具有比較強的理論性， 同時也具有較強的可應(yīng)用性和實踐性。 上機實驗是 一個重要的教學(xué)環(huán)節(jié)。一般情況下學(xué)生對于編寫程序上機練習(xí)具有一定的積極性，但容易忽略實驗的總結(jié)，忽略實驗報告的撰寫。正確的實驗步驟如下：1問題分析與系統(tǒng)結(jié)構(gòu)設(shè)計充分分析和理解問題，弄清要求做什么（而不是怎么做），限制條件是什么。按照以數(shù) 據(jù)結(jié)構(gòu)為

27、中心的原則劃分模塊，搞清數(shù)據(jù)的邏輯結(jié)構(gòu)（是線性表還是樹、圖？），確定數(shù)據(jù) 的存儲結(jié)構(gòu)（是順序結(jié)構(gòu)還是鏈表結(jié)構(gòu)？）然后設(shè)計有關(guān)操作的函數(shù)。在每個函數(shù)模塊中， 要綜合考慮系統(tǒng)功能，使系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試。 最后寫出每個模塊的算法頭和規(guī)格說明，列出模塊之間的調(diào)用關(guān)系（可以用圖表示），便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。2. 詳細設(shè)計和編碼詳細設(shè)計是對函數(shù)（模塊）的進一步求精，用偽高級語言（如類C語言）或自然語言寫出算法框架，這時不必確定很多結(jié)構(gòu)和變量。編碼，即程序設(shè)計，是對詳細設(shè)計結(jié)果的進一步求精，即用某種高級語言（如C/C+語言）表達出來。盡量多設(shè)一些注釋語句，清晰易懂。盡量臨時增加一些輸出語句，

28、便于差錯 矯正，在程序成功后再刪去它們。3. 上機準(zhǔn)備熟悉高級語言用法，如 C語言。熟悉機器（即操作系統(tǒng)和編譯系統(tǒng)），基本的常用命令。 靜態(tài)檢查主要有兩條路徑，一是用一組測試數(shù)據(jù)手工執(zhí)行程序（或分模塊進行）；二是通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個過程中再加入一些注釋和斷言。如果程序中邏輯概念清楚，后者將比前者有效。4. 上機調(diào)試程序調(diào)試最好分塊進行，自底向上，即先調(diào)試底層函數(shù)， 表面上的麻煩工作可以大大降低調(diào) 試時所面臨的復(fù)雜性，提高工作效率。5. 整理實習(xí)報告在上機實開始之前要充分準(zhǔn)備實驗數(shù)據(jù)，在上機實踐過程中要及時記錄實驗數(shù)據(jù)，在上機實踐完成之后必須及時總結(jié)分析

29、。寫出實驗報告。二、實驗報告的基本要求：一般性、較小規(guī)模的上機實驗題，必須遵循下列要求，養(yǎng)成良好的習(xí)慣：（1）題目：內(nèi)容敘述（2）程序清單（帶有必要的注釋）（3）調(diào)試報告：實驗者必須重視這一環(huán)節(jié)，否則等同于沒有完成實驗任務(wù)。這里可以體現(xiàn)個人特色、或創(chuàng)造性思維。具體內(nèi)容包括：測試數(shù)據(jù)與運行記錄；調(diào)試中遇到的主要問題，自己是如何解決的；經(jīng)驗和體會等。、實驗報告的提高要求:階段性、較大規(guī)模的上機實驗題，應(yīng)該遵循下列要求。養(yǎng)成科學(xué)的習(xí)慣。（1 ）需求和規(guī)格說明描述問題，簡述題目要解決的問題是什么，規(guī)定軟件做什么，原題條件不足時補全。（2）設(shè)計a. 設(shè)計思想：存儲結(jié)構(gòu)（題目中限定的要描述）；主要算法基本

30、思想。b. 設(shè)計表示：每個函數(shù)的頭和規(guī)格說明；列出每個函數(shù)所調(diào)用和被調(diào)用的函數(shù)，也 可以通過調(diào)用關(guān)系圖表達。c. 實現(xiàn)注釋：各項功能的實現(xiàn)程度、在完成基本要求的基礎(chǔ)上還有什么功能。（3 ）用戶手冊：使用說明。（4）調(diào)試報告：調(diào)試過程中遇到的主要問題是如何解決的；設(shè)計的回顧、討論和分析； 時間復(fù)雜度、空間復(fù)雜度分析；改進設(shè)想；經(jīng)驗和體會等。四、關(guān)于實驗題目本實驗手冊共分七個大實驗，每個實驗中又有幾個小題目。 學(xué)生可以根據(jù)實際情況選做其中一個或全做。有的實驗只有一個題目，要求必做。實驗一線性表一、實驗?zāi)康?. 掌握線性表的邏輯結(jié)構(gòu)特性以及在計算機內(nèi)的兩種存儲結(jié)構(gòu)。2. 掌握線性表的基本操作在兩種存

31、儲結(jié)構(gòu)上的實現(xiàn)；其中以鏈表的操作為側(cè)重點；會靈活運用線性表結(jié)構(gòu)解決某些實際問題。二、實例：線性表的順序表示（順序表）及操作實現(xiàn)。閱讀下列程序請注意幾個問題：（1）關(guān)于線性表的順序存儲結(jié)構(gòu)的本質(zhì)是：在邏輯上相鄰的兩個數(shù)據(jù)元素an , a,在存儲地址中也是相鄰的，既地址連續(xù)。不同的教材有不同的表示，我們采用含動態(tài)分配 一維數(shù)組的結(jié)構(gòu)體：Typedef struct ElemType *elem;int len gth; int listsize;SqList;/定義順序表的存儲結(jié)構(gòu)（2 ）本程序是一個完整的、子函數(shù)較多的源程序。目的為學(xué)生提供一個示范，提供順序存儲表示的資料，供學(xué)生參考?！驹闯绦颉?/p>

32、#i nclude #i nclude #i nclude #defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -1#defi ne INITSIZE 100#define INCREMENT 10 / 預(yù)定義常量 typedef int Status; /定義狀態(tài)結(jié)果類型 typedef int ElemType;定義數(shù)據(jù)元素類型typedef struct ElemType *elem;int len gth;int listsize;SqList; /定義順序表的存儲結(jié)構(gòu)Status In itList(SqList &L)/構(gòu)造一個空的順序表

33、L.L.elem=(ElemType*)malloc(INITSIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.le ngth=O;L.listsize=INITSIZE;return(OK);void Assig n(SqList &L) /為順序表L的各元素賦值.int i, N;prin tf(Please in put the Number of the SqList:); scan f(%d,&N);prin tf(Please in put the eleme nts:); for(i=0;iN;i+) scan f(%d,&L.e

34、lemi);L.le ngth+;void ListTraverse(SqList L)/遍歷順序表L.int i;for(i=0;i=Len gth-1;i+)prin tf(%d”,L.elemi);prin tf(n);prin tf(the len gth is:%dn, L.le ngth);void Prin t(ElemType g)prin tf(%dn,g);void ListTraverse2(SqList L,void (*vi)(ElemType)/遍歷順序表L的另一種方法.int i;ElemType *p;p=L.elem;for (i=0;i=L .len gth

35、-1;i+)vi(*p+);prin tf(the len gth is:%dn, L.le ngth);Status GetELem(SqList L, int i, ElemType &e)/取順序表L的第i個元素的值，用e返回.e=L.elemi-1;return OK; int ListLe ngth(SqList L) /求順序表的長度return(L.le ngth);Status ListI nsert(SqList &L, int i, ElemType e) /在順序表L的第i個元素前插入元素e.ElemType *p,*q,* newbase;if(iL.le ngth+1

36、)return ERROR;if(L.len gth=L .li stsize) newbase=(ElemType*)realloc(L.elem,(INITSIZE+INCREMENT)*sizeof(ElemType); if(! newbase)exit(OVERFLOW);L.elem=n ewbase;L.listsize+=INCREMENT;q=&L.elemi-1;for(p=&L.elemLen gth-1;p=q;-p)*(p+1)=*p;*q=e;+L .len gth;return OK;void MergeList(SqList La,SqList Lb, SqLi

37、st &Lc) /已知順序表La和Lb的元素按值非遞減排列，/歸并La和Lb得到新的順序表 Lc,Lc的元素也按值非遞減排列.ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem;pb=Lb.elem;Lc.li stsize=Lcen gth=La .len gth+Lb .len gth;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem)exit(OVERFLOW);paast=La.elem+La.le ngth-1;pb_last=Lb.elem+L

38、b .len gth-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pb=pb_last) *pc+=*pb+; void mai n() SqList L, L1,L2;int i,j；ElemType e,f;if(lni tList(L)prin tf(l nit success n);Assig n( L);ListTraverse(L);ListTraverse2(L,Pri nt);prin tf(Plsese in put t

39、he locatio n i:); scan f(%d,&i);GetELem(L,i,e);prin tf(The ith elem is: %dn,e);prin tf(Please in put the In serted elemi scan f(%d%d,&j, &f);List In sert(L,j,f);ListTraverse(L);Ini tList(L1);Assig n(L1);ListTraverse(LI);MergeList(L,L1, L2);ListTraverse(L2);初始化順序表L/為L的元素賦值遍歷順序表L/取順序表的第i個元素，賦給eNo. and

40、 the value:）;在L的第i個位置之前插入f初始化順序表L1/為L1的元素賦值/遍歷順序表L1歸并順序表L，L1，得到L2/遍歷順序表L2三、實驗內(nèi)容1 線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)下基本操作的實現(xiàn)（初始化、賦值、取值、插入、刪除等）。2 線性表歸并運算兩個數(shù)據(jù)元素按值非遞減有序排列的線性表，要求將二者歸并為一個新表， 新表中的數(shù)據(jù)元素仍按值非遞減有序排列。要求分別采用順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu).。3使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)一元多項式相表示及相加。4.約瑟夫環(huán)問題。設(shè)有 n個人圍坐一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到m的人出列，接著從出列的下一個人開始重新報數(shù)，數(shù)到m的人又出列，如此下去，直到所有人都出列為止。試

41、設(shè)計一個程序求出出列順序。要求利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序打印出各人的編號。實驗二 棧一、實驗?zāi)康?.深入了解棧的定義和特性。2.掌握棧的數(shù)組表示、 鏈表表示以及相應(yīng)操作的實現(xiàn)，鞏固對這兩種結(jié)構(gòu)的構(gòu)造方法的掌握。、實例：隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）及操作實現(xiàn)。閱讀下列程序請注意：該例程是標(biāo)準(zhǔn)C語言的程序。算法中函數(shù)的引用參數(shù)全部轉(zhuǎn)化為指針來實現(xiàn)，這將有助同學(xué)們掌握在Turbo C環(huán)境下將算法轉(zhuǎn)化為程序的方法?！驹闯绦颉?in elude 數(shù)組最大界限*/數(shù)據(jù)元素類型*/一維數(shù)組子域*/ 頭、尾指針子域*/循環(huán)隊列的結(jié)構(gòu)體類型 */#i nclude #defi ne M

42、AXSIZE 20/*typedef int ElemType;/*typedef struct ElemType aMAXSIZE;/*int fron t,rear;/*SqQueue;/*SqQueue Q1;/*函數(shù)聲明*/void in it_Q(SqQueue *Q);void out_Q(SqQueue Q);void En Queue(SqQueue *Q,ElemType e);ElemType DeQueue(SqQueue *Q);/* 主函數(shù)*/main () int k; ElemType e,x; char ch; in it_Q( & Q1);/*do pri n

43、tf(nnn);prin tf(nn1.prin tf(nn2.prin tf(nn3.prin tf(n=prin tf(nscan f(%d,&k); switch(k) case 1: pri ntf(n初始化一個空循環(huán)隊列*/數(shù)據(jù)元素e進隊列”）；出隊一個元素，返回其值 ）； 結(jié)束程序運行）;=);請輸入您的選擇(1,2,3);進隊 e=?); scan f(%d, &e);En Queue(SqQueue & Q1,e); out_Q(Q1); break;case 2: x= DeQueue(&Q1);printf(n出隊元素：%d, x);out_Q(Q1 ); break;ca

44、se 3: exit(O); /* switch */prin tf(n);while(k=1 & kfro nt=O; Q-rear=0; /* i nit_Q */*輸出隊列的內(nèi)容*/void out_Q(SqQueue Q) char ch; int i;/*不能修改隊列頭、尾指針 */if (Q-fro nt=Q-rear) pri ntf(“n Queue is NULL.“；else i=(Q-fro nt+1)% MAXSIZE;while( i!=Q-rear) printf(“n data=%d ”, Q-ai);i=(i+1)%MAXSIZE; printf(“n data

45、=%d ”, Q-ai);printf( “n 打回車鍵，繼續(xù)。 );ch=getch(); /* out_Q */ *進隊函數(shù)*/n Queue is Overflow! ”);void En Queue(SqQueue *Q,ElemType e) if(Q-rear+1)%MAXSIZE=Q-fro nt) pri ntf( else Q-rear=(Q-rear+1)% MAXSIZE ;Q_aQ_rear=e;/* En Queue */* 出隊函數(shù)*/ElemType DeQueue(SqQueue *Q) ElemType x;if（Q-fr on t=Q_rear） print

46、f（“n Queue is NULL! ”）;x=_1;else Q-fro nt=（Q-fro nt+1）% MAXSIZE ;x=Q-aQ-fro nt;return（x）; /* DeQueue */三、實驗內(nèi)容1. 棧的基本操作的實現(xiàn)（初始化、賦值、取值、插入、刪除等），要求分別采用順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)。2. 寫一個程序，將輸入的十進制數(shù)據(jù) M轉(zhuǎn)換為八進制數(shù)據(jù) M8，將其調(diào)試通過。在此基礎(chǔ)上修改程序，實現(xiàn)十進制數(shù)據(jù)M向N進制（2或8或16）的轉(zhuǎn)換。（1）采用順序存儲結(jié)構(gòu)實現(xiàn)棧。（2 ）采用鏈表結(jié)構(gòu)實現(xiàn)棧。3. 括號匹配的檢驗【問題描述】假設(shè)表達式中允許有兩種括號：圓括號和方括號，其嵌套的

47、順序隨意，即（）或（）等為正確格式，（）或（均為不正確的格式。讀入含圓括號和方括號的符號序 列，輸出 匹配”或 此串括號匹配不合法”?！緶y試數(shù)據(jù)】輸入（），結(jié)果匹配”輸入（），結(jié)果此串括號匹配不合法”【選作內(nèi)容】考慮增加大括號的情況。4. 1.算術(shù)表達式求值【問題描述】表達式求值是實現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型的例子，設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程?！净疽蟆恳宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達式。利用教科書表3.1給出的算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值?！緶y試數(shù)據(jù)】3*（7-1） ； 1+2+3+4; 88-

48、1*5 ； 1024/4*8 ； （20+2）*（6/2）； （6+2*（3+6）。實驗三 隊列一、實驗?zāi)康?. 深入了解隊列的定義和特性。2. 掌握隊列的數(shù)組表示、鏈表表示以及相應(yīng)操作的實現(xiàn)，鞏固對這兩種結(jié)構(gòu)的構(gòu)造方法的掌握。二、實例：隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）及操作實現(xiàn)閱讀下列程序請注意：該例程是標(biāo)準(zhǔn)C語言的程序。算法中函數(shù)的引用參數(shù)全部轉(zhuǎn)化為指針來實現(xiàn)，這將有助同學(xué)們掌握在Turbo C環(huán)境下將算法轉(zhuǎn)化為程序的方法。【源程序】#i nclude #in elude #defi ne MAXSIZE 20/*typedef int ElemType;/*typedef struct E

49、lemType aMAXSIZE;/*int fron t,rear;/*SqQueue;/*SqQueue Q1;/*函數(shù)聲明*/void in it_Q(SqQueue *Q);void out_Q(SqQueue Q);void En Queue(SqQueue *Q,ElemType e); ElemType DeQueue(SqQueue *Q);/* 主函數(shù)*/數(shù)組最大界限*/數(shù)據(jù)元素類型*/一維數(shù)組子域*/ 頭、尾指針子域*/循環(huán)隊列的結(jié)構(gòu)體類型 */main () int k; ElemType e,x; char ch; in it_Q( & Q1);/*do pri ntf

50、(nnn);prin tf(nn1.prin tf(nn2.prin tf(nn3.prin tf(n=prin tf(nscan f(%d,&k); switch(k) case 1: pri ntf(n初始化一個空循環(huán)隊列*/數(shù)據(jù)元素e進隊列”）；出隊一個元素，返回其值 ）； 結(jié)束程序運行）;=);請輸入您的選擇(1,2,3);進隊 e=?); scan f(%d, &e);En Queue(SqQueue & Q1,e); out_Q(Q1); break;case 2: x= DeQueue(&Q1);printf(n出隊元素：%d, x);out_Q(Q1 ); break;case

51、 3: exit(O); /* switch */prin tf(n);while(k=1 & kfro nt=O; Q-rear=0; /* i nit_Q */*輸出隊列的內(nèi)容*/void out_Q(SqQueue Q) char ch; int i;/*不能修改隊列頭、尾指針 */if (Q-fro nt=Q-rear) pri ntf(“n Queue is NULL.“；else i=(Q-fro nt+1)% MAXSIZE;while( i!=Q-rear) printf(“n data=%d ”, Q-ai);i=(i+1)%MAXSIZE; printf(“n data=%d ”, Q-ai);printf(