计算机软件技术基础徐士良第2章ppt课件.ppt

《计算机软件技术基础徐士良第2章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章基本数据结构及其运算2.1数据结构的基本概念2.2线性表及其顺序存储结构2.3线性链表及其运算2.4数组2.5树与二叉树2.6图1第2章基本数据结构及其运算2.1数据结构的基本概念2.1.1两个例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构2第2章基本数据结构及其运算数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间3第2章基本数据结构及其运算2.

2、1.1两个例子例无序表的顺序查找35167885432933215446有序表的对分查找16212933354346547885数据元素在表中的排列顺序对查找效率是有很大影响。4第2章基本数据结构及其运算例学生情况登记表以学号为顺序排列5第2章基本数据结构及其运算6第2章基本数据结构及其运算7第2章基本数据结构及其运算8第2章基本数据结构及其运算结论：在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同的形式，以便于做该种运算，从而提高数据处理的效率。9第2章基本数据结构及其运算2.1.2什么是数据

3、结构数据结构是指相互有关联的数据元素集合。现实世界中客观存在的一切个体都可以是数据元素。10第2章基本数据结构及其运算描述一年四季的季节名春，夏，秋，冬可以作为季节的数据元素；表示数值的各个数18，11，35，23，16，…可以作为数值的数据元素；表示家庭成员的各成员名父亲，儿子，女儿可以作为家庭成员的数据元素。11第2章基本数据结构及其运算前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。12第2章基本数

4、据结构及其运算1.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。13第2章基本数据结构及其运算数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。数据结构可以表示成B＝（D，R）其中B表示数据结构。14第2章基本数据结构及其运算为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例如B＝（D，R）D＝{春，夏，秋，冬}R＝{

5、(春，夏)，(夏，秋)，(秋，冬)}15第2章基本数据结构及其运算家庭成员数据结构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)}16第2章基本数据结构及其运算m×n的矩阵是一个数据结构。即A＝（D，R）D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中A

6、i=（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)}17第2章基本数据结构及其运算2.数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。18第2章基本数据结构及其运算2.1.3数据结构的图形表示数据集合D中的每一个数据元素用中间

7、标有元素值的方框表示（数据结点，结点）用一条有向线段从前件结点指向后件结点。19第2章基本数据结构及其运算一年四季数据结构的图形表示20第2章基本数据结构及其运算家庭成员间辈份关系数据结的图形表示21第2章基本数据结构及其运算用图形表示数据结构B＝（D，R）D＝{di

8、1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}22第2章基本数据结构及其运算2.1.4线性数据结构与非线性数据结构线性结构：（1）有且只有一个根

9、结点；（2）每一个结点最多有一个前件，也最多有一个后件。线性结构又称线性表。23第2章基本数据结构及其运算不是线性结构的数据结构特例24第2章基本数据结构及其运算如果一个数据结构不是线性结构，则称之为非线性结构25第2章基本数据结构及其运算2.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用26第2章基本数据结构及其运算2.2.1线性表及其运算1.什么是线性表(Linea