《数据结构》实验报告

实验室：****

实验日期和时间：****

班级：****

学号：****

姓名：****

实验一：栈的顺序表示和实现

二．实验主要内容和目的：

实验主要内容：

编制一个顺序栈的演示，实现顺序栈的基本操作，并由这些基本操作实现一些复杂的函数，如进行数值转换、判断回文数等。

实验目的：

1.编制一个演示顺序栈的初始化、插入、删除、取栈顶元素、置空顺序表、数制转换、判断回文数等操作的程序

2.学会定义顺序栈的结构类型，实现对顺序栈的一些基本操作和具体的函数定义。

三．概要设计：

1) 为了实现上述程序功能，需要定义单链表的抽象数据类型：

ADT Stack{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系：R1={-1,ai>|ai-1,ai∈D, i=1,2,…,n }

约定an端为栈顶，a1端为栈底。

基本操作：

InitStack（&S）

操作结果：构造一个空栈S

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回true；否则返回false。

GetTop(S，&e)

初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

Push(&S，e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。

Pop(&S，&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素并用e返回其值。

OutStack(&s)

初始条件：栈S已存在。

操作结果：将栈S的数据元素从栈顶到栈底依次输出。

shuzhi(&S, n, x)

初始条件：空栈S已存在。

操作结果：将一个十进制转化为其他进制。

huiwen(&S,n)

初始条件：空栈S已存在。

操作结果：若进栈序列和入栈序列相同，即是回文数，则返回1；否则，返回0。

}ADT Stack

2）　本程序包含9个函数：

a) 主函数main( )

b) 初始化顺序栈InitStack ( )

c) 入栈Push ( )

d) 出栈 Pop( )

e) 获取栈顶元素 GetTop( )

f) 遍历顺序表 OutStack( )

g) 置空顺序表 setEmpty( )

h) 数值转换 shuzhi( )

i) 判断回文 huiwen( )

3） 各函数间关系如下：

四．运用的存储结构说明：

//顺序存储结构

#define MAXNUM 20

#define ElemType int

/*定义顺序栈的存储结构*/

typedef struct

{ElemType stack[MAXNUM];

int top;

}SqStack;

五．主要算法及相关函数功能、参数说明：

1.switch（cord）语句，随之cord的选择（1至8）而进行不同的操作。

2.

a. 主函数main()

无返回值，为void型。

b．初始化顺序表InitStack ( )

参数SqStack *p；无返回值；void型。

c. 入栈Push ( )

参数SqStack *p,ElemType x；无返回值；void型。

d. 出栈 Pop( )

参数 SqStack *p；返回值为ElemType型，又#define ElemType int，即为整型；ElemType型

e. 获取栈顶元素 GetTop( )

参数SqStack *p；返回值为ElemType型，又#define ElemType int，即为整型；ElemType型

f. 遍历顺序表 OutStack( )

参数SqStack *p;int i; 无返回值；void型。

g．置空顺序表 setEmpty( )

参数SqStack *p;无返回值；void型。

h．数值转换 shuzhi( )

参数SqStack *p， int n,int x;无返回值；void型。

i． 判断回文 huiwen( )

参数SqStack *p， int n；返回值非1即0；bool型。

六．在设计和调试程序时我遇到的主要问题及其解决方案：

无

七．程序运行结果截图：

1.开始界面，如图（1） 2.初始化顺序栈，如图（2）

（1）开始界面 （2）初始化线性表

3.插入:下面是插入第一个元素的图（3），插入后再一次插入其他元素，最终插完元素，见图（4）

(3)插入第一个元素 (4)插入最后一个元素（第五个）

4.删除栈顶元素 ，如图（5） 5.取栈顶元素，如图（6）

(5)删除栈顶元素 （6）取栈顶元素

6.置空顺序栈，如图（7）

（7）置空顺序表

7. 数值转换（将一个十进制数转换为任意进制），如图（8），是将一个十进制数78三进制数2220。

（8）数值转换

8. 判断整数回文数，如图(9)和图（10）

（9）回文数判断a （10）回文数判断b

实验结论：实验成功

八．我对本次实验的总结：

1.通过对该程序的调试和运行，使的对顺序栈的功能及其构成有了进一步的了解。

