数据结构知识点总结.ppt

数组一般用顺序存储的方式表示。 存储的方式有： ·行优先顺序，也就是把数组逐行依次排列。PASCAL、C
·列优先顺序，就是把数组逐列依次排列。FORTRAN
·子串在主串中的序号就是指子串在主串中首次出现的位置。
地址的计算方法： ·按行优先顺序排列的数组：LOCa（ij）=LOCa（11）+（（i-1）
·三角矩阵： ·上三角阵：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa[0]）+k*d. ·下三角阵：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d.
·对角矩阵：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d. 稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一
·第三种就是用一个计数器记录队列中的元素的总数。 队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在
但不适合插入、链接操作。 ·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存
储单元。 串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链
单元中的各元素的物理位置和
·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于 数据结构。
逻辑结构中各结点相邻关系是一致的。地址计算：LOCa（i）=LOCa（1）+（i-1）*d； （首地址为 1）
在顺序表中实现的基本运算：
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间；

数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据元素（Data Element）
数据元素是组成数据的基本单位,是计算机程序加工处理的基本单位，在计算机中通常 作为一个整体进行考虑和处理。
数据项（Data Item）
数据项（Data Item）是有独立含义的最小单位。一个数据元素可由一个或多个数据 项组成，此时的数据元素通常称为记录（Record）。 例如：表1.1所示，学生信息表是数据，一行表示一个学生的记录，每一条记录就是一个数据 元素，每一个数据元素都是由学号、姓名、性别、出生日期、政治面貌5个数据项组成。
设计算法
编写代码
数值问题 非数值问题
数学方程式 设计合理的数据结构（表、树、图等）
数据结构是一门研究非数值计算程序设计问题中的操作对象，以及 它们之间的关系和操作等相关问题的学科。
数据结构的3种基本结构---线性结构
线性结构
实例：学生信息管理系统
数据结构的3种基本结构---树结构
树结构
实例：八皇后问题
1.5 算法与性能分析---算法的设计要求
算法的设计要求
1.正确性 程序中不含语法错误、算法的执行结果应当满足预先规定的功能和性能要求。
2.可读性 一个好的算法首先应该便于人们理解和相互交流，其次才是机器可执行。可读 性好的算法有助于人对算法的理解，难懂的算法易于隐藏错误且难于调试和修 改。
3.健壮性 一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的 处理，而不会产生一些莫名其妙的输出结果。
1.5 算法与性能分析---算法的特性
算法的特性
（1）有穷性：有限步骤之内正常结束，不能形成无穷循环，并且每一步骤在可接 受的时间内完成。这里的有穷的概念并不是纯数学意义的，而是在实际应用当 中合理的、可以接受的“有边界”。

54
6
6
到一位8进制数则进栈
6
0
6
保存，转换完毕后依
所以：（3456）10 =（6613）8
次出栈则正好是转换 结果。
3.1 栈
3.1.4 栈的应用实例
例3.4
算法设计： 当N>0时，重复(1)，(2)：
（1）若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈 s的内容依次出栈，算法结束。
3.1 栈
3.1.1 栈的定义和运算
栈的定义：
栈是只能在一端进行插入和删除的线性表(运算受限)。 由此，栈具有后进先出（LIFO）的特性。
入栈(插入)
栈顶元素
an
…
a2 a1
出栈(删除) 栈顶：插入、删除的一端
栈底：栈顶的另一端
3.1 栈
3.1.1 栈的定义和运算
栈的基本运算：
(1) 初始化栈init_stack(S)： 设置栈S为空。
量top来标识栈顶位置。 类型定义如下：
#define maxsize 50 typedef struct
{ elementtype data[maxsize]; int top;
} seqstack; //定义了一个栈类型seqstack seqstack s1,*s; //定义了栈变量s1和指向栈类型的指针s
为此，可采用循环结构来解决，即将Q->data[0]做为Q>data[maxsize-1]的下一个存储位置——循环队列。
3.2 队列
3.2.2 顺序队列与循环队列
1、存储结构
Q->rear
1
Q->data: 0
maxsize-1
Q->front

