數(shù)據(jù)結(jié)構(gòu)C語言習(xí)題解答

1、 (2)i=1; k=0;do k+=10*i;i+;while(i<=n-1)當(dāng)n=1時(shí)，執(zhí)行1；當(dāng)n>=2時(shí)，執(zhí)行n-1次；(3)i=1; k=0; do k+ = 10*i; i+;while(i=n);當(dāng)n=2時(shí)，執(zhí)行2次；當(dāng)n!=2時(shí)，執(zhí)行1次；(4)i=1; j=0;while(i+jn) if(i<j) i+; else j+;執(zhí)行n次；(5)x=n; y=0; /n是不小于1的常數(shù)while(x>=(y+1)*(y+1)y+;執(zhí)行n(向下取整)(6)x=91; y=100;while ( y>0 )if(x>100) x-=10; y-; e

2、lse x+ ; If語句執(zhí)行100次(7)for( i=0; i<n; i+)for( j=i; j<n; j+)for( k=j; k<n; k+)x+=2;過程：第二章2.3已知順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個(gè)算法，將元素x插到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲(chǔ)空間是否滿，若滿返回Error；否則從后向前先移動(dòng)數(shù)據(jù)，找到合適的位置插入。Status Insert_SqList(SqList &La,int x)/把x 插入遞增有序表La 中if(L=La.listsize) return ERROR;for(i=La.le

3、ngth-1;La.elemi>x&&i>=0;i-)La.elemi+1=La.elemi;La.elemi+1=x;La.length+;return OK;/Insert_SqList試寫一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)/思路就是兩個(gè)指示變量i，j同時(shí)分別從順序表的開始和結(jié)尾處相向改變void reverse(SqList &A)/順序表的就地逆置ElemType p;for(i=1,j=A.length;i<j;i+,j-)/A.elem

4、i<->A.elemj;p=A.elemi; A.elemi=A.elemj; A.elemj=p; /reverse2.7 已知線性表L采用順序存儲(chǔ)結(jié)構(gòu)存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復(fù)元素：（1）L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。void Delete_SameElem(SqLink &L, int L.length)/內(nèi)層循環(huán)移動(dòng)參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個(gè)表int i=0; int j=i+1; int length=L.length;while(i<length)for(j=i+1;j&

5、lt;length; j+)if(L.Elemj=L.Elemi)/for(k=j; k<length-1; k+)L.Elemk=L.Elemk+1;length-;j-;/移動(dòng)元素后，由于少了一個(gè)元素，因此要減1/end if If(L.Elemj>L.Elemi) break;/第二小問添加此句/end for/end while/end functoion2.8已知線性表L采用鏈?zhǔn)浇Y(jié)構(gòu)存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復(fù)元素：(1)L中數(shù)據(jù)元素?zé)o序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素?zé)o序排列；思路：由于是無序排列

6、，需要線性表中每個(gè)元素都要相互進(jìn)行比較。Status ListDelete（Linklist &L）/L是帶頭結(jié)點(diǎn)的線性表 ElemType *p,*q; p=L->next;q=p->next; /設(shè)定p變化較慢，q變化較快while(p->next) while(q)if(p->data!=q->data) q=q->next;elseq=q->next; p->next=q; /else/whilep=p->next;q=p->next;/開始后一結(jié)點(diǎn)的尋找return OK；/ListDelete(2)L中數(shù)據(jù)元素非遞

7、減有序排列。思路：由于是有序的，遍歷一次線性表就行了Status ListDelete (LinkList &L) ElemType *p,*q; p=L->next;q=p->next;while(p->next) if (p->data!=q->data) p=p->next;/和第一問不同地方 q=p->next; /if else while(p->data=q->data) q=q->next;/多個(gè)連續(xù)的重復(fù)值 /else p->next=q;p=q;q=p->next;/刪除值重復(fù)的結(jié)點(diǎn)，并修改相應(yīng)的

8、指針return OK；/ListDelete2.9 設(shè)有兩個(gè)非遞減有序的單鏈表A,B。請寫出算法，將A和B就地歸并成一個(gè)按元素值非遞增有序的單鏈表。/ 將合并逆置后的結(jié)果放在C表中，并刪除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;/ 保存pa的前驅(qū)指針qb=pb;/ 保存pb的前驅(qū)指針pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&a

