数据结构的基本概念

《数据结构的基本概念》由会员分享，可在线阅读，更多相关《数据结构的基本概念（10页珍藏版）》请在金锄头文库上搜索。

1、数据结构的基本概念数据结构是讨论计算机系统中数据的组织形式及其相互关系的一门学科,它是计算机专业的重要基础课,也是其他从事计算机软件开发工作的人需要掌握的必备知识。1、 数据结构的主要内容数据结构实际上就是研究：（1） 数据元素间的逻辑关系是什么？（2） 适宜采用什么样的存储结构（3） 有那些基本运算？怎样实现？ 也就是数据结构的三个层次：数据的逻辑结构、数据的存储结构、数据操作相关算法集合。下面举例说明：职工档案表如表7-1所示。 表7-1 职工档案表姓名性别出生年月部门职称工资婚否奖惩胡一民李 静张冬梅李清明王文明刘明伦男女女男女男01/10/6703/12/7804/12/6411/25

2、/7201/12/5412/03/76.技术科生产科生产科技术科生产科生产科.工程师助工高工工程师助工高工.165013001550165012001800.T.F.T.T.F.T.MemoMemoMemoMemoMemoMemo.这张档案表可称为一个数据结构,它是一个线性表结构,表中的每一行为一个数据元素(它是数据结构的基本单位)。（1） 表中书元素的逻辑关系是：对表中任一元素，与它相邻且在它前面的数据元素（也称为直接前驱）最多只有一个，与表中任一数据元素相邻且在它后面的数据元素（也称直接后继）也最多只有一个。表中第一个元素没有直接前驱，故称为开始 数据元素，最后一个数据元素没有直接后继，故

3、称为终点元素（例：表中李静所在元素的直接前驱为胡一民所在的数据元素；直接后继为张冬梅所在的数据元素）（2） 该表的存储方式：表中的数据元素是顺序地邻接在一片连续的单元中，而不是用指针将这些元素连接在一起。（3） 对表元素怎样进行查找、删除、插入等操作方能提高数据操作效率。2、 有关概念（1） 数据：能被计算机识别、存储和加工的客观事物的描述，称为数据。（2） 结构：是指事物间的相互关系和约束。（3） 数据元素：数据的基本单位，也称数据结点（4） 算法：是指为解决某一问题而需进行的有限操作的过程描述。3、 数据结构的具体内容（1） 数据元素逻辑关系（逻辑结构），分为两大类：A 线性结构：其逻辑特

4、征为：有且仅有一个开始元素和一个终点元素，所有数据元素最多只有一个直接前驱和 一个直接后继，线性表就是一个典型的线性结构。B 非线性结构： 其逻辑特征为：该结构中一个数据元素可能有多个直接前驱或直接后继。除最一般的图结构外， 还有树结构。图结构：对数据元素的直接前驱和直接后继的个数不作限制。 树结构：有且仅有一个根元素无直接前驱，其他元素有且仅有一个直接前驱；每个元素都可 能有多个直接后继；除根元素外， 所有的数据元素都存在一条从根元素到该元素的路径。（2） 数据元素在计算机中的存储方法（即数据的存储结构，也称物理结构），分四类：A 顺序存储方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储

5、单元里，元素间的逻辑关系由存储单元的邻接关系体现，其存储表示我们称为顺序存储结构。顺序存储方法主要应用于线性的数据结构，如线性表、数组等，但非线性数据结构也可以通过某种线性化方法来实现顺序存储。B 连接存储方法并不要求逻辑上相邻的元素在物理位置上也相邻，元素的逻辑关系是由附加的指针字段表示。它要借助于程序语言的指针类型来描述元素的存储地址，每个数据元素所占存储单元分成两部分：元素数据项和指针项。C 索引存储方法在存储元素信息的同时，还建立附加的索引表。索引表的每一项成为索引项，而地址则指示存储位置。D 散列存储方法（地址转移法）根据元素的关键字，通过某一散列函数直接计算出该元素的存储地址。同一

6、种逻辑结构采用不同的存储方法，可得到不同的存储结构，采用何种存储方法来表示相应的逻辑结构，主要是根据算法具体确定。例如：线性表是一种逻辑结构，采用顺序方法的存储表示，该结构为顺序表；若采用链接方法的存储表示，该结构为链表；若采用散列方法的存储表示，该结构为散列表。（3） 数据处理与运算对一个数据结构，一般有如下的一些基本运算：A 遍历：在数据结构里的各元素间移动，或查看所有的数据元素。B 插入：往数据结构中添加新元素。C 更新：修改数据元素的数据项（又称为字段）的值D 删除：把指定的数据元素从数据结构中去掉。E 查找：在数据接中查找满足一定条件的数据元素F 排序：在保持数据元素个数不变的前提下

7、，将数据元素按指定顺序重新排列（一般针对线性逻辑结构）由于数据运算是数据结构不可分割的部分，对于同一个数据结构，同一个基本运算，当选择的存储结构不同时,其运算的实现也会完全不同。例如，对一个线性表结构，同样进行插入操作，采用顺序存储时的算法就与采用链式存储时迥然不同。同样地，已给定了数据的逻辑结构和存储结构，若定义的运算不同，也可能导致完全不同的数据结构。例如，对线性表上的插入、删除运算仅在表的一端进行，则该线性表称之为栈；而插入限制在表的一端进行，删除限制在表的另一端进行的线性表称为队列。若线性表采用顺序表示和链表作为存储结构，则对插入和删除运算在做了上述限制之后可分别得到顺序栈和链栈、顺序

