数据结构实践.docx
《数据结构实践.docx》由会员分享，可在线阅读，更多相关《数据结构实践.docx（11页珍藏版）》请在冰点文库上搜索。
数据结构实践
第一章课程设计性质与目的4
第二章设计内容及基本要求5
第三章详细设计说明11
项目一7
项目二16
项目三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.创建：
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT20
typedfstruct{
ElemType*elem;
intlength;
intlistsize;
}SqList;
Status（SqList&L）{
=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
exit（OVERFLOW）;
=0;
=LIST_INIT_SIZE;
returnOk;
}入:
StatusListInsert_Sq（SqList&L,inti,ElemTypee）{除：
Status
ListDelete_Sq（SqList&L，nti,ElemType&e）{
if（（i<1||（i>）returnERROR;
p=&[i-1]）;
e=*p;
q=+;找：
IntLocateElem_Sq（SqListL,ElemTypee,构造\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（"Pleasechoose1to9:
\n"）;scanf（"%d",&i）;
switch（i）
{
case1:
1nitList_Sq（L）;break;
case2:
ListInsert_Sq（L）;break;
case3:
ListDelete_Sq（L）;break;
case4:
Print_Sq（L）;break;
case5:
ListLength_Sq（L）;break;
case6:
LocateElem_Sq（L）;break;
case7:
inverse_Sq（L）;break;
case8:
output_Sq（L）;break;
case9:
Quit_Sq（L）;break;default:
printf（"输入有误"）;
}
}
}
三、操作结果
项目二：
链表操作
考查知识点：
（1）利用链表的插入运算建立链表；
（2）实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数）；
（3）能够在屏幕上输出操作前后的结果。
一、算法
1.创建：
voidCreateList_L（LinkList&L）{创建\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）;
■1C:
\Wi'iindowE\sy£tem22\Delb」g^g^e.exe"
更寒尹■smh!
a■
戶土戸
AA
□unn
值的吗»VA--L-賈一?
1TA
个：
2
4
S
个
■«ft—MH-IMMU-为卜入入笹请要爱
岀4第I输2d入除歹?
圭F请青士冃匮
3点
仁S,3
車
醸囱
hr
nrbrl£^br沖勢卿4NXE4.JOE连二目功UOTtt
8uo821-21.后1在會在
任意给定的二叉树（顶点数自定）建立它的二叉链表存储结
构；
2.利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、
判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。
3.求二叉树高度、结点数、度为1的结点数和叶子结点数。
二、算法：
1.创建二叉树：
StatusCreatebitree（bitree&t）序遍历：
Status
PreOrderTraverse（Bitree「Status（*visit）
（TEIemType））{序遍历：
StatusInOrderTraverse（Bitree「Status（*Visit）（TElemType））{
InitStack（s）;Push（S,T）;
While（!
StackEmpty（s）{
While（GetTop（s,p）&&p）Push（S,p->lchild）;
Pop（S,p）;
lf（!
StackEmpty（s））{
Pop（s,p）;if（!
Visit（p->data））retuERROR;
Push（S,p->rchild）;
}
数数
睛选择1L-B：
最深刻的总结成一个公式：
学了？
学会了？
会用了，有些东西自己利用所学的地只是远远不能用算法很好的表达出来，只能借助于书本，互联网查找资料，甚至以前老师所给做的笔记才能勉强完成•有些不足还是•
在开始的时候困难是很大的，于是乎我并没有急于开工，我先翻阅书本查找
了有关知识点进行温习熟悉，然后翻阅有关笔记，上网查找资料•之后我才开始编
写算法,实现目标这个过程中不免与同学进行交流合作•这个铺桥的工作完成了
面的''路''也就好修了
附录
参考文献：
（1）《C程序设计（第二版）》，谭浩强编，清华大学出版社，1999年1月。
（2）《C语言程序设计题解与上机指导》，谭浩强编，清华大学出版社，2000年11月。
（3）数据结构C语言版，严蔚敏，吴伟民编着，清华大学出版社，1997年4月。
升级会员 