数据结构课程设计全集

数据结构实践教程

前言

数据结构是计算机专业的必修。主干课程之一，它旨在使读者学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中，解题能力和技巧的训练是一个重要的环节。为了帮助教师讲授“数据结构”，满足指导和评价“课程设计”的需要，为了帮助和指导读者更好地学习数据结构这门课程，我们特编写了这本《数据结构实践教程》辅助教材，旨在弥补课堂教学和实验中的不足，帮助学生充分理解和巩固所学的基本概念、原理和方法，达到融会贯通、举一反三的目的。

实践证明，理解课程内容与较好地解决实际问题之间存在着明显差距，而算法设计完成的质量与基本的程序设计素质的培养是密切相关的。要想理解和巩固所学的基本概念。原理和方法，牢固地掌握所学的基本知识。基本技能，达到融会贯通。举一反三的目的，就必须多做。多练。多见（见多识广）。正是为了达到上述目的，书中用一些实际的应用，对一些重要的数据结构和算法进行解读。经过循序渐进地训练，就可以使读者掌握更多的程序设计技巧和方法，提高分析。解决问题的能力。

本书根据学生的基础知识和兴趣爱好将内容分为基础篇和提高篇两个部分。第一部分基础篇精选出适当的、与实际生活结合密切的课程设计实例加以分析实现。第二部分提高篇旨在使读者通过运用数据结构知识及复杂算法去解决现实世界中的一些实际问题。

本书依据数据结构课程教学大纲要求，同时又独立于具体的教科书，既重视实践应用，又重视理论分析，本书的主要特点有：

●本书精选出来的实例项目经典、实用、具有一定的趣味性，其内容丰富、涉及面广、难易适当，能给读者以启发，达到让读者掌握相关知识和开阔视野的目的

●为了提高学生分析问题、解决问题的能力，本书对实例项目进行分析，其设计思路清晰流畅，值得参考。

●本书不仅仅是对照数据结构课程教学大纲举些例子说明数据结构能解决什么问题，而是通过分析具体的实例项目，得到对数据组织关系的需求，从而选择某个数据结构适应一些特定的问题和算法，并说明使用这种数据结构的优缺点。

●所有实例项目都给出了参考算法和源程序代码并在Turbo C和VisualC++6.0环境下运行通过。

由于作者水平有限、时间仓促，本书难免存在一些缺点和错误，恳请广大读者及同行们批评指正。

目录

第一部分基础篇

第一章线性表

1.1学生成绩管理

1.1.1项目简介

1.1.2设计思路

1.1.3数据结构

1.1.4程序清单

1.1.5运行结果

1.2考试报名管理

1.2.1项目简介

1.2.2设计思路

1.2.3数据结构

1.2.4程序清单

1.2.5运行结果

1.3约瑟夫生者死者游戏

1.3.1项目简介

1.3.2设计思路

1.3.3数据结构

1.3.4程序清单

1.3.5运行结果

1.4约瑟夫双向生死游戏

1.4.1项目简介

1.4.2设计思路

1.4.3数据结构

1.4.4程序清单

1.4.5运行结果

第二章栈和队列

2.1 迷宫旅行游戏

2.1.1 项目简介

2.1.2 知识要点

2.1.3 设计思路

2.1.4 程序清单

2.1.5 运行结果

2.2 八皇后问题

2.1.1 项目简介

2.1.2 知识要点

2.1.3 设计思路

2.1.4 程序清单

2.1.5 运行结果

2.3 停车场的停车管理

2.1.1 项目简介

2.1.2 知识要点

2.1.3 设计思路

2.1.4 程序清单

2.1.5 运行结果

第三章串、数组和广义表

3.1 单词检索统计程序

3.1.1 项目简介

3.1.2 设计思路

3.1.3 数据结构

3.1.4 程序清单

3.1.5 运行结果

3.2 Internet网络通路管理

3.2.1 项目简介

3.2.2 设计思路

3.2.3 数据结构

3.2.4 程序清单

3.2.5 运行结果

第四章树和二叉树

4.1 家谱管理

4.1.1 项目简介

4.1.2 设计思路

4.1.3 数据结构

4.1.4 程序清单

4.1.5 运行结果

4.2 表达式求值问题

4.2.2 设计思路

4.2.3 数据结构

4.2.4 程序清单

4.2.5 运行结果

4.4 图像压缩编码优化

4.4.1 项目简介

4.4.2 设计思路

4.4.3 数据结构

4.4.4 程序清单

4.4.5 运行结果

第五章图

5.1 公交路线管理

5.1.1 项目简介

5.1.2 设计思路

