《数据结构》(C语言版)实验(4)

void PrintStack(SqStack *S){ ElemType e;

while(Pop(S,&e)) printf(\}/*Pop_and_Print*/

int main(){ SqStack ss;

printf(\ CreateStack(&ss);

printf(\ PrintStack(&ss); return 0; }

?

算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。 ? 实现代码 ? 验证

3、阅读并运行程序，并分析程序功能。 #include #include #include #define M 20

#define elemtype char typedef struct

16

{

elemtype stack[M]; int top; }

stacknode;

void init(stacknode *st);

void push(stacknode *st,elemtype x); void pop(stacknode *st);

void init(stacknode *st) {

st->top=0; }

void push(stacknode *st,elemtype x) {

if(st->top==M)

printf(\ else {

st->top=st->top+1; st->stack[st->top]=x; } }

void pop(stacknode *st) {

if(st->top>0) st->top--;

else printf(“Stack is Empty!\\n”); }

int main() {

char s[M]; int i;

stacknode *sp;

printf(\ sp=malloc(sizeof(stacknode)); init(sp);

printf(\ gets(s);

for(i=0;i

if(s[i]=='(')

push(sp,s[i]); if(s[i]==')') pop(sp); }

if(sp->top==0)

printf(\ else

printf(\ return 0; }

? ?

输入：2+((c-d)*6-(f-7)*a)/6 运行结果：

17

? ? ?

输入：a-((c-d)*6-(s/3-x)/2 运行结果：

程序的基本功能：

以下为选做实验：

4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。 ? 实现代码 5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。 实现代码：

四、实验小结

18

五、教师评语

19

实验三 串的模式匹配（选做）

一、实验目的

1、了解串的基本概念

2、掌握串的模式匹配算法的实现

二、实验预习

说明以下概念 1、模式匹配：

2、BF算法：

3、KMP算法：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。 #include #include #define MAXSIZE 100 typedef struct{

char data[MAXSIZE]; int length; }SqString;

int strCompare(SqString *s1,SqString *s2); /*串的比较*/ void show_strCompare();

void strSub(SqString *s,int start,int sublen,SqString *sub); /*求子串*/

void show_subString();

int strCompare(SqString *s1,SqString *s2){ int i;

for(i=0;ilength&&ilength;i++) if(s1->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i]; return s1->length-s2->length; }

void show_strCompare(){ SqString s1,s2; int k;

printf(\

20