數(shù)據(jù)結構C語言習題解答

1、 (2)i=1; k=0;do k+=10*i;i+;while(i<=n-1)當n=1時，執(zhí)行1；當n>=2時，執(zhí)行n-1次；(3)i=1; k=0; do k+ = 10*i; i+;while(i=n);當n=2時，執(zhí)行2次；當n!=2時，執(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ù)元素按非遞減有序排列。試寫一個算法，將元素x插到La的合適位置上，保持該表的有序性。思路：先判斷線性表的存儲空間是否滿，若滿返回Error；否則從后向前先移動數(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試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表（a1,a2, ., an-1,an）逆置為(an,an-1, ., a2,a1)/思路就是兩個指示變量i，j同時分別從順序表的開始和結尾處相向改變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采用順序存儲結構存放，對兩種不同情況分別寫出算法，刪除L中多余的元素，使得L中沒有重復元素：（1）L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。void Delete_SameElem(SqLink &L, int L.length)/內層循環(huán)移動參數(shù)，中層循環(huán)尋找相同元，外層循環(huán)遍歷整個表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-;/移動元素后，由于少了一個元素，因此要減1/end if If(L.Elemj>L.Elemi) break;/第二小問添加此句/end for/end while/end functoion2.8已知線性表L采用鏈式結構存放。對兩種不同情況分別寫出算法，刪除L中值相同的多余元素，使得L中沒有重復元素：(1)L中數(shù)據(jù)元素無序排列；(2)L中數(shù)據(jù)元素非遞減有序排列。（1）L中數(shù)據(jù)元素無序排列；思路：由于是無序排列

6、，需要線性表中每個元素都要相互進行比較。Status ListDelete（Linklist &L）/L是帶頭結點的線性表 ElemType *p,*q; p=L->next;q=p->next; /設定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;/開始后一結點的尋找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;/多個連續(xù)的重復值 /else p->next=q;p=q;q=p->next;/刪除值重復的結點，并修改相應的

8、指針return OK；/ListDelete2.9 設有兩個非遞減有序的單鏈表A,B。請寫出算法，將A和B就地歸并成一個按元素值非遞增有序的單鏈表。/ 將合并逆置后的結果放在C表中，并刪除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;/ 保存pa的前驅指針qb=pb;/ 保存pb的前驅指針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;/將當前最小結點插入A表表頭A->next=qa;elseqb=pb;pb=pb->next;qb->next=A->next;/將當前最小結點插入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 設以帶頭結點的雙向循環(huán)鏈表表示的線性表L=(a1,a2,a3,.,an)。試寫一時間復雜度為O(n)的算法，將L改造為L=(a1,a3,.,an,.,a4,a2)。void Reform(DuLinkedList &L)/按1,3,5,.4,2 的順序重排雙向循環(huán)鏈表L 中的所有結點xt;while(p->next!=L&&p->next->next!=L)p->next=p->next->next;p=p->next; /p指向最后一

11、個奇數(shù)結點if(p->next=L) /結點個數(shù)是奇數(shù)，使最后一個奇數(shù)結點next指向最后一個偶數(shù)結點 p->next=L->pre->pre;else/結點個數(shù)是偶數(shù)，使最后一個奇數(shù)結點next指向最后一個偶數(shù)結點p->next=L->pre;p=p->next; /此時p 指向最后一個偶數(shù)結點while(p->pre->pre!=L)p->next=p->pre->pre;p=p->next;p->next=L;/最后一個結點next指向頭結點 /調整了next 鏈的結構,此時pre 鏈仍為原狀/調整pre

12、 鏈的結構for(p=L;p->next!=L;p=p->next) p->next->pre=p;L->pre=p; /頭結點的pre指向a2結點/Reform第三章 棧和隊列3.6 試寫一個算法，識別依次讀入的一個以為結束符的字符序列是否為形如“序列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 假設一個算術表達式中可以包含三種符號：圓括號“(”和“)”、方括號“”和“”、

14、花括號“”和“”，且這三種括號可按任意次序嵌套使用。編寫判別給定表達式中所含的括號是否正確配對的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。算法：Status BracketTest(char *str)/判別表達式中三種括號是否匹配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; /必須與當前棧頂括號匹配/if/forif(!StackEmpty(s) return ERROR;/進棧的符號還有剩余，Errorreturn OK;/BracketTest3.8 設表達式由單字母變量、雙目運算符和圓括號組成（如:“(a*(b+c)-d)/e）”。試寫

16、一個算法，將一個書寫正確的表達式轉換為逆波蘭式。思路：1.()則將棧內元素發(fā)送直至遇到( 4.?？談t直接入棧 5.棧非空時若優(yōu)先級大于棧內則入棧，否則棧內元素出棧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+相抵消，使得棧內優(yōu)先級大于等于棧外的都出棧 /end switch/end elseexp+;/end whilewhile(!IsEmpty(s) suffixi+=pop(s); suffixi=0;3.10 假設以帶頭結點的單循環(huán)鏈表表示隊列，只設一個尾指針指向隊尾元素，不設頭指針。試編寫相應的隊列初始化、入隊和出隊算法（在出隊算法中要傳回隊頭元素的值）要點：定義好數(shù)據(jù)類型，帶頭結點的單循環(huán)鏈表，只有尾指針，注意刪除元素時只有一個元素的特殊性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 假設將循環(huán)隊列定義為：以rear和length分別指示隊尾元素和隊列長

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

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

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

24、k=2(i-1)+1-1=2(i-1)；否則i行有2個元素，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;當i為偶數(shù)時，k=2i-(i-j)-1=i+j-1k=i+j-2 i為奇數(shù)i+j-1 i為偶數(shù)5.5 已知稀疏矩陣A4×5如下：(1)用三元組表作為存儲結構，繪出相應的三元組表示意圖；(2)用十字鏈表作為存儲結構，繪出相應的十字鏈表示意圖。(1)三元組表：ijv121155212223246424457(2)十字鏈表第六章 數(shù)和二叉樹6.5已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的

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

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

27、 h:1011 (3) 在對該電文進行最優(yōu)二進制編碼處理后，電文的二進制位數(shù)。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 寫出按層次遍歷二叉樹的算法。思路：用隊列存儲結構，并用遞歸方法Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)/層序遍歷二叉樹InitQueue(Q); /初始化隊列if(!T) return Error;/空樹，直接返回EnQueue(Q,T);/根結點入隊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的左、右子樹分別相似。)思路：采用遞歸進行比較判斷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)計樹中葉子結點個數(shù)的算法，樹用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結點的firstchild為Null，則為葉子結點；采用遞歸方法。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域為空，則為葉子結點return num;圖7-1V5V4V2V3V1V6第七章圖7.1 已知有向圖如圖7-1所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強連通分量(1) 鄰接矩陣（2）鄰接表（3）逆鄰接表V5V4V2V3V1V6（4）強連通分量7.2 已知圖G的鄰接矩陣如圖7-2所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖7-2深度優(yōu)先序列：1 7 3 4 5 6 2 10 9 8深度優(yōu)先生成樹：廣度優(yōu)