基本数据结构及其运算.ppt

《基本数据结构及其运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4数组2.5树与二叉树2.6图2.1数据结构的基本概念2.1.1两个例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构2数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算目的：提高数据处理的效率(1)提高数据处理的速度(2)尽量节省计算机存储空间数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。32.1.1两个例子例无序表的顺序

2、查找35167885432933215446有序表的对分查找16212933354346547885数据元素在表中的排列顺序对查找效率是有很大影响。4例学生情况登记表以学号为顺序排列567结论：在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同的形式，以便于做该种运算，从而提高数据处理的效率。82.1.2什么是数据结构数据结构是指相互有关联的数据元素集合。现实世界中客观存在的一切个体都可以是数据元素。在实际应用中，每个数据结构中的数据元素一般具有某种共同特征。9描述一年四季的季节名春，夏，秋，冬可以作为季节的数据元素；表示数值的各个数18，11，35，23，16，…可以

3、作为数值的数据元素；表示家庭成员的各成员名父亲，儿子，女儿可以作为家庭成员的数据元素。10在数据处理领域中，通常把数据元素之间固有的关系简单地用前后件关系来描述。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。111.数据的逻辑结构是指反映数据元素之间关系的数据元素集合的表示。即带有结构的数据元素的结合。（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。12数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。数据结构可以表示成B＝（D

4、，R）其中B表示数据结构。13为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例如B＝（D，R）D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}14家庭成员数据结构B＝（D，R）D＝{父亲，儿子，女儿}R＝{(父亲，儿子），(父亲，女儿）}n维向量X＝（x1，x2，…，xn）也是一种数据结构。即X＝（D，R）D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}15m×n的矩阵是一个数据结构。即A＝（D，R）D＝{A1，A2，…，Am}R＝{

5、(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中Ai=（ai1，ai2，…，ain），i＝1，2，…，mAi＝（Di，Ri）Di＝{ai1，ai2，…，ain}Ri＝{(ai1，ai2)，(ai2，ai3)，…，(aij，ai，j＋1)，…，(ai，n－1，ain)}162.数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。172.1.3数据结构的图形表示数据集合D中

6、的每一个数据元素用中间标有元素值的方框表示（数据结点，结点）用一条有向线段从前件结点指向后件结点。一年四季数据结构的图形表示18家庭成员间辈份关系数据结的图形表示19用图形表示数据结构B＝（D，R）D＝{di

7、1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}20在数据结构中，根结点：没有前件的结点。终端结点（叶子结点）：没有后件的结点。内部结点：除了根结点与终端结点外的其他结点。数据结构的基本运算：插入和删除其他运算：查找、分类、合并、分解、复制和修改。212.1.4线性数据结构与非线

8、性数据结构线性结构：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。注意：在一个线性结构中插入或删除任何一个结点后还应是线性结构。22不是线性结构的数据结构特例如果一个数据结构不是线性结构，则称之为非线性结构。232.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用242.2.1线性表及其运算1.什么是线性表(LinearList)n维向量(x1，x2，…，xn)是一个长度为n的线性表英文小写字母表(a，b，c