數(shù)據(jù)結(jié)構(gòu)課習(xí)題參考答案

1、數(shù)據(jù)結(jié)構(gòu)目錄一、1.1比較2個(gè)線(xiàn)性鏈表的c函數(shù) 31.2寫(xiě)一個(gè)倒置順序存貯的線(xiàn)性表的c函數(shù)31.3 寫(xiě)一個(gè)在線(xiàn)性表中，使線(xiàn)性表中沒(méi)有值相同的結(jié)點(diǎn)的函數(shù)。41.4 編寫(xiě)一個(gè)求解給定多項(xiàng)式的值的c函數(shù)。51.5 實(shí)現(xiàn)多項(xiàng)式乘法61.7 車(chē)廂出站問(wèn)題91.8編寫(xiě)對(duì)任一棧作進(jìn)棧和出棧運(yùn)算的c函數(shù)101.10 寫(xiě)出表達(dá)式等價(jià)的后綴表達(dá)式。121.11編寫(xiě)一個(gè)統(tǒng)計(jì)給定的線(xiàn)性鏈表的結(jié)點(diǎn)個(gè)數(shù)的c函數(shù)。151.12編寫(xiě)一個(gè)將給定的線(xiàn)性鏈表逆轉(zhuǎn)的c函數(shù)。161.13編寫(xiě)一個(gè)插入值的c函數(shù)。181.14編寫(xiě)一個(gè)刪除鏈表中結(jié)點(diǎn)的前趨結(jié)點(diǎn)的c函數(shù)。191.15試編寫(xiě)一個(gè)將兩個(gè)鏈表歸并成一個(gè)線(xiàn)性鏈表的c函數(shù)。201.17

2、 用環(huán)形鏈表解1。6題23118 將給定的線(xiàn)性鏈表改成環(huán)形鏈表241 19將給定的線(xiàn)性鏈表改成一個(gè)帶表頭的環(huán)形鏈表25120 編寫(xiě)用hash函數(shù)h（xi）xi，對(duì)x1，x2x800進(jìn)行hash存儲(chǔ)的程序261 21求廣義表的深度。2721試編寫(xiě)一個(gè)在兩個(gè)順序字符串中尋找最大公共子串的c函數(shù)。292 2試編寫(xiě)一個(gè)實(shí)現(xiàn)strins（s1，i，s2）的c函數(shù)。3123 按照2.2題的要求，編一個(gè)實(shí)現(xiàn)strdel（s，i，j）的c函數(shù)。3231編寫(xiě)一個(gè)二分插入排序的c程序3332編寫(xiě)一個(gè)對(duì)給定鏈表進(jìn)行插入排序的c程序。3435采用順序存儲(chǔ)實(shí)現(xiàn)，即用數(shù)組存放排序過(guò)程中以排好序的鏈表的頭指針。363 6采

3、用順序存儲(chǔ)的結(jié)構(gòu)即數(shù)組實(shí)現(xiàn)。3837編寫(xiě)一個(gè)實(shí)現(xiàn)快速排序的非遞歸的c函數(shù)。3938對(duì)于分別寫(xiě)出用下列排序方法對(duì)線(xiàn)性表進(jìn)行排序的結(jié)果。4043將n階三對(duì)角陣（即半帶寬為1的帶狀矩陣）a按行序列序存放在一維數(shù)組b3*n-2中。若aij(|i-j|<=1)存放在bk中，請(qǐng)求出求解k的計(jì)算公式。4244如果把廣義的anab按行序列序存放在一維數(shù)組b(a+b-1)*n-(a+b-2)中，元素aij存放在bk中，那么請(qǐng)寫(xiě)出計(jì)算k的計(jì)算公式。4245試編寫(xiě)一個(gè)求解兩個(gè)三元數(shù)組相加的c函數(shù)。4246試編寫(xiě)一個(gè)將十字鏈表轉(zhuǎn)置的c函數(shù).4451請(qǐng)分別給出對(duì)樹(shù)進(jìn)行前序、后序、層次序遍歷后的結(jié)點(diǎn)序列。4552試

