2022年数据结构习题解答文 .pdf

《2022年数据结构习题解答文 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构习题解答文 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章习题解答1.分别写出对链栈的入栈和出栈操作的算法。链栈的结点类型定义如下：Typedef struct stacknode SElemtype data; struct stacknode *next; stacknode, *linkstack; 入栈操作：Status push( linkstack &S, SElemtype e) p=(linkstack)malloc(sizeof(stacknode); If (!p) return ERROR; p-data=e; p-next=S; S=p; return OK; 出栈操作：Status pop(linkstack &S,

2、SElemtype &e) if (!S) return ERROR; p=s; s=p-next; free(p); return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - P24/3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈， 它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws 的三个操作：初始化inistack(tws),入栈 push(tws,i,x)和出栈 p

3、op(tws,i)的算法，其中i 为 0 或 1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。双栈的结构类型定义如下：typedef struct Elemtype *base2; Elemtype *top2; BDStacktype; /双向栈类型栈的初始化操作：status Init_Stack(BDStacktype &tws,int m) /初始化一个大小为m 的双向栈 tws tws.base0=(Elemtype*)malloc(m*sizeof(Elemtype); tws.base1=tws.base0+m-

4、1; tws.top0=tws.base0; tws.top1=tws.base1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - return OK; 入栈操作：Status push(BDStacktype &tws,int i,Elemtype x) / x 入栈,i=0 表示低端栈 ,i=1 表示高端栈 if (tws.top0tws.top1) return OVERFLOW; /注意此时的栈满条件if (i=0)

5、*tws.top0+=x; else if (i=1) *tws.top1-=x; else return ERROR; return OK; 出栈操作：Status pop(BDStacktype &tws, int i, Elemtype &x) / x 出栈 ,i=0 表示低端栈 ,i=1 表示高端栈 if (i=0) if (tws.top0=tws.base0) return OVERFLOW; x=*-tws.top0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3

6、 页，共 6 页 - - - - - - - - - else if (i=1) if (tws.top1=tws.base1) return OVERFLOW; x=*+tws.top1; else return ERROR; return OK; P24/3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。Status Bracket_Test(char *exp) /判别表达式中小括号是否匹配 count=0; for (p=exp; *p; p+) if (*p= ( ) count+; else if (*p= ) ) count-; if (countnext=rear;

7、/形成循环 入队操作：void EnCiQueue(CiQueue &rear, int x) /把元素 x 插入循环链表表示的队列rear, rear指向队尾元素 , /rear-next指向头结点 , rear-next-next指向队头元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - p=(CQnode*)malloc(sizeof(CQnode); p-data=x; /产生一个新结点p p-next=rear-nex

8、t; /直接把 p 加在 rear 的后面rear-next=p; rear=p; /修改尾指针 出队操作：Status DeCiQueue(CQlink &rear, int &x) /从用队尾指针rear 表示的循环链表删除一个头部元素，并用x返回其数据域的值。 if(rear=rear-next) return ERROR; /队列已空p=rear-next-next; x=p-data; rear-next-next=p-next; if (p=rear) rear=rear-next; free(p); return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -