《数据结构(C语言描述)》-马秋菊-源代码和习题参考答案.doc

习题配套第一章2C、A、B、B、A、A、D3D=A,B,C,E,F,G,H,I,J;R=,ABCEFGHI题1-3图 J4顺序、链式、索引、哈希。*5解：100n22nn至少要多大6.(n)、(n)、(n)、()、(5)当nm，(n),当mn，(m)7n!2100lgnn1/2n3/2(3/2)n2nnlgnnn第二章1、2AAD4顺序表void Delete_SeqListx(SeqList *L,ElemType x)/*删除表中值为x元素*/inti,j;for(i=1;ilength;i+)if(L-elemi=x)for(j=i;jlength-1;j+)L-elemj=L-elemj+1;L-length-;/*向上移动*/O(n2)链表void del_link(LinkList H，int x)/*删除数据域为x的结点*/LNode *p，*q;p=H;q=H-next;while(q!=NULL)if(q-data=x)p-next=q-next;free(q);q=p-next;elsep=q;q=q-next;O(n)5int Delete_SeqListx(SeqList *L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/intj;if(i1|kL-length)/*检查空表及删除位置的合法性*/printf(不存在第i个元素);return ERROR;for(j=i;jlength-k;j+)L-elemj=L-elemj+k; /*向上移动*/L-length-=k;Return OK;/*删除成功*/O(n)6void Delete_SeqListx(SeqList *L,ElemType x)/*将表中值为x元素换成y*/inti,j;for(i=1;ilength;i+)if(L-elem=x)L-elemi=y;/* */O(n)7写一算法在循环单链表上实现线性表的CList_length(L)运算。int link_length(LinkList H)LNode *p;int i=0;p=H;while(p-next!=H)i+;p=p-next;return i;O(n)8在用头指针表示的单循环链表中，查找开始结点a1的时间是O(1)，然而要查找终端结点则需从头指针开始遍历整个链表，其时间是O(n)。但在很多实际问题中，表的操作常常是在表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rear-next-next和rear，显然，查找时间都是O(1)。9.int Insert_LinkListab(LinkList H, ElemType a,ElemType b)/*在单链表中值为a的结点前插入一个值为b的结点*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-data!=a) /*q-next&q-next-data!=a*/q=p;p=p-next;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s-data=b;s-next=q-next;/*新结点插入在第i-1个结点的后面*/q-next=s；return OK;/*Insert_LinkListab*/10顺序表void Reverse_Sq(SqList *L)/*顺序表的就地逆置*/for(i=1，j=L.len;inext;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next;/*把H的元素逐个插入新表表头*/q-next=p;s-next=q;H-next=s;/*Reverse_L*/分析：本算法的思想是，逐个地把L的当前元素q插入新的链表头部，p为新表表头。11void merge1(LinkList &A,LinkList &B,LinkList &C)/*把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间*/p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q;/*将B的元素插入*/if(s)t=q-next;q-next=s;/*如A非空,将A的元素插入*/p=s;q=t;/*while*/*merge1*/12Status Delete_Pre(CiLNode s)/*删除单循环链表中结点p的直接前驱*/q=p;while(q-next-next!=p)q=q-next;/*找到p的前驱的前驱*/s=q-next;q-next=p;free(s);return OK;/*Delete_Pre*/13Status Insert_SqList(SeqList &L，int x)if(L-length+1m-1)return ERROR;L-length+;i=L-length;while(L-elemix&i0;)L-elemi+1=L-elemi;i-;L-elemi+1=x;return OK;/*Insert_SqList14intInsert_Linkx(LinkList H,ElemType x)/*在值递增单链表中插入一个值为x的结点，仍递增*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-datanext&q-next-datanext;/*查找a结点*/s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/s-data=x;s-next=q-next;/*新结点插入*/q-next=s；return OK;/*Insert_Linkx*/15源程序代码：（在TubroC2.0测试通过）#include#includestructnodeintnumber;/*人的序号*/intcipher;/*密码*/structnode*next;/*指向下一个节点的指针*/;structnode*CreatList(intnum)/*建立循环链表*/inti;structnode*ptr1,*head;if(ptr1=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);returnptr1;head=ptr1;ptr1-next=head;for(i=1;inext=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);ptr1-next=head;returnhead;ptr1=ptr1-next;ptr1-next=head;returnhead;main()inti,n=30,m;/*人数n为30个*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;inumber=i;head-cipher=rand();head=head-next;m=rand();/*m取随机数*/i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/while(head-next!=head)/*当剩下最后一个人时，退出循环*/if(i=m)ptr=head-next;/*ptr记录数到m的那个人的位置*/printf(number:%dn,ptr-number);printf(cipher:%dn,ptr-cipher);m=ptr-cipher;/*让m等于数到m的人的密码*/head-next=ptr-next;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=hea/d-next;/*head移向后一个节点*/free(ptr);/*释放ptr指向的内存*/i=0;/*将i重新置为0，从0再开始数*/elsehead=head-next;i+;printf(number:%dn,head-number);printf(cipher:%dn,head-cipher);free(head);/*让最后一个人也出列*/16void SqList_Intersect(SqList A,SqList B,SqList &C)/*求元素递增排列的线性表A和B的元素的交集并存入C中*/i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj)C.elem+k=A.elemi;/当发现了一个在A,B中都存在的元素,/就添加到C中i+;j+;/*while*/*SqList_Intersect*/17Status DuLNode_Pre(DuLinkList*H)/*完成双向循环链表结点的pre域*/p=H;while(q-next!=H)p-next-pre=p;p=p-next;return OK;/*DuLNode_Pre*/第三章 栈与队列1假定有编号A、B、C的3辆列车顺序开进一个栈式结构的站台，请写出每一种开出站台的列车编号顺序(注：每一列车开出栈开出站台后，不允许再进栈)。2指出下述程序段的功能是什么？ void Demo1(SeqStack *S) int i; arra16;n=16；initStack(&S);for(i=0,inext=NULL;s=( LinkStack *)malloc（sizeof（LinkStack）;s-top= p; 判栈空int Empty_LS（LinkStack *s ） return s-top-next=NULL; 入栈 LinkStack *Push_LS（LinkStack *s , ElemType x） StackNode *p=(StackNode*)malloc（sizeof（StackNode）; p-data=x; p-next=s-top-next; /* 将元素x插入链栈顶 */ s-top-next =p ; return s; 出栈int Pop_LS(LinkStack *s , ElemType *y) StackNode *p; if （Empty_LS（s）printf (Stack Underflow.) ; /* 下溢 */ return OVERFLOW; else *y=s-top-next-data ; = s-top-next ; s-top-next=p-next ; free (p); return OK ; 取栈顶元素int GetTop(LinkStack *s,ElemType *y)if(Empty_LS(s )printf(Stack underflow.);/*下溢*/return OVERFLOW;else*y= s-top-next-data;return OK;4Status AllBrackets_Test(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);if(*p=)&c!=()return ERROR;if(*p=)&c!=return ERROR;if(*p=)&c!=return ERROR;/*必须与当前栈顶括号匹配*/*for*/if(!StackEmpty(s)return ERROR;return OK;/*AllBrackets_Test*/或int PairBracket(char *S)/*检查表达式中括号是否配对*/int i;SeqStack T;/*定义一个栈*/InitStack(&T);for(i=0;istrlen(S);i+)if(Si=()Push(&T，Si);/*遇(时进栈*/if(Si=)Pop(&T);/*遇)时出栈*/return !EmptyStack(&T);/*由栈空否返回正确配对与否*/5写出计算表达式5+3*（3/6-7）时操作数和算符栈的变化情况。 表达式5+3*（4/6-7）的求值过程 步骤运算符栈OPTR对象栈OPND读字符主要操作1#55+3*（3/6-7）#5入栈OPND2# +5+3*（3/6-7）#+入栈OPTR3# +5，33*（3/6-7）#3入栈OPND4# + *5，3*（3/6-7）#*入栈OPTR5# + * (5，3（3/6-7）#( 入栈OPTR6# + * (5，3，34/6-7）#3入栈OPND7# +* ( /5，3，3/6-7）#/入栈OPTR8# + * ( /5，3，3，66-7）#6入栈OPND9# + * (5，3，0.5-7）#3，6出栈OPND，/出栈OPTR求4/6，结果0.5入栈OPND10# +* (-5，3，0.5-7）#-入栈OPTR11# +* (-5，3，0.5，77）#7入栈OPND12# + * (5，3，-6.5）#0.5，7出栈OPND，-出栈OPTR求0.5-7，结果-6.5入栈OPND13# + *5，3，-6.5#( 出栈14# +5，-19.5#3，-6.5出栈OPND，*出栈OPTR求3*-6.5，结果-19.5入栈OPND15#-14.5#5，-19.5出栈OPND，*出栈OPTR,求5+-19.5，结果-14.5入栈OPND16#-14.5#RERTURN(-14.5) 6对于给定的十进制正整数，输出对应的八进制正整数。(1)写出递归算法。(2)写出非递归算法。(1)递归算法。void conversion1(int N, int R) if ( N0) push(S,n); n=n-1 ; while (!EmptyStack(S) ) Pop(S,i); f=f*i; return (f) ; 8.void huiwen()Init_LS(s); printf(Please input a string:n); for(i=0;(i20)&(ai=getchar()!=n);+i); /*输入字符串*/ for(j=0;ji/2;+j) /* 字符串的前一半入栈*/ Push_LS(s,aj); for(j=i-i/2;jrear-sq-front sq-rear=sq-frontcount= m-(sq- front-sq-rear) sq-rearfront11循环队列的优点是什么？如何判别它的空和满？优点：防止假溢出；判别循环队列的空：return(sq-rear=sq-front)；判别循环队列的满：return(sq-rear+1)%MAXSIZE=sq-front)12假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素位置(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。typedef struct qnode ElemType data; struct qnode *next; QCNode; /* 链式循环链队列结点的类型 */typedef struct QCNode *rear; LCQueue ; /* 只设一个指向队尾元素的指针 */（1）置空队算法：void Init_LCQueue(LCQueue *Lcq ) p=(QCnode*)malloc(sizeof(QCNode); /* 申请头结点 */ p-next=p; Lcq-rear=p; （2）判队空算法：int Empty_LCQueue( LCQueue *Lcq) return Lcq-rear-next=Lcq-rear; /* 或Lq-rear=NULL; */ （3）入队算法：void In_LCQueue(LCQueue *Lcq , ElemType x) /*进队操作*/ LCQueue *p; p=(QCNode*)malloc(sizeof(QCNode); /* 申请新结点 */ p-data=x; p-next= Lcq-rear-next; Lcq-rear-next=p; Lcq-rear=p; /* In_LCQueue */（4）出队算法：int Out_LCQueue(LCQueue *Lq , ElemType *y) LCQueue p ; if (Empty_LCQueue(Lq) ) printf (队空) ; return OVERFLOW ; /* 队空, 出队失败 */ else p=Lcq-rear-next-next; /* 队头第一个数据元素结点*/ Lcq-rear-next-next =p-next ; *y=p-data; /* 队头元素放y中 */ free (p); return OK; 13假设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针，用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队列的算法。typedef struct queuenode ElemType elemMAXSIZE; /* 队列中数据元素的存储空间 */ int front ,count; /* 队头指针、队中元素数量 */ CirQueue;/* 以上是结点类型的定义 */ void Init_Queue ( CirQueue *Q) /* 置空队 */ Q-front=Q-count=0; int Empty_Queue( CirQueue *Q) /* 判队空 */ return (Q-count=0); int In_Queue (CirQueue *Q, ElemType x) /* 入队 */ if(Q-count=MAXSIZE) printf(队已满，不可以入队); return OVERFLOW; Q-elem(sq-front+sq-count)%MAXSIZE=x; sq-count +; return OK; int Out_Queue( CirQueue *Q,ElemType *y) /* 出队 */ if(Empty_Queue(Q) printf(队已空，无元素可以出队); return OVERFLOW); *y=sq-elemsq-front; /* 读出队头元素 */ sq-front=(sq-front+1)%MAXSIZE; sq-count-; return OK; int Front_Queue( CirQueue *Q, ElemType *y) /* 取队头元素 */ if(Empty_Queue(Q) printf(队空，无元素可取); return OVERFLOW); *y=sq-elemsq-front; /* 读出队头元素 */ return OK; 14设长度为n的链队列用单循环链表表示，若只设头指针，则入队出队操作的时间复杂度是多少？若只设尾指针呢？若只设头指针，则入队操作的时间复杂度是O(1)，出队操作的时间复杂度是O(n)；若只设尾指针，则入队操作的时间复杂度都是O(1)。*15写一个算法，借助于栈将一个单链表置逆。第4章 数组1请按行和按列优先顺序列出二维数组A34的所有元素在内存中的存储次序，开始结点为a00。a00 a10 a20 a01 a11 a21 a02 a12 a22 a03 a13 a232写出三维数组地址计算公式。设三维数组Amn*p，先行，列，最后Z方向LOC（Aijk）= LOC（A00 0）+(imn+jm+k) L 3设有三对角矩阵A nn，将其三条对角线上的元素逐行地存储到向量B03n-3中，使得Bk=aij，求：用i,j表示k的下标变换公式。Aij之间的对应关系为：k=2i+j4二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素（ ）的起始地址相同。A. m24 B. M34 C. M35 D. M43M35 与M存储时元素M35 起始地址相同。5数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A85的起始地址是（2），若该数组按列存放时，元素A85的起始地址是（）。 （1） A. 80 B. 100 C. 240 D. 270 （2） A.SA+141 B.SA+144 C.SA+222 D.SA+225（3） A.SA+141 B.SA+180 C.SA+222 D.SA+225（1）C. （2） C. （3） A6对于二维数组Amn，其中m=80，n=80，先读入m，n，然后读入该数组的全部元素，对如下三种情况分别编写相应函数： (1) 求数组A边界元素之和。int sum( L ) int row,col,sum=0;for ( row=0;rown;row+) sum= L0row;sum= sum+Lm-1row;/*列*/for (col = 0; coln;col+) sum= Lcol0;sum= sum+ Lcolm-1; /*行*/ (2)求从A00开始的互不相邻的各元素之和；int sum2( L ) int row,col,sum1=0,sum2=0;for ( row=0;rown;row+,row+) for (col=0; coln;col +, col +) sum1= sum1+Lrowcol; sum2= sum2+Lrow+1col+1; (3)当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息。int sum2( L ) int row,col,sum3=0, sum3=0;if(m!=n) printf (m!=n !n);elsefor ( row=0;rowrheadi; while(q)&(q-colright; if(!q) printf(“not searched!”;return NULL;) p=M-cheadj; while(q)&(q -rowdown; if(!p) printf(“not searched!”;return NULL;) return p;（2）已知数据元素的值x，查找 x 在A中的行、列号；QLNode * searchx(CrossList M,ElemType x) int i; /*mu,nu*/for (i=1;irheadi; if (q)&(q-vx) q=q-right; else return q;9简述广义表和线性表的区别和联系。答：相同点：线性；不同点：数据元素分为原子和广义表。10设广义表L=(),()，试问head(L),tail(L)，L的长度、深度各为多少？head(L)= ()tail(L)= ()L的长度为2。11求下列广义表运算的结果(1) head(a,b,c)= (a,b,c)；(2) tail(b,d,p,h) =()；(3) head(a,b),(c,d) =(a,b),(c,d)；(4) tail(a,b),(c,d) =()；(5)head(tail(a,b),(c,d) =()；(6) tail(head(a,b),(c,d) =()第6章 树树的形状acbfgdeljkimmh1.根据题意画出树的形状为右图：a是根结点，mndfjkl是叶结点；c是g的双亲；c，a是g的祖先；j，k是g的孩子；imn是e的子孙；d是e的兄弟；g，h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。2三个结点的二叉树如下所示：有五种形态：(1)(2)(3)(4)(5)3分别写出图6-28(a)所示的二叉树的前序、中序和后序遍历序列。前序ABCDEF中序ACEDB后序EDCBA4画出图6-28(b)所示二叉树顺序存储和二叉链表的存储结构。BACDEABCDGEFHI(b)(a)图6-285请画出如图6-29所示两棵二叉树的顺序存储结构，并比较每棵二叉树所用的存储空间的大小。CBADLKMN图6-29 (a)(b)(b) 所用的存储空间的大6一棵完全二叉树的第3层上有4个叶子结点，问该二叉树最多有多少个结点？7个结点7已知一棵二叉树只存在度数为0或度数为2的结点，度数为2的结点有19个，问度数为0的结点有多少个？20个，分析：根据公式n0=n2+1，有n0=19+1=208写出用非递归实现二叉树的中序遍历算法，并分析其时间复杂度和栈所需要的最大容量。二叉树的中序遍历的非递归算法。void Inorder2（BTNode *bt） /* 利用栈实现前序遍历非递归算法 */ p=bt；top=-1； while(p|top-1) if(p) /* 二叉树非空 */ +top ；stop=p ； /*根结点指针进栈*/p=p-lchild ； /*p移向左孩子*/else /*栈非空*/ p=stop ；-top ； /*双亲结点指针出栈*/ printf(p-data)； /*访问根结点，输出结点*/ p=p-rchild ； /*p移向右孩子*/ /* Inorder2 */9若已知某二叉树的前序遍历序列为ABCDEFGHI和中序遍历序列为BCAEDGHFI，试画出该二叉树。并写出后序遍历的结果。ABDCHEFGI10设二叉树以二叉链表形式存储，写一算法交换各结点的左右子树。void Exchange1(BTNode *bt) /* 交换左右子树的第一种方法*/ if(*bt) /* 这里以指针为参数使交换在实参结点上进行 */ BTNode p; Exchange1(&(*bt)-lchild); Exchange1(&(*bt)-rchild); p=(*bt)-lchild; (*bt)-lchild=(*bt)-rchild; (*bt)-rchild=p; void Exchange2(BTNode *bt) /*交换左右子树的第二种方法*/ if(bt) BTNode *p; p=bt-lchild; bt-lchild=bt-rchild; bt-rchild=p; Exchange2(bt-lchild); Exchange2(bt-rchild); /* Exchange2 */11设二叉树以二叉链表形式存储，写出一个求叶子结点总个数的算法。void Leaf_BiTree(BTNode *T)/*求树的深度及叶子结点个数*/if(T) if(T-lchild=NULL & T-rchild=NULL) printf(%cn,T-data); count+; Leaf_BiTree(T-lchild,j); Leaf_BiTree(T-rchild,j); /* Leaf_BiTree */12画出6-28(b)所示二叉树对应的森林。ABCDGEFHI13画出