数据结构实训报告.doc

山东科技大学泰山科技学院
课程实训说明书

课程： 数据结构

系部名称： 信息工程系
专业班级： 电子信息科学与技术13-2＿
学生姓名： 徐志宏 ＿＿＿
学 号： 201323010230 ＿＿
指 导 教 师： 亓静
学 校: 山东科技大学
2015年7月22日

指导教师对课程设计的评语

课程设计成绩：
教师评语：

指导教师（签字）：—————

2013年 月 日

目录

第一章 课程设计性质与目的..................................4

第二章 设计内容及基本要求............................5

第三章 详细设计说明.........................................11
3.1 项目一.............................................................7
3.2 项目二............................................................16
3.3 项目三..........................................................26

第四章 实训总结...................................................37

附录 （参考文献、核心代码）

第一章 课程设计性质与目的

《数据结构》实训是信息管理与信息系统专业集中实践性环节之一，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。
链表和顺序表操作的设计目的： 1．掌握线性表的在顺序结构和链式结构实现。 2．掌握线性表在顺序结构和链式结构上的基本操作。
二叉树操作的设计目的： 1．掌握二叉树的概念和性。2. 掌握任意二叉树存储结构。 3．掌握任意二叉树的基本操作。

第二章 设计内容及基本要求
一、实验实训的基本要求是：
本实训面向应用，以解决实际问题为主。题目以选用学生相对比较熟悉的为宜，要求通过本实训，理解有关数据结构的基本概念、不同数据类型的存储和基本操作的算法实现，理解数据类型的逻辑结构及物理存储结构， 通过自己设计，编程、调试、测试、能够基本掌握在不同存储结构下的算法实现及算法优化，树立并培养系统规范开发的理念。实训中学生要将相关课程中学到的知识、思想和理念尽量应用在实训中。结束后要按规定提交代码和各种文档。
实训基本步骤：
1. 选题
设计的课题尽量结合教学、科研的实际课题，规模、大小适当，具有一定复杂度。应根据题目大小、难度确定是否分组，组内成员人数。
2. 数据结构及算法设计
根据需求分析，选择合理的数据结构及设计相应的算法。
3. 编码
根据已设计的数据结构和算法，编写代码。
4. 测试
按照系统测试的原则、方法和步骤，对系统进行测试。测试中应形成测试报告。
5. 编写实训报告
实训说明书，内容及要求如下：
（1） 封面
（2） 成绩评定
（3） 目录
（4） 说明书正文，主要内容包括：
一、 设计题目
二、 运行环境（软、硬件环境）
三、 数据结构及算法设计的思想
四、 数据结构及算法设计
五、 源代码
六、 运行结果分析
七、 实习总结（收获及体会）
参考资料：附录（核心代码）。
二、设计内容 项目一：顺序表操作
1、设计目的
（1）掌握线性表的在顺序结构上的实现。
（2）掌握线性表在顺序结构上的基本操作
2、设计内容和要求
利用顺序表的插入运算建立顺序表，然后实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。
项目二：链表操作
1、设计目的
（1）掌握线性表的在链式结构上的实现。
（2）掌握线性表在链式结构上的基本操作
2、设计内容和要求
利用链表的插入运算建立链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。
项目三：二叉树的基本操作
1、设计目的
（1）掌握二叉树的概念和性质
（2）掌握任意二叉树存储结构。
（3）掌握任意二叉树的基本操作。
2、设计内容和要求
（1）对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
（2） 求二叉树高度、结点数、度为1的结点数和叶子结点数。

第三章 详细设计说明

