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

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

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

3、儲(chǔ)的結(jié)構(gòu)即數(shù)組實(shí)現(xiàn)。3837編寫一個(gè)實(shí)現(xiàn)快速排序的非遞歸的c函數(shù)。3938對(duì)于分別寫出用下列排序方法對(duì)線性表進(jìn)行排序的結(jié)果。4043將n階三對(duì)角陣（即半帶寬為1的帶狀矩陣）a按行序列序存放在一維數(shù)組b3*n-2中。若aij(|i-j|bs?as:bs; int i; for(i=0;ibi) return 1; if(aibs) return 1; if(bsas) 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:

4、 -14 a3=1,2,3 b4=1,2,3,0 output: -1;5 a4=1,2,3,0 b3=1,2,3 output: 1;6 a4=1,2,3,0 b3=1,3,2 output:-1;1.2 寫一個(gè)倒置順序存貯的線性表的c函數(shù)。要求用最少的附加存貯空間來(lái)完成。 分析：假設(shè)用數(shù)組a存貯一組int類型的數(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 #

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

6、 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)的順序存貯的線性表中，對(duì)值相同的結(jié)點(diǎn)只保留一個(gè)，把多余的結(jié)點(diǎn)刪除掉，使線性表中沒(méi)有值相同的結(jié)點(diǎn)。試編寫一個(gè)實(shí)現(xiàn)上述操作的c函數(shù)，并分析該程序的執(zhí)行時(shí)間。解答：首先應(yīng)對(duì)線性表中每一個(gè)結(jié)點(diǎn)進(jìn)行搜索，找到和他值相同的結(jié)點(diǎn)就把其刪除，同時(shí)改變?cè)Y(jié)點(diǎn)的個(gè)數(shù)。主要運(yùn)用兩層循環(huán)：最外層對(duì)線性表中的第0到第n-2個(gè)元素進(jìn)行掃描，第二層是對(duì)于第一層的每一個(gè)元素從其后面一個(gè)元素開始掃描，檢查是否有和該元素值相同的元素若有則刪除該元素，若無(wú)則循環(huán)關(guān)鍵值+1

7、進(jìn)行下一個(gè)元素比較，直到線性表最后一個(gè)元素，然后在回到上層循環(huán)。如此繼續(xù)，直到跳出所有循環(huán)時(shí)，所得線性表即為題目要求的線性表。 下面給出實(shí)現(xiàn)的函數(shù)。sq_delete()為刪除一個(gè)結(jié)點(diǎn)的函數(shù)，i表示所要?jiǎng)h除的結(jié)點(diǎn)的下標(biāo)，del()為刪除線性表中所有相同結(jié)點(diǎn)的函數(shù)。其中l(wèi)ist為進(jìn)行操作的線性表，*p_m和*p_n在兩個(gè)函數(shù)中都表示線性表中結(jié)點(diǎn)個(gè)數(shù)。 #include#define m 100int sq_delete(int list,int *p_m,int i) int j; if(i=*p_m) return(1); for(j=i+1;j*p_m;j+) listj-1=listj;

8、(*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:n); scanf(%d,&n); for(i=0;in;i+) printf(input data %d:n,i+1); scanf(%d,&listi); del(list,&n); for(i=

9、0;in;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ù)雜性分析：主要是del 和sq_delete兩個(gè)函數(shù)中的循環(huán)語(yǔ)句的執(zhí)行時(shí)間。一種極端情況是線性表中的數(shù)據(jù)沒(méi)有一個(gè)重復(fù)，則只執(zhí)行del中的循環(huán)體，(n-1)+(n-2)+1=o(n*n);另一種極端情況是線性表中只有一個(gè)元素，其他都與它重復(fù)，此時(shí)del的內(nèi)和外循環(huán)都只執(zhí)行一次，主要的執(zhí)行時(shí)間用在了sq_delete上，可以知道他的復(fù)雜性也是o(n*n

10、).故總的來(lái)說(shuō)該程序的時(shí)間復(fù)雜性是o(n*n)。 1.4 編寫一個(gè)求解給定多項(xiàng)式在x=xo(xo為指定的某個(gè)值)時(shí)的值的c函數(shù)。存儲(chǔ)法：定義結(jié)構(gòu)數(shù)組 struct node int exp; float coef; ; typedef struct node term #define max 100 node amax;算法步驟：1 令sum=0, i=02 算出第i項(xiàng)的值，并與sum相加。3 若in, 則轉(zhuǎn)2，否則return(sum)程序： float cal ( float x, term a , int n ) float sum; int i, j, k; for ( i=0; in

11、; 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é)果為 349。 1.5實(shí)現(xiàn)多項(xiàng)式乘法一：存儲(chǔ)結(jié)構(gòu)：多項(xiàng)式以線性鏈表存儲(chǔ)，以增加其插入刪除的效率。結(jié)果多項(xiàng)式與所給多項(xiàng)式采取相同的存儲(chǔ)結(jié)構(gòu)，以方便實(shí)現(xiàn)多項(xiàng)式的連乘。二：分析 多項(xiàng)式的加法書上有源程序，而乘法與加法相似，只是由于乘法的規(guī)則與加法不同，因此我用了一個(gè)雙重循環(huán)來(lái)實(shí)現(xiàn)（詳見源程序），得到一個(gè)結(jié)果項(xiàng)之后，查找結(jié)果鏈表，若已有，則看是否相加之后為0，若為0，則將該項(xiàng)刪去，否則