4、敘述將m棵有序樹(shù)組成的有序樹(shù)林轉(zhuǎn)換成相應(yīng)的二叉樹(shù)的逆變換。4653試編寫(xiě)一個(gè)把樹(shù)中每個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)進(jìn)行對(duì)換的c函數(shù)。4754編寫(xiě)一個(gè)利用棧來(lái)實(shí)現(xiàn)后序遍歷一棵給定的二叉樹(shù)的c函數(shù)。4955題目：51試為下面各小題分別編寫(xiě)一個(gè)c函數(shù)：（1） 按前序輸出t的結(jié)點(diǎn)值。（2） 按后序輸出t的結(jié)點(diǎn)值。（3） 輸出樹(shù)t的葉子結(jié)點(diǎn)值。（4） 求出樹(shù)t的次數(shù)。56試編寫(xiě)一個(gè)把樹(shù)t按標(biāo)準(zhǔn)形式進(jìn)行存貯的c函數(shù)。5357 已知樹(shù)t中結(jié)點(diǎn)的中序和后序，編寫(xiě)一個(gè)把t按標(biāo)準(zhǔn)形式存儲(chǔ)的c函數(shù)5458 判斷給定的二叉樹(shù)是否為完全二叉樹(shù)5559 判斷兩棵給定的二叉樹(shù)是否相似55510 把樹(shù)t轉(zhuǎn)換成由標(biāo)準(zhǔn)形式進(jìn)行存儲(chǔ)的樹(shù)t55

5、511試編寫(xiě)一個(gè)尋找結(jié)點(diǎn)a的父結(jié)點(diǎn)的c函數(shù)。56512試編寫(xiě)一個(gè)按前序遍歷穿線(xiàn)樹(shù)的c函數(shù)。5861畫(huà)出由集合中結(jié)點(diǎn)所構(gòu)成的查找樹(shù)，畫(huà)出刪除后的查找樹(shù)。6062試編寫(xiě)一個(gè)用平分法構(gòu)造出由集合中結(jié)點(diǎn)所構(gòu)成的豐滿(mǎn)查找樹(shù)的c函數(shù)。6065編寫(xiě)一個(gè)判斷給定二叉樹(shù)t是否為平衡樹(shù)的c函數(shù)。6266試畫(huà)出adelson插入方法的右改組的轉(zhuǎn)換圖。6569試畫(huà)出用hu-tucker算法構(gòu)造出的最佳葉子查找樹(shù)。66610 畫(huà)出每次插入后的b樹(shù)67612 修改皇后問(wèn)題70613 馬的周游路線(xiàn)7671對(duì)于圖題7.1（p235）的無(wú)向圖，給出：79（1） 表示該圖的鄰接矩陣。（2） 表示該圖的鄰接表。（3） 圖中每個(gè)頂點(diǎn)

6、的度。72對(duì)于圖題7.1的無(wú)向圖，給出：79（1）從頂點(diǎn)1出發(fā)，按深度優(yōu)先搜索法遍歷圖時(shí)所得到的頂點(diǎn)序（2）從頂點(diǎn)1出發(fā)，按廣度優(yōu)先法搜索法遍歷圖時(shí)所得到的頂點(diǎn)序列。73對(duì)于圖題7.3的有向圖，給出：84（1） 表示該圖的鄰接矩陣。（2） 表示該圖的鄰接表。（3） 圖中每個(gè)頂點(diǎn)的入度和出度。74對(duì)于圖題7.3的有向圖，給出：85（1） 從頂點(diǎn)1出發(fā)，按深度優(yōu)先搜索法遍歷圖時(shí)的所得的頂點(diǎn)序列。（2） 從頂點(diǎn)1出發(fā)，按廣度優(yōu)先搜索法遍歷圖時(shí)的所得的定點(diǎn)序列。75對(duì)于圖題7.1的無(wú)向圖，試問(wèn)它是（1）連通圖嗎？（2）完全圖嗎？8576對(duì)于圖題 7.3的有向圖，試問(wèn)它是（1）弱連通圖嗎？（2）強(qiáng)連通圖

