桂林航天工业学院
实验报告
系（部）：计算机科学与工程系
课程名称: 数据结构
专业班级: 计算机应用技术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…cas e实现函数的调用。
设计分析：使用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 使用 p=p–>next; j++; 进行地址和指针后移， 再用 if (i==j) return p; else return NULL; 返回查找结果。 流程图： 3．插入： 算法思想：插入运算是将值为x的新结点插入到表的第i个结点的位置上首先找到a i-1的存储位置p，然后生成一个数据域为x的新结点*q， 并令结点*p的指针域指向新结点，新结点的指针域指向结点a i。 设计分析： 使用 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个结点删去，是在单链表中结点a i的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到a i-1 的存储位置p。然后令p–>next指向a i的直接后继结点，即把 a i从链上摘下。最后释放结点a i的空间。 设计分析： 使用 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…cas e实现函数的调用。 设计分析：使用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实现主函数的菜单界面，使用sw itch…cas e实现函数的调用。 设计分析：使用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--)
相关主题
文本预览