项目一：
顺序表操作：
考查知识点：（1）利用顺序表的插入运算建立顺序表；
（2）实现顺序表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；
（3）能够在屏幕上输出操作前后的结果。
一、算法
1. 创建：#define LIST_INIT_SIZE 100
#define LISTINCREMENT 20
typedf struct{
Elem Type *elem;
int length;
int listsize;
}SqList;
Status InitList.Sq(SqList&L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.lengh=0;
L.listsize=LIST_INIT_SIZE;
return Ok;
}//InitList_Sq
2.插入:Status ListInsert_Sq(SqList&L,int i,ElemType e){//插入
if(i<1||i>L.length+1)return ERROR;
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；
return OK;
}//ListInsert_Sq
3.删除：Status ListDelete_Sq(SqList &L，nt i,ElemType&e){
if((i<1||(i>L.length))return ERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;//表尾元素的位置
for(++p;p<=q;++p)=*p;
--L.length;//表长减1
return OK;
}//ListDelete_Sq
4.查找：Int LocateElem_Sq(SqList L，ElemType e， //查找
Status（*compare）（ElemType，
ElemType））{
i=1；
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e))++i;
if(i<=L.length) return i;
else return 0;
}//LocateElem_Sq
二、源代码
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 20
typedef struct {
ElemType *list;
int length;
int listsize;
}SqList;
int InitList_Sq(SqList &L) {
L.list = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.list) exit (OVERFLOW); // 存储分配失败
int i,y;
L.length = 0;
L.listsize = LIST_INIT_SIZE;
printf("请输入元素个数:");
scanf("%d",&y);
printf("请输入元素:\n");
for(i=0;i<y;i++,L.length++)
scanf("%d",&L.list[i]);
for(i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
return OK;
} // InitList_Sq
//*****************输出函数******************
void output_Sq(SqList &L)
{
printf("输出顺序表\n");
for(int i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
}
//*****************插入*********************
Status ListInsert_Sq(SqList &L){
ElemType *q,*p,*newbase;
int i,e;
printf("请输入插入位置i:");
scanf(" %d",&i);
if(i < 1 || i > L.length + 1) return ERROR;
if(L.length >= L.listsize){
newbase = (ElemType *)realloc(L.list,
(L.listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
L.list = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.list[i-1]); // q指示插入位置
for (p = & (L.list[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置及之后的元素右移
printf("输入插入数值e: ");
scanf("%d",&e);
*q = e;
++L.length;
printf("输出插入之后的顺序表:");
for( i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
return OK;
} // ListInsert_Sq
//*****************删除*********************
int ListDelete_Sq(SqList &L){
ElemType *p,*q;
int i,e;
printf("请输入你要删除的元素位序：");
scanf("%d",&i);
if ((i < 1) || (i > L.length)) return ERROR;
p = & (L.list[i-1]);
e = *p;
q = L.list + L.length - 1; // 表尾元素的位置
printf("删除的元素值为: %d\n",e);
for (++p; p <= q; ++p)
*(p-1) = *p;
--L.length;
for( i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
return OK;
} // ListDelete_Sq
//******************查找********************
Status LocateElem_Sq(SqList L){
int e,i;
printf("请输入你要查找元素的数值: ");
scanf("%d",&e);
printf("你要查找元素的位序为: ");
for(i=0;i<L.length;i++)
{
if(e==L.list[i])
printf("%d ",i+1);
}
printf("\n");
return 0;
}
//************排序（由小到大）*************
void Print_Sq(SqList &L)
{int t;
for(int j=0;j<L.length-1;j++)
for(int i=0;i<L.length-1-j;i++)
if(L.list[i]>L.list[i+1])
{t=L.list[i];L.list[i]=L.list[i+1];L.list[i+1]=t;}
printf("输出排序（由小到大）表\n");
for(int i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
}
//*****************计数********************
void ListLength_Sq(SqList L){
printf("输出表中元素个数\n");
printf("%d\n",L.length);
}
//*****************逆置********************
void inverse_Sq(SqList &L)
{
int t,i;
for(i=0;i<=L.length/2-1;i++)
{
t=L.list[i];
L.list[i]=L.list[L.length-i-1];
L.list[L.length-i-1]=t;
}
printf("输出逆置顺序表\n");
for( i=0;i<L.length;i++)
printf("%d ",L.list[i]);
printf("\n");
}
//*****************退出*********************
int Quit_Sq(SqList L)
{
exit (0);
return 0;
}
//****************主函数********************
void main()
{
SqList L;
int i;
printf(" 1. 构造 \n");
printf(" 2. 插入 \n");
printf(" 3. 删除 \n");
printf(" 4. 排序 \n");
printf(" 5. 计数 \n");
printf(" 6. 查找 \n");
printf(" 7. 逆置 \n");
printf(" 8. 输出 \n");
printf(" 9. 退出 \n");
for(;;)
{
printf("Please choose 1 to 9 :\n");
scanf("%d",&i);
switch(i)
{
case 1:InitList_Sq(L);break;
case 2:ListInsert_Sq(L); break;
case 3:ListDelete_Sq(L); break;
case 4:Print_Sq(L); break;
case 5:ListLength_Sq(L); break;
case 6:LocateElem_Sq(L);break;
case 7:inverse_Sq(L);break;
case 8:output_Sq(L);break;
case 9: Quit_Sq(L);break;
default:printf("输入有误");
}
}
}
三、操作结果

项目二：
链表操作
考查知识点：（1）利用链表的插入运算建立链表；
（2）实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；
（3）能够在屏幕上输出操作前后的结果。
一、算法
1.创建：
void CreateList_L(LinkList &L){ //逆序输入n个元素的值，建立带头结点的单链线性表L。
L=(LinkList)malloc(sizeof(LNode));//生成新的结点
L->next=NULL;
//先建立一个带头结点的单链表
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(LNode));
scanf(&p->data);
p->next = L->next;L->next = p; //插入到表头
}
}//CreateList L
2. 插入：
Status ListInsert_L(LinkList &L,int i ,ElemType e){ //插入
p=L;j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i)return ERROR；
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
3. 删除：
Status ListDelete_L(LinkList &L,int &e){ //删除
j=0;
p=L;
while(p->next && j<i-1) //寻找第i个结点，并令p指向其前驱
{
p=p->next;
++j;
}
if(!(p->next)||j>i-1)
return ERROR;
q=p->next;
p->next=q->next;
e=q->data;
free(q);
return OK;
}//ListDelete_L
4. 查找:
Status GetElem_L(LinkList L,int i , ElemType &e) //查找
{
p=L->next;
j=1;
while(p && j<i)//按序号查找
{
p=p->next;
j++;
}
if(!p||j>1)retun ERROR
e=p->data;
retun OK;
}//GetElem.L
二、源代码
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef struct LNode
{
int data;
struct LNode * next;
}LNode, * LinkList;
//逆序输入n个元素的值，建立带头结点的单链线性表L。
void CreateList_L(LinkList &L){
int i,x;
LNode *p=NULL;
L=(LinkList)malloc(sizeof(LNode));//生成新的结点
L->next=NULL; //先建立一个带头结点的单链表
printf("请输入结点个数:");
scanf("%d",&x);
printf("请输入各结点元素的值为:");
for(i=x;i>0;--i) //逆序输入x个元素的值
{
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next = L->next;L->next = p; //插入到表头
}
p=L->next; //将p指向头结点
//输出已创建的链表
printf("逆序输出链表为:\n");
while(p)
{
printf("%d ",p->data);
p=p->next;
}

}
//*****************插入*******************
int ListInsert_L(LinkList &L){
LNode *p,*s;
int j=0,e,i;
p=L;
printf("请输入所要插入的位置:");
scanf("%d",&i);
printf("请输入所要插入的数:");
scanf("%d",&e);
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
printf("输入数据有误,请输入数值在1 -- x+1之间输入");
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
p=L ->next;
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
return OK;
}
//*****************删除********************
int ListDelete_L(LinkList &L,int &e){
LNode *p,*q;
int i,j=0;
p=L;
printf("请输入要删除的第几个结点:");
scanf("%d",&i);
while(p->next && j<i-1) //寻找第i个结点，并令p指向其前驱
{
p=p->next;
++j;
}
if(!(p->next)||j>i-1)
printf("输入的数值错误或删除位置不合理");
q=p->next;
p->next=q->next;
e=q->data;
free(q);//释放被删除结点
printf("被删除结点的数值为: %d\n",e);
p=L ->next;
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
return OK;
}
//******************计数********************
void CountList_L(LinkList &L)
{
int i=0;
LNode *p=L->next;
while(p)
{i++;
p=p->next;}
printf("结点个数为:%d\n",i);
}
//*****************查找*******************
int LocateElem_L(LinkList L)
{
LinkList p=L;
int i,j=0;
printf("请输入要查找的数的序号:");
scanf("%d",&i);
while(p && j<i)//按序号查找
{
p=p->next;
j++;
}
if(j!=i||!p)
{
printf("参数i错或单链表不存在");
return(NULL);
}
printf("你查找的第 %d 个结点的数值为 %d\n",i,p->data);
return OK;
}
//*******************排序*******************
void SortList_L(LinkList L)
{
int i,j,t,k = 0;
LNode *p = L->next,*q;
while(p)
{
k++;
p=p->next;
}
p=L->next; q=p->next; //初始化
for(i=0;i<k-1;++i)
{
p = L->next;
for(j=0,p;j<k-i-1;++j,p=p->next)
{
q = p->next;
if(p->data > q->data) //升序
{
t=p->data;
p->data=q->data;
q->data=t;
}
}
}
p=L->next;
printf("输出升序的链表为:\n");
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
}
//*******************输出***************
void OutputList_L(LinkList L)
{
LNode *p;
p=L->next;
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
}
//*******************逆置****************
int ReverseList_L(LinkList &L)
{
LNode *p ,*q;
p=L->next;
q=p->next;
L->next=NULL;
while(p->next)
{
p->next=L->next;
L->next=p;
p=q;
q=q->next;
}
p->next=L->next;
L->next=p;
printf("逆置后的链表结果为:");
for(p=L->next;p;p=p->next)
printf("%d ",p->data);
printf("\n");
return 0;
}
//***************主函数**************
int main()
{
LinkList L=NULL;
int i,e;
printf("逆序输入创建一个链表并实现下列功能\n");
printf(" 1. 创建 \n");
printf(" 2. 插入 \n");
printf(" 3. 删除 \n");
printf(" 4. 计数 \n");
printf(" 5. 查找 \n");
printf(" 6. 排序 \n");
printf(" 7. 输出 \n");
printf(" 8. 逆置 \n");
for(;;)
{
printf("请在1-8功能中选择一个: ");
scanf("%d",&i);
//************函数调用*************
switch(i)
{
case 1:CreateList_L(L); break;
case 2:ListInsert_L(L); break;
case 3:ListDelete_L(L,e); break;
case 4:CountList_L(L); break;
case 5:LocateElem_L(L); break;
case 6:SortList_L(L); break;
case 7:OutputList_L(L); break;
case 8:ReverseList_L(L); break;
default:printf("输入错误");
}
}
printf("\n");
return 0;
}
三、操作结果

项目三：
二叉树的操作：
一、考查知识点：1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构；
2.利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
3. 求二叉树高度、结点数、度为1的结点数和叶子结点数。
二、算法：
1.创建二叉树：
Status Createbitree(bitree &t) //功能1：构建二叉树的二叉链表
{ scanf(& ch); //按先序遍历建立二叉树
if(ch==’’)
T=NULL;
else
{
if(!(T=(BiTNde)malloc(sizeof(BiTNode))))exit(OVERFLOW);
}
T->data=ch;
Createbitree(t->lchild);
Createbitree(t->rchild);
}
Return OK;
}//CreatBiTree
2.先序遍历： Status PreOrderTraverse(Bitree T,Status（* visit）（TElemType)） {//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
if(T)
{ if(Visist(T->data))
if (PreOrderTraverse(p->lchild,Visit));
if PreOrderTraverse(p->rchild,Visit));
}
return OK;
return ERROR;
}elese returnOK;
}// PreOrderTraverse
3.中序遍历：Status InOrderTraverse(Bitree T,Status（* Visit）（TElemType)）{
InitStack(s);Push (S,T);
While(!StackEmpty(s){
While(GetTop(s,p)&&p)Push(S,p->lchild);
Pop(S,p);
If(!StackEmpty(s)){
Pop(s,p);if (!Visit(p->data))retu ERROR;
Push(S,p->rchild);
}//if
}//While
Retun OK;
}// InOrderTraverse
二、源代码
#include<stdio.h>
#include<malloc.h>

#include<stdlib.h>

#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2

typedef void status;
typedef char BTtype;
typedef char Stype;

typedef struct BTnode {//定义二叉树存储结构
BTtype data;
struct BTnode *lc,*rc;
}BTnode,*BTtree;

type