12、，就直接改系數(shù)，若沒(méi)有，則直接鏈上。 原本想用數(shù)組加鏈表的索引法來(lái)實(shí)現(xiàn)，但據(jù)分析后，認(rèn)為并不能顯著提高效率，顯得得不償失，因此，我就使用了最原始的方法，請(qǐng)老師同學(xué)多多指教。三：輸入/輸出輸入：先輸入a、b多項(xiàng)式（根據(jù)提示）輸出：a、b、c（ab）四：源程序#includestruct 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(*

13、qc)-expexp) *pc=*qc;*qc=(*qc)-next;if(*qc)-exp=exp) return(1);return(0);node *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) i

14、f(!(data+qc-data) pc-next=qc-next;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);getchar();if(ch=y|c

15、h=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(please input the exp of node %d:n,i);scanf(%d,&(q-exp);getchar();printf(do you want to continue(y/n)?n);s

16、canf(%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)printf(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=c

17、reat();printf(na:n);print(a);printf(nb:n);print(b);c=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é)車廂，它們依次被拖進(jìn)站，從左邊軌道依次出站的號(hào)的排列順序有a n 種情況 。那么a n是用下列方法所形成的所有可能排列順序的總數(shù)：某時(shí)刻站中只剩下編號(hào)為k

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

19、0)讓g（x）自乘得 g2(x)=g(x)g(x) =(a0+a1x+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)式定理，將

20、(1-4x)1/2展開，得 g(x)=1/2x1-(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é)車廂出站有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，編寫對(duì)任一棧作進(jìn)棧和出棧運(yùn)算的c函數(shù)，push(x,i) 和pop(i),i=1,2。這里i=1表示左邊的棧，2則表示

21、右邊的棧。要求整個(gè)數(shù)組元素都被占用時(shí)才產(chǎn)生溢出。存儲(chǔ)結(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ù)組滿，溢出。（2） 若對(duì)棧1入棧，把元素存入stackhead1，head1+；（3） 若對(duì)棧2入棧，把元素存入s

22、tackhead2，head2；2執(zhí)行出棧時(shí)：（1）對(duì)棧1：若head10，?？?，出棧失??；否則head1； （2）對(duì)棧2：若head2m1，棧2空，出棧失敗；否則head2+；tc程序：include#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)

23、 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=0;i-) printf(%d,stacki); printf(n); for(i=head2+1;i=a&c=a&c=z) return(1); else return(0);int mid_to_pos(char

24、 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)0) posexpressj+=stacktop-; posexpressj=0; return(0);測(cè)試報(bào)告： void main()char midexpressmaxn,posex

25、pressmaxn,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) printf(convertion fails!n); else printf(the pos_expresstion is:n); printf(%s,posexpress); 輸入

26、：(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 編寫一個(gè)統(tǒng)計(jì)給定的線性鏈表的結(jié)點(diǎn)個(gè)數(shù)的c函數(shù)。存儲(chǔ)結(jié)構(gòu)：連表的結(jié)點(diǎn)采用：struct nodeint data;/關(guān)鍵字的類型自定 struct node *link;算發(fā)分析：利用鏈表的性質(zhì)（結(jié)點(diǎn)中的指針指向下一個(gè)結(jié)點(diǎn)），逐步向表尾移動(dòng)，以此計(jì)算出結(jié)點(diǎn)數(shù)。下面給出程序：typedef struct nodeint data; struct nod

27、e *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(;i9;i+) ai.data=i; ai.link=&ai+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

28、the linked node is:10112 編寫一個(gè)將給定的線性鏈表逆轉(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) r=p,plink,r-linklink為空，轉(zhuǎn)（5），否則轉(zhuǎn)（4）；(5) p-link=r,返回p,算法結(jié)束。源程序如下：#include typedef struct node int data; struct node* link; node; node* tranfer(head) nod

29、e *head; node *p,*q,*r; p=head; r=q=null; if(head=null) return(null); if(p-link!=null) 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;idata); q=(n

30、ode*)malloc(sizeof(node); 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=head; printf(now the list is:n); while(p!=null) pr

31、intf(%d ,p-data); p=p-link; printf(n); 輸入：1 2 3 4 5輸出：5 4 3 2 11.13對(duì)于給定的線性鏈表,編寫一個(gè)把值為a的結(jié)點(diǎn)插在值為b的結(jié)點(diǎn)的前面的c函數(shù)。若值為b的結(jié)點(diǎn)不在線性鏈表中，則把a(bǔ)插在表的最后。存儲(chǔ)結(jié)構(gòu) 利用線形表的鏈接存儲(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為空，或*

32、head的結(jié)點(diǎn)值為b，修改頭指針，結(jié)束算法；(2) 查找值為b的結(jié)點(diǎn)，若找到，把值為a的結(jié)點(diǎn)插到b的前面；(3) 若找不到，把a(bǔ)結(jié)點(diǎn)插在鏈表最后；結(jié)束算法。 程序 #include typedef struct nodechar data; struct node *link;node; void insert(node *head,char a) node *p,*q,*t; q=(node*)malloc(sizeof(node); q-data=a; if(*head=null|(*head)-data=b) q-link=*head; *head=q; return; for(p=*head;p-data!=b&p!=null;p=p-link) t=p; q-link=p; t-link=q; 測(cè)試用例1 原鏈表：b,c,d,e,g,h插入a結(jié)點(diǎn)后：a,b,c,d,e,f,g,h測(cè)試用例2 原鏈表：c,d,e,f,g,h 插入a結(jié)點(diǎn)后:c,d,e,f,g,h,a測(cè)試用例3 原鏈表：c,d,e,b,f,g,h插入a結(jié)點(diǎn)后:c,d,e,a,b,f,g,h1-14 對(duì)于