不同点
10.01.2020
11
1.2 数据结构的内容
逻辑结构 存储结构 运算集合
10.01.2020
12
逻辑结构
定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。
形式化描述： Data_Structure=（D,R）其中D是数据元素的
有限集，R是D上关系的有限集。
四类基本的结构 集合结构、线性结构、树型结构、图状结构。
10.01.2020
13
集合结构
定义： 结构中的数据元素之间除了同属于
一个集合的关系外，无任何其它关系。
例如：
集合
10.01.2020
14
线ቤተ መጻሕፍቲ ባይዱ结构
定义： 结构中的数据元素之间存在着一对
一的线性关系。
例如：
线性表
10.01.2020
15
树型结构
定义： 结构中的数据元素之间存在着一对
多的层次关系。
数据结构课件
用C语言描述
西北师范大学经济管理学院
----信息管理系
10.01.2020
1
第1章 绪 论
1.1 数据结构的基本概念(定义) 1.2 数据结构的内容（研究范围） 1.3 算法设计 1.4 算法描述工具 1.5 对算法作性能评价 1.6 数据结构与C语言表示
●1.7 关于学习数据结构
100001 张爱芬 女 345．67 145．45 30．00 451．12
100002 李 林 男 445．90 185．60 45．00 586．50
100003 刘晓峰 男 345．00 130．00 25．00 450．00
100004 赵 俊 女 560．90 225．90 65．00 721．80

求解函数perm：
void perm (char *a, const int k，const int n) { // n 是数组a的元素个数，生成a[k],…,a[n-1]的全排列
int i; if (k = = n-1) { // 终止条件，输出排列
for ( i=0; i<n; i++) cout << a[i] << “ ”; // 输出包括前 // 缀，以构成整个问题的解
29
其中各语句的程序步数如下所示：
其总程序步数是2n+3。
30
例的1.6程设序r步su数m如(a下, n：)的程序步数为Trsum(n)，其各语句
= 可2+见Tr，sum当(nn-1=)。0时Trsum(0) = 2；当n > 0时Trsum(n)
31
通过反复代入可得： Trsum(n) = 2+ Trsum(n-1) = 2+2+Trsum(n-2) = 2*2+ Trsum(n-2) = 2+2+2+ Trsum(n-3) = 2*3+ Trsum(n-3) … = 2n+ Trsum(0) = 2n+2 所以rsum的程序步数为2n+2。
注意：这些定义不依赖于数据对象的具体表示，也
没有给出操作实现的过程。
10
数据抽象和封装机制的意义： （1）简化软件开发：
假设一个问题经分析将使用A、B、C三个数据 类型和协调代码求解。
（a）四位程序员，可由其中三位程序员各开发 一个数据类型，另一位程序员实现协调代码。
（b）一位程序员，数据抽象也可减少其在某一 具体时间需要考虑的范围。

依据数据集中可能出现的最坏情况估算出的时间复杂度 称为最坏时间复杂度。
五、平均时间复杂度
在假设数据集的分布是等概率的条件下，估算出的时间 复杂度称为平均时间复杂度。
例：顺序查找
2020/3/11
数据结构
14
第一章 概 论
五、空间复杂度S(n)： 算法所耗费的存储空间，仍是问题规模n的函数。
2020/3/11
2020/3/11
数据结构
25
typedef int datatype; typedef struct node {datatype data; struct node *next; } linklist; linklist *head, *p;
说明：•区分指针变量和结点变量 :p ,*p •结点的动态分配和释放
2020/3/11
数据结构
11
第一章 概 论
1.4 算法分析
一、算法评价五要素 （1）正确性 （2）执行算法所耗费的时间 （3）执行算法所耗费的空间 （4）可读性 （5）健壮性
2020/3/11
数据结构
12
第一章 概 论
二、算法的时间复杂度
•一个算法所耗费的时间:该算法中每条语句的执行时间之和。 •每条语句的执行时间：该语句的执行次数乘以该语句执行一次 所需时间。 •频度：语句重复执行的次数 •算法的时间耗费T(n)=每条语句的执行的时间
2020/3/11
数据结构
8
例：一个学生成绩表： •是一个数据结构 •每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。 •逻辑关系：线性结构 •存储结构： •表的运算：
2020/3/11
数据结构
9
第一章 概 论

for (i = 1; i <= Lb_len; i++) {
GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之 } } // purge
ListInsert(Lc, ++k, bj); ++j; }
void MergeList(List La, List Lb, List &Lc) {
// 本算法将非递减的有序表 La 和 Lb 归并为 Lc
InitList(Lc); // 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) { // La 和 Lb 均不空 } while (i<=La_len) // 若 La 不空 while (j<=Lb_len) // 若 Lb 不空
查找: 例如：顺序表
L.elem
（定位函数）
初始条件：线性表L已存在，e为给定值，
compare( )是元素判定函数。
操作结果： 返回L中第1个与e满足关系
compare( )的元素的位序。 若这样的元素不存在， 则返回值为0。
ListTraverse(L, visit( ))
（遍历线性表）
初始条件： 线性表L已存在，