数据结构课程设计.doc

桂林航天工业学院
实验报告

系（部）： 计算机科学与工程系
课程名称: 数据结构
专业班级: 计算机应用技术1班
学 号:
学生姓名:
完成日期： 2016年12月22日

一、 运行环境
操作系统：Windows10 64位操作系统
编译软件：Microsoft Visual C++ 6.0
处理器：Intel（R）Core（TM）2 CPU 6320 @ 1.86GHz 1.86GHz
安装内存（RAM）：2.00GB
二、 算法设计的思想和设计分析及流程图
1.线性表的顺序存储
1．插入：
算法思想：查找到元素X需要插入到线性表L的位置i，将该位置i后面的元素后移，将要元素X插入到i位置，表长加1。
设计分析：先使用
if(L->last==MAXSIZE1-1)
提示空间满
else if(i<1||i>L->last+2)
提示位置错误
函数判断位置i在该线性表L中是否存在，若位置i正确再使用
for(j=L->last;j>=i-1;j--)
{
L->data[j+1]=L->data[j];
}
使该位置i后面的数据元素后移，然后将数据元素插入到位置i，表长加1。
流程图：
2．删除：
算法思想：先判断线性表L是否存在数据元素i，然后在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，删除后新表长=原表长-1。
设计分析：先使用
if(i<1 || i>L->last+1)
提示数据元素不存在
判断元素i在线性表L中是否存在，若数据元素i存在再使用
for(j=i;j<=L->last;j++)
{
L->data[j-1]=L->data[j];
}L->last--;
使数据元素i后面的数据元素前移，将数据元素i覆盖删除，然后表长减1。
流程图：
3．查找：
算法思想：调用函数查找数据元素i，如果其调用函数结果返回在线性表L中首次出现的值为i的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为ｘ的数据元素，返回某特殊值表示查找失败。
设计分析：先使用
while(y<=L->last && L->data[y]!=x)
y++;
查找数据元素i在线性表L中的位置，如果查找失败则使用
if(y>L->last)
return -1;
返回特殊值，否则使用
else return y+1;
返回该数据元素的地址。