5.1.3 数据结构

5.1.4 程序清单

5.1.5 运行结果

5.2 导航最短路径查询

5.2.1 项目简介

5.2.2 设计思路

5.2.3 数据结构

5.2.4 程序清单

5.2.5 运行结果

5.4 电网建设造价计算

5.4.1 项目简介

5.4.2 设计思路

5.4.3 数据结构

5.4.4 程序清单

5.4.5 运行结果

5.4 软件工程进度规划

5.4.1 项目简介

5.4.2 设计思路

5.4.3 数据结构

5.4.4 程序清单

第六章查找

6.1 电话号码查询系统

6.1.1 项目简介

6.1.2 知识要点

6.1.3 设计思路

6.1.4 程序清单

6.1.5 运行结果

6.2 高校录取分数线查询系统

6.2.1 项目简介

5.2.2 知识要点

6.2.3 设计思路

6.2.4 程序清单

6.2.5 运行结果

6.3 储蓄账户查询系统

6.3.1 项目简介

6.3.2 知识要点

6.3.3 设计思路

6.3.4 程序清单

6.3.5 运行结果

6.3 期刊稿件查询系统

6.3.1 项目简介

6.3.2 知识要点

6.3.3 设计思路

6.3.4 程序清单

6.3.5 运行结果

第七章排序

7.1 设备清单排序

7.1.1 项目简介

7.1.2 知识要点

7.1.3 设计思路

7.1.4 程序清单

7.1.5 运行结果

7.2 地名排序

7.2.1 项目简介

7.2.3 设计思路

7.2.4 程序清单

7.2.5 运行结果

7.3 工厂产量排序

7.3.1 项目简介

7.3.2 知识要点

7.3.3 设计思路

7.3.4 程序清单

7.3.5 运行结果

7.4 高校科研成果排序

7.4.1 项目简介

7.4.2 知识要点

7.4.3 设计思路

7.4.4 程序清单

7.4.5 运行结果

7.5 火车车次排序

7.5.1 项目简介

7.5.2 知识要点

7.5.3 设计思路

7.5.4 程序清单

7.5.5 运行结果

7.6 IP地址排序

7.6.1 项目简介

7.6.2 知识要点

7.6.3 设计思路

7.6.4 程序清单

7.6.5 运行结果第二部分综合篇

8.1 益智游戏之七巧板

8.1.1 项目需求

8.1.2 知识要点

8.1.3 设计流程

8.1.4 程序清单

8.1.5 运行测试

8.2.1 项目需求

8.2.2 知识要点

8.2.3 设计流程

8.2.4 程序清单

8.2.5 运行测试

8.4 景区旅游信息管理系统

8.4.1 项目需求

8.2.2 知识要点

8.4.2 设计流程

8.4.4 程序清单

8.4.5 运行测试

第一部分基础篇

第一章线性表

线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继知识的学习。本章通过四个模拟项目来学习线性表的顺序和链式存储结构，首先通过使用有关数组的操作实现学生成绩管理，其次通过使用有关线性链表的操作实现考试报名管理，然后通过使用循环链表的操作实现约瑟夫生者死者游戏。

1.1 学生成绩管理

1.1.1 项目简介

学生成绩管理是学校教务部门日常工作的重要组成部分，其处理信息量很大。本项目是对学生成绩管理的简单模拟，用菜单选择方式完成下列功能：输入学生数据；输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生数据。

1.1.2 设计思路

本项目的实质是完成对学生成绩信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。

1.1.3 数据结构

本项目的数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名和成绩组成，这组学生的成绩信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据具有线性表中数据元素的性质，所以该系统的数据采用线性表来存储。

顺序表是线性表的顺序存储结构，是指用一组连续的内存单元依次存放线性表的数据元素。在顺序存储结构下，逻辑关系相邻的两个元素在物理位置上也相邻，这是顺序表的特点。本项目可以采用顺序表的线性表顺序存储结构。

若一个数据元素仅占一个存储单元，则其存储方式参见图1-1。

从图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)，预先分配空间需按最大空间分配，利用不充分，表容量难以扩充。

用结构体类型定义每个学生数据，故该数组中的每个数据的结构可描述为：

typedef struct STU

{ char stuno[10]; //学号

char name[10]; //姓名

float score; //成绩

} ElemType;

1.1.4 程序清单

#include

#include

#include

#include

#define MaxListSize 20

#define EQUAL 1

typedef struct STU{

char stuno [10];

char name [10];

}ElemType;

class List

