数据结构c语言版习题解答

1、1.3设n是正整数。试写出下列程序段中用记号“”标注的语句的频度:(2) i=1; k=0;do k+=10*i; i+；while(i=2时，执行n-1次；(3) i=1; k=0;do k+ = 10*i; i+;while(i=n);当n=2时，执行2次；当n!=2时，执行1次；i=1； j=0;while(i+j n) if(i=(y+1)*(y+1) y+;执行川向下取整)x=91; y=100;while ( y0 ) if(x100) x-=10; y-; else x+ ;If语句执行100次(7) for( i=0; in; i+)for( j=i; jn; j+)for(

2、k=j; kx&i =0;i-)La.elemi+1=La.elemi;La.elemi+1=x;La.len gth+;return OK;/l nsert_SqList2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表(a1,a 2,a n-1 ,a n) 逆置为(a n,a n-1,，a 2,a 1)/思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)/ 顺序表的就地逆置ElemType p;for(i=1,j=A.le ngth;ij;i+,j-)/A.elemiA.elemj;p=A.elemi;A.ele

3、mi=A.elemj;A.elemj=p;/reverse2.7已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除 L中多余的元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中 数据元素非递减有序排列。int L.le ngth)void Delete_SameElem(SqL ink &L,/内层循环移动参数，中层循环寻找相同元，外层循环遍历整个表int i=0; int j=i+1; int len gth=Len gth;while (ilength)for (j=i+1;jlength; j+)if (L.EIemj=L.EIemi)/for (k=j;

4、 kL.EIemi) break;/第二小问添加此句 /end for /end while /end functoion2.8已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L 中数据元素非递减有序排列。(1) L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。Status ListDelete ( Linklist &L )/L 是带头结点的线性表ElemType *p,*q;p=L-next;q=p-next; /设定 p变化较慢， q变化较快while(p-n e

5、xt)while(q) if(p-data!=q-data)q=q-n ext;elseq=q-n ext;p-n ext=q;/eIse/whiIep=p- next;q=p- next;/开始后一结点的寻找return OK ；/ListDelete(2) L中数据元素非递减有序排列。思路：由于是有序的，遍历一次线性表就行了Status ListDelete (Li nkList &L)ElemType *p,*q;p=L-n ext;q=p-n ext;while(p-n ext)if (p_data!=q_data)p=p- next; /和第一问不同地方q=p-n ext;/ifel

6、se while(p-data=q-data)q=q- next;/ 多个连续的重复值/elsep- next=q;p=q;q=p- next;/删除值重复的结点，并修改相应的指针return OK ；/ListDelete2.9设有两个非递减有序的单链表A,B。请写出算法，将A和B就地归并成一个按元素值非递增有序的单链表。/将合并逆置后的结果放在 C表中，并删除 B表Status ListMergeOppose_L(L in kList &A,L in kList & B,Li nkList &C)Lin kList pa,pb,qa,qb;pa=A;pb=B;qa=pa; / 保存pa的前

7、驱指针qb=pb; /保存pb的前驱指针pa=pa-n ext;pb=pb-n ext;A- next=NULL;C=A;while(pa&pb)if(pa-datadata)qa=pa;pa=pa-n ext;/将当前最小结点插入A表表头qa-n ext=A-n ext;A_n ext=qa;elseqb=pb;pb=pb-n ext;qb-next=A-next;/将当前最小结点插入A表表头A_n ext=qb;while(pa)qa=pa;pa=pa-n ext;qa-n ext=A -n ext;A_n ext=qa;while(pb)qb=pb;pb=pb-n ext;qb-n ex

8、t=A -n ext;A_n ext=qb;pb=B;free(pb);return OK;2.13设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,.,an)。试写时间复杂度为0(n)的算法，将L改造为L=(a1,a3,.,an,.,a4,a。void Reform(DuLinkedList &L)/ 按1,3,5,.4,2的顺序重排双向循环链表L中的所有结点p=L .n ext;while(p-n ext!=L&p-n ext- n ext!=L)p-n ext=p-n ext- n ext;p=p-n ext; /p指向最后一个奇数结点if(p-next=L) /结点个数是奇

9、数，使最后一个奇数结点next指向最后一个偶数结点p-n ext=L-pre-pre;else/结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点p-n ext=L-pre;p=p-next; / 此时p指向最后一个偶数结点while(p-pre-pre!=L)p_n ext=p_pre_pre;p=p-n ext;p-next=L;最后一个结点next指向头结点/ 调整了 next链的结构，此时pre链仍为原状/调整pre链的结构for(p=L;p-n ext!=L;p=p-n ext) p_n ext-pre=p;L-pre=p; /头结点的pre指向a2结点/Reform第三

10、章栈和队列3.6试写一个算法，识别依次读入的一个以砂结束符的字符序列是否为形如“序 列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符 & ,且序 列2是序列1的逆序。例如，“ a+b&b+a是属于该模式的字符序列，而“ 1 + 3&3 1”则不是。算法：int SeqReverse()判断输入的字符串中&前和& 后部分是否为逆串，是则返回1,否则返回0Ini tStack(s);while(e=getchar()!=&)if(e= )return 0;/不允许在&之前岀现push(s,e);/序列1输入完毕while( (e=getchar()!=)if(StackEmpty(

11、s)return 0;pop(s,c);if(e!=c)return 0;if(!StackEmpty(s)return 0;/ 序列1元素还有剩余return 1;/lsReverse3.7假设一个算术表达式中可以包含三种符号：圆括号“（”和“）”、方括号“和“”、花括号“ ”和“ ”，且这三种括号可按任意次序嵌套使用。编写判别 给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中）。算法：Status BracketTest(char *str)Ini tStack(s);for(p=str;*p;p+)if(*p=( | *p= | *p=)push(s,*

12、p);elseif(*p= ) | *p= | *p= )if(StackEmpty(s)return ERROR;pop(s,c);if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR;if(*p=&c!=) return ERROR; / /if/forif(!StackEmpty(s) return ERROR;/ return OK;/BracketTest判别表达式中三种括号是否匹配必须与当前栈顶括号匹配进栈的符号还有剩余，Error3.8设表达式由单字母变量、双目运算符和圆括号组成（如：“（a*（b+c）-d）/e）试写一个算法，

13、将一个书写正确的表达式转换为逆波兰式。思路：1.遇到数字直接发送2.遇到（直接入栈 3.遇到）则将栈内元素发送直至遇至（4.栈空则直接入栈5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈int Ran kOfOperator(char c)switch(c)case#:return-1;case(:return0;case+:case1 1 .return1;case1*1case /case )return 2;int Precede( char c, char ch) return Ran kOfOperator(c)Ra nkOfOperator(ch);void Expressio

14、 nTOPola ndStyle(Stack s; I nitStack(s,100);char suffix, char * exp) int i=0; char c;while (* exp)if (isdigital(*exp)suffixi+=* exp ;else switch (* exp )case (: push(s, ();case ): while (c=pops(s)!=()suffixi+=c;break ;default : if (IsEmpty(s)push(s,* exp);else suffixi+=pop(s);exp -;/与后面的exp+相抵消，使得栈内

15、优先级大于等于栈外的都出栈 /end switch /end elseexp +; /end whilewhile (!lsEmpty(s) suffixi+=pop(s); suffixi=0; 3.10假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素， 不设头指针。试编写相应的队列初始化、入队和出队算法（在出队算法中要传回 队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时 只有一个元素的特殊性typedef int DataTypestruct NodeDataType data;Node * n ext;；struct CycleList

16、QueueNode * tail;；void In itCycleListQueue(CycleListQueue&L)L.tail =new Node;L.tail-n ext = L.tail;void En terQueue(CycleListQueue&L,DataType value)Node* p = new Node;p-data = value;p-n ext = L.tail-n ext;L.tail-n ext = p;L.tail = p;void DeparQueue(CycleListQueue&L,DataType & d)if (L.tail-next != L.

17、tail-next-next)Node *p = L.tail-n ext- n ext;L.tail-n ext- n ext = p-n ext;d = p-data;if (p=L.tail) L.tail=p-next;delete p;return d;3.11假设将循环队列定义为：以rear和length分别指示队尾元素和队列长度。 试给出此循环队列的队满条件，并写出相应的入队和出队算法(在出队算法中要 传递回队头元素的值)。此循环队列的队满条件：Q.le ngth=MAXQSIZE;入队算法：Status EnCyQueue(CyQueue &Q,int x)带 length 域

18、的循环队列入队算法if(Q.le ngth=MAXSIZE) return OVERFLOW;Q.rear=(Q.rea 叶1)%MAXSIZE;Q.baseQ.rear=x; /rear 指向队尾元素Q.le ngth+;return OK;/E nCyQueue出队算法：Status DeCyQueue(CyQueue & Q,i nt &x)带len gth 域的循环队列岀队算法，用x返回队头元素的值if(Q.le ngth=O) return Error;/空队列，错误head=(Q.rear-Q.le ngth+1)%MAXSIZE; /head指向队头x=Q.basehead;Q.

19、le ngth-;return OK ；/DeCyQueue3.12试写一个算法：判别读入的一个以为结束符的字符序列是否是“回文” (所谓“回文”是指正读和反读都相同的字符序列，如“xxyzyxx ”是回文，而“ abcab”则不是回文)。Status Test()/判别输入的字符串是否回文序列，是则返回1,否则返回0In itStack(S);Ini tQueue(Q);while(c=getchar()!=)Push(S,c);En Queue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) ret

20、urn ERROR;return OK;/ Test第五章多维数组5.4设有一个准对角矩阵a 21a22a33a34a43a44a2m,2ma2m,2ma2m,2ma2m,2m按以下方式存于一维数组 B4m中:或若 i 为奇数，k=2(i-1)+j-i=i+j-2;卩+ J-2i为奇数k=li + j-li为偶数当 i 为偶数时，k=2i-(i-j)- 1=i+j-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,2m0123456k4m-24m-1写出由一对下标(i,j)求k的转换公式。因为i行前有2(i-1)素,k=2(i-1)+1-1=2(i-1)个元素。现考

21、虑i行情况，当j是奇数，i行有1个元;否则i行有2个元素，k=2(i-1)+2-1=2i-1。故：5.5已知稀疏矩阵A4x 5如下：0100523060A =00000.04007一(1) 用三元组表作为存储结构，绘出相应的三元组表示意图;(2) 用十字链表作为存储结构，绘出相应的十字链表示意图。(1)三元组表:ijv121155212223246424457(2)十字链表1211552122231424246457data);if(p-lchild) En Queue(Q,p-lchild); if(p-rchild) En Queue(Q,p-rchild);/whilereturn Ok

22、;/LevelOrderTraverse6.19写出判断两棵给定二叉树是否相似的算法。(注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右 子树和B2的左、右子树分别相似。)思路：采用递归进行比较判断bool BiTreeSimilar (BiTree T1,BiTree T2)if(T仁=Null& T2=Null)return 1;else if(T1=Null | T2=Null)return 0;elsereturn(BiTreeSilimar(T1-lchild,T2-lchild)&BiTreeSimilar(T1-rchild,T2-rchild); 6.

23、21写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示思路：在孩子兄弟链表中，若结点的firstchild 为Null ,则为叶子结点；采用递归方法。int CountLeaves(Tree T , int &num)/num 传递的初值为 0 if(T- nextsibli ng!=Null)nu m+=Co un tLeaves (T- nextsibli ng);if(T-firstchild!=Null)nu m+=Co un tLeaves(T- firstchild);elsenu m+=1;/firstchild域为空，则为叶子结点return num;第七章图7.1已知有向图

24、如图7-1所示,请给出该图的(1)邻接矩阵示意图邻接表示意图逆邻接表所有强连通分量V1V5V2V4V3图7-1012345v5v6(1)邻接矩阵000000100100010001001011100000110 0 10(2)邻接表v1 二v2v3v4(4)强连通分量(3 )逆邻接表7.2已知图G的邻接矩阵如图7-2所示。写出该图从顶点1出发的深度优先搜索 序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000

25、018100100001090000101001101000010000深度优先序列：1 7 3 4 5 6 2 10 9 8图7-26 102深度优先生成树：广度优先序列：1 7 9 3 10 5 4 8 6 2广度优先生成树:109.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找, 别讨论两者在等概率时平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定的值（2 ）查找成功，且表中只有一个关键字等于给定值（3 ）查找成功，且表中有若干个关键字等于给定值解：对有序顺序表：.1/ 八 n+21.1+2+. + （ n+1）l =n+12个元素序列的成功查找问题）c 1 丿

26、 cn+12-1+2 + . + n=试在下列三种情况下分K的记录；K的记录；K的记录，要求找出所有这些记录。（将该项看作一项混入原有序列中，问题转变成n+13.1+2 +. + n-(k-1)|n- (k- 1)Ln- k + 2将此K项看作一项2对无序顺序表:1.2.n1n+1-1+2+. + n=n23.?i = (n + k)(n-k+1)Li=k2n - k +12亡 考虑最后一个记录的出现位置画出对长度为17的有序表进行折半查找的判定树，并分别求其等概率时查找长度和查9.3找失败的ASL。1解：ASL= (1?1 2? 2 3? 4 4? 8 5? 2)176ASL= (4? 7 5