8、队列和链队列。常用的数据结构 一、线性结构线性结构是数据结构中最简单且最常用的一种数据结构。其基本特点是：数据元素有序并有限。线性结构的数据元素可排成一个线性队列： a1,a2,a3,a4an其中：a1为起始元素，an为终点元素，ai为索引号为I的数据元素。 在线性表中，除首元素外，每个元素有且仅有一个前驱；除尾元素外，每个元素有且仅有一个后继。线性结构有各种类型，如线性表、堆栈、队列、数组、串等。线性表的主要基本操作有以下几种：（1） initiate(L) 初始化 设定一个空的线性表L。（2） length(L) 求表长 返回线性表中数据元素的个数。（3） get(L,I) 取元素 返回线

9、性表中第I个数据元素。（4） locate(L,x) 定位 返回值等于x的数据元素在线性表中的序号，若不存在这样的元素，则返回0。1顺序表当线性表采用顺序存储结构时，我们称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。设顺序表中的每个元素占用K个存储单元，索引号为1的数据元素a1的内存地址为loc(a1)，则索引号为I的数据元素ai的内存地址为：loc(ai)=loc(al)+(I-l)*k显然，顺序表中每个元素的存储地址是该元素在表中索引号的线性函数。只要知道某元素在顺序

10、表中的索引号，就可以确定其在内存中的存储位置。所以说，顺序表的存储结构是一种随机存取结构。顺序表的特点： 物理上相邻的元素在逻辑上也相邻。 可随机存取。 存储密度大，空间利用率高。 对顺序可进行插入、删除等操作，但运算效率低，需要大量的数据元素移位。【例72】 在下面的顺序表中，在数据元素c、d之间插入h ,则歩骤为： abcdef 先将f、e、d按次序向后移动一个位置。 将h放入元素移动后空出的位置上。 元素总数加1。元素个数为n 时，要在第I个元素前插入新元素，需移动n-i+1个元素。在等概率情况下，插入一个新元素平均需移动(n+1)/2个元素。【例73】 在下面的顺序表中，删除元素c，则

11、步骤为：abcde 将b、e按次序向左移动一个位置。 元素个数减1。元素个数为n 时，要删除第I个元素，需移盍n-I+1个元素。在等概率情况下，删除一个元素平均需移动n/2个元素。2线性链表采用顺序表的运算效率较低，需要大量的数据元素的移位，而采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。在线性链表中每个元素结除存储自身信息外要额外存储一个指向直接后继的信息（即后继的存储位置：地址）。对链表的访问总是从链表的头部开始，根据每个结点中存储的后继结点的地址信

12、息顺链进行的。信息地址数据域 指针域 优点：插入、删除操作时移动的元素少。 缺点：所有的操作都必须顺链操作，访问不方便。 将顺序表与链表作一比较，可以看出： 顺序存储的访问是随机访问，而链式存储的访问是顺链进行的顺序访问。顺序存储下插入、删除平均移动一半元素，效率不高，而链式存储下插入、删除效率高。（3）顺序存储空间利用效率高，链式存储需额外增加地址指针的存储，增加空间耗费。3栈与队列栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。（1） 栈 栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈

13、底，当表中没有元素时称为空栈，一摞盘子的情形就是栈的生动形态。栈的特点是：后进先出（LIFOLast In,First Out）栈的基本运算有五种： SETNULL（S）（置空栈）：将栈S置成空栈。 EMPTY（S） （判空栈：这是一个布尔函数，若栈S为空栈，返回值为“真”；否则，返回值为“假”。） PUSH（S，X）（进栈，又称压栈）：在栈S的顶部插入（亦称压入）元素X。 POP（S） （出栈）：若栈S不空，则删除（亦称弹出）顶部元素X。 TOP（S） （取栈顶）：取栈顶元素，并不改变栈中内容。由于栈是运算受限的线性表，因此线性表的存储结构对栈适用。所以，栈也可以分成采用顺序结构的顺序栈和采

14、用链结构的链栈。顺序存储的顺序栈：顺序栈是利用一组地址连续的存储单元的从栈底到栈顶依次存放数据的元素。链式存储的链栈：链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。链栈中每个数据元素用一个节点表示，栈顶指针作为链栈的头指针。（2） 队列 队列是一种操作受限的线性表，它只允许在线性表的一端进行数据元素的插入操作，而在另一端才能进行数据元素的删除操作。其中，允许插入的一端称为队尾，允许删除的另一端称为队头。日常生活中的排队就是队列的实例。特点：先进先出（FIFOFirst In,First Out）。同栈的操作类似，队列的基本操作也有五种：SETNULL(Q) ( 置空队列)：将队列Q初始化为空。EMPTY(Q)(队列为空)：若队列Q为空队列，返回“真”；否则返回“假”.