2019清华大学殷仁昆教授《数据结构》C语言描述课件.ppt

李四 男 20 上海 6001 75 80 90 80
王五 男 19 长沙 6002 85 80 75 90
………… … … …… …
一个数据元素
一个初等数据项
一个组合数据项
整张表就是一个数据对象，其中每个学生的情况是其 中的一个数据元素。
第5页/共34页
2.1.2 数据结构
• 从数学意义上讲，数据结构是指数据的组织形式，由数据对象及该对象中数 据元素之间的关系组成。数据结构可描述为一个二元组 • Data-Structure=（D，R） 其中：D是数据对象，为数据元素的有限集；R是该对象中数据元素之间关 系的有限集。
• 面向对象的程序设计：将软件看成由数据对象组成 的集合，这些对象是应用问题所涉及的物理实体的 数据模型，它们之间的相互作用构成了一个软件系 统。
• 面向对象的软件设计方法优于传统的软件设计方法， 因为面向对象的软件设计方法采用了抽象数据类型
第15页/共34页
2.3.2 数据类型
• 数据类型 (data type) 是一组性质相同的值的集合以及定义在这个集合上的一组 操作的总称。
float Perimeter(void) const ;
};
Rectangle :: Rectangle(float l , float w ) : length(l) , width(w) {}
float Rectangle :: Area(void) const {return length * width ; }
• 这种意义上的数据结构称为数据的逻辑结构。除此之外，要将数据放在计算 机内进行处理，还将涉及数据的存储结构。
第6页/共34页
2.1.2 数据结构
• 涉及到计算机的数据结构概念，至今尚未有一个公 认的标准定义，但一般认为应包括以下三个方面：

查找操作
顺序查找
二分查找
链表查找
在顺序存储结构的线性表中，查找操 作需要从线性表的第一个节点开始， 逐个比较节点的数据域，直到找到目 标数据或遍历完整个线性表。时间复 杂度为O(n)。
在有序的顺序存储结构的线性表中， 查找操作可以采用二分查找算法。每 次比较目标数据与中间节点的数据域 ，如果目标数据大于中间节点，则在 右半部分继续查找；否则在左半部分 查找。时间复杂度为O(log n)。
数据结构是算法的基础。许多算法的实现需要依赖于特定的数据结构， 因此掌握常见的数据结构是编写高效算法的关键。
数据结构在解决实际问题中具有广泛应用。无论是操作系统、数据库系 统、网络通信还是人工智能等领域，数据结构都发挥着重要的作用。
数据结构的分类
根据数据的逻辑关系，数据结构可以分为线性结构和非线 性结构。线性结构如数组、链表、栈和队列等，非线性结 构如树形结构和图形结构等。
04
数据结构操作
插入操作
顺序插入
在顺序存储结构的线性表中，插入操作 需要找到插入位置的前驱节点，修改前 驱节点的指针，使其指向新节点，然后 让新节点指向后继节点。如果线性表的 第一个节点是空节点，则将新节点作为 第一个节点。
VS
链式插入
在链式存储结构的线性表中，插入操作需 要找到插入位置的前驱节点，修改前驱节 点的指针，使其指向新节点。如果线性表 的第一个节点是空节点，则将新节点作为 第一个节点。
图
01
02
03
04
图是一种非线性数据结构，由 节点和边组成，其中节点表示 数据元素，边表示节点之间的
关系。
图具有网络结构，节点之间的 关系可以是任意复杂的，包括
双向、单向、无向等。

…
an-1,0 an-1,1
…
an-1,n-1
an-1,0 an-1,1
…
…
Ann
a0,0 a1,0
a0,1 a1,1
… …
a0,n-1 a1,n-1
Ann
a0,0 a1,0
a1,1
…
…
…
an-1,n-1
对称阵
中国网页设计 xin126
下三角矩阵
第5章 数组和广义表
中国网页设计 xin126
数据结构
（C语言版）
严蔚敏、吴伟民编著 清华大学出版社 学习网站：xin126/list.asp?id=301
中国网页设计 xin126
第5章 数组和广义表
主要内容：
一、数组的定义 二、数组的表示和实现 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构
中国网页设计 xin126
第5章 数组和广义表
0 0 0 0 0 0
0 0 0 0 0 0
中国网页设计 xin126
第5章 数组和广义表
(2) 稀疏矩阵的存储： 若按常规方法进行存储，零值元素会占了很大空间 因此对于稀疏矩阵的存储通常采用以下两种方式： 三元组表和十字链表进行存储。
中国网页设计 xin126
第5章 数组和广义表
中国网页设计 xin126
第5章 数组和广义表
以行序为主序的求址公式：
假设每个数据元素占L个存储单元，则二维 数组A中任一元素aij的存储位置可由下式确定： LOC(i, j) = LOC(0, 0) + (n×i + j)*L 式中，LOC(i, j)是aij的存储位置，LOC(0, 0)是a00的存储位置，即二维数组A的起始存储 位置，也称为基地址或基址。b2是数组第二维 的长度，即数组A(m×n)中的列数n。

//判集合this与R相等
friend istream& operator >> (istream& in,
bitSet<T>& R);
//输入
friend ostream& operator << (ostream& out,
bitSet<T>& R);
//输出
private:
int setSize;
bitVector = new int [vectorSize]; //分配空间
assert (bitVector != NULL); //检查存储分配是否成功
for (int i = 0; i < vectorSize; i++) //初始化
bitVector[i] = R.bitVector[i];
//集合大小
int vecterSize;
//位数组大小
unsigned short *bitVector;
//存储集合元素的位数组
};
11
使用示例
Set s1, s2, s3, s4, s5; int index, equal; for (int k = 0; k < 10; k++) { //集合赋值
清华大学计算机系 数据结构（用面向对象方法与
C++语言描述）第二版3
殷人昆
1
数据结构电子教案
第六章 集合与字典
殷人昆 王 宏
2
第六章 集合与字典
• 集合及其表示 • 并查集与等价类 • 字典 • 跳表 • 散列
3
集合及其表示