{private:

//线性表的数组表示

ElemType elem[MaxListSize];

int length;

int MaxSize;

public:

//输入学生数据

void init(List **L,int ms);

//删除所有学生数据

void DestroyList(List &L){free(&L);}

//将顺序表置为空表

void ClearList(){length=0;}

//判断顺序表是否为空表

bool ListEmpty()

{return length==0;}

//判断顺序表是否为满

bool ListFull()

{return length==MaxSize;}

//删除某个学生数据

bool ListDelete(int,ElemType &e);

//遍历顺序表

void ListTraverse();

//返回顺序表的长度

int ListLength();

//学生数据查询

void GetElem(int,ElemType *);

//修改学生数据

bool UpdateList(ElemType& e,ElemType); //添加学生数据

bool ListInsert(int,ElemType &);

//对学生数据按升序或降序输出

void printlist(int);

void List::init(List **L,int ms)

{*L=(List *)malloc(sizeof(List));

(*L)->length=0;

(*L)->MaxSize=ms;

}

int List::ListLength()

{return length;}

bool List::ListDelete(int mark,ElemType &e) {int i,j;

if(ListEmpty()) return false;

if(mark>0) { //删除表头元素

e=elem[0];

for(i=1; i

elem[i-1]=elem[i];}

else //删除表尾元素

if(mark<0) e=elem[length-1];

else { //删除值为e的元素

for(i=0;i

if(strcmp(elem[i].name,https://www.sodocs.net/doc/374009061.html,)==0) break;

if(i>=length) return false;

else e=elem[i];

for(j=i+1;j

elem[j-1]=elem[j];}

length--;

return true;

}

void List::ListTraverse()

{for(int i=0;i

{cout<

cout<

cout<

cout<

void List::GetElem(int i,ElemType *e)

{*e=elem[i];}

bool List::EqualList(ElemType *e1,ElemType *e2)

{ if (strcmp(e1->name,e2->name))

return false;

if (strcmp(e1->stuno,e2->stuno))

return false;

if (e1->age!=e2->age)

return false;

if (e1->score!=e2->score)

return false;

return true;

}

bool List::Less_EqualList(ElemType *e1,ElemType *e2) { if(strcmp(e1->name,e2->name)<=0) return true;

else return false;

}

bool List::LocateElem(ElemType e,int type)

{ int i;

switch (type)

{ case EQUAL:

for(i=0;i

if(EqualList(&elem[i],&e))

return true;

break;

default:break;}

return false;

}

//修改学生数据

bool List::UpdateList(ElemType& e,ElemType e1) {for(int i=0;i

if(strcmp(elem[i].name,https://www.sodocs.net/doc/374009061.html,)==0) {

elem[i]=e1;return true;}

}

bool List::ListInsert(int i,ElemType &e)

{ElemType *p,*q;

if(i<1||i>length+1) return false;

q=&elem[i-1];

for(p=&elem[length-1];p>=q;--p)

*(p+1)=*p;

*q=e;

++length;

return true;

}

//对学生成绩按升序或降序输出

void List::printlist(int mark)

{int* b=new int[length];

int i,k;

cout<<" 姓名学号成绩\n";

if(mark!=0){

for(i=0; i

for(i=0; i

for(int j=i+1;j

if(mark==1&&elem[b[j]].score

if(mark==-1&&elem[b[k]].score

for(int i=0;i

{cout<

cout<

cout<

cout<

else {

for(i=0;i

{cout<

cout<

cout<

cout<

void main()

{ cout<<"linelist1m.cpp运行结果:\n"; ElemType e,e1,e2,e3,e4,e5,e6;

List *La,*Lb,*Lc;

int k;

cout<<"首先调用插入函数.\n";

La->init(&La,4);

strcpy(https://www.sodocs.net/doc/374009061.html,,"stu1");

strcpy(e1.stuno,"100001");

e1.age=22;

e1.score=88;

La->ListInsert(1,e1);

strcpy(https://www.sodocs.net/doc/374009061.html,,"stu2");

strcpy(e2.stuno,"100002");

e2.age=21;

e2.score=79;

La->ListInsert(2,e2);

strcpy(https://www.sodocs.net/doc/374009061.html,,"stu3");

strcpy(e3.stuno,"100003");

e3.age=19;

e3.score=87;

La->ListInsert(3,e3);

La->printlist(0);

cout<<"表La长:"<ListLength()<

Lb->init(&Lb,4);

strcpy(https://www.sodocs.net/doc/374009061.html,,"zmofun");

strcpy(e4.stuno,"100001");

e4.age=20;

e4.score=94;

Lb->ListInsert(1,e4);

strcpy(https://www.sodocs.net/doc/374009061.html,,"bobjin");