7、嗎？8677圖題7-7是有向圖，試問(wèn)其中哪個(gè)圖是86（1） 弱連通的？（2） 強(qiáng)連通的？78具有n個(gè)頂點(diǎn)的連通無(wú)向圖至少有幾條邊？8679具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖至少有幾條邊？86710分別寫(xiě)出用深度和廣度優(yōu)先搜索法遍歷完全無(wú)向圖的頂點(diǎn)序列。 87711改寫(xiě)以深度優(yōu)先搜索法遍歷給定的連通圖的dfs程序。87 712在圖題7.1中，從頂點(diǎn)1出發(fā)，分別畫(huà)出其dfs生成樹(shù)和bfs生成樹(shù)。881.1：比較2個(gè)線(xiàn)性鏈表的c函數(shù)1 存儲(chǔ)法：用兩個(gè)數(shù)組存放線(xiàn)性表。2 存儲(chǔ)結(jié)構(gòu)：一般的順序存儲(chǔ)方式。3 源程序：int comp(int a,int as,int b,int bs) int tmp=as>

8、;bs?as:bs; int i; for(i=0;i<tmp;i+) if(ai>bi) return 1; if(ai<bi) return -1; if(as>bs) return 1; if(bs>as) return -1; return 0;4.測(cè)試用例：1 a3=1,2,3 b3=1,2,3 output : 0;2 a3=1.2.3 b3=1,1,3 output: 1;3 a3=1,2,3 b3=1,2,4 output: -14 a3=1,2,3 b4=1,2,3,0 output: -1;5 a4=1,2,3,0 b3=1,2,3 outpu

9、t: 1;6 a4=1,2,3,0 b3=1,3,2 output:-1;1.2 寫(xiě)一個(gè)倒置順序存貯的線(xiàn)性表的c函數(shù)。要求用最少的附加存貯空間來(lái)完成。· 分析：假設(shè)用數(shù)組a存貯一組int類(lèi)型的數(shù)據(jù)，每次將a0取出，其余數(shù)依次前移，然后將a0放到 尚未倒置的數(shù)據(jù)元素的最后，直至整個(gè)數(shù)組完成倒置。· 算法：（1）取t=a0，余下的a1，a2，.an-1依次前移一個(gè)位置； （2）an-1=t； （3）對(duì)由a0，a1.an-2組成的數(shù)組重復(fù)上述步驟。· 程序： # include<stdio.h> # define n 10 void reverse(a,n)

10、 int a; int n; int t,i,j=0; while(j<n-1) t=a0; for(i=0;i<n-j-1;i+) ai=ai+1; ai=t; j+; void main( ) int an; int i; printf("input the array:n"); for(i=0;i<n;i+) scanf("%d", &ai); reverse(a,n); printf("the reversed array:n"); for(i=0;i<n;i+); printf("%

11、d ",ai); printf("n"); · sample: input the array: 0 1 2 3 4 5 6 7 8 9 the reversed array:9 8 7 6 5 4 3 2 1 01.3 在具有n個(gè)結(jié)點(diǎn)的順序存貯的線(xiàn)性表中，對(duì)值相同的結(jié)點(diǎn)只保留一個(gè)，把多余的結(jié)點(diǎn)刪除掉，使線(xiàn)性表中沒(méi)有值相同的結(jié)點(diǎn)。試編寫(xiě)一個(gè)實(shí)現(xiàn)上述操作的c函數(shù)，并分析該程序的執(zhí)行時(shí)間。解答：首先應(yīng)對(duì)線(xiàn)性表中每一個(gè)結(jié)點(diǎn)進(jìn)行搜索，找到和他值相同的結(jié)點(diǎn)就把其刪除，同時(shí)改變?cè)Y(jié)點(diǎn)的個(gè)數(shù)。主要運(yùn)用兩層循環(huán)：最外層對(duì)線(xiàn)性表中的第0到第n-2個(gè)元素進(jìn)行掃描，第二層是對(duì)

12、于第一層的每一個(gè)元素從其后面一個(gè)元素開(kāi)始掃描，檢查是否有和該元素值相同的元素若有則刪除該元素，若無(wú)則循環(huán)關(guān)鍵值+1進(jìn)行下一個(gè)元素比較，直到線(xiàn)性表最后一個(gè)元素，然后在回到上層循環(huán)。如此繼續(xù)，直到跳出所有循環(huán)時(shí)，所得線(xiàn)性表即為題目要求的線(xiàn)性表。 下面給出實(shí)現(xiàn)的函數(shù)。sq_delete()為刪除一個(gè)結(jié)點(diǎn)的函數(shù)，i表示所要?jiǎng)h除的結(jié)點(diǎn)的下標(biāo)，del()為刪除線(xiàn)性表中所有相同結(jié)點(diǎn)的函數(shù)。其中l(wèi)ist為進(jìn)行操作的線(xiàn)性表，*p_m和*p_n在兩個(gè)函數(shù)中都表示線(xiàn)性表中結(jié)點(diǎn)個(gè)數(shù)。 #include<stdio.h>#define m 100int sq_delete(int list,int *p_m

