数据结构实验-创新互联

姓名：黎怀       学号：2103101009       班级：计科211

实验一 栈的基本操作

（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素

(2)栈的顺序表示和实现
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能:
初始化顺序栈;入栈;出栈;取栈项元素;判断栈是否为空。
(2)栈的链式表示和实现
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成初始化链栈;入栈;出栈;取栈顶元素;判断栈是否为空。

二、【实验内容】

栈的顺序表示和实现
顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数元素，同时附设指针top指示栈顶元素在顺序栈中的位置，利用一位数组实现栈的顺序存放。初始化顺序栈，

三、【程序代码】

#include #include #define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top;        //栈 顶指针
} SeqStack;        //定义栈
typedef struct
{ElemType elem[MaxSize];
int front,rear;  //队首和队尾指针
} SqQueue:   //定义队列
//--初始栈函数
void InitStack(SeqStack *&s)
{
s=(SeqStack *)malloc(sizeof(SeqStack));
s->top=-1;
}
//---进栈函数
int Push(SeqStack *&s,ElemType e)
{
if (s->top==MaxSize- 1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
//--显示栈函数
void DispStack(SeqStack *s)
{
int i; .
for (i=s->top;i>=0;--)
printf("%c ",s->data[i]);
printf("\n"); 
}
//--显示栈底元素
void DispBottomStack(SeqStack *s)
printf("%c ",s->data[)];//先进后出,栈底元素为第一个 元素,即data[0] 
printf("\n"); .
/--判空栈函数
int StackEmpty(SeqStack *s)
{
return(s->top==-1);
}
//--出栈函数
int Pop(SeqStack *&s,ElemType &e)
{
if(s->top==-l)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
//--初始队列函数
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
//-入队列函数
int InQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+ 1)%MaxSize==q->front)//队满
return 0;
q->rear=(q->rear+ 1)%MaxSize; 
q->elem[q->rear]=e;
return 1;
//--出队列函数
int OutQueue(SqQueue *&q.ElemType &e)
{
if(q->front== =q->rear) //队空
return 0;
q->front=(q->front+ 1)%MaxSize; .
e=q->elem[q->front]; 
return 1;
}
//--判空队列函数
int QueueEmpty(SqQueue *q)
{
return(q->front= = =q->rear);
}
//--主程序.
void main()
{
ElemType e; 
SeqStack *s;
printf("(1)初始化栈s\n");
InitStack(s);
printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf("(3)依次进栈元素a,b,c,d,e\n"); 
Push(s,’a’);//入栈元素1
Push(s,’b’);//入栈元素2
Push(s,’c’);//入栈元素3
Push(s,’d’);//入栈元素4
Push(s,’e’);//入栈元素5
printf("(4)栈为%s\n' ,(StackEmpty(s)?"空":"非空));
printf("(5)从栈顶到栈底元素:");DispStack(s);
printf("(6)栈底元素为:");DispBottomStack(s); 
printf("(7)出栈/入队列序列:");
SqQueue *q;
InitQueue(q);
while (!StackEmpty(s))
{
Pop(s,e);//出栈
printf("%c ",e);
InQueue(q.e);//入队
}
printf("\n"); .
printf("(8)栈为%s," ,(StackEmpty(s)?"空":"非空)); .
printf("队列为%s\I",(QueueEmpty(q)?"空""非空");
printf("(9)出队列/入栈序列:");
while (!QueueEmpty(q))
{ 
OutQueue(q,e);//出 队
Push(s,);//入栈
printf("%c ",e);
}
printf("\n");
printf("(10)栈为%s,",(StackEmpty(s)?"空":"非空));
print("队列为%s\n",(QueueEmpty(q)?"空":"非空));
free(q);//释放队列
printf("(11)从栈顶到栈底元素:"):DispStack(s);
free();//释放栈
}

四、【输出结果】

五、【实验总结】

本次实验中学会了顺序栈和链栈的各个功能和操作，通过实验栈得到了更加深刻的认识和更完善的运用。

实验二 二叉排序树的建立

1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对排序二叉树程序的设计。
2、理解和掌握二叉树的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言实现。
3、理解排序二叉树的建立过程。

二、【实验内容】

编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序

三、【程序代码】

#include#include#define MAX 5
typedef struct Bnode
{
int key;
struct Bnode *left;
struct Bnode *right;
}Bnode;
Bnode * btInsert(int x,Bnode *root);
void Inorder(Bnode *root);
void main()
{
int i;
int a[MAX]={60,40,70,20,80};
Bnode * root=NULL;
printf("按关键字序列建立二叉排序树\n"); .
for(i=0;key=x;
p->right=p->left=NULL;
if(root==NULL)
{ root=p; return p; }
q=root;
while(flag==0)
{
if(q->key>x)
{
if(q->left!=NULL)
q=q->left;
else
{
q->left=p;
flag=1;
     }
}
else
{
if(q->right!=NULL)
q=q->right;
else
{
q->right=p;
flag=1;
      }
   }
}
return root;
}
void Inorder(Bnode *root)
if(root!=NULL)
{
Inorder(root->left);
printf("%d ",root->key);
Inorder(root->right);
    }
}

四、【输出结果】

五、【实验总结】

通过本次试验，对树的知识还是有了更深层次的了解，比如如何去构建一棵二叉排序树，平时简建树的算法才用递归的算法，但是二叉排序树是有规律的树，对加深了递归算法了解

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