2.通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中的不同作用域的问题

3.通过该程序中的的函数思想,可以重新熟悉函数在编程中的设置方法,熟悉函数中参数的设置和传递过程.

九．附录：

#include

#include

#define MAXNUM 20

#define ElemType int

/*定义顺序栈的存储结构*/

typedef struct

{ElemType stack[MAXNUM];

int top;

}SqStack;

/*初始化顺序表*/

void InitStack(SqStack *p)

{if(!p)

printf("内存分配失败!");

p->top =-1;

}

/*入栈*/

void Push(SqStack *p,ElemType x)

{if(p->top

{p->top =p->top+1;

p->stack[p->top]=x;

}

else

printf("Overflow! \n");

}

/*出栈*/

ElemType Pop(SqStack *p)

{ElemType x;

if(p->top>=0)

{ x=p->stack[p->top];

printf("以前的栈顶数据元素%d已经被删除!\n",p->stack[p->top]);

p->top=p->top-1;

return(x);

}

else

{printf("Underflow! \n");

return(0);

}

}

/*获取栈顶元素*/

ElemType GetTop(SqStack *p)

{ ElemType x;

if(p->top>=0)

{ x=p->stack[p->top];

printf("\n栈顶元素为:%d\n",x);

return(x);

}

else

{ printf("Underflow! \n");

return(0);

}

}

/*遍历顺序表*/

void OutStack(SqStack *p)

{ int i;

printf("\n");

if(p->top<0)

printf("这是一个空表!");

for(i=p->top;i>=0;i--)

printf("第%d个数据元素是: %6d\n",i,p->stack[i]);

}

/*置空顺序表*/

void setEmpty(SqStack *p)

{p->top=-1;}

/* 数值转换 */

void shuzhi(SqStack *p,int n,int x)

{

while(n){

Push(p,n%x);

n=n/x;

}

}

/*判断回文数*/

bool huiwen(SqStack *p,int n){

int i=0,j=0;

int a[MAXNUM];

while(n){

a[i]=n%10;

Push(p,n%10);

n=n/10;

i++;

}

while(p->stack[p->top-j]==a[j]) j++;

if(j

return 0;

else

return 1;

}

/*主函数*/

void main()

{SqStack *q;

int cord,x,n,y;ElemType a;

printf("第一次使用必须初始化!\n");

do{

printf("\n");

printf("\n----------主菜单------------\n");

printf("\n 1 初始化顺序表 \n");

printf("\n 2 插入一个元素 \n");

printf("\n 3 删除栈顶元素 \n");

printf("\n 4 取栈顶元素 \n");

printf("\n 5 置空顺序栈 \n");

printf("\n 6 数制转换 \n");

printf("\n 7 判断回文数 \n");

printf("\n 8 结束程序运行 \n");

printf("\n----------------------------\n");

printf("请输入您的选择(1,2,3,4,5,6,7)");

scanf("%d",&cord);

printf("\n");

switch(cord)

{case 1:

{q=(SqStack * )malloc(sizeof(SqStack));

InitStack(q);

OutStack(q);

}break;

case 2:

{printf("请输入要插入的数据元素: a=");

scanf("%d",&a);

Push(q,a);

OutStack(q);

}break;

case 3:

{ Pop(q);

OutStack(q);

}break;

case 4:

{ GetTop(q);

OutStack(q);

}break;

case 5:

{ setEmpty(q);

printf("\n顺序栈被置空! \n");

OutStack(q);

}break;

case 6:

{q=(SqStack * )malloc(sizeof(SqStack));

int i;

InitStack(q);

printf("请输入要转换的数制：\n");

scanf("%d",&x);

printf("请输入要转换的数：N=");

scanf("%d",&n);

shuzhi(q,n,x);

if(q->top<0)

printf("!");

for(i=q->top;i>=0;i--)

printf("%6d",q->stack[i]);

}break;

case 7:

{

q=(SqStack * )malloc(sizeof(SqStack));

int s;

InitStack(q);

printf("请输入要判断的正数：\n");

scanf("%d",&y);

s=huiwen(q,y);

if(s==1)

printf("%d是回文数!",y);

else

printf("%d不是回文数!",y);

}break;

case 8:

exit(0);

}

}while(cord<=8);

}