当前课程知识点:数据结构(Data Structures) > 1. Introduction > 1.1 Introduction of Data Structure > Introduction of Data Structure
返回《数据结构(Data Structures)》慕课在线视频课程列表
返回《数据结构(Data Structures)》慕课在线视频列表
各位同学大家好
我是华南理工大学的吕建明老师
非常高兴认识你们
在接下来的一个学期中
将由我给大家讲授数据结构这门课
数据结构它是一门专业的计算机基础课程
有着非常广泛的研究意义和应用价值
那么数据结构它是一门怎样的课程呢
什么叫做数据结构
现实应用中又有哪些数据结构的例子呢
又应当如何去描述并且去实现数据结构呢
下面我将给大家一一解答
数据结构简而言之就是数据的结构
主要研究的是在计算机中
如何有效地存储和组织数据的方法
在不同的应用场景中
我们要使用不同类型的数据
从而我们也需要去采用不同的数据结构
下面我们来看一些常见的例子
第一个例子是关于数字图书馆的
当我们在图书馆主页上
输入我们想要检索的关键字的时候
会得到这样一张书目列表
列表是由一系列
具有相同结构的数据单元来构成的
比如在这个例子中
每个数据单元它对应一本书的信息
其中包括序号 题目 作者 出版社等等
这些数据单元之间
体现出一个接着一个的这样的线性的关系
针对这种类型的数据我们可以采用List
也就是线性列表这种数据结构来进行描述
我们再来看一个关于井字棋的游戏
每个棋盘的状态
可以看成是一个9×9的方阵
而我们每下一步棋就会产生一个新的状态
而在每种状态下面
又有多种可以试探下棋的方法
从而可以衍生出多种可能的棋盘状态
在这里数据元素之间
它们具有一个一对多的逻辑关系
我们通常可以采用树这种数据结构
来去刻画这种类型的数据
每个棋盘的状态就对应树上的一个结点
接下来我们来看一个更为复杂的例子
这个例子是关于社交网络的
社交网络中
每一个人都可以抽象为图中的一个结点
那么每个人都可能和其他的若干个人
建立社交关系
这种社交关系
又可以直观地看成是图中的一条连边
针对这种比较复杂的
多对多的关联关系的数据
我们可以采用图这种数据结构
来进行描述和实现
我们来总结一下
前面我们列举了三个数据结构
这将是我们后面课程的学习重点
首先第一个
是用来刻画一对一关系的线性表结构
第二个是用来去刻画一对多关系的树结构
还有就是用来描述多对多关系的图结构
最后我们来看看
如何去形式化地描述一个数据结构
一个数据结构所包含的关键元素
首先是数据它本身
也就是我们需要存储和计算的对象
另外非常重要的就是
我们需要在这些数据上面所进行的操作
这些操作体现了我们程序设计的主要目的
那么数据和操作
它们共同构成了数据结构的关键元素
在后面的课程中
我们采用抽象数据类型 ADT
来去描述一个数据结构
所谓的抽象数据类型
它是对数据结构的一种抽象描述
在不同的教科书中ADT有不同的描述形式
在我们这里采用的是C++抽象类的方式
例如前面我们提到的线性列表
我们可以通过一个List抽象类
来去描述它
在列表上的操作
可以描述成为这个类的两个抽象函数
insert的函数以及remove函数
它们操作的数据对象
可以描述成为这两个函数的输入参数
也就是这里Elem类型的数据单元
我们通过实现一个C++类
来去实现这个数据结构
以线性表作为例子
我们可以实现AList类
去继承前面我们所定义的List抽象类
并且我们要去实现前面所定义的
insert函数以及remove函数
同时我们在实践的过程中
需要去定义相关的数据成员
用来去实现数据的存储以及和记录
在后面的课程中我们将会看到
我们都会通过构建C++类的形式
来去具体地实现一个数据结构
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video