数据结构学习指导

数据结构东北大学

孟凡荣2009年3月数据结构学习指导

1课程简介

2章节目录

3数据结构实验

4实验课题

5学习方法

6考试指导

1课程简介课程性质专业技术基础课先修课程离散数学、C/C++语言程序设计学时安排总学时64学时（含16学时实验）

1课程简介教学要求

从课程性质上讲，本课程是一门专业技术基础课。其教学要求是：学会从问题分析入手，研究数据在计算机中的数据结构特性，为应用所涉及到的数据选择适当的逻辑结构、存储机构及其相应的操作算法。1课程简介教学要求本课程的学习过程也是进行复杂程序设计的训练过程，要求初步掌握基本的算法设计技术，以及算法的时间和空间性能的分析方法，会书写符合软件工程规范的程序文档，为今后的计算机软件程序开发奠定良好的基础。1课程简介教学要求本课程是一门实践性很强的课程，因此在学习过程中，除了掌握课程的基本知识内容之外，还应上机完成实验课题和做好课后习题。上机前，必须对课程内容做到真正的消化和理解，特别是对于算法的学习，应掌握它们的设计思想、编写程序并能上机正确调试运行。

1课程简介课程内容本课程分为四个知识单元，共7章18课。第1单元，数据结构基础；第2单元，常用数据结构；第3单元，数据结构及算法应用；第4单元，数据结构实验。2章节目录第1章数据结构与算法基础第2章基本数据结构第3章栈和队列第4章树和图第5章查找表和文件第6章数据结构及算法应用2章节目录第1课数据结构基本概念

1数据结构的研究对象

2数据结构的定义及分类3数据类型和抽象数据类型4数据结构的描述与实现2章节目录第2课算法基础

1算法的概念

2算法的描述3算法分析基础

4算法设计基础2章节目录第3课顺序表

1顺序表的存储结构

2顺序表的基本操作3有序顺序表4顺序表的简单应用2章节目录第4课线性链表

1链表的存储结构

2链表的基本操作

3有序链表

4链表的简单应用2章节目录第5课字符串

1串的逻辑结构

2串的顺序存储结构

3串的链式存储结构

4串的模式匹配

2章节目录第6课数组

1数组的逻辑结构

2数组的存储结构

3特殊矩阵的存储

2章节目录第7课栈

1栈的逻辑结构

2顺序栈

3链栈

4栈的简单应用2章节目录第8课队列

1队列的逻辑结构

2链队列

3循环队列

4队列的简单应用2章节目录第9课二叉树

1树和二叉树的逻辑结构

2二叉树的性质3二叉树的存储结构4二叉树的遍历

2章节目录第10课树和森林

1树的存储结构2树、森林与二叉树3树和森林的遍历

2章节目录第11课图

1图的逻辑结构

2图的存储结构3图的遍历

2章节目录第12课查找表

1查找表的概念

2静态查找表3二叉排序树

4散列（Hash）表

2章节目录第13课文件

1文件的概念

2索引文件3散列文件

2章节目录第14课排序1排序的基本概念2插入排序5归并排序3快速排序6多关键字排序4堆排序7外部排序

2章节目录第15课线性结构应用

1约瑟夫环

2静态链表应用

3三元组求解稀疏矩阵

4实用型线性链表5一元多项式运算

2章节目录第15课线性结构应用

6栈与递归7简单背包问题8地图着色问题

9共享栈10子集划分2章节目录第16课树形结构应用

1全线索链表

2表达式求值3哈夫曼树

4等价类划分5树的形态

2章节目录第17课图形结构应用

1迷宫问题

2无向图的连通性应用

3有向无环图应用

4最短路径问题

2章节目录第18课数据结构程序设计

1问题求解策略

2

0-1背包问题3数据结构程序实现4数据结构程序设计实例3数据结构实验实验教学要求数据结构是计算机专业的核心课程。通过本课程的实验，使学生加深对课程内容的理解，培养将原理应用于实际的能力，提高软件编程设计及算法应用的综合素质。本课程实验要求所编写的程序能够正常运行，并提交实验报告。3数据结构实验实验报告内容（1）实验目的说明课题的目的和任务。应包括对问题的需求分析，具体有数据的输入的形式和输入值的范围；数据输出的形式；程序的功能等。3数据结构实验实验报告内容（2）实验原理包括课题的程序中所用到的抽象数据类型的定义、主程序的流程以及各程序模块之间的调用关系。3数据结构实验实验报告内容（3）实验步骤实现课题设计中定义的所有数据类型及存储结构；对每个模块及操作写出伪码算法。3数据结构实验实验步骤启动编程环境定义存储结构定义基本操作设计基本操作算法编写源代码设计主算法和主程序调试源程序

3数据结构实验源程序调试全局变量及包含头文件存储结构定义结构创建及销毁操作属性操作查找操作更新操作主程序

3数据结构实验实验报告内容（4）程序运行及结果分析列出包括输入和输出的测试结果；对程序调试中所遇问题的解决方法及分析；算法的时空分析及改进设想；经验和体会。3数据结构实验实验报告内容（5）实验文档必要的程序使用说明及带注释的源程序及调试文件的电子版。4实验课题实验1顺序表基本操作及应用实现顺序表的基本操作，包括顺序表的创建、查找、求长度、插入、删除、遍历等函数。应用参考题目

1.1学生成绩统计

1.2有序表求并

1.3字典维护

4实验课题实验2单链表基本操作及应用实现单链表的基本操作，包括顺序表的创建、查找、求长度、插入、删除、遍历等函数。应用参考题目

