山东科技大学数据结构实训报告.docx
《山东科技大学数据结构实训报告.docx》由会员分享，可在线阅读，更多相关《山东科技大学数据结构实训报告.docx（39页珍藏版）》请在冰点文库上搜索。
山东科技大学数据结构实训报告
课程实训说明书
课程：
数据结构实训
题目：
顺序表、链表与二叉树
院 系：
信息工程系
专业班级 ：
学 号：
学生姓名：
指导教师：
2015年7月21日
1.1实训内容和基本要求···············································3
1.2设计题目及其运行环境························3
1.3数据结构及算法思想的设计····················4
一．顺序表代码及其运行结果及分析······························4
二．链表源代码及其运行结果及结果分析····························15
（1）主函数代码及其运行结果
（2）输入功能及结果代码
（3）插入功能代码及其运行结果
（4）删除功能代码及其运行结果
（5）查找函数代码及其运行结果
（6）输出函数代码及其运行结果
（7）计数函数代码及其运行结果
（8）排序函数代码及其运行结果
（9）逆置函数代码及其运行结果
三．二叉树源代码及其运行结果及结果分析····························23
（1）主函数代码及其运行结果
（2）创建二叉树函数代码及其运行结果
（4）求树的结点个数及其运算结果
（5）求树的结点度为一的结点个数
（6）求树的叶子个数代码及其运行结果
（7）先序遍历二叉树及其运行结果
（8）中序遍历二叉树及其运行结果
（9）后序遍历二叉树及其运行结果
四．实训总结················································32
五．参考文献················································33
1.1实训内容和基本要求
这次的实训是以面向应用，以解决实际问题为主。
老师给的题目基本都是我们在课堂上接触过的，实训的要求是通过上机练习，理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及物理存储结构，通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树立并培养系统规范开发的理念。
实训中我们要将课本上的理论知识运用到实际操作中，真正做到学以致用。
1.2设计题目及其运行环境
课程设计题一：
顺序表的基本操作
一、设计目的
2．掌握线性表在顺序结构上的基本操作。
二、设计内容和要求
利用顺序表的插入运算建立线性链表，然后实现查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。
课程设计题二：
链表的基本操作
一、设计目的
1．掌握线性表的在链式结构实现。
2．掌握线性表在链式结构上的基本操作。
二、设计内容和要求
利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。
课程设计题三：
二叉树的基本操作
一、设计目的
1．掌握二叉树的概念和性质
2.掌握任意二叉树存储结构。
3．掌握任意二叉树的基本操作。
二、设计内容和要求
1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
2．求二叉树高度、结点数、度为1的结点数和叶子结点数。
·运行环境
首先需要一台PC机，WindowsXP系统下，其次程序在visualC++6.0的编译环境中进行，界面将通过屏幕的输出显示功能选项。
通过键盘输入完成相应操作。
程序主界面是一个文本方式的菜单，通过键盘相应选择操作指令。
1.3数据结构及算法思想的设计
首先可以把需要实现的功能分别写成一个个子函数，然后在主函数里面调用这些子函数，此外还需编写一个菜单子函数，在主函数里面最先调用菜单函数实现在运行界面时首先显示主菜单，根据菜单提示完成你想要执行的操作。
链表的各种功能，例如创建，输出，查找，插入，删除，计数，排序；
对于二叉树的各种功能，例如创建，先序，中序，后序三种遍历，高度，结点数，叶子结点数等.对于二叉树的遍历，是运用的非递归的思想，求高度，结点数，叶子结点数等方法和链表一样，都是先建立子函数，再进行调用。
1．顺序表代码及其运行结果及结果分析
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefintStatus;
typedefintElemType;
//-------------线性表的动态分配顺序存储结构--------------
typedefstruct
{
ElemType*elem;//数组指针elem指线性表的基地址
intlength;//当前长度
intlistsize;
}SqList;
//---------------顺序表的函数调用部分--------------------
StatusNiZhi（SqList&L,inti）;
StatusSort（SqList&L,inti）;
StatusCount（SqList&L,inti）;
StatusSearchElem（SqList&L,inti）;
StatusListDelete（SqList&L,inti,ElemTypee）;
StatusInitList_Sq（SqList&L）;
StatusBuild（SqList&L）;
StatusOutPut（SqList&L）;
StatusListInsert_Sq（SqList&L,inti,ElemTypee）;
//--------------------主函数部分-------------------------
intmain（）
{
SqListL;
inta,i;
printf（"--------【请先建立顺序表】---------\n"）;
InitList_Sq（L）;
Build（L）;
for（i=0;i<=1000;i++）//循环输出，然后输入调用
{printf（"-------------请选择如下操作码-------------\n"）;
printf（"******************************************\n"）;
printf（"*****-----------【1】查找------------*****\n"）;
printf（"*****-----------【2】插入------------*****\n"）;
printf（"*****-----------【3】删除------------*****\n"）;
printf（"*****-----------【4】计数------------*****\n"）;
printf（"*****-----------【5】输出------------*****\n"）;
printf（"*****-----------【6】排序------------*****\n"）;
printf（"*****-----------【7】逆置------------*****\n"）;
printf（"******************************************\n"）;
scanf（"%d",&a）;
switch（a）
{inti,e;
case1:
SearchElem（L,i）;break;
case2:
ListInsert_Sq（L,i,e）;break;
case3:
ListDelete（L,i,e）;break;
case4:
Count（L,i）;break;
case5:
OutPut（L）;break;
case6:
Sort（L,i）;break;
case7:
NiZhi（L,i）;break;
default:
printf（"选择错误!
\n"）;
}
}
return0;
}
//------------初始化操作为顺序表分配一个预定义大小的数组空间---------------------
StatusInitList_Sq（SqList&L）
{//构造一个空的线性表L
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}
//---------建立线性表----------------------
StatusBuild（SqList&L）
{
intn,i;
printf（"请输入元素个数\n"）;
scanf（"%d",&n）;
printf（"请输入%d个元素\n",n）;
if（n>LIST_INIT_SIZE）
{
L.elem=（ElemType*）realloc（L.elem,（n+LISTINCREMENT）*sizeof（ElemType））;
if（!
L.elem）exit（OVERFLOW）;
L.listsize=n+LISTINCREMENT;
}
for（i=0;i{
scanf（"%d",&L.elem[i]）;
}
L.length=n;
returnOK;
}
//--------------查找----------------------
StatusSearchElem（SqList&L,inti）
{intb;
printf（"请选择查找方式：
\n"）;
printf（"按位置查找元素请选【1】\n"）;
printf（"按元素查找位置请选【2】\n"）;
scanf（"%d",&b）;
if（b==1）
{
printf（"请输入所查找的位置\n"）;
scanf（"%d",&i）;
printf（"所查找的元素为%d\n",L.elem[i-1]）;
}
else
if（b==2）
{intc;
printf（"请输入所查找的元素\n"）;
scanf（"%d",&c）;
for（i=0;i{
if（c==L.elem[i]）break;
}
printf（"%d在顺序表的第%d个位置\n",c,i+1）;
return0;
}
elseprintf（"选择查找方式错误!
\n"）;
returnOK;
}
//--------------插入----------------
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{int*q,*p,*newbase;
printf（"请输入插入位置和元素\n"）;
scanf（"%d%d",&i,&e）;
if（i<1||i>L.length+1）returnERROR;//i值不合法
if（L.length>=L.listsize）//当前存储空间已满，增加分配
{newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）exit（OVERFLOW）;
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;
}
q=&（L.elem[i-1]）;//q为插入位置
for（p=&（L.elem[L.length-1]）;p>=q;--p）//插入位置及之后的元素右移
*（p+1）=*p;
*q=e;
++L.length;
OutPut（L）;//调用输出
returnOK;
}
//--------------删除-----------------
StatusListDelete（SqList&L,inti,ElemTypee）
{int*p,*q;
printf（"删除第几个元素\n"）;
scanf（"%d",&i）;
if（（i<1）||（i>L.length））returnERROR;//i值不合法
p=&（L.elem[i-1]）;//p为被删除元素的位置
e=*p;
q=L.elem+L.length-1;//表尾元素的位置
for（++p;p<=q;++p）*（p-1）=*p;//被删除元素之后的元素左移
--L.length;
OutPut（L）;
returnOK;
}
//---------------计数-----------------
StatusCount（SqList&L,inti）
{intn=0;
for（i=0;i{
n++;
}
printf（"本顺序表总共有%d个元素\n",n）;
return0;
}
//--------------输出--------------------
StatusOutPut（SqList&L）
{
inti;
printf（"输出\n"）;
for（i=0;i{
printf（"%d",L.elem[i]）;
}
printf（"\n"）;
returnOK;
}
//---------------排序-----------------
StatusSort（SqList&L,inti）
{intj,t,d;
printf（"*****请选择：
【1】升序-----【2】降序*****\n"）;
scanf（"%d",&d）;
if（d==1）//升序排列
{
for（j=0;jfor（i=0;iif（L.elem[i]>L.elem[i+1]）
{t=L.elem[i];L.elem[i]=L.elem[i+1];L.elem[i+1]=t;}
printf（"升序排列为:
\n"）;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
}
elseif（d==2）//降序排列
{
for（j=0;jfor（i=0;iif（L.elem[i]{t=L.elem[i];L.elem[i]=L.elem[i+1];L.elem[i+1]=t;}
printf（"降序排列为:
\n"）;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
}
elseprintf（"选择错误!
\n"）;
return0;
}
//---------------逆置-----------------
StatusNiZhi（SqList&L,inti）
{
intt,j,m=L.length/2;
for（i=0;i{j=L.length-1-i;
t=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=t;
}
printf（"逆置后的顺序为:
\n"）;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
return0;
}
运行结果：
二．链表源代码及其运行结果及结果分析
主函数代码及其运行结果如下：
#include
#include
#defineOK1
#defineERROR0
typedefintStatus;
typedefintElemType;
//-----------------线性表的单链表的存储结构----------------------
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
intn;
LinkListq,p,L,s;
//----------------链表函数的调用部分----------------
StatusNiZhi（LinkList&L,inti）;
StatusSort（LinkList&L,inti）;
StatusCount（LinkList&L,intn）;
StatusLocateElem（LinkList&L,inti,ElemType&e）;
StatusListDelete_L（LinkList&L,inti,ElemType&e）;
StatusBuild_L（LinkList&L,intn）;
StatusOutPut（LinkList&L,intn）;
StatusListInsert_L（LinkList&L,inti,ElemTypee）;
//-----------------主函数部分----------------------
intmain（）
{
inti,e,a;
printf（"************【请先建立单链表】************\n"）;
printf（"请输入元素个数值\n"）;
scanf（"%d",&n）;
printf（"请输入%d个元素\n",n）;
Build_L（L,n）;
for（i=0;i<=1000;i++）
{printf（"--------------请选择如下操作码------------\n"）;
printf（"******************************************\n"）;
printf（"*****-----------【1】查找------------*****\n"）;
printf（"*****-----------【2】插入------------*****\n"）;
printf（"*****-----------【3】删除------------*****\n"）;
printf（"*****-----------【4】计数------------*****\n"）;
printf（"*****-----------【5】输出------------*****\n"）;
printf（"*****-----------【6】排序------------*****\n"）;
printf（"*****-----------【7】逆置------------*****\n"）;
printf（"******************************************\n"）;
scanf（"%d",&a）;
switch（a）
{inti,e;
case1:
LocateElem（L,i,e）;;break;
case2:
ListInsert_L（L,i,e）;break;
case3:
ListDelete_L（L,i,e）;break;
case4:
Count（L,n）;break;
case5:
OutPut（L,n）;break;
case6:
Sort（L,i）;break;
case7:
NiZhi（L,i）;break;
default:
printf（"选择错误!
\n"）;
}
}
return0;
}
//---------从表尾到表头逆向建立单链表-------------------
StatusBuild_L（LinkList&L,intn）
{inti;
L=（LinkList）malloc（sizeof（LNode））;
LinkListp;
L->next=NULL;//先建立一个带头结点的单链表
for（i=n;i>0;--i）
{
p=（LinkList）malloc（sizeof（LNode））;
scanf（"%d",&p->data）;//输入元素值
p->next=L->next;
L->next=p;//插入到表头
}
return0;
}
//-----------------------插入--------------------------
StatusListInsert_L（LinkList&L,inti,ElemTypee）
{intj=0;
p=L;
printf（"请输入插入位置\n"）;
scanf（"%d",&i）;
while（p&&j{p=p->next;
++j;}//寻找第i-1个结点
if（!
p||j>i-1）returnERROR;
s=（LinkList）malloc（sizeof（LNode））;//生成新的结点
printf（"请输入插入元素\n"）;
scanf（"%d",&e）;
s->data=e;//插入L中
s->next=p->next;
p->next=s;
OutPut（L,n）;
returnOK;
}
//-----
升级会员 