流程图：
4．Main主函数：
算法思想：使用Do…while实现主函数的菜单界面，使用switch…case实现函数的调用。
设计分析：使用do…while做出主菜单，使用
scanf("%d",&k);
getchar();
switch(k)
{
case 1: case 2: case 3: case 4: case 5:
}
实现函数的调用。
2. 线性表的链式存储
1．建表：
算法思想：使用头插入法建立单链表，该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
设计分析：
使用p=(LNode2*)malloc(sizeof(LNode2));开辟一个动态空间
使用
p->data=c;
p->next=head;
进行赋值和使指针后移，再用head=p;使head与p同指向。
流程图：
2．按序号查找：
算法思想：调用函数查找数据元素i，从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点。
设计分析：
使用while(p->next && j<i)限定i的合法性
使用
p=p–>next;
j++;
进行地址和指针后移，
再用
if (i==j) return p;
else return NULL;
返回查找结果。
流程图：
3．插入：
算法思想：插入运算是将值为x的新结点插入到表的第i个结点的位置上首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*q，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。
设计分析：
使用
p=Get_LinkList(L,i-1);
if(p==NULL)
{
printf("位置错误");
return 0;
}
判断i的是否存在，若存在，则使用
q=(LNode*)malloc(sizeof(LNode));
q->data=x;
q->next=p->next;
p->next=q;
进行插入，
再用
return 1返回插入结果。
流程图：
4．删除：
算法思想：将表的第i个结点删去，是在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。
设计分析：
使用
p=Get_LinkList(L,i-1);
if(p->next==NULL)
{
return 0;
}
判断i的是否存在，若存在，则使用
q=p->next;
p->next=q->next;
free(q);
进行删除和释放，
再用
return 1返回删除结果。
流程图：
5．Main主函数：
算法思想：使用Do…while实现主函数的菜单界面，使用if…else实现函数的调用。
设计分析：使用do…while做出主菜单，使用
scanf("%d",&k);
getchar();
if (k==1)
else if (k==2)
else if (k==3)
实现函数的调用。
3. 栈的应用
1．置空栈：
算法思想：使链栈的头指针指向空。
设计分析：使用top=NULL; 将头指针赋值为空。
流程图：
2．链式进栈：
算法思想：在栈顶插入新的元素，先使栈顶指针top加1，再给top赋值
设计分析：使用p=(LinkStack3)malloc(sizeof(StackNode3));建立新结点，使用
p->data =x;
p->next=top;
top=p;实现栈顶top的加1和赋值。
流程图：
3．链式入栈：
算法思想：先使栈顶指针top减1，再释放删除的数据i。
设计分析：使用
*x=top->data ;
p=top;
top=top->next ;
free(p);实现栈顶top的减1和释放。
流程图：
4．Main主函数：
算法思想：使用Do…while实现主函数的菜单界面，使用switch…case实现函数的调用。
设计分析：使用do…while做出主菜单，使用
scanf("%d",&k);
getchar();
switch(k)
{
case 1: case 2: case 3: case 4: case 5:
}
实现函数的调用。
4. 队列的应用
1． 置空队：
算法思想：对头指针front和队尾指针rear指向同一个位置
设计分析：使用
Q->rear=Q->front=T;
T->next=NULL
将头指针front和队尾指针rear指向同一个位置T，再把T的next指向NULL。
流程图：
2． 进队列：
算法思想：入队时将新元素插入队尾指针rear所指的位置，然后将队尾指针rear加１
设计分析：使用p->data=x；新元素插入队列，再使用
p->next=NULL;
Q->rear->next=p;
Q->rear=p; rear指针加1
流程图：
3． 出队列：
算法思想：出队时先判断元素是否存在，若存在则将队尾指针rear减１，再释放元素。
设计分析：使用if(queueempty(Q)) 判断元素是否存在，若存在再使用
p=Q->front;
x=p->next->data;
Q->front=p->next;
free(p);
将队尾指针rear减１和释放元素。
流程图：
4．Main主函数：
算法思想：使用Do…while实现主函数的菜单界面，使用switch…case实现函数的调用。
设计分析：使用do…while做出主菜单，使用
scanf("%d",&k);
getchar();
switch(k)
{
case 1: case 2: case 3: case 4: case 5:
}
实现函数的调用。
5. 二叉树的遍历和应用
1．建二叉树
算法思想：对一般的二叉树，首先添加若干个虚结点，使其成为完全二叉树，然后依次输入结点信息，若输入结点非虚结点，则建立一个新结点；若是第一个则令其为根结点，否则将新结点链接到它的双亲结点上。如此反复直到输入结束信息为止。
设计分析：使用
scanf("%d",&x);
if (x==0)
判断输入结点结束，再使用
T=(BTree5 *)malloc(sizeof(BTree5)) ;
T->data=x;
printf(" 请输入 %d 结点的左孩子：",T->data);
T->LChild=CreatBTree();
printf(" 请输入 %d 结点的右孩子：",T->data);
T->RChild=CreatBTree();
二叉树的前序遍历的递归算法建立二叉树。
流程图：
2．前序递归遍历二叉树
算法思想：访问根结点，先序遍历左子树，先序遍历右子树。
设计分析：使用printf("%d ",T->data); 访问根结点
使用PreOrder(T->LChild) ; 递归遍历左子树
使用PreOrder(T->RChild) ; 递归遍历右子树
流程图：
3．中序递归遍历二叉树
算法思想：中序遍历左子数，访问根节点，中序遍历右子树
设计分析：使用InOrder(T->LChild) ; 递归遍历左子树
使用printf("%d ",T->data); 访问根结点
使用InOrder(T->RChild) ; 递归遍历右子树
流程图：
4．后序递归遍历二叉树
算法思想：后序遍历左子树，访问根节点，后序遍历右子树
设计分析：使用postOrder(T->LChild) ; 递归遍历左子树
使用postOrder(T->RChild) ; 访问根结点
使用printf("%d ",T->data); 递归遍历右子树
流程图：
5．Main主函数：
算法思想：使用Do…while实现主函数的菜单界面，使用if…else实现函数的调用。
设计分析：使用do…while做出主菜单，使用
scanf("%d",&k);
getchar();
if (k==1)
else if (k==2)
else if (k==3)
实现函数的调用。
三、 源代码
1. 一级菜单
#include "实验1.c"
#include "实验2.c"
#include "实验3.c"
#include "实验4.c"
#include "实验5.c"
void main()
{
int k;
do
{
printf("\n\n\n\n");
printf("\t\t\t 数据结构课程设计一级菜单\n");
printf("\t\t***************************************\n");
printf("\t\t* 1----线性表的顺序存储　 　　*\n");
printf("\t\t* 2----线性表的链式存储　　　　*\n");
printf("\t\t* 3----栈的应用　　　 *\n");
printf("\t\t* 4----队列的应用　　　 *\n");
printf("\t\t* 5----二叉树的遍历和应用　　　*\n");
printf("\t\t* 0----返　　回　　　　 *\n");
printf("\t\t***************************************\n");
printf("\t\t 请选择菜单项(0－5)：");
scanf("%d",&k);
getchar();
switch(k)
{
case 1:
main1(); //线性表的顺序存储
break;
case 2:
main2(); //线性表的链式存储
break;
case 3:
main3(); //栈的应用
break;
case 4:
main4(); //队列的应用
break;
case 5:
main5(); //二叉树的遍历和应用
break;
}
}while(k!=0);
}
2. 实验1---线性表的顺序存储
#include "stdio.h"
#include "malloc.h"
#define MAXSIZE1 200 //线性表允许的最大长度
#define datatype1 int
typedef struct //定义线性表的结构
{ datatype1 data[MAXSIZE1]; //表示线性表（a1，a2，….,an）
int last; //last表示线性表的实际长度
} SeqList1;