2.1约瑟夫环

2.2一元多项式相加

2.3商品维护4实验课题实验3顺序栈基本操作及应用实现栈的基本操作，包括栈的创建、销毁、出栈、入栈、取栈顶元素、判栈空等函数。应用参考题目

3.1数制转换

3.2算术表达式求值

3.3停车场管理4实验课题实验4队列基本操作及应用实现队列的基本操作，包括队列的创建、销毁、出队、入队、取对头元素、判队列空等函数。应用参考题目

4.1存储缓冲区问题

4.2迷宫最短路径问题

4.3杨辉三角形

4实验课题实验5二叉树基本操作及应用实现二叉树的初始化、创建、查找、遍历、插入、删除和判空树等基本操作。应用参考题目

5.1哈夫曼编码

5.2表达式求值

5.3因特网查询4实验课题实验6图的基本操作及应用实现图结构的初始化、创建、查找、遍历、插入、删除等基本操作。应用参考题目

6.1无向图的关节点问题

6.2最小生成树

6.3迷宫问题4实验课题实验7查找表基本操作实现实现静态查找表、二叉排序树及哈希表的基本操作。应用参考题目

7.1分块查找应用

7.2二叉排序树应用

7.3哈希表应用4实验课题实验8排序算法实现实现希尔排序、快速排序、堆排序、二路归并排序和基数排序的基本操作。应用参考题目

8.1排序算法应用

8.2排序算法比较

8.3计数式基数排序4实验课题实验9数据结构综合应用实现类似迷宫问题、银行排队问题等综合应用算法。应用参考题目

9.1背包问题

9.2表达式求值

9.3智能搜索5学习方法预备知识课程内容体系存储结构与基本操作循序渐进实验能力典型应用算法综合应用5学习方法预备知识

C与C++

Turbo3.0C/C++VisualC++5学习方法预备知识-引用参数&问题

C++语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。

标准C不支持引用参数，对此需进行转换。5学习方法预备知识-引用参数&问题含有引用参数的函数如下：

Status

DestroyTriplet(Triplet&T)

{//操作结果：三元组T被销毁

free(T);

T=NULL;

returnOK;

}5学习方法预备知识-引用参数&问题转换后的标准C程序如下：StatusDestroyTriplet(Triplet*T)

//将&T改为*T

{//操作结果：三元组T被销毁

free(*T);//将T改为*T

*T=NULL;//将T改为*T

returnOK;

}5学习方法预备知识-引用参数&问题另外，如果调用该函数，实参前应加&。如调用DestroyTriplet()的语句为：

DestroyTriplet(T);

相应的标准C程序调用语句为：

DestroyTriplet(&T);5学习方法预备知识-引用参数&问题在调用DestroyTriplet()的两程序中，两实参T的类型是相同的。在转换过程中，遇到&*或*&可“抵消”，即将*&T转换为T。5学习方法预备知识-typedef类型定义只要在定义结构体时使用typedef，则在指明结构体的类型时就不必加struct。如：

StatusClearList(SqList&L)5学习方法预备知识-变量定义问题

C++允许在执行语句中变量使用之前定义变量。而标准C语言是不允许的。如：

voidPrintUser(Spacep[])

{

//输出p数组所指的已分配空间

for(inti=0;i<MAX;i++)……5学习方法预备知识-动态申请空间问题

在C++中可用new申请空间，如一条语句如下：

p=new

Chunk;在标准C中要改为：

p=(Chunk*)malloc(sizeof(Chunk));5学习方法预备知识-输入输出语句在C++中可用cout<<T[0]<<''<<T[1]<<''<<T[2]

<<endl;

好处是不必给出格式符。这样，当变量的类型发生变化时，不必修改语句。5学习方法预备知识-输入输出语句但在标准C中必须改为：

printf(“%d%d%d\n”,T[0],T[1],T[2]);//当ElemType的类型变化时，要

//相应改变printf()的格式符5学习方法课程内容体系（1）数据结构定义逻辑结构-存储结构-基本操作（2）数据结构应用基本结构-常用结构-复杂结构（3）数据结构算法应用线形结构-树形结构-图形结构5学习方法存储结构与基本操作

顺序存储链式存储索引存储散列存储结构创建及销毁属性操作查找操作更新操作5学习方法循序渐进

简单数组-顺序表-单链表-字符串-二叉树-图简单基本操作-复杂基本操作简单应用-高级应用-综合应用5学习方法实验能力

基本操作实现简单应用实现简单综合应用实现复杂综合应用实现

5学习方法典型应用算法一元多项式表达式求值哈夫曼树最小生成树拓扑排序

……5学习方法综合应用

迷宫问题背包问题排队时间模拟工程关键路径局部与全局最优问题

……6考试指导考试题型

单选题填空题算法应用题算法分析题算法设计题

6考试指导单选题在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行操作A.s->next=p->next;p->next=s;B.s->next=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;6考试指导单选题假设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A．A，B，C，D

B．D，C，B，AC.A，C，D，B

D.D，A，B，C6考试指导单选题在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是A．LL型

B．LR型

C．RL型

D．RR型6考试指导单选题有向图G用邻接矩阵A存储，则顶点i的入度等于A中

A.第i行1的元素之和

B.第i列1的元素之和

C.第i行0的元素个数

D.第i列非0的元素个数6考试指导单选题在分块索引查找的顺序表中查找，算法中采用的技术是

A.穷举法

B.贪心法

C.分治法

D.回溯法

6考试指导填空题数据的逻辑结构包括线性