数据结构讲义

第一章：绪论课程：数据结构课题：第一章 1.1—1.4小节（共4个课时）1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。

新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：……………………………第1-2课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。

计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。

进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。

1.1 什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。

其中建立数学模型的实质：找出操作对象之间的关系。

例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。

（地位）1.2 数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声音、图象等。

2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。

一个数据元素可由若干个数据项组成（Data Item）。

3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

目录绪论30。

1 基本概念3第一章线性表51。

1 线性表的定义51。

2 线性表的实现51.2.2 线性表的链式存储结构8第二章栈、队列和数组162。

1 栈162。

2 队列212。

3 特殊矩阵的压缩存储232.3.1 数组232。

3。

2 特殊矩阵24第三章树与二叉树263。

1 树的概念261。

树的定义262．相关术语273.2 二叉树273。

2.1 定义与性质273.2。

2 二叉树的存储293.2.3 二叉树的遍历303。

2。

4 线索二叉树353。

3 树和森林393。

3。

1 树的存储结构393。

3.2 森林和二叉树的转换4013。

3。

3 树和森林的遍历403.4 哈夫曼（Huffman)树和哈夫曼编码42第四章图434.1 图的概念434。

2 图的存储及基本操作444。

2。

1 邻接矩阵444.2。

2 邻接表454.3 图的遍历474。

3。

1 深度优先搜索474。

3。

2 广度优先搜索484。

4 图的基本应用494。

4.1 最小生成树494.4。

2 最短路径504.4.3 拓扑排序534。

4。

4 关键路径54第五章查找565。

1 查找的基本概念565。

2 顺序查找法575。

3 折半查找法585.4 动态查找树表605.4。

1 二叉排序树605.4.2 平衡二叉树635.4.3B 树及其基本操作、B+树的基本概念665.5 散列表675.5。

2 常用的散列函数6825。

5.3 处理冲突的方法695。

5.4 散列表的查找705.5.5 散列表的查找分析71第六章排序726.1 插入排序726.1.1 直接插入排序726。

1.2 折半插入排序736.2 冒泡排序736。

3 简单选择排序746。

4 希尔排序756.5 快速排序766.6 堆排序786.7 二路归并排序806。

8 基数排序816。

9 各种内部排序算法的比较82绪论0。

1 基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合.数据结构是一个二元组Data_Structure ＝（D，R），其中，D 是数据元素的有限集，R 是D 上关系的有限集.32、逻辑结构：是指数据之间的相互关系。

第一章绪论第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。

数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。

信息模型：信息处理领域中的数学模型。

数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。

忽略数据的具体含义，研究信息模型的结构特性、处理方法。

第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。

例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码……数据元素：数据的基本单位。

相当于"记录"。

一个数据元素由若干个数据项组成，相当于"域"。

数据对象：性质相同的数据元素的集合。

数据结构：相互之间存在特定关系的数据集合。

四种结构形式：集合、线性、树形、图(网)状形式定义：(D，S，P)D：数据元素的集合(数据对象)S：D上关系的有限集P：D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。

存储结构：数据结构在计算机中的存储形式。

顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。

存储结构：便于机器运算，面向机器。

程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。

包括：原子类型、结构类型。

抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。

核心：是逻辑特性，而非具体表示、实现。

课程任务：学习ADT、实践ADT。

如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采用模块结构。

如：C中的头文件、C++中的类第三节 ADT的表示与实现本教材中，算法书写习惯的约定。

数据元素类型ElemType：int,float,char, char[] ……引用参数 &算法：void add(int a,int b,int &c) { c=a+b; }程序：void add(int a,int b,int *p_c){ *p_c=a+b; }第四节算法的描述及分析一、有关算法的概念算法：特定问题求解步骤的一种描述。

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。

…}，字母字符数据对象是集合象。

由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

为数据结构的有限集，S是D上关系的有限集。

表示复数的虚部。

存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。

例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

《数据结构》讲义（new）第1章C程序设计程序设计＝数据描述＋算法设计，即程序＝数据结构＋算法。

用计算机去解决问题过程：首先用数据结构的知识表示出问题，然后设计出解决问题的算法，最后写出程序在计算机上运行输出问题解决的结果。

本章我们将对C的主要知识作回顾，为学习数据结构奠定基础。

1.1 表达式算术运算：5/3 值为1，2.5/5 值为0.5,10%3 值为1，'A'+1 值为66赋值运算：a=3+5 a值为8，式值为8。

b=a=3+5 a,b值均为8，式值为8。

a+=3 即a=a+3; a-=3; a*=3; a/=3;a%=3.i++ ,++i,即i=i+1;i...,...i.区别：x=i++;与x=++i;关系运算：3==2，式值为0，3！=2，式值为1。

逻辑运算：0<x&&x<=1, x<=0||x>1,!(x<0). 注：“非零”为1。

条件运算：b>=0?a+b:a-b,即a+︱b︱逗号运算: a=6,a*3,a+3 式值为91.2 函数与参数1.2.1传值参数例1.1 输入四个数，输出其中的最大数。

int max(int x,int y) /*x,y是形参*/{int t;if(x>y) t=x; else t=y;return t;}main(){int a,b,c,d,m;scanf(“%d%d%d%d”,&a,&b,&c,&d);m=max(max(a,b),max(c,d)); /*a,b,c,d,max(a,b),max(c,d)是实参,传值调用*/ printf(“%d”,m);}1.2.1传址参数例1.2输入二个数到变量a与b，交换变量a与b的值后输出。

swap(int *x,int *y) /*x,y为传址参数*/{int t;t=*x;*x=*y;*y=t;}main(){int a,b;scanf("%d%d",&a,&b);swap(&a,&b); /*传址调用*/printf("%d %d",a,b);}例1.3 输入n 个数，升序排列后输出。