数据结构 第1讲 基础知识

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出：数据结构+算法＝程序。数据结构是程序的骨架，算法则是程序的灵魂。

        学习数据结构首先从几个概念开始：

• 数据：所有能输入到计算机中去的描述客观事物的符号。 包括文本、声音、图像、各种符号，例如扫一扫的二维码等等。

• 数据元素：数据的基本单位，也称结点或记录。

• 数据项：有独立含义的数据最小单位，也称域。

                                                 若干个数据项构成一个数据元素，数据项是不可分割的最小单位。

• 数据对象：相同特性数据元素的集合，是数据的一个子集。
• 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

                            数据结构是带"结构"的数据元素的集合，"结构"是指数据元素之间存在的关系。

• 逻辑结构和存储结构

数据结构包括逻辑结构和存储结构。逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。例如小明同学和小勇同学是表兄弟，这是他们之间的逻辑关系，他们在教室里面的位置是挨着坐，还是分开坐，对角交叉坐，这是他们的存储结构。

逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。

数据结构的逻辑结构一共有四种：

              1. 集合——数据元素间除"同属于一个集合"外，无其它关系。

         集合中的元素是离散、无序的，就像鸡圈中的小鸡一样，可以随意走动，它们之间没有什么关系，唯一的亲密关系就是在同一个鸡圈里。数据结构重点研究的是数据之间的关系，而集合中元素是离散的，没有什么关系，因此集合虽然是一种数据结构，数据结构书中却不讲，离散数学中有集合论部分。

                        2. 线性结构——一个对一个，如线性表、栈、队列

线性结构就像宝宝穿珠子，是一条线，不会发叉。有一个唯一的开始和结束，除了第一个元素外，每个元素都有唯一的前驱（前面那个），除了最后一个元素外，每个元素都有唯一的后继（后面那个）。

3. 树形结构——一个对多个，如树

树形结构就像一棵倒立的树，树根可以发出多个分支，每个每支也可以继续发出分支。树枝和树枝之间是不相交的。

4. 图形结构——多个对多个，如图

图形结构就像我们经常见到的地图，任何一个结点都可能和其它结点有关系，就像一张错综复杂的网。

存储结构：数据元素及其关系在计算机存储器中的存储方式。

存储结构可以分为四种：顺序存储，链式存储，散列存储，索引存储。很多数据结构书只说了前两种最基本的存储结构。在这里加上后两种，有必要让大家了解一下。

1. 顺序存储

          顺序存储在计算机内的存储位置是连续的，可以快速定位第几个元素的问题。中间不允许有空，所以插入、删除时需要移动大量元素。

2.链式存储

              链式存储就像一个铁链子，一环扣一环才能连在一起。每个结点除了数据域，还有一个指针域，记录下一个元素的存储地址。

3. 散列存储

           散列存储，又称哈希(hash)存储，由节点的关键码值决定节点的存储地址。用哈希函数确定数据元素的存储位置与关键码之间的对应关系。

例如：设哈希表的地址范围为0～9，哈希函数为：H（key）=key%10。输入关键字序列：（24，10，32，17，41，15，49），构造哈希表。

24%10=4：存储在下标为4的位置

10%10=0：存储在下标为0的位置

32%10=2：存储在下标为2的位置

17%10=7：存储在下标为7的位置

41%10=1：存储在下标为1的位置

15%10=5：存储在下标为5的位置

49%10=9：存储在下标为9的位置

散列存储可以通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。如果有冲突，则有多种处理冲突的方法。

4. 索引存储

         索引存储，除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项，则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。

在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引就叫做倒排索引，带有倒排索引的文件就叫做倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，这种索引存储方法是目前搜索引擎最常用的存储方法。

• 抽象数据类型

          抽象数据类型可以用以下的三元组来表示：

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

} ADT抽象数据类型名

例如：

线性表的抽象数据类型的定义：     ADT List{         数据对象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}         数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}         基本操作：         InitList(&L)          操作结果：构造一个空的线性表L         DestroyList(&L)          初始条件：线性表已存在          操作结果：销毁线性表L         ClearList(&L)          初始条件：线性表已存在          操作结果：置线性表L为空表         ListEmpty(L)          初始条件：线性表已存在          操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE         ListLenght(L)          初始条件：线性表已存在          操作结果：返回线性表L数据元素个数         GetElem(L,i,&e)          初始条件：线性表已存在（1≤i≤ListLenght(L)）          操作结果：用e返回线性表L中第i个数据元素的值         locatElem(L,e,comare())          初始条件：线性表已存在,comare()是数据元素判定函数          操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序         PriorElem(L,cur_e,&pre_e)          初始条件：线性表已存在          操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义         NextElem(L,cur_e,&)          初始条件：线性表已存在          操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义         ListInsert(&L,i,e)          初始条件：线性表已存在（1≤i≤ListLenght(L)+1）          操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1         ListDelete(&L,i,&e)          初始条件：线性表已存在（1≤i≤ListLenght(L)）          操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1         ListTraverse(L,visit())          初始条件：线性表已存在          操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败 }ADT List

对于一种数据结构, 常见的运算：插入，删除，修改，查找，排序。

        为什么要使用抽象数据类型？

信息隐蔽和数据封装，使用与实现相分离。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。在C++中可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型。

        小结：

        本节需要知道数据、数据元素、数据项、数据结构的基本概念，逻辑结构有四种：集合，线性结构，树，图，存储结构有四种：顺序存储，链式存储，散列存储，索引存储。