9、mp;pb)if(pa->data<pb->data)qa=pa;pa=pa->next;qa->next=A->next;/將當(dāng)前最小結(jié)點(diǎn)插入A表表頭A->next=qa;elseqb=pb;pb=pb->next;qb->next=A->next;/將當(dāng)前最小結(jié)點(diǎn)插入A表表頭A->next=qb;while(pa)qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;while(pb)qb=pb;pb=pb->next;qb->next=A->n

10、ext;A->next=qb;pb=B;free(pb);return OK;2.13 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時(shí)間復(fù)雜度為O(n)的算法，將L改造為L=(a1,a3,.,an,.,a4,a2)。void Reform(DuLinkedList &L)/按1,3,5,.4,2 的順序重排雙向循環(huán)鏈表L 中的所有結(jié)點(diǎn)xt;while(p->next!=L&&p->next->next!=L)p->next=p->next->next;p=p->next; /p指向最后一

11、個(gè)奇數(shù)結(jié)點(diǎn)if(p->next=L) /結(jié)點(diǎn)個(gè)數(shù)是奇數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn)next指向最后一個(gè)偶數(shù)結(jié)點(diǎn) p->next=L->pre->pre;else/結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)，使最后一個(gè)奇數(shù)結(jié)點(diǎn)next指向最后一個(gè)偶數(shù)結(jié)點(diǎn)p->next=L->pre;p=p->next; /此時(shí)p 指向最后一個(gè)偶數(shù)結(jié)點(diǎn)while(p->pre->pre!=L)p->next=p->pre->pre;p=p->next;p->next=L;/最后一個(gè)結(jié)點(diǎn)next指向頭結(jié)點(diǎn) /調(diào)整了next 鏈的結(jié)構(gòu),此時(shí)pre 鏈仍為原狀/調(diào)整pre

12、 鏈的結(jié)構(gòu)for(p=L;p->next!=L;p=p->next) p->next->pre=p;L->pre=p; /頭結(jié)點(diǎn)的pre指向a2結(jié)點(diǎn)/Reform第三章 棧和隊(duì)列3.6 試寫一個(gè)算法，識別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是屬于該模式的字符序列，而“13&31”則不是。算法：int SeqReverse()/判斷輸入的字符串中'&'前和'&'

