【正文】 的進一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。1數(shù)據(jù)結(jié)構(gòu)（C 語言版）（第2 版）習(xí)題解析揭安全 李云清 楊慶紅江西師范大學(xué)計算機信息工程學(xué)院聯(lián)系方式：janquan（習(xí)題答案僅供參考）2第1 章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計算機中，并在這些數(shù)據(jù)上定義了一個運算集合。程序是算法的一種描述方式，通過程序可以在計算機上實現(xiàn)算法。為了評價算法的執(zhí)行效率，通常采用大寫O 符號表示算法的時間復(fù)雜度，大寫O 符號給出了函數(shù)f 的一個上限。表11 常用的漸進函數(shù) 算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個數(shù)。in。j=n。jn。A．O(n) B．O(1) C．O(n2) D．O(n3)（6）表達式a*(b+c)?d 的后綴表達式是（ B ）。 設(shè)計一個算法，求順序表中值為x 的結(jié)點的個數(shù)。for (i=0。j=Llength1。amp。【答】：解題思路：棧具有先進后出、后進先出的特點，因此，任何一個調(diào)度結(jié)果應(yīng)該是1，2，3，4全排列中的一個元素。依此遞歸定義，可設(shè)計產(chǎn)生perm(R)的遞歸算法如下：遞歸解法：()includeint cont=1。 str[i]=temp。i++) /*對每個str[i]判斷其后比它小的數(shù)是否為降序序列*/{ m=0。}}}if(flag) /*滿足出棧規(guī)則則輸出str[]中的序列*/{ printf( %2d:,cont++)。n)。}當(dāng)參與進出棧的元素個數(shù)為4 時，輸出的結(jié)果如下圖所示。為得到排列124653 的下一個排列，應(yīng)從已考察過的那部分數(shù)字中選出比數(shù)字4 大，但又是它們中最小的那一個數(shù)字，比如數(shù)字5，與數(shù)字4 交換。rf = fopen(, w) 。while (j=n amp。}}if (flag1){ for (i=1。 /*從后向前找相鄰位置后大前小的元素值*/while (i1 amp。 a[i]a[j]) i。x=a[i]。 /*返回排列總個數(shù)*/}void main(){int n,m=0。結(jié)論：如果n 個數(shù)按編號由小到大的順序進棧，進棧的過程中可以出棧，則所有可能的出棧序列的總數(shù)為：( 1) ! !(2 )!n n nn+11第3 章 線性表的鏈?zhǔn)酱鎯?選擇題（1）兩個有序線性表分別具有n 個元素與m 個元素且n≤m，現(xiàn)將其歸并成一個有序表，其最少的比較次數(shù)是（ A ）。B．node *p=head。pinfo!=x) p=pnext。A．僅修改隊頭指針 B．僅修改隊尾指針C．隊頭、隊尾指針都要修改 D．隊頭,隊尾指針都可能要修改（7）若從鍵盤輸入n 個元素，則建立一個有序單向鏈表的時間復(fù)雜度為（ B ）。（10）在一個單鏈表中，若p 所指結(jié)點不是最后結(jié)點，在p 之后插入s 所指結(jié)點，則執(zhí)行（ B ）。snext=p。printf(\n 請輸入一組以0 結(jié)束的整數(shù)序列：\n)。x)。}printf(\n)。linklist p=headnext。getch()。 pdata!=y){ pre=p。head=creatlinklist()。}程序的一種運行結(jié)果如下圖所示： 設(shè)計一個算法，判斷一個單鏈表中各個結(jié)點值是否有序。amp。pnext amp。print(head)。}程序運行時的三種輸出結(jié)果如下圖所示： 設(shè)計一個算法，利用單鏈表原來的結(jié)點空間將一個單鏈表就地轉(zhuǎn)置。}}int main() /*測試函數(shù)*/{linklist head。rnext=NULL。p=pnext。print(head)。amp。pre=qnext。 /*輸出原單鏈表*/printf(\n 請輸入要刪除的數(shù)據(jù)區(qū)間:\n)?！敬稹浚菏紫榷x雙鏈表的數(shù)據(jù)結(jié)構(gòu)，內(nèi)容如下：typedef int datatype。 /*建立雙鏈表的頭結(jié)點*/headllink=headrlink=NULL。rrlink=s。while (p){ printf(%5d,pdata)。else /*插入值為x 的新結(jié)點*/{ s=(dlinklist)malloc(sizeof(dnode))。20head=creatdlinklist()。insertxaty(head,y,x)。head=creatdlinklist()。r=head。}}int main() /*測試函數(shù)*/{ dlinklist head。 常對數(shù)組進行的兩種基本操作為（ 訪問數(shù)據(jù)元素 ）和（ 修改數(shù)組元素 ）。/* 函數(shù)strpare()的功能是：當(dāng)s1s2 時返回1，當(dāng)s1==s2 時返回0，當(dāng)s1s2 時返回1*/int strpare(seqstring s1,seqstring s2){ int i,m=0,len。}return m。=strlen()。} seqstring。}elsej=next[j]。}if (j==plength) return (iplength)。 //快速模式匹配temppos=pos+T1length。 //修改長度}elseif (lent2lent1) //T2 串長度大于T1 串長度{for (i=Slength1。iT2length。sappearances in characters batch S: \n\n)。scanf(%s,T1str)。free(S)。i=0。j=0。}if(j==) //匹配成功{ c=。k。for(k=0。}}int main(){ int next[MAXSIZE]。=strlen()?！緟⒖汲绦颉浚?**/include include typedef struct node{char data。while ((ch=getchar())!=39。}}if (r!=NULL) rnext=NULL。S2){ if(S1dataS2data)return 1。int k。 /*建立字符串s2*/print(s2)。while(p){s=(linkstring)malloc(sizeof(linkstrnode))。}/**//* 在字符串S 中用T2 替換T1 *//**/linkstring replace(linkstring S,linkstring T1,linkstring T2){linkstring p,q,r,s,pre,temp,pos。q=T1。q=T1。 /*復(fù)制一個T2 串*/while (rnext!=NULL) /*找temp 串的尾結(jié)點*/r=rnext。pos=p。strcreate(amp。printf(\nThe result is:\n)。 /*分別存放稀疏矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/} matrix。amp。a[i][1]b[j][1])){ c[k][0]=b[j][0]。34c[k][1]=a[i][1]。j++。c[0][1]=a[0][1]。 j++)if (Adata[i][j] !=0){ B[k][0]=i。printf(the spmatrix is:\n)。jw。jw。i=0。q)。36while(i=c[0][2]){ printf(%d%5d%5d\n,c[i][0],c[i][1],c[i][2])。Am,amp。i ++){for(j = 0。i = Avalue。while(i = Avalue amp。}else if(Adata[i][1] Bdata[j][1]){Cdata[k][0] = Adata[i][0]。k ++。Cdata[k][1] = Bdata[j][1]。i ++。Cdata[0][2] = k1。printf(Input B matrix:\n)。}程序運行時按照三元組的格式輸入矩陣信息，程序運行結(jié)果如下圖所示： 寫出兩個稀疏矩陣相乘的算法，計算：Cpn = Apm?Bmn其中，A、B 和C 都采用三元組表示法存儲。An,amp。j 3。i ++){for(j = 0。}void Output(matrix *A){int i,j。Adata[0][2] = Avalue。matrix *Input(matrix *A){ int i,j。free(A)。printf(提示：請按三元組格式輸入矩陣內(nèi)容。k ++。}}while(i = Avalue){Cdata[k][0] = Adata[i][0]。Cdata[k][2] = Adata[i][2]。i ++。Cdata[k][2] = Adata[i][2] + Bdata[j][2]。printf(\n)。}return A。Adata[0][1] = An。}matrix。q,b)。w)。sn=w。}printf(the array is:\n)。printf(input numbers:\n)。}B[0][0]=Am。for ( i=0。c[k][2]=a[i][2]。if (c[k][2]!=0 ) k++。k++。i++。i=j=k=1。 已知三維數(shù)組A[3][2][4]，數(shù)組首地址為100，每個元素占用1 個存儲單元，分別計算數(shù)組元素A[0][1][2]在按行優(yōu)先和按列優(yōu)先存儲方式下的地址。strcreate(amp。strcreate(amp。pre=r。while (r!=p) /*首先刪除子串T1,最后p 指向刪除串T1 的下一個結(jié)點*/{s=r。q=qnext。pos=S。30r=s。elseprintf(s1==s2)。 /*建立字符串s1*/print(s1)。}if(S1) return 1。p=pnext。 /*產(chǎn)生新結(jié)點*/if (*S==NULL) /*新結(jié)點插入空表*/{ *S=p。/**//* 尾插法建立單鏈表 *//**/void strcreate(linkstring *S){ char ch。replace(amp。printf(\nInput string t1:)。sstr[slength]=39。\039。else if(){ for(m=slength1。amp。next[i]=j。int length。T2length=strlen(T2str)。T2=(seqstring*)malloc(sizeof(seqstring))。Sstr[Slength]=39。iT2length。for(i=0。lent1=strlen(T1str)。amp。j=1。else if(m==0) printf(s1=s2\n)。23gets()。i++)if([i][i]){m=1。 試編寫一個函數(shù)，實現(xiàn)在順序存儲方式下字符串的strpare（S1，S2）運算。printcdlink(head)。}void printcdlink(dlinklist head){ /*打印雙鏈表*/dlinklist p。getch()。 設(shè)計一個算法，從右向左打印一個雙鏈表中各個結(jié)點的值。y)。pllinkrlink=s。while (p amp。}return head。while (x) /*輸入結(jié)點值信息，以0 結(jié)束*/{ s=(dlinklist ) malloc(sizeof(dnode))。typedef dnode* dlinklist。deletedata(head,x,y)。}}void main() /*測試函數(shù)*/{ linklist head,L。amp。 設(shè)計一個算法，對一個有序的單鏈表，刪除所有值大于x 而不大于y 的結(jié)點。head=creatlinklist()。rnext=p。 /*就地倒置單鏈表*/print(head)。while (p) /*每次從原表取一個結(jié)點插入到新表的最前面*/{q=p。elseif (issorted(head,39。}break。case 39。a39。y,amp。snext=p。pre=head。}main() /*測試函數(shù)*/{linklist head。13p=pnext。p=headnext。sdata=x。}linkn