數(shù)據(jù)結構課習題參考答案

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

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

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

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

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

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

7、嗎？8677圖題7-7是有向圖，試問其中哪個圖是86（1） 弱連通的？（2） 強連通的？78具有n個頂點的連通無向圖至少有幾條邊？8679具有n個頂點的強連通有向圖至少有幾條邊？86710分別寫出用深度和廣度優(yōu)先搜索法遍歷完全無向圖的頂點序列。 87711改寫以深度優(yōu)先搜索法遍歷給定的連通圖的dfs程序。87 712在圖題7.1中，從頂點1出發(fā)，分別畫出其dfs生成樹和bfs生成樹。881.1：比較2個線性鏈表的c函數(shù)1 存儲法：用兩個數(shù)組存放線性表。2 存儲結構：一般的順序存儲方式。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.測試用例：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 寫一個倒置順序存貯的線性表的c函數(shù)。要求用最少的附加存貯空間來完成。· 分析：假設用數(shù)組a存貯一組int類型的數(shù)據(jù)，每次將a0取出，其余數(shù)依次前移，然后將a0放到 尚未倒置的數(shù)據(jù)元素的最后，直至整個數(shù)組完成倒置。· 算法：（1）取t=a0，余下的a1，a2，.an-1依次前移一個位置； （2）an-1=t； （3）對由a0，a1.an-2組成的數(shù)組重復上述步驟。· 程序： # 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個結點的順序存貯的線性表中，對值相同的結點只保留一個，把多余的結點刪除掉，使線性表中沒有值相同的結點。試編寫一個實現(xiàn)上述操作的c函數(shù)，并分析該程序的執(zhí)行時間。解答：首先應對線性表中每一個結點進行搜索，找到和他值相同的結點就把其刪除，同時改變原結點的個數(shù)。主要運用兩層循環(huán)：最外層對線性表中的第0到第n-2個元素進行掃描，第二層是對

12、于第一層的每一個元素從其后面一個元素開始掃描，檢查是否有和該元素值相同的元素若有則刪除該元素，若無則循環(huán)關鍵值+1進行下一個元素比較，直到線性表最后一個元素，然后在回到上層循環(huán)。如此繼續(xù)，直到跳出所有循環(huán)時，所得線性表即為題目要求的線性表。 下面給出實現(xiàn)的函數(shù)。sq_delete()為刪除一個結點的函數(shù)，i表示所要刪除的結點的下標，del()為刪除線性表中所有相同結點的函數(shù)。其中l(wèi)ist為進行操作的線性表，*p_m和*p_n在兩個函數(shù)中都表示線性表中結點個數(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);對于以上程序提供一組測試數(shù)據(jù)：input the number of the data:5輸入一組數(shù)據(jù)為：13 23 33 13 23執(zhí)行完畢后得到的輸出結果為：13 23 33對于該程序的時間復

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

16、node term #define max 100 node amax;算法步驟：1 令sum=0, i=02 算出第i項的值，并與sum相加。3 若i<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); 測試用例： 令x=2; 多項式為 3x6+8x4+5x2+9 結果為