13、后部分是否為逆串,是則返回1,否則返回0InitStack(s);while(e=getchar()!='&')if(e=) return 0;/不允許在&之前出現(xiàn)push(s,e);/序列1輸入完畢while( (e=getchar()!='')if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;/序列1元素還有剩余return 1;/IsReverse3.7 假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三種符號：圓括號“(”和“)”、方括號“”和“”、

14、花括號“”和“”，且這三種括號可按任意次序嵌套使用。編寫判別給定表達(dá)式中所含的括號是否正確配對的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。算法：Status BracketTest(char *str)/判別表達(dá)式中三種括號是否匹配InitStack(s);for(p=str;*p;p+)if(*p='('|*p=''|*p='') push(s,*p);else if(*p=')' | *p=''|*p='')if(StackEmpty(s) return ERROR;pop(s,c);i

15、f(*p=')'&&c!='(') return ERROR;if(*p=''&&c!='') return ERROR;if(*p=''&&c!='') return ERROR; /必須與當(dāng)前棧頂括號匹配/if/forif(!StackEmpty(s) return ERROR;/進(jìn)棧的符號還有剩余，Errorreturn OK;/BracketTest3.8 設(shè)表達(dá)式由單字母變量、雙目運(yùn)算符和圓括號組成（如:“(a*(b+c)-d)/e）”。試寫

16、一個(gè)算法，將一個(gè)書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式。思路：1.()則將棧內(nèi)元素發(fā)送直至遇到( 4.棧空則直接入棧 5.棧非空時(shí)若優(yōu)先級大于棧內(nèi)則入棧，否則棧內(nèi)元素出棧int RankOfOperator(char c)switch(c)case'#': return -1;case'(': return 0;case'+':case'-': return 1;case'*':case'/':case')':return 2;int Precede(char c, char ch)retu

17、rn RankOfOperator(c)>RankOfOperator(ch);void ExpressionTOPolandStyle(char suffix,char *exp)Stack s; InitStack(s,100); int i=0; char c;while(*exp)if(isdigital(*exp)suffixi+=*exp;elseswitch(*exp)case'(': push(s,'(');case')': while(c=pops(s)!='(') suffixi+=c;break;def

18、ault: if(IsEmpty(s) push(s,*exp);else suffixi+=pop(s);exp-;/與后面的exp+相抵消，使得棧內(nèi)優(yōu)先級大于等于棧外的都出棧 /end switch/end elseexp+;/end whilewhile(!IsEmpty(s) suffixi+=pop(s); suffixi=0;3.10 假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，只設(shè)一個(gè)尾指針指向隊(duì)尾元素，不設(shè)頭指針。試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳回隊(duì)頭元素的值）要點(diǎn)：定義好數(shù)據(jù)類型，帶頭結(jié)點(diǎn)的單循環(huán)鏈表，只有尾指針，注意刪除元素時(shí)只有一個(gè)元素的特殊性typede

19、fint DataTypestruct NodeDataType data;Node * next;struct CycleListQueueNode * tail;void InitCycleListQueue(CycleListQueue&L) L.tail = new Node; L.tail->next = L.tail;void EnterQueue(CycleListQueue&L,DataType value)Node* p = new Node;p->data = value;p->next = L.tail->next;L.tail-&

20、gt;next = p;L.tail = p;void DeparQueue(CycleListQueue&L,DataType &d)if(L.tail->next != L.tail->next->next)Node *p = L.tail->next->next;L.tail->next->next = p->next;d = p->data;if(p=L.tail) L.tail=p->next;delete p;return d;3.11 假設(shè)將循環(huán)隊(duì)列定義為：以rear和length分別指示隊(duì)尾元素和隊(duì)列長

21、度。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)和出隊(duì)算法（在出隊(duì)算法中要傳遞回隊(duì)頭元素的值）。此循環(huán)隊(duì)列的隊(duì)滿條件=MAXQSIZE;入隊(duì)算法：Status EnCyQueue(CyQueue &Q,int x)/帶length 域的循環(huán)隊(duì)列入隊(duì)算法if(Q.length=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;/rear指向隊(duì)尾元素Q.length+;return OK;/EnCyQueue出隊(duì)算法：Status DeCyQueue(CyQueue &Q,int &x)/帶l

22、ength 域的循環(huán)隊(duì)列出隊(duì)算法，用x返回隊(duì)頭元素的值if(Q.length=0) return Error;/空隊(duì)列，錯(cuò)誤head=(Q.rear-Q.length+1)%MAXSIZE; /head指向隊(duì)頭x=Q.basehead;Q.length-;return OK；/DeCyQueue3.12 試寫一個(gè)算法：判別讀入的一個(gè)以為結(jié)束符的字符序列是否是“回文”（所謂“回文”是指正讀和反讀都相同的字符序列，如“xxyzyxx”是回文，而“abcab”則不是回文）。Status Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0InitStack(S);InitQueue(Q

23、);while(c=getchar()!='')Push(S,c);EnQueue(Q,c); /同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/ Test第五章 多維數(shù)組5.4 設(shè)有一個(gè)準(zhǔn)對角矩陣按以下方式存于一維數(shù)組B4m中：0123456k4m-24m-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,2m寫出由一對下標(biāo)(i,j)求k的轉(zhuǎn)換公式。因?yàn)閕行前有2(i-1)個(gè)元素。現(xiàn)考慮i行情況，當(dāng)j是奇數(shù)，i行有1個(gè)元素,

24、k=2(i-1)+1-1=2(i-1)；否則i行有2個(gè)元素，k=2(i-1)+2-1=2i-1。故：k=2i-1 j為奇數(shù)2i-1 j為偶數(shù)或若i為奇數(shù)，k=2(i-1)+j-i=i+j-2;當(dāng)i為偶數(shù)時(shí)，k=2i-(i-j)-1=i+j-1k=i+j-2 i為奇數(shù)i+j-1 i為偶數(shù)5.5 已知稀疏矩陣A4×5如下：(1)用三元組表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的三元組表示意圖；(2)用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，繪出相應(yīng)的十字鏈表示意圖。(1)三元組表：ijv121155212223246424457(2)十字鏈表第六章 數(shù)和二叉樹6.5已知一棵度為k的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的

25、結(jié)點(diǎn)，.，nk個(gè)度為k的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？設(shè)葉子結(jié)點(diǎn)有x個(gè)，則樹的結(jié)點(diǎn)總數(shù)為n1+n2+nk+x;同時(shí)除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都指向一個(gè)結(jié)點(diǎn)，所有從這個(gè)角度考慮樹的結(jié)點(diǎn)總數(shù)為：n1+2n2+knk+1;n1+n2+nk+x=n1+2n2+knk+1,可得x=已知一棵樹如圖6-1所示，畫出與該樹對應(yīng)的二叉樹，并寫出該樹的先根遍歷序列和后根遍歷序列。ABCDEFGHKIJ圖6-1先根遍歷：ABCEIJFGKHD后根遍歷：BIJEFKGHCDA對應(yīng)的二叉樹：ABCDEFGHKIJ 將如圖6-2所示的森林轉(zhuǎn)化為對應(yīng)的二叉樹。K圖6-2ACDEBFGHJILMNO樹對應(yīng)的二叉樹K圖6-2AC

26、DEBFGHJILMNO森林對應(yīng)的二叉樹：KACDEBFGHJILMNO6.11已知某二叉樹的中序序列為DCBGEAHFIJK，后序序列為DCEGBFHKJIA。請畫出該二叉樹。KACDEBFGHJI6.14假設(shè)某個(gè)電文由(a,b,c,d,e,f,g,h)8個(gè)字母組成，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別為(7,19,2,6,32,3,21,10)，試解答下列問題： (1) 畫出出huffman樹；10002c3f511G287a1732e606d19b21g4010h(2) 寫出每個(gè)字母的huffman編碼； a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01

27、 h:1011 (3) 在對該電文進(jìn)行最優(yōu)二進(jìn)制編碼處理后，電文的二進(jìn)制位數(shù)。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 寫出按層次遍歷二叉樹的算法。思路：用隊(duì)列存儲(chǔ)結(jié)構(gòu)，并用遞歸方法Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)/層序遍歷二叉樹InitQueue(Q); /初始化隊(duì)列if(!T) return Error;/空樹，直接返回EnQueue(Q,T);/根結(jié)點(diǎn)入隊(duì)BiTNode *p;while(!QueueEmpty(Q)DeQueue(Q,p);Vi

28、sit(p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);/whilereturn Ok;/LevelOrderTraverse6.19 寫出判斷兩棵給定二叉樹是否相似的算法。(注：兩棵二叉樹B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似。)思路：采用遞歸進(jìn)行比較判斷bool BiTreeSimilar (BiTree T1,BiTree T2)if(T1=Null&&T2=Null)return

29、1;else if(T1=Null | T2=Null) return 0; else return (BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild);6.21 寫出統(tǒng)計(jì)樹中葉子結(jié)點(diǎn)個(gè)數(shù)的算法，樹用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點(diǎn)的firstchild為Null，則為葉子結(jié)點(diǎn)；采用遞歸方法。int CountLeaves(Tree T，int &num)/num傳遞的初值為0 if(T->nextsibling!=Null)

30、num+=CountLeaves (T->nextsibling); if(T->firstchild!=Null) num+=CountLeaves(T->firstchild); else num+=1;/firstchild域?yàn)榭?，則為葉子結(jié)點(diǎn)return num;圖7-1V5V4V2V3V1V6第七章圖7.1 已知有向圖如圖7-1所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強(qiáng)連通分量(1) 鄰接矩陣（2）鄰接表（3）逆鄰接表V5V4V2V3V1V6（4）強(qiáng)連通分量7.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點(diǎn)1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-2深度優(yōu)先序列：1 7 3 4 5 6 2 10 9 8深度優(yōu)先生成樹：廣度優(yōu)