/* 线性表初始化：Init_List(L)
初始条件：表L不存在
操作结果：构造一个空的线性表 */
SeqList1 *insert_SeqList( )
{ SeqList1 *L;
L=(SeqList1 *)malloc(sizeof(SeqList1));//L=new SeqList;
L->last=-1;
return L;
}
/* 插入操作：Insert_List(L,i,x)
初始条件：线性表L存在，插入位置正确 (1<=i<=n+1,ｎ为插入前的表长)。
操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，
这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长=原表长+1。 */
int Insert_SeqList(SeqList1 *L,int i,datatype1 x)
{
int j;
if(L->last==MAXSIZE1-1)
{
printf("空间满");
return 0;
}
else if(i<1||i>L->last+2)
{
printf("位置错误");
return 0;
}
for(j=L->last;j>=i-1;j--)
{
L->data[j+1]=L->data[j];
}
L->data[i-1]=x;
L->last++;
return 1;
}
/*删除操作：Delete_List(L,i)
初始条件：线性表L存在，1<=i<=n。
操作结果：在线性表L中删除序号为i的数据元素，
删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，删除后新表长＝原表长－１。 */
int Delete_SeqList(SeqList1 *L,int i)
{
int j;
if(i<1 || i>L->last+1)
{
printf("元素不存在");
return 0;
}
for(j=i;j<=L->last;j++)
{
L->data[j-1]=L->data[j];
}
L->last--;
return 1;
}
/*按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。
初始条件：线性表L存在
操作结果：在表L中查找值为ｘ的数据元素，
其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功;
否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。*/
int Location_SeqList(SeqList1 *L, datatype1 x)
{
int y=0;
while(y<=L->last && L->data[y]!=x)
y++;
if(y>L->last)
return -1;
else return y+1;
}
void print1(SeqList1 *L) //打印线性表 　　　
{ int i;
for (i=0;i<=L->last;i++)
printf("%d,",L->data[i]);
printf("\n");
}
void main1()
{ SeqList1 *L;
int i,j,k;
datatype1 x;
do
{ printf("\n\n\n\n");
printf("\t\t\t 线性表子系统\n");
printf("\t\t*******************************\n");
printf("\t\t* 1----初始化表　 　　*\n");
printf("\t\t* 2----插 入　　　　*\n");
printf("\t\t* 3----删　　除　　　　*\n");
printf("\t\t* 4----查　　找　　　　*\n");
printf("\t\t* 5----显　　示　　　　*\n");
printf("\t\t* 0----返　　回　　　　*\n");
printf("\t\t*******************************\n");
printf("\t\t 请选择菜单项(0－5)：");
scanf("%d",&k);getchar();
switch(k)
{
case 1:
L=insert_SeqList( ); //初始化线性表
break;
case 2: //在线性表第i位置处插入值为X的元素
printf("\n 请输入插入的位置i和数据X(输入格式：i,X):");
scanf("%d,%d",&i,&x);
j=Insert_SeqList(L,i,x);
if (j==1) printf("插入成功!!");
else printf("插入失败!!");
break;
case 3: //删除线性表中值为X的元素
printf("\n 请输入要删除元素的位置i:");
scanf("%d",&i);
j=Delete_SeqList(L,i);
if (j == 1) printf("删除成功!!");
else printf("删除失败!!");
break;
case 4: //查找线性表中元素值为x的位置
printf("\n 请输入要查找的数值X:");
scanf("%d",&x);
j=Location_SeqList(L,x);
if (j != -1 )
{ print1(L);printf("中值为X所在的位置是 %d ",j);}
else
printf("线性表中无此元素!!\n");
break;
case 5: //输出线性表
printf("\n线性表的顺序存储为：");
print1(L);
}
}while(k!=0);
}
3. 实验2---线性表的链式存储
#include "stdio.h"
#include "malloc.h"
#define datatype2 int
typedef struct node
{ datatype2 data; //链表的数据域
struct node *next; //链表的指针域
} LNode2,*LinkList2;
LinkList2 Creat_LinkList1( ) //头插入法建立单链表算法
{
datatype2 c;
LinkList2 head;
LNode2 *p;
head=NULL;
printf("请输入数据");
scanf("%d",&c);
while (c!=0)
{
p=(LNode2*)malloc(sizeof(LNode2));
p->data=c;
p->next=head;
head=p;
scanf("%d",&c);
}
return head;
}
/*按序号查找 Get_Linklist(L,i)
在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/
LNode2 *Get_LinkList(LinkList2 L,int i)
{
int j;
LNode2 *p;
p=L;
j=0;
while(p->next && j<i)
{
p=p->next;
j++;
}
if (i==j)
{
return p;
}
else return NULL;
}
/*插入运算 Insert_LinkList(L,i,x)
在单链表L的第i个位置上插入值为x的元素*/
int Insert_LinkList(LinkList2 L,int i,datatype2 x)
{
LNode2 *p,*q;
p=Get_LinkList(L,i-1);
if(p==NULL)
{
printf("位置错误");
return 0;
}
else
{
q=(LNode2*)malloc(sizeof(LNode2));
q->data=x;
q->next=p->next;
p->next=q;
return 1;
}
}
/*删除运算：Del_LinkList(L,i)
删除单链表L上的第i个数据结点*/
int Del_LinkList(LinkList2 L,int i)
{
LNode2 *p,*q;
p=Get_LinkList(L,i-1);
if(p->next==NULL)
{
return 0;
}
else
{
q=p->next;
p->next=q->next;
free(q);
return 1;
}
}
void print2(LinkList2 L) //输出单链表
{ LNode2 *p=L;
while(p->next!=NULL)
{ printf("%d->",p->data); //输出表中非最后一个元素
p=p->next;
}
printf("%d\n",p->data); //输出表中最后一个元素
}
void main2()
{
LNode2 *p;
LinkList2 H;
int i,j,k;
datatype2 x;
do
{
printf("\n\n\n\n");
printf("\t\t\t 链表子系统\n");
printf("\t\t*******************************\n");
printf("\t\t* 1----建 表　 　　*\n");
printf("\t\t* 2----插 入　　　　*\n");
printf("\t\t* 3----删　　除　　　　*\n");
printf("\t\t* 4----查　　找　　　　*\n");
printf("\t\t* 5----显　　示　　　　*\n");
printf("\t\t* 0----返　　回　　　　*\n");
printf("\t\t*******************************\n");
printf("\t\t 请选择菜单项(0－5)：");
scanf("%d",&k);getchar();
if (k==1)
H=Creat_LinkList1( ); //用头插入法建立单链表
else if (k==2) //在线性表第i位置处插入值为X的元素
{
printf("\n 请输入插入的位置i和数据X(输入格式：i,X):");
scanf("%d,%d",&i,&x);
j=Insert_LinkList(H,i,x);
if (j == 1) printf("插入成功!!");
else printf("插入失败!!");
}
else if (k==3)
{ printf("\n 请输入要删除元素的位置i:");
scanf("%d",&i);
j=Del_LinkList(H,i);
if (j == 1) printf("删除成功!!");
else printf("删除失败!!");
}
else if (k==4) //查找线性表中元素值为x的位置
{ printf("\n 请输入要查找的序号i:");
scanf("%d",&i);
p=Get_LinkList(H,i);
if (p!=NULL)
{ print2(H);printf("中序号为i的地址是 %d ",p);}
else
printf("链表中无此序号!!\n");
}
else if (k==5) //输出链表
{ printf("\n表的存储顺序为：");
print2(H);
}
}while(k!=0);
}
4. 实验3---栈的应用
#include "stdio.h"
#include "malloc.h"
typedef int datatype3;
typedef struct node3 //定义链式栈结构
{ datatype3 data;
struct node3 *next;
}StackNode3,*LinkStack3;
//置空栈
LinkStack3 Init_LinkStack()
{
LinkStack3 top;
top=NULL;
return top;
}
//入栈
LinkStack3 Push_LinkStack(LinkStack3 top, datatype3 x)
{
StackNode3 *p;
p=Init_LinkStack(top);
if(x!=0)
{
p=(LinkStack3)malloc(sizeof(StackNode3));
p->data=x;
p->next=top;
top=p;
printf("插入成功！！！\n");
}
return p;
}
//出栈
LinkStack3 Pop_LinkStack (LinkStack3 top, datatype3 *x)
{
StackNode3 *q=top;
if(top==NULL)
printf("栈为空");
else
{
*x=q->data;
top=q->next;
free(q);
return top;
}
}
void print3(LinkStack3 top)
{ StackNode3 *p=top;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
}
//顺序栈
#define MAXSIZE3 1024
typedef struct
{ datatype3 data[MAXSIZE3];
int top;
}SeqStack3;
//顺序栈置空栈：首先建立栈空间，然后初始化栈顶指针。
SeqStack3 *Init_SeqStack()
{ SeqStack3 *s;
s=(SeqStack3*)malloc(sizeof(SeqStack3));
s->top= -1;
return s;
}
//顺序栈判空栈
int Empty_SeqStack(SeqStack3 *s)
{ if (s->top == -1) return 1;
else return 0;
}
//顺序栈入栈
int Push_SeqStack (SeqStack3 *s, datatype3 x)
{if (s->top == MAXSIZE3-1) return 0; //栈满不能入栈
else { s->top++;
s->data[s->top]=x;
return 1;
}
}
//顺序栈出栈
int Pop_SeqStack(SeqStack3 *s, datatype3 *x)
{
if (Empty_SeqStack(s)) return 0; //栈空不能出栈
else { *x=s->data[s->top];
s->top--; return 1; //栈顶元素存入*x，返回
}
}
void conversion(int N,int r)
{ SeqStack3 *s;
datatype3 x;
s=Init_SeqStack(); //初始化栈
printf("\n %d 的十进制数转换成 %d 进制为: ",N,r);
while ( N )
{ Push_SeqStack (s,N%r); //余数入栈
N=N/r ; //商作为被除数继续
}
while ( !Empty_SeqStack(s))
{ Pop_SeqStack (s,&x) ;
printf(" %d ",x) ;
}
}
void main3()
{ LinkStack3 top;
int N,r;
int k;
datatype3 x;
top=Init_LinkStack();
do
{
printf("\n\n\n\n");
printf("\t\t\t 栈的应用子系统\n");
printf("\t\t*******************************\n");
printf("\t\t* 1----链式进栈　 　　*\n");
printf("\t\t* 2----链式出栈　　　　*\n");
printf("\t\t* 3----链栈显示　　　　*\n");
printf("\t\t* 4----进制转换　　　　*\n")