13、,int i) int j; if(i<0|i>=*p_m) return(1); for(j=i+1;j<*p_m;j+) listj-1=listj; (*p_m)-; return (0);void del(int list,int *p_n) int i,j; for(i=0;i<(*p_n)-1);i+) for(j=i+1;j<(*p_n);j+) if(listi=listj)sq_delete(list,p_n,j);j-;main() int listm,i,n; printf("input the number of the data

14、:n"); scanf("%d",&n); for(i=0;i<n;i+) printf("input data %d:n",i+1); scanf("%d",&listi); del(list,&n); for(i=0;i<n;i+) printf("%d ",listi);對(duì)于以上程序提供一組測(cè)試數(shù)據(jù)：input the number of the data:5輸入一組數(shù)據(jù)為：13 23 33 13 23執(zhí)行完畢后得到的輸出結(jié)果為：13 23 33對(duì)于該程序的時(shí)間復(fù)

15、雜性分析：主要是del 和sq_delete兩個(gè)函數(shù)中的循環(huán)語(yǔ)句的執(zhí)行時(shí)間。一種極端情況是線(xiàn)性表中的數(shù)據(jù)沒(méi)有一個(gè)重復(fù)，則只執(zhí)行del中的循環(huán)體，(n-1)+(n-2)+1=o(n*n);另一種極端情況是線(xiàn)性表中只有一個(gè)元素，其他都與它重復(fù)，此時(shí)del的內(nèi)和外循環(huán)都只執(zhí)行一次，主要的執(zhí)行時(shí)間用在了sq_delete上，可以知道他的復(fù)雜性也是o(n*n).故總的來(lái)說(shuō)該程序的時(shí)間復(fù)雜性是o(n*n)。 1.4 編寫(xiě)一個(gè)求解給定多項(xiàng)式在x=xo(xo為指定的某個(gè)值)時(shí)的值的c函數(shù)。存儲(chǔ)法：定義結(jié)構(gòu)數(shù)組 struct node int exp; float coef; ; typedef struct

16、node term #define max 100 node amax;算法步驟：1 令sum=0, i=02 算出第i項(xiàng)的值，并與sum相加。3 若i<n, 則轉(zhuǎn)2，否則return(sum)程序： float cal ( float x, term a , int n ) float sum; int i, j, k; for ( i=0; i<n; i+ ) for ( k=1, j=1; j<= ai . exp; j+) k=k*x; sum+= ai .coef*k; return(sum); 測(cè)試用例： 令x=2; 多項(xiàng)式為 3x6+8x4+5x2+9 結(jié)果為

17、349。 1.5實(shí)現(xiàn)多項(xiàng)式乘法一：存儲(chǔ)結(jié)構(gòu)：多項(xiàng)式以線(xiàn)性鏈表存儲(chǔ)，以增加其插入刪除的效率。結(jié)果多項(xiàng)式與所給多項(xiàng)式采取相同的存儲(chǔ)結(jié)構(gòu)，以方便實(shí)現(xiàn)多項(xiàng)式的連乘。二：分析 多項(xiàng)式的加法書(shū)上有源程序，而乘法與加法相似，只是由于乘法的規(guī)則與加法不同，因此我用了一個(gè)雙重循環(huán)來(lái)實(shí)現(xiàn)（詳見(jiàn)源程序），得到一個(gè)結(jié)果項(xiàng)之后，查找結(jié)果鏈表，若已有，則看是否相加之后為0，若為0，則將該項(xiàng)刪去，否則，就直接改系數(shù)，若沒(méi)有，則直接鏈上。 原本想用數(shù)組加鏈表的索引法來(lái)實(shí)現(xiàn)，但據(jù)分析后，認(rèn)為并不能顯著提高效率，顯得得不償失，因此，我就使用了最原始的方法，請(qǐng)老師同學(xué)多多指教。三：輸入/輸出輸入：先輸入a、b多項(xiàng)式（根據(jù)提示）輸出

18、：a、b、c（a×b）四：源程序#include<stdio.h>struct node int exp; int data; struct node *next; ;typedef struct node node;int search(int exp,node *c,node *pc,node *qc)*pc=null;*qc=c;if(c=null) return(0);while(*qc)->exp>exp) *pc=*qc;*qc=(*qc)->next;if(*qc)->exp=exp) return(1);return(0);node

19、 *multi(node *a,node *b) node *pa,*pb,*pc,*qc,*p,*c=null; int exp,data,flag; for(pa=a;pa!=null;pa=pa->next) for(pb=b;pb!=null;pb=pb->next) exp=pa->exp+pb->exp;data=pa->data*pb->data; if(data) flag=search(exp,c,&pc,&qc); if(flag) if(!(data+qc->data) pc->next=qc->nex

20、t;free(qc); else (qc->data)+=data; else p=(node *)malloc(sizeof(node); p->data=data;p->exp=exp; if(!pc) c=p; else pc->next=p; p->next=qc; return(c);node* creat()node *root,*p,*q; char ch;int i;printf("do you want to creat a null one(y/n)?n");scanf("%c",&ch);get

21、char();if(ch='y'|ch='y') return(null);p=null;ch='y'for(i=0;ch='y'|ch='y'i+)q=(node*)malloc(sizeof(node);if(p=null) root=q; else p->next=q;printf("nplease input the data of node %d:n",i);scanf("%d",&(q->data);getchar();printf("

22、;please input the exp of node %d:n",i);scanf("%d",&(q->exp);getchar();printf("do you want to continue(y/n)?n");scanf("%c",&ch);getchar();p=q;p->next=null;return(root);void print(node *root)int i=0;if(!root) printf("n0");while(i+,root!=null)p

23、rintf("nnode %d:tdata:%dtexp:%d",i,root->data,root->exp);root=root->next;main()char ch;node *a,*b,*c;clrscr();printf("now please input a:n");a=creat();printf("now please input b:n");b=creat();printf("na:n");print(a);printf("nb:n");print(b);c

24、=multi(a,b);printf("nnnc:n");print(c);五：測(cè)試數(shù)據(jù)：輸入：a：5x6+3x4+2xb：7x3+3x2+5輸出：c：35x9+15x8+21x7+34x6+29x4+6x3+10x輸入：a：0b：5x3+2x2輸出：0輸入：a：3x2+5x1b：3x15c：01.7假設(shè)右邊軌道排列有編號(hào)為1，2，3,n的n節(jié)車(chē)廂，它們依次被拖進(jìn)站，從左邊軌道依次出站的號(hào)的排列順序有a n 種情況 。那么a n是用下列方法所形成的所有可能排列順序的總數(shù)：某時(shí)刻站中只剩下編號(hào)為k+1的車(chē)廂，而此時(shí)左邊軌道是已出站的編號(hào)為1，2，3，,k的車(chē)廂，則排列順序有a

25、k種；右邊軌道是尚未進(jìn)站的編號(hào)為k+1，k+2,k+n的n-k-1節(jié)車(chē)廂，則可能有的排列順序有an-k-1種。因此 給出了前k節(jié)車(chē)廂已出站的情況下所有的排列順序，我們應(yīng)該取遍k（0kn）的所有可能值，獲得akan-k-1這樣形式的所有項(xiàng)，然后把它們相加起來(lái)，可得到如下的關(guān)系式： a0=1； a1=1； an=a0an-1+a1an-2+.+an-1a0 ( n>1) an=akan-k-1 (0kn-1) 為了求解排列順序的數(shù)目，先求解這個(gè)遞推關(guān)系：令 g（x）=a0+a1x+anx? n>1即g（x）=akxk (k0)讓g（x）自乘得 g2(x)=g(x)g(x) =(a0+a

26、1x+a2x2+.)(a0+a1x+a2x2+.) =a0a0+(a0a1+a1a0)x+(a0a2+a1a1+a2a0)x2+. =(akan-k)x? (0n,0kn)由上式可知，g2(x)的xn項(xiàng)的系數(shù)正好是an1。因此有g(shù)2(x)=an+1x? (n0)如果我們用x乘g2(x)，則有 xg2(x)=a1x+a2x2.兩邊都加上a0，又因?yàn)閍0=1，故有 1+x g2(x)=akxk (k0) 1+xg2(x)=g(x)求解得g（x）=1±(1-4x)/2x因?yàn)閍0=1，所以g（x）=1-(1-4x)/2x再根據(jù)二項(xiàng)式定理，將(1-4x)1/2展開(kāi)，得 g(x)=1/2x1-(

27、1n/2)(-4x)n (n0)令n=m+1,則有 g(x)= ( 1/2m+1)(-1)m 22m+1xm (m0) 比較可知an是上式中x?項(xiàng)的系數(shù)。所以 an=(1n+1/2)(-1)n22n+1化簡(jiǎn)得an=1/(n+1)(2nn)n節(jié)車(chē)廂出站有1/(n+1)(2nn)種排列順序。所以，當(dāng) n=3時(shí)，有5種排列順序，分別為，；當(dāng)n=4時(shí)，有14種排列順序。存儲(chǔ)結(jié)構(gòu)可采用棧實(shí)現(xiàn)。1_8.假設(shè)2個(gè)棧共享一個(gè)數(shù)組stackn，編寫(xiě)對(duì)任一棧作進(jìn)棧和出棧運(yùn)算的c函數(shù)，push(x,i) 和pop(i),i=1,2。這里i=1表示左邊的棧，2則表示右邊的棧。要求整個(gè)數(shù)組元素都被占用時(shí)才產(chǎn)生溢出。存儲(chǔ)

28、結(jié)構(gòu)：用一個(gè)數(shù)組存放2個(gè)棧。如圖：(m為數(shù)組元素個(gè)數(shù))32 tail1=0 head1 head2 tail2=m-1head1,head2分別為棧1，棧2中下個(gè)元素入棧的位置，tail1，tail2為兩個(gè)棧底。分析與算法步驟：因?yàn)閠ail10,tail2m1，一般情況下不會(huì)變動(dòng)，所以省去這2個(gè)量。初始值：head10，head2m-1；1執(zhí)行入棧時(shí)：（1） 若head1-1+1head2+1，即head1head2+1時(shí)，整個(gè)數(shù)組滿(mǎn)，溢出。（2） 若對(duì)棧1入棧，把元素存入stackhead1，head1+；（3） 若對(duì)棧2入棧，把元素存入stackhead2，head2；2執(zhí)行出棧時(shí)：（1）

29、對(duì)棧1：若head10，?？眨鰲Ｊ?；否則head1； （2）對(duì)棧2：若head2m1，棧2空，出棧失??；否則head2+；tc程序：include<stdio.h>#define m 10int head1=0,head2=m-1;int stackm;void push(int x,int i)if(head1=head2+1) printf("the stack is full.fail to push.n"); return; if(i=1) stackhead1+=x; else stackhead2-=x;void pop(int i)if(i=1

30、) if(head1=0) printf("the stack is empty.fail to pop.n"); return; *p=stack-head1; else if(head2=m1) printf("the stack is empty.fail to pop."); return; *p=stack+head2; main()int x,i,no=1; for(i=0;i<m;i+) stacki=0; while(no!=0)printf("seclect the operation:npush:1;npop:2;np

31、rint:3nexit:0;n"); scanf("%d",&no); switch(no) case 1: printf("input the number you want push and the team no,n"); scanf("%d %d",&x,&i); if(i=1|i=2) push(x,i); else printf("wrong number.select again.n"); break; case 2: printf("input the t

32、eam you want to pop:n"); scanf("%d",&i); if(i=1|i=2) pop(i); else printf("wrong number,select again.n"); break; case 3: for(i=head1-1;i>=0;i-) printf("%d",stacki); printf("n"); for(i=head2+1;i<m;i+) printf("%d",stacki); printf("n&

33、quot;); break; 測(cè)試用例：在main函數(shù)中，提供了操作的選擇。1為入棧，2為出棧，3為輸出2個(gè)棧中的元素，0為退出操作。第一次進(jìn)棧1：1，2，3，4，5； 輸出：12345第二次進(jìn)棧2：6，7，8，9，10； 輸出：678910棧1連續(xù)出棧5次后，繼續(xù)執(zhí)行出棧，輸出為the stack is empty.fail to pop.棧2連續(xù)出棧3次后，輸出棧2中元素為910110 寫(xiě)出與下列表達(dá)式等價(jià)的后綴表達(dá)式：(1) a+b*c/d+efg+h(2) (a+b)*(c/d)+(ef)(g+h)存儲(chǔ)結(jié)構(gòu)： 對(duì)于兩個(gè)表達(dá)式采用字符數(shù)組存儲(chǔ)形式，并以0作為結(jié)尾。 另外，使用一個(gè)棧來(lái)存放

34、運(yùn)算符，當(dāng)遇到運(yùn)算符,就把運(yùn)算符入棧，直到某個(gè)適當(dāng)?shù)臅r(shí)機(jī)，再讓運(yùn)算符出棧。算法分析：當(dāng)前掃描到的字符按以下幾種情況分別處理：a) 若當(dāng)前的字符是變量，則立即將它輸出。b) 若當(dāng)前的字符是(，則讓(入棧。c) 若當(dāng)前的字符是運(yùn)算符(+,-,*,/,),則將它的（進(jìn)棧前)優(yōu)先級(jí)別與棧頂字符的（棧中）優(yōu)先級(jí)別相比較。如果當(dāng)前的運(yùn)算符的優(yōu)先級(jí)別小于等于棧頂字符的優(yōu)先級(jí)別，那么退出棧頂字符并輸出。這樣的過(guò)程一直進(jìn)行到當(dāng)前的運(yùn)算符的優(yōu)先級(jí)別大于棧頂字符的為止，然后讓當(dāng)前的運(yùn)算符入棧。d) 若當(dāng)前的字符是)，則從棧中依次退出運(yùn)算符并輸出，直到(為止，然后退出(，但不輸出(.e) 若當(dāng)前的字符是0,則從棧中依

35、次退出所有的運(yùn)算符并輸出，直到$為止，$”不退棧，也不輸出。下面給出程序：#define maxn 100int icp(char c) switch(c) case '':return(4); /進(jìn)棧前的運(yùn)算符的優(yōu)先級(jí) case '*': case '/':return(2); case '+': case '-':return(1); int isp(char c) switch(c) case '':return(3); /棧中的運(yùn)算符的優(yōu)先級(jí) case '*': case &

36、#39;/':return(2); case '+': case '-':return(1); case '(':return(0); case '$':return(-1);/置于棧底，保證后面的運(yùn)算符能進(jìn)棧 int ischar(char c) if(c>='a'&&c<='z')|(c>='a'&&c<='z') return(1); else return(0);int mid_to_pos(ch

37、ar midexpress,char posexpress)char stackmaxn,c; int top,i,j; stack0='$' top=0; j=0; i=0; c=midexpress0; while(c!='0') if(ischar(c)posexpressj+=c; elseswitch(c) case '+': case '-': case '*': case '/': case '': while(icp(c)<=isp(stacktop) pose

38、xpressj+=stacktop-; stack+top=c; break; case '(': stack+top=c; break; case ')': while(stacktop!='(') posexpressj+=stacktop-; top-; break; default: return(1); c=midexpress+i; while(top>0) posexpressj+=stacktop-; posexpressj='0' return(0);測(cè)試報(bào)告： void main()char midexp

39、ressmaxn,posexpressmaxn,c; int i,result; i=0; printf("ninput the mid_expresstion:(end with '!')n"); scanf("%c",&c); while(c!='!') midexpressi+=c; scanf("%c",&c); midexpressi='0' result=mid_to_pos(midexpress,posexpress); if(result=1) print

40、f("convertion fails!n"); else printf("the pos_expresstion is:n"); printf("%s",posexpress); 輸入：(a+b*c)d(e*f/g)-h*i!(輸入以!結(jié)尾) 輸出：abc*+def*g/hi*-輸入：a+b*c/d+efg+h!輸出：abc*d/+efg+h+輸入：(a+b)*(c/d)+(ef)(g+h)!輸出：ab+cd/*efgh+111 編寫(xiě)一個(gè)統(tǒng)計(jì)給定的線(xiàn)性鏈表的結(jié)點(diǎn)個(gè)數(shù)的c函數(shù)。存儲(chǔ)結(jié)構(gòu)：連表的結(jié)點(diǎn)采用：struct nodeint d

41、ata;/關(guān)鍵字的類(lèi)型自定 struct node *link;算發(fā)分析：利用鏈表的性質(zhì)（結(jié)點(diǎn)中的指針指向下一個(gè)結(jié)點(diǎn)），逐步向表尾移動(dòng)，以此計(jì)算出結(jié)點(diǎn)數(shù)。下面給出程序：typedef struct nodeint data; struct node *link; node;int count(node *head)node *p;int c=0;p=head;while(p!=null)p=p->link; c+;return(c);測(cè)試報(bào)告：void main()node a10; int i=0; for(;i<9;i+) ai.data=i; ai.link=&ai+

42、1; ai.data=i; ai.link=null; printf("the total amount of the linked node is:%dn",count(&a0);輸入：|0-1-2-3-4-5-6-7-8-9輸出：the total amount of the linked node is:10112 編寫(xiě)一個(gè)將給定的線(xiàn)性鏈表逆轉(zhuǎn)的c函數(shù)，只允許改變結(jié)點(diǎn)的指針值，不允許移動(dòng)結(jié)點(diǎn)值。算法如下：(1) 置p為鏈表首址，r,q為空；(2) 若p為空返回null；算法結(jié)束，轉(zhuǎn)（5），否則轉(zhuǎn)（3）；(3) 若鏈表只有一個(gè)結(jié)點(diǎn)，轉(zhuǎn)（5），否則轉(zhuǎn)（4）；(4)

43、 r<=p,p<=p->link,r->link<=q,置q=r,若p->link為空，轉(zhuǎn)（5），否則轉(zhuǎn)（4）；(5) p->link<=r,返回p,算法結(jié)束。源程序如下：#include <stdio.h>typedef struct node int data; struct node* link; node; node* tranfer(head) node *head; node *p,*q,*r; p=head; r=q=null; if(head=null) return(null); if(p->link!=nul

44、l) do r=p; p=p->link;r->link=q;q=r;while(p->link!=null); p->link=r; return(p); node* create(n)/*建立初始鏈表*/ int n; int i; node *head,*p,*q; if(n=0) return(null); head=(node*)malloc(sizeof(node); p=head; for(i=1;i<n;i+) scanf("%d",&(p->data); q=(node*)malloc(sizeof(node);

45、 p->link=q; p=q; scanf("%d",&(p->data); p->link=null; return(head); main() node *head,*r,*p; int n=5; printf("enter the data:n"); head=create(n); p=head; while(p!=null) printf("%d ",p->data); p=p->link; printf("n"); head=tranfer(head); p=hea

46、d; printf("now the list is:n"); while(p!=null) printf("%d ",p->data); p=p->link; printf("n"); 輸入：1 2 3 4 5輸出：5 4 3 2 11.13對(duì)于給定的線(xiàn)性鏈表,編寫(xiě)一個(gè)把值為a的結(jié)點(diǎn)插在值為b的結(jié)點(diǎn)的前面的c函數(shù)。若值為b的結(jié)點(diǎn)不在線(xiàn)性鏈表中，則把a(bǔ)插在表的最后。存儲(chǔ)結(jié)構(gòu) 利用線(xiàn)形表的鏈接存儲(chǔ)：typedef struct nodechar data; struct node *link;node; 定義指針node *head,*p,*q,*t; 解題思路 指針*head指向鏈表的根結(jié)點(diǎn)，指針p指向值為b的結(jié)點(diǎn)，指針t指向它的前趨結(jié)點(diǎn)，指針q指向插入結(jié)點(diǎn)a。 (1) 如果頭結(jié)點(diǎn)*head為空，或*head的結(jié)點(diǎn)值為b，修改頭指針，結(jié)束算法；(2) 查找值為b的結(jié)點(diǎn)，若找到，把值為a的結(jié)點(diǎn)插到b的前面；(3) 若找不到，把a(bǔ)結(jié)點(diǎn)插在鏈表最后；結(jié)束算法。 程序 #include<stdio.h> typedef struct nodechar data; struct node *link;node; void insert(node *head,char a) n