17、349。 1.5實現(xiàn)多項式乘法一：存儲結構：多項式以線性鏈表存儲，以增加其插入刪除的效率。結果多項式與所給多項式采取相同的存儲結構，以方便實現(xiàn)多項式的連乘。二：分析 多項式的加法書上有源程序，而乘法與加法相似，只是由于乘法的規(guī)則與加法不同，因此我用了一個雙重循環(huán)來實現(xiàn)（詳見源程序），得到一個結果項之后，查找結果鏈表，若已有，則看是否相加之后為0，若為0，則將該項刪去，否則，就直接改系數(shù)，若沒有，則直接鏈上。 原本想用數(shù)組加鏈表的索引法來實現(xiàn)，但據(jù)分析后，認為并不能顯著提高效率，顯得得不償失，因此，我就使用了最原始的方法，請老師同學多多指教。三：輸入/輸出輸入：先輸入a、b多項式（根據(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);五：測試數(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假設右邊軌道排列有編號為1，2，3,n的n節(jié)車廂，它們依次被拖進站，從左邊軌道依次出站的號的排列順序有a n 種情況 。那么a n是用下列方法所形成的所有可能排列順序的總數(shù)：某時刻站中只剩下編號為k+1的車廂，而此時左邊軌道是已出站的編號為1，2，3，,k的車廂，則排列順序有a

25、k種；右邊軌道是尚未進站的編號為k+1，k+2,k+n的n-k-1節(jié)車廂，則可能有的排列順序有an-k-1種。因此 給出了前k節(jié)車廂已出站的情況下所有的排列順序，我們應該取遍k（0kn）的所有可能值，獲得akan-k-1這樣形式的所有項，然后把它們相加起來，可得到如下的關系式： a0=1； a1=1； an=a0an-1+a1an-2+.+an-1a0 ( n>1) an=akan-k-1 (0kn-1) 為了求解排列順序的數(shù)目，先求解這個遞推關系：令 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項的系數(shù)正好是an1。因此有g2(x)=an+1x? (n0)如果我們用x乘g2(x)，則有 xg2(x)=a1x+a2x2.兩邊都加上a0，又因為a0=1，故有 1+x g2(x)=akxk (k0) 1+xg2(x)=g(x)求解得g（x）=1±(1-4x)/2x因為a0=1，所以g（x）=1-(1-4x)/2x再根據(jù)二項式定理，將(1-4x)1/2展開，得 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?項的系數(shù)。所以 an=(1n+1/2)(-1)n22n+1化簡得an=1/(n+1)(2nn)n節(jié)車廂出站有1/(n+1)(2nn)種排列順序。所以，當 n=3時，有5種排列順序，分別為，；當n=4時，有14種排列順序。存儲結構可采用棧實現(xiàn)。1_8.假設2個棧共享一個數(shù)組stackn，編寫對任一棧作進棧和出棧運算的c函數(shù)，push(x,i) 和pop(i),i=1,2。這里i=1表示左邊的棧，2則表示右邊的棧。要求整個數(shù)組元素都被占用時才產(chǎn)生溢出。存儲

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

29、對棧1：若head10，?？眨鰲Ｊ?；否則head1； （2）對棧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; 測試用例：在main函數(shù)中，提供了操作的選擇。1為入棧，2為出棧，3為輸出2個棧中的元素，0為退出操作。第一次進棧1：1，2，3，4，5； 輸出：12345第二次進棧2：6，7，8，9，10； 輸出：678910棧1連續(xù)出棧5次后，繼續(xù)執(zhí)行出棧，輸出為the stack is empty.fail to pop.棧2連續(xù)出棧3次后，輸出棧2中元素為910110 寫出與下列表達式等價的后綴表達式：(1) a+b*c/d+efg+h(2) (a+b)*(c/d)+(ef)(g+h)存儲結構： 對于兩個表達式采用字符數(shù)組存儲形式，并以0作為結尾。 另外，使用一個棧來存放

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

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

36、#39;/':return(2); case '+': case '-':return(1); case '(':return(0); case '$':return(-1);/置于棧底，保證后面的運算符能進棧 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);測試報告： 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!(輸入以!結尾) 輸出：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 編寫一個統(tǒng)計給定的線性鏈表的結點個數(shù)的c函數(shù)。存儲結構：連表的結點采用：struct nodeint d

41、ata;/關鍵字的類型自定 struct node *link;算發(fā)分析：利用鏈表的性質（結點中的指針指向下一個結點），逐步向表尾移動，以此計算出結點數(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);測試報告：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 編寫一個將給定的線性鏈表逆轉的c函數(shù)，只允許改變結點的指針值，不允許移動結點值。算法如下：(1) 置p為鏈表首址，r,q為空；(2) 若p為空返回null；算法結束，轉（5），否則轉（3）；(3) 若鏈表只有一個結點，轉（5），否則轉（4）；(4)

43、 r<=p,p<=p->link,r->link<=q,置q=r,若p->link為空，轉（5），否則轉（4）；(5) p->link<=r,返回p,算法結束。源程序如下：#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對于給定的線性鏈表,編寫一個把值為a的結點插在值為b的結點的前面的c函數(shù)。若值為b的結點不在線性鏈表中，則把a插在表的最后。存儲結構 利用線形表的鏈接存儲：typedef struct nodechar data; struct node *link;node; 定義指針node *head,*p,*q,*t; 解題思路 指針*head指向鏈表的根結點，指針p指向值為b的結點，指針t指向它的前趨結點，指針q指向插入結點a。 (1) 如果頭結點*head為空，或*head的結點值為b，修改頭指針，結束算法；(2) 查找值為b的結點，若找到，把值為a的結點插到b的前面；(3) 若找不到，把a結點插在鏈表最后；結束算法。 程序 #include<stdio.h> typedef struct nodechar data; struct node *link;node; void insert(node *head,char a) n