《《数据结构(c语言描述)》-马秋菊-源代码和习题参考答案》由会员分享，可在线阅读，更多相关《《数据结构(c语言描述)》-马秋菊-源代码和习题参考答案（27页珍藏版）》请在金锄头文库上搜索。
1、习题配套 第一章 2C、A、B、B、A、A、D 3 D=A,B,C,E,F,G,H,I,J; R=, 4顺序、链式、索引、哈希。 *5解：100n 2 2 n n至少要多大 6.(n)、(n)、(n)、( )、 n (5)当nm，(n),当mn，(m) 7n! 2 100 lgnn 1/2 n 3/2 (3/2) n 2 n n lgn n n 第二章 1、 2AAD 4顺序表 void Delete_SeqListx(SeqList *L,ElemType x) /*删除表中值为x元素*/ inti,j; for(i=1;ilength;i+) if(L-elemi=x) for(j=i;j
2、length-1;j+) L-elemj=L-elemj+1; L-length-; /*向上移动*/ O(n 2 ) A B C E F G H I 题 1-3图 J链表 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) 5 int Delete_SeqListx(SeqList *L,int i,int k) /*删除表中删除自第i
3、个结点开始的k个结点*/ intj; if(iL-length) /*检查空表及删除位置的合法性*/ printf(不存在第i个元素); return ERROR; for(j=i;jlength-k;j+) L-elemj=L-elemj+k; /*向上移动*/ L-length-=k; Return OK;/*删除成功*/ O(n) 6 void 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写一算法
4、在循环单链表上实现线性表的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 在用头指针表示的单循环链表中，查找开始结点 a 1 的时间是 O(1)，然而要查找终端结点则 需从头指针开始遍历整个链表，其时间是 O(n)。但在很多实际问题中，表的操作常常是在 表的首、尾位置上进行，如果改用尾指针rear来表示单循环链表，则查找开始结点 a 1 和 终端结点 a n 都很方便，它们的存储位置分别是 rear-next-
5、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!=NULLp=p-next; /*查找a结点*/ s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/ s-data=b; s-next=q-next;/*新结点插入在第i-1个结点的后面*/ q-next=s； return OK; /*Insert_LinkList
6、ab*/ 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为新表表头。 11 void merge1(LinkList q=B-next;C=A; while(pp-next=
7、q;/*将 B 的元素插入*/ if(s) t=q-next;q-next=s;/*如 A 非空,将 A 的元素插入*/ p=s;q=t; /*while*/ /*merge1*/ 12 Status 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*/ 13 Status Insert_SqList(SeqList L-length+;i=L-length;
8、 while(L-elemix) L-elemi+1=L-elemi;i-; L-elemi+1=x; return OK; /*Insert_SqList 14 intInsert_Linkx(LinkList H,ElemType x) /*在值递增单链表中插入一个值为x的结点，仍递增*/ LNode*q=H,*s;*p=H-next;while(p!=NULL /*查找a结点*/ s=(LinkList)malloc(sizeof(LNode);/*申请、填装结点*/ s-data=x; s-next=q-next;/*新结点插入*/ q-next=s； return OK; /*Ins
9、ert_Linkx*/ 15 源程序代码：（在 TubroC2.0 测试通过） #include #include structnode intnumber;/*人的序号*/ intcipher;/*密码*/ structnode*next;/*指向下一个节点的指针*/ ; structnode*CreatList(intnum)/*建立循环链表*/ inti; structnode*ptr1,*head; if(ptr1=(structnode*)malloc(sizeof(structnode)=NULL) perror(“malloc“); returnptr1; head=ptr1;
10、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
11、-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 从链表中
12、脱节，将前后两个节点连接起来*/ head=hea/d-next;/*head 移向后一个节点*/ free(ptr);/*释放 ptr 指向的内存*/ i=0;/*将 i 重新置为 0，从 0再开始数*/ else head=head-next; i+; printf(“number:%dn“,head-number); printf(“cipher:%dn“,head-cipher); free(head);/*让最后一个人也出列*/ 16 void SqList_Intersect(SqList A,SqList B,SqList j=1;k=0; while(A.elemi if(A.
13、elemi=B.elemj) C.elem+k=A.elemi;/当发现了一个在 A,B 中都存在的元素,/就添加到 C 中 i+;j+; /*while*/ /*SqList_Intersect*/ 17 Status 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辆列车顺序开进一个栈式结构的站台，请写出每一种开出站 台的列车编号顺序(注：每一列车开出栈开出站
14、台后，不允许再进栈)。 2指出下述程序段的功能是什么？void Demo1(SeqStack *S) int i; arra16;n=16； initStack( for(i=0,in; i+) push(S,arrai);while(!StackEmpty(S) arrai =pop(S); 3写出带表头链栈取栈顶元素和置栈空的算法。 4假设一个算术表达式中包含圆括号、方括号和花括号，编写一个判别表达式中括号 是否配对的算法。 5写出计算表达式5+3*（4/6-7）时操作数和算符栈的变化情况。 6对于给定的十进制正整数，输出对应的八进制正整数。 (1)写出递归算法。 (2)写出非递归算法。
15、7已知n为大于等于零的整数，试写出计算下列递归函数f(n)的递归和非递归算法。8回文是指正读和反读均相同的字符序列，如”abba”和”abdba”均是回文，而” ashgash”不是回文。试写一个算法判断读入的一个以为结束符的字符序列是否为回文。 (提示：将一半字符入栈)。 9一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的 两端。设计初始化InitStack(S,i)、入栈push(S,i,x)和出栈pop(S,i)等算法，其中i为0或 1，用以指示栈号。 10对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。 11循环队列的优点是什么？如何判别它的空和满？ 12假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素位置(注意 不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。 13假设用一个数组QM来表示队列，该队列只设一个队头指针front，不设队尾指针， 用计数器count来记录队列中元素的个数。试编写出相应的置空队列、入队列和出队
