1、1数据结构学习指导说明：本指导以数据结构(C 语言版)(严蔚敏等编著,清华大学出版社 1997年出版，国家级优秀教材特等奖)和数据结构题集(严蔚敏等编著,清华大学出版社 1999年出版)为教学主要参考书。一、绪论1、学习目的： 明确数据结构课程在本专业知识结构中的地位，作用。课程的特点，教学的要求，方法。明确数据结构所研究的问题以及有关基本概念。初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。3、
2、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4) 数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。(二) 课程的地位，性质，作用。(1) 地位: 计算机专业的核心课程之一。(2) 性质: 算法理论基础和软件设
3、计的技术基础课。(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：数据结构(C 语言版)严蔚敏等编著 北京 清华大学出版社 1997年参考书：数据结构许卓群等编著 北京 高等教育出版社 1987年数据结构实用教程 （C/C+描述）徐孝凯 北京 清华大学出版社 1999 年2数据结构题集严蔚敏等编著 北京 清华大学出版社 1999年数据结构导学苏光奎等编著 北京 清华大学出版社 2002年数据结构(C 语言篇)习题与解析 李春葆编著 北京 清华大学出版社2002年数据结构实验指导书 唐开山 自编
4、讲义 2002 年(五) 基本概念和术语(1)数据(2)数据元素(3)数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。数据结构综合三方面的内容：数据的逻辑结构，数据的存储结构及其运算。且不涉及元素本身的内容。(5) 结构：数据元素相互之间的关系。a) 四类基本结构；b) 表示形式(6) 逻辑结构(7) 物理结构(存储结构)(8) 元素或结点(9) 数据域(10) 数据元素之间关系的两种表示方法：顺序映像顺序存储结构；非顺序映像链式存储结构。(11) 存储结构的描述(12) 数据类型(
5、13) 抽象数据类型(14) 抽象数据类型按其值的不同特性分为三种类型(15) 抽象数据类型可用三元组表示(16) 多型数据类型(六) 抽象数据类型的表示和实现(1) 概述 用伪码和类 c语言作为描述工具(2) 基本约定(3) 抽象数据类型 triplet的表示和实现 赋值参数和引用参数 部分基本操作及其实现：构造三元组(七) 算法和算法分析(1) 算法的概念3(2) 算法的五个特性 有穷性 确定性 可行性 输入 输出(3) 算法设计的要求 正确性 可读性 健壮性 效率与低存储量需求(4) 算法效率的度量 事后统计方法 事前分析估算的方法(5) 时间复杂度：时间复杂度的确定：算法中基本操作，重
6、复执行的次数是问题规模 n的基本函数f(n)，算法的时间量度记做 T(n)=O(f(n)，则 f(n)为该问题的渐进时间复杂，简称时间复杂度。只需选择一种基本操作来讨论算法的时间复杂度。只需求出它关于 n的增长率为何即可。线性查找的平均时间复杂度和最坏时间复杂度。(6) 空间复杂度：算法的存储空间需求。5、作业 P7 1.3，1.5，P8 1.8 中(1)、(3)、 （5） 、(7)、(8),P10 1.12，1.14二、线性表1、学习目的：明确线性表的概念与基本运算；明确顺序表和链表的定义、组织形式、结构特征和类型说明；熟练掌握线性表的顺序存储结构和链接存储结构（单链表、循环链表、双向链表）
7、及其基本运算的实现原理和方法。2、学习重点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结构特点；循环链表、双链表上删除与插入运算的实现。3、学习难点：指针操作；删除、插入运算中的指针操作顺序；双链表上指针的操作顺序。4、课程内容与基本要求(一) 线性表类型的定义 (1) 线性表的四个特性(2) 定义(3) 抽象数据类型线性表的定义(二) 线性表的顺序表示和实现(1) 有关概念 线性表的顺序表示 存储位置公式 线性表的动态分配顺序存储结构，及初始化的操作
8、。(2) 基本操作4 结构定义 初始化：int initlist_sq(sqlist *l) 线性表中插入元素：int listinsert(sqlist *l,int i,int e) 动态存储分配函数 realloc的使用 线性表中删除元素：int listdelete_sq (sqlist *l int i, int *e)(3) 算法分析 插入：期望值(平均次数)：E is = pi(n-i+1)= (n-i+1)=1ni1ni 2n 删除：期望值(平均次数)：E dl= qi(n-1)= (n-1)= i1i1(4) 两个集合归并的不同合并法：条件：有序与无序21n(三) 线性链表(
9、1) 线性表顺序存储结构的缺点(2) 结点，线性表链式存储结构及其特点每个结点只包含一个指针域的链表称为线性链表或单链表(3) 线性表的单链表存储结构定义(4) 带头结点的单链表(5) 线性链表的基本操作 得到第 i个元素操作 getelem_l(linklist l ,lnt i,elemtype *e) 插入元素操作 listinsert_l(linklist l,int i,elemtype e) 删除第 i 个元素操作 listdelete_l(linklist l,int i,elemtype *e) 建立单链表操作 creatlist_l(linklist l,int n) 合并两
10、个单链表 mergelist_l(linklist la,linklist lb,linklist lc) (四) 线性表的静态单链表存储结构(1) 结构描述(2) 存储线性表的特点(3) 基本算法 ： 查找元素算法 int locateelem_sq(slinklist s,int e) 求(A-B)U(B-A)算法 (五)循环链表(1) 特点：单链表中最后一个结点的指针域指向头结点，形成一个环。(2) 逻辑结构(3) 只设立尾指针将两个线性表并成一个表的操作5(4) 循环链表结束判断(六)双向链表(1) 特点：结点中有两个指针域，其一指向直接后继，另一指向直接前趋(2) 逻辑结构(3) 双
11、向链表存储结构的结点定义(4) 带头结点的双向循环链表 逻辑结构 结点指针关系 插入结点时指针变化状况 删除结点的指针变化状况(5) 带头结点双向循环链表的插入操作 listinsert_dul(dulinklist l,int i,int e)(6) 带头结点双向循环链表的删除操作 listdelete_dul(dulinklist l,int i,int *e)(7) 带头结点的单链线性表应用举例 在第个元素之前插入元素 int listinsert_l(linklist l,int i,int e) 合并两个非递减单链线性表int mergelist_l(linklist la,link
12、list lb,linklist *le)(七) 一元多项式的表示及相加(1) 一元多项式的逻辑结构(2) 两种结构表示，重点讨论链式存储结构(3) 抽象数据类型一元多项式的定义(4) 抽象数据类型 polynomial的实现(5) 基本操作的算法描述 建立一有序链表 void crealepolyn(polynomail p,int m) 合并两个多项式 void addpolyn(polynomial pa,polynomail pb) 了解两个多项式相乘5、作业 P13 2.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9，2.11，2.19，2.21，2.22三、栈和
13、队列1、学习目的：明确栈和队列的概念、特征及在其上所定义的基本运算，熟练掌握在两种存储结构上对栈和队列所施加的基本运算的实现。掌握循环队列的基本运算；了解多栈共享邻接空间；了解双端队列。2、学习重点：栈的定义及逻辑特点；入栈、出栈等运算在两种存储结构栈上的实现；队列的定义及逻辑特点；入队、出队等运算在两种存储结构栈上的实现；循环队列的顺6序存储结构及其运算实现。3、学习难点：循环队列的队空、队满判断条件；循环队列上的插入、删除操作。4、课程内容与基本要求(一) 栈的有关概念(1) 栈的引入(2) 栈的定义(3) 栈的逻辑结构及进出栈(5) 栈的抽象数据类型的定义(ADT stack) 栈的插入
14、元素的操作称入栈push 栈的删除栈顶元素的操作称出栈pop(二)栈的表示和实现(1) 顺序栈 结构定义 顺序栈表示 顺序栈的基本操作 基本操作的算法描述a) 栈初始化 int initstack(sqstack s)b）访问栈顶 int getop(sqstack s,selemtype e)c) 入栈 int push(sqstack s,selemtype e)d) 出栈 int pop(sqstack s,selemtype *e)(2) 链式栈 结构定义 链式栈表示 链式栈的基本操作 基本操作(三) 栈的应用举例(1) 数制转换：算法(2) 括号匹配的检验：思路(3) 行编辑程序：思
15、路(4) 迷宫求解和表达式求值作为实践内容(四)队列的有关概念(1) 定义(2) 特点: 是一种先进先出(FIFO)结构(3) 队列的表示7(4) 队列的抽象数据类型定义(5) 关于双端队列(五) 队列的顺序存储结构(1) 结构定义(2) 基本操作 初始化操作 int initsqueue(squeue *sq) 入队操作 int putsq(squeue *sq, elemtype e) 出队操作 int outsq(squeue *sq, elemtype *e)(六) 队列的链式存储表示和基本操作(带头结点)(1) 结构定义：结点、结构(2) 链式队列的表示(七) 队列的链式存储结构的基
16、本操作(带头结点)(1) 初始化(2) 入队(3) 出队(八) 循环队列(1) 循环队列的引入：顺序存储结构中，一般顺序队列的缺点(2) 循环队列的处理方法(3) 队满与队空的判断: 两种方法：设置一标志以区别是队满还是队空；另一种方法是损失一个元素空间，一般用后一种方法。 队满判断：(q.rear+1)%maxsize=q.front; 队空：q.front=q.rear; 指针(下标)移动增 1的处理：q.front=(q.front+1)%maxsize;q.rear=(q.rear+1)%maxsize;(九) 循环队列的基本操作(1) 结构定义(2) 初始化循环队列 int init
17、queue(squque *q)(3) 求队列长度 int queuelength (sqqueue q)(4)入队 int enqueue(sqqueue *q,elemtype e)(5)出队 int dequeue (sqqueue *q, elemtype *e)5、作业 p22 3.3，3.4，3.7，3.12，3.13，3.28，3.30 四、串和数组81、学习目的：明确串的概念、存储方式和常用的串运算；明确多维数组的结构特点和在内存中的两种顺序存储方式；掌握串的基本运算及其初步应用；了解串操作在文本编辑中的应用。明确数组的概念、数组的顺序存储的特点；掌握数组的基本操作方法；掌握稀
18、疏矩阵和特殊矩阵的存储方法；了解广义表的定义和基本运算。2、学习重点：串的基本概念、基本运算；串的两种存储方式；多维数组的逻辑结构；多维组的两种顺序存储方式；计算给定元素在存储区中的地址；对称矩阵、三角矩阵的压缩存储方式；稀疏矩阵的三元组表表示方法。3、学习难点：串的基本运算及其综合应用；稀疏矩阵的压缩存储表示下的运算的实现。4、课程内容与基本要求(一) 串的基本概念(1) 定义：(2) 子串、主串、位置、相等、空格串(3) 特点:串的逻辑结构与线性表极为相似；串的操作与线性表差别很大，线性表中一般以单链表操作为主，而在串操作中常以串的整体为操作对象。(4) 串的抽象数据类型的定义(二) 五种
19、基本操作：(1) 串赋值 strassign，(2) 串比较 strcompare，(3) 求串长度strlength，(4) 串连接 concat，(5) 求子串 substring(三) 串的表示和实现（三种表示）(1) 定长顺序存储表示 结构定义 串赋值：Int strassign(sstring s1,sstring s2) 串比较：Int strcompare (sstring s1,sstring s2) 求串长度：Int strlen(sstring s) 串连接：Int concat (sstring s1,sstring s2) 求子串：int substr(sstring
20、t,sstring s,int pos,int len)(2) 堆内存存储表示 实现特点(堆分配存储含义)：动态分配一组地址连续的存储单元有存放串值字符序列。 结构定义，注意动态分配 基本操作(a) 生成操作 strassign(hstring t,char *chars)(b) 求长度 strlength (c) 两串比较 int strcompare (hstring s,hstring t)9(d) 清空串 clearstring (hstring s)(e) 串联接 int concat (hstring t,hstring s1,hstring s2)(f) 求子串 int subs
21、tring (hstring sub, hstring s,int pos,int len)(g) 子串定位 int index(hstring s,hstring t,int pos)(3) 串的块链表存储表示 概念 结构定义 串处理效率(存储密度) 优缺点(四) 串操作应用举例(了解)(1) 文本编辑的基本操作查找、输入、删除、替换(2) 文本编辑的实现方法 建立行表：行号、起始地址、长度等 页表：页号、起始地址、长度 设立页、行、字符指针。用动态数组实现为方便 光标的捕捉(五) 数组的概念(1) 特点：线性表的扩充表中的数据元素本身也是一个数据结构(2) 数组的定义：抽象数据类型数组的定
22、义形式(3) 二维数组的解释(4) 数组的顺序表示 二维数组的两种存储方式：以列序为主；以行序为主 储位置的公式：二维；多维(5) 结构定义(6) 基本操作算法 初始化 int initarray(array *a,int dim)va_start(ap,dim) /ap是存放各维容量的数组 求下标元素 a(j0,j1,j2,j0dm-1)的地址int locate(array a,va_list ap,int *off)(六) 矩阵的压缩存储(1) 压缩存储的有关概念 压缩存储：为多个值相同的元素分配一个存储空间，对零元不分配空间 特殊矩阵：值相同的元素或者零元素在矩阵中的颁布有一定规律 稀
23、疏矩阵：非零元个数的矩阵(2) 特殊矩阵 对称矩阵10(a) 概念 (b) 压缩存储方法 (c) 下标对应关系 三角矩阵 对角矩阵(3) 稀疏矩阵 含义 ADT 稀疏矩阵的定义 压缩存储(三种方法)：(a) 三元组顺序表 (b) 行逻辑链接的顺序表 (c)十字链表(4) 三元组顺序表 三元组表示 结构定义 转置算法 1(保持以行为存储) int tpm(tsmatrix m, tsmatrix t) 转置算法 2(较高效的算法。了解)(5) 了解行逻辑链接的顺序表和十字链表(七) 广义表的有关概念.(1) 线性表的推广,也称为列表.(2) 形式(3) 有关概念(4) 三个重要结论(5) 求表头
24、和表尾(八) 广义表的存储结构(了解)(1) 两种结点结构. 表结点：用以表示列表 原子结点：用以表示原子(2) 广义表的头尾链表存储表示5、作业 P27 4.3，4.4，4.5，4.6, P29 4.18，4.24 ，P31 5.1，5.2，5.3，5.8，5.10，5.11五、树和二叉树1、学习目的：明确树的基本概念及性质；明确树的各种存储结构；明确二叉树的概念及其二叉树的顺序存储表示和链接存储表示；熟练掌握二叉树的性质和遍历，掌握前序、中序、后序遍历的递归算法与非递归算法；明确线索二叉树的概念；掌握前序线索化二叉树的有关算法；了解中序、后序线索化二叉树的有关算法问题；初步掌握树、森林与二叉树的转换；明确哈夫曼树的概念，掌握哈夫曼树的构造方法并能初步应用。2、学习重点：树的存储结构；二叉树的定义、逻辑特点及五种基本形态；二叉树的
