数据结构实例分析.docx
- 文档编号:18360621
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:79
- 大小:153.46KB
数据结构实例分析.docx
《数据结构实例分析.docx》由会员分享,可在线阅读,更多相关《数据结构实例分析.docx(79页珍藏版)》请在冰点文库上搜索。
数据结构实例分析
数据结构
实践教程
1
前言
数据结构是运算机专业的必修。
骨干课程之一,它旨在使读者学会分析研究数据对象的特性,
学会数据的组织方式,以便选择适合的数据逻辑结构和存储结构,和相应的运算(操作),把现
实世界中的问题转化为运算机内部的表示和处置,这是一个良好的程序设计技术训练的进程。
在整
个教学或学习进程中,解题能力和技术的训练是一个重要的环节。
为了帮忙教师教学“数据结构”,
知足指导和评判“课程设计”的需要,为了帮忙和指导读者更好地学习数据结构这门课程,咱们特编
写了这本《数据结构实践教程》辅助教材,旨在弥补课堂教学和实验中的不足,帮忙学生充分明白得
和巩固所学的大体概念、原理和方式,达到融会贯通、触类旁通的目的。
实践证明,明白得课程内容与较好地解决实际问题之间存在着明显差距,而算法设计完成的质量
与大体的程序设计素养的培育是紧密相关的。
要想明白得和巩固所学的大体概念。
原理和方式,牢固
地把握所学的大体知识。
大体技术,达到融会贯通。
触类旁通的目的,就必需多做。
多练。
多见
(见多识广)。
正是为了达到上述目的,书顶用一些实际的应用,对一些重要的数据结构和算法进
行解读。
通过循序渐进地训练,就能够够使读者把握更多的程序设计技术和方式,提高分析。
解决问
题的能力。
本书依照学生的基础知识和爱好爱好将内容分为基础篇和提高篇两个部份。
第一部份基础篇精
选出适当的、与实际生活扣合紧密的课程设计实例加以分析实现。
第二部份提高篇旨在使读者通过
运用数据结构知识及复杂算法去解决现实世界中的一些实际问题。
本书依据数据结构课程教学大纲要求,同时又独立于具体的教科书,既重视实践应用,又重视
理论分析,本书的要紧特点有:
●本书精选出来的实例项目经典、实用、具有一定的趣味性,其内容丰富、涉及面广、难易适
当,能给读者以启发,达到让读者把握相关知识和开阔视野的目的
●为了提高学生分析问题、解决问题的能力,本书对实例项目进行分析,其设计思路清晰流畅,
值得参考。
●本书不仅仅是对照数据结构课程教学大纲举些例子说明数据结构能解决什么问题,而是通过
分析具体的实例项目,取得对数据组织关系的需求,从而选择某个数据结构适应一些特定的问题和
算法,并说明利用这种数据结构的优缺点。
●所有实例项目都给出了参考算法和源程序代码并在TurboC和VisualC++环境下运行通过。
由于作者水平有限、时刻仓促,本书不免存在一些缺点和错误,恳请广大读者及同行们批评指
正。
2
第一部份基础篇
第一章线性表
学生成绩治理
项目简介
设计思路
数据结构
程序清单
运行结果
考试报名治理
项目简介
设计思路
数据结构
程序清单
运行结果
约瑟夫生者死者游戏
项目简介
设计思路
数据结构
程序清单
运行结果
约瑟夫双向生死游戏
项目简介
设计思路
数据结构
程序清单
运行结果
第二章栈和队列
迷宫旅行游戏
项目简介
知识要点
设计思路
程序清单
目
3
录
运行结果
八皇后问题
项目简介
知识要点
设计思路
程序清单
运行结果
停车场的停车治理
项目简介
知识要点
设计思路
程序清单
运行结果
第三章串、数组和广义表
单词检索统计程序
项目简介
设计思路
数据结构
程序清单
运行结果
Internet网络通路治理
项目简介
设计思路
数据结构
程序清单
运行结果
第四章树和二叉树
家谱治理
项目简介
设计思路
数据结构
程序清单
运行结果
表达式求值问题
项目简介
2
设计思路
数据结构
程序清单
运行结果
图像紧缩编码优化
项目简介
设计思路
数据结构
程序清单
运行结果
第五章图
公交线路治理
项目简介
设计思路
数据结构
程序清单
运行结果
导航最短途径查询
项目简介
设计思路
数据结构
程序清单
运行结果
电网建设造价计算
项目简介
设计思路
数据结构
程序清单
运行结果
软件工程进度计划
项目简介
设计思路
数据结构
程序清单
运行结果
3
第六章查找
号码查询系统
项目简介
知识要点
设计思路
程序清单
运行结果
高校录取分数线查询系统
项目简介
知识要点
设计思路
程序清单
运行结果
储蓄账户查询系统
项目简介
知识要点
设计思路
程序清单
运行结果
期刊稿件查询系统
项目简介
知识要点
设计思路
程序清单
运行结果
第七章排序
设备清单排序
项目简介
知识要点
设计思路
程序清单
运行结果
地名排序
项目简介
知识要点
4
设计思路
程序清单
运行结果
工厂产量排序
项目简介
知识要点
设计思路
程序清单
运行结果
高校科研功效排序
项目简介
知识要点
设计思路
程序清单
运行结果
火车车次排序
项目简介
知识要点
设计思路
程序清单
运行结果
IP地址排序
项目简介
知识要点
设计思路
程序清单
运行结果
第二部份综合篇
益智游戏之七巧板
项目需求
知识要点
设计流程
程序清单
运行测试
航空客运定票系统
5
项目需求
知识要点
设计流程
程序清单
运行测试
景区旅行信息治理系统
项目需求
知识要点
设计流程
程序清单
运行测试
2
第一部份基础篇
第一章线性表
线性表是数据结构中最简单、最经常使用的一种线性结构,也是学习数据结构全数内容的基
础,其把握的好坏直接阻碍着后继知识的学习。
本章通过四个模拟项目来学习线性表的顺序
和链式存储结构,第一通过利用有关数组的操作实现学生成绩治理,第二通过利用有关线性
链表的操作实现考试报名治理,然后通过利用循环链表的操作实现约瑟夫生者死者游戏。
学生成绩治理
项目简介
学生成绩治理是学校教务部门日常工作的重要组成部份,其处置信息量专门大。
本项目是
对学生成绩治理的简单模拟,用菜单项选择择方式完成以下功能:
输入学生数据;输出学生数据;
学生数据查询;添加学生数据;修改学生数据;删除学生数据。
设计思路
本项目的实质是完成对学生成绩信息的成立、查找、插入、修改、删除等功能,能够首
先概念项目的数据结构,然后将每一个功能写成一个函数来完成对数据的操作,最后完成主函
数以验证各个函数功能并得出运行结果。
数据结构
本项目的数据是一组学生的成绩信息,每条学生的成绩信息由学号、姓名和成绩组成,
这组学生的成绩信息具有相同特性,属于同一数据对象,相邻数据元素之间存在序偶关系。
由此能够看出,这些数据具有线性表中数据元素的性质,因此该系统的数据采纳线性表来存
储。
顺序表是线性表的顺序存储结构,是指用一组持续的内存单元依次寄存线性表的数据元
素。
在顺序存储结构下,逻辑关系相邻的两个元素在物理位置上也相邻,这是顺序表的特点。
本项目能够采纳顺序表的线性表顺序存储结构。
假设一个数据元素仅占一个存储单元,那么其存储方式参见图1-1。
3
从图1-1中可见,第i个数据元素的地址为
Loc(ai)=loc(a1)+(i-1)
假设线性表中每一个元素占用k个存储单元,那么在顺序表中,线性表的第i个元素的存
储位置与第1个元素的存储位置的关系是
Loc(ai)=loc(a1)+(i-1)*k
那个地址Loc(ai)是第i个元素的存储位置,loc(a1)是第1个元素的存储位置,也称为线性表
的基址。
显然,顺序表便于进行随机访问,故线性表的顺序存储结构是一种随机存储结构。
顺序表适宜于做查找如此的静态操作;顺序存储的优势是存储密度大,存储空间利用率
高。
缺点是插入或删除元素时不方便。
由于C语言的数组类型也有随机存储的特点,一维数组的机内表示确实是顺序结构。
因此,
可用C语言的一维数组实现线性表的顺序存储。
数组实现线性表的顺序存储的优势是能够随
机存取表中任一元素O
(1),存储空间利用紧凑;缺点是在插入,删除某一元素时,需要移动
大量元素O(n),预先分派空间需按最大空间分派,利用不充分,表容量难以扩充。
用结构体类型概念每一个学生数据,故该数组中的每一个数据的结构可描述为:
typedefstructSTU
{charstuno[10];
charname[10];
floatscore;
}ElemType;
程序清单
#include<>
#include<>
#include<>
#include<>
#defineMaxListSize20
#defineEQUAL1
typedefstructSTU{
charstuno[10];
charname[10];
floatscore;
}ElemType;
ame,==0)break;
if(i>=length)returnfalse;
elsee=elem[i];
for(j=i+1;j elem[j-1]=elem[j];} length--; returntrue; } voidList: : ListTraverse() {for(inti=0;i {cout< cout< cout< cout< } voidList: : GetElem(inti,ElemType*e) 6 {*e=elem[i];} boolList: : EqualList(ElemType*e1,ElemType*e2) {if(strcmp(e1->name,e2->name)) returnfalse; if(strcmp(e1->stuno,e2->stuno)) returnfalse; if(e1->age! =e2->age) returnfalse; if(e1->score! =e2->score) returnfalse; returntrue; } boolList: : Less_EqualList(ElemType*e1,ElemType*e2) {if(strcmp(e1->name,e2->name)<=0)returntrue; elsereturnfalse; } boolList: : LocateElem(ElemTypee,inttype) {inti; switch(type) {caseEQUAL: for(i=0;i if(EqualList(&elem[i],&e)) returntrue; break; default: break;} returnfalse; } ame,==0){ elem[i]=e1;returntrue;} returnfalse; } 7 boolList: : ListInsert(inti,ElemType&e) {ElemType*p,*q; if(i<1||i>length+1)returnfalse; q=&elem[i-1]; for(p=&elem[length-1];p>=q;--p) *(p+1)=*p; *q=e; ++length; returntrue; } core if(mark==-1&&elem[b[k]].score if(k! =i){intx=b[i];b[i]=b[k];b[k]=x;}} for(inti=0;i {cout< cout< cout< cout< else{ for(i=0;i {cout< cout< cout< cout< } 8 voidmain() {cout<<"运行结果: \n"; ElemTypee,e1,e2,e3,e4,e5,e6; List*La,*Lb,*Lc; intk; cout<<"第一挪用插入函数.\n"; La->init(&La,4); strcpy,"stu1"); strcpy,"100001"); =22; =88; La->ListInsert(1,e1); strcpy,"stu2"); strcpy,"100002"); =21; =79; La->ListInsert(2,e2); strcpy,"stu3"); strcpy,"100003"); =19; =87; La->ListInsert(3,e3); La->printlist(0); cout<<"表La长: "< (); Lb->init(&Lb,4); strcpy,"zmofun"); strcpy,"100001"); =20; =94; Lb->ListInsert(1,e4); strcpy,"bobjin"); strcpy,"100002"); =23; 9 } =69; Lb->ListInsert(2,e5); strcpy,"stu1"); strcpy,"100001"); =22; =88; Lb->ListInsert(3,e6); Lb->printlist(0); cout<<"表Lb长: "< (); k=Lc->ListDelete(-1,e6); if(k==0)cout<<"删除失败! \n"; elsecout<<"删除成功! \n"; cout<<"输出表Lc: \n"; Lc->printlist(0); (); cout<<"按成绩升序输出表Lc\n"; Lc->printlist (1);(); cout<<"按成绩降序输出表Lc\n"; Lc->printlist(-1);(); 运行结果 第一成立学生信息治理,输出结果为: 姓名 Stu1 Stu2 Stu3 学号 100001 100002 100003 80 91 56 成绩 第二查询学号为100002的学生的成绩,输出结果为: 91 再次挪用插入函数,插入Stu4成功! 输入结果为: 姓名 Stu1 学号 100001 80 成绩 10 Stu2 Stu3 Stu4 100002 100003 100004 91 56 75 最后删除Stu2功效! 输出结果为: 姓名 Stu1 Stu3 Stu4 学号 100001 100003 100004 80 56 75 成绩 查询不合格的学生,输出结果为: Stu3 100003 56 考试报名治理 项目简介 考试报名工作给各高校报名工作带来了新的挑战,给教务治理部门增加了专门大的工作量, 报名数据手工录入既费时又会不可幸免地显现错误,同时也给很多学生以可乘之机。 本项目 是对考试报名治理的简单模拟,用菜单项选择择方式完成以下功能: 输入考生信息;输出考生信 息;查询考生信息;添加考生信息;修改考生信息;删除考生信息。 设计思路 本项目的实质是完成对考生信息的成立、查找、插入、修改、删除等功能,能够第必然 义项目的数据结构,然后将每一个功能写成一个函数来完成对数据的操作,最后完成主函数以 验证各个函数功能并得出运行结果。 数据结构 本项目的数据是一组考生信息,每条考生信息由准考证号、姓名、性别、年龄、报考类 别等信息组成,这组考生信息具有相同特性,属于同一数据对象,相邻数据元素之间存在序 偶关系。 由此能够看出,这些数据也具有线性表中数据元素的性质,因此该系统的数据能够 采纳线性表来存储。 从上一节的例子中可见,线性表的顺序存储结构的特点是逻辑关系相邻的两个元素在物 理位置上也相邻,因此能够随机存储表中任一元素,它的存储位置可用一个简单、直观的公 式来表示。 但是,从另一个方面来看,那个特点也铸成了这种存储结构的弱点: 在做插入或 11 删除操作时,需要移动大量元素。 为克服这一缺点,咱们引入另一种存储形式――链式存储。 链式存储是线性表的另一种表示方式,由于它不要求逻辑上相邻的元素在物理位置上也相邻, 因此它没有顺序存储结构的弱点,但同时也失去了顺序表可随机存取的特点。 链式存储的优势是插入或删除元素时很方便,利用灵活。 缺点是存储密度小,存储空间 利用率低。 事实上,链表插入、删除运算的快捷是以空间代价来换取时刻。 顺序表适宜于做查找如此的静态操作;链表宜于做插入、删除如此的动态操作。 假设线性 表的长度转变不大,且其要紧操作是查找,那么采纳顺序表;假设线性表的长度转变较大,且其 要紧操作是插入、删除操作,那么采纳链表。 本项目对考生数据要紧进行插入、删除、修改等操作,因此采纳链式存储结构比较适合。 用结构体类型概念每一个考生信息,故该单链表中的每一个结点的结构可描述为: typedefstructexaminee {charexamno[10]; charname[10]; charsex; floatage; charexamtype[5]; }ElemType; 程序清单 intnews,olds; cout<<"\n请输入要被修改的元素: ";cin>>olds; cout<<"请输入修改后要变成的元素: ";cin>>news; (olds,news); cout<<"\n修改后单链表list变成: "; (ff); cout<<"\n下面请构造单链表list2"; cout<<"\n请输入单链表list2初始化长度(1--30): "; cin>>init_size; seed=120; cout<<"请选择是不是排序: (=0不排序,=1升序,=-1降序): "; cin>>xu; cout<<"\n按回车键终止..."; ();();} 运行结果 18 项目简介 约瑟夫生者死者游戏者 约瑟夫生者死者游戏的大意是: 30个旅客同乘一条船,因为严峻超载,加上风高浪大, 危险万分;因此船长告知乘客,只有将全船一半的旅客投入海中,其余人材能幸免遇难。 无 奈,大伙儿只得同意这种方法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第 9人,便把他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此 循环,直到剩下15个乘客为止。 问哪些位置是将被扔下大海的位置。 设计思路 本游戏的数学建模如下: 假设n个旅客排成一个环形,依次顺序编号1,2,…,n。 从 某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始从头计 数,继续进行下去。 那个进程一直进行到剩下k个旅客为止。 本游戏的要求用户输入的内容包括: 1.旅客的个数,也就是n的值; 2.离开旅客的间隔数,也就是m的值; 3.所有旅客的序号作为一组数据要求存放在某种数据结构中。 本游戏要求输出的内容是包括 1.离开旅客的序号; 2.剩余旅客的序号; 因此,依照上面的模型分析及输入输出参数分析,能够概念一种数据结构后进行算法实 现。 数据结构 为了解决这一问题,能够用长度为30的数组作为线性存储结构,并把该数组看成是一个 首尾相接的环形结构,那么每投入大海一个乘客,就要在该数组的相应位置做一个删除标记, 该单元以后就再也不作为计数单元。 如此做不仅算法较为复杂,而且效率低,还要移动大量的 元素。 用单循环链表解决这一问题,实现的方式相对要简单得多。 第一要概念链表结点,单 循环链表的结点结构与一样的结点结构完全相同,只是数据域用一个整数来表示位置;然后 将它们组成具有30个结点的单循环链表。 接下来从位置为1的结点开始数,数到第8个结点, 就将下一个结点从循环链表中删去,然后再从删去结点的下一个结点开始数起,数到第8个 结点,再将其下一个结点删去,如此进行下去,直到剩下15个结点为止。 19 为了不失一样性,将30改成一个任意输入的正整数n,而报数上限(原为9)也为一个 任选的正整数k。 如此该算法描述如下: (1)创建含有n个结点的单循环链表; (2)生着与死者的选择: p指向链表的第一个结点,初始i置为1; while(i<=n/2)报数上限k=”); scanf(“%d%d”,&n,&k); R=InitRing(n,R); R=DeleteDeath(n,k,R); OutRing(n,R); 运行结果 编译运行上述程序,提示: 总人数n.报数上限k= 输入30和9后并“回车”可得出如下结果: 9182761626719301224822523 21252829123410111314151720 约瑟夫双向生死游戏死 项目简介 约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上,正向计数后反向计数,然后再
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实例 分析