软件技术基础_数据结构课件.ppt

《软件技术基础_数据结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第四章1内容4．1概述4．2线性表4．3特殊线性表4．4树4．5图4．6查找4．7排序24.1数据结构概述4.1.1数据结构的定义数据(data)——是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。数据元素(dataelement)——是数据的基本单位。如数据集合N={1，2，3，4，5}中整数1至5均为数据元素。数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。数据元素有时也称结点或记录。3

2、数据元素的表示方法：1）对于单个的数字或字符，用简单数据就可以表示，如整数型，实数型或字符型等；2）对于组合型的数据元素，用记录（或结构体）来表示。例如学生信息记录描述为：typedefstructstu{charName;/*学生姓名*/charNumber;/*学生学号*/charClass;/*学生班级*/}STU;4数据结构(datastructure)——是指同一数据对象中各数据元素间存在的关系，包括：数据的逻辑结构数据的物理结构数据的运算数据结构与算法——程序＝算法＋数据结构数据对

3、象(dataobject)——性质相同的数据元素的集合。如大写字母字符的数据对象是集合：C={‘A’，’B’，...，’Z’}。51.逻辑结构：研究数据元素及其关系的数学特性，即数据元素间的逻辑关系。二元组S=（D，R）D－－数据元素的集合R－－D内数据元素之间关系的集合。4.1.2数据的逻辑结构和物理结构6三类基本逻辑结构线性结构（一对一）树形结构（一对多）图形结构（多对多）举例7例1：linearity=(D,R)，其中D＝{1,2,3,4,5,6,7,8,9,10}R={r}r={<7,2>,<2

4、,1>,<1,6>,<6,10>,<10,8>,<8,4>,<4,5>,<5,3>,<3,9>}例2：Tree=(D,R)，其中D＝{1,2,3,4,5,6,7,8,9,10}R={r}r={<1,2>,<2,3>,<2,4>,<1,5>,<5,6>,<1,7>,<7,8>,<7,9>,<7,10>}8例3：Graph=(D,R)，其中D＝{1,2,3,4,5};R={r}r={<1,2>,<1,4>,<1,3>,<3,5>,<2,3>}92.物理结构(存储结构)：是数据结构（包括数据元素及数据元素之间

5、的关系）在计算机存储器上的存储表示，即具体实现。常用的两种基本存储结构：顺序存储结构（借助相对位置）链式存储结构（借助指示元素位置的指针）※逻辑结构与存储结构的关系※－算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。－同一种逻辑结构可采用不同的存储结构。103.数据的运算查找排序插入删除修改114.2线性表4.2.1线性表的定义和运算线性表的概念线性表的逻辑结构是n个数据元素的有限序列:L=(a1,a2,...，an)L为线性表，ai(i=1,...，n)是属于某数据对

6、象的元素，n为线性表的长度(n≥0)，n=0的表称为空表。2.线性表的定义L=（D，R）123.线性表的结构特点表中的数据元素为同一数据类型数据元素之间是线性关系，即在逻辑上是有序的每个元素有且只有一个前趋元素(第一个元素除外)，每个元素有且只有一个后继元素(最后一个元素除外)4.2.1线性表的定义和运算4.2线性表13有序表与无序表的概念若线性表中的数据元素相互之间可以比较，且ai≥ai+1，i=2，3，...，n（或ai≤ai+1，i=1，2，...，n-1），则称该线性表为有序表，否则称为无序表。

7、线性表的基本运算清表、插入、删除、查找、排序、修改、求表长等。(按位置、按值)4.2.1线性表的定义和运算4.2线性表144.2.2线性表的存储结构一、顺序存储结构（顺序表）用一组地址连续的存储单元存放线性表的数据元素该结构用高级语言中的一维数组类型表示。例如：可用一维数组A[n+1]来存储线性表：（a1,a2,...，an）。对应数组中A[1]～A[n]。数据元素地址计算：addr(ai)=addr(a1)+(i-1)*L其中L为每个数据元素占据的内存空间大小（一般以字节计算）。4.2线性表15

8、例：a1a2a3a4a5a6…2000H2001H……2005Haddr(a4)=addr(a1)+(i-1)×L=2000H+(4-1)×1=2003H16二、线性表顺序存储结构的算法1.插入1)概念：有线性表(a1,a2,...，an)，长度为n，要在第i-1与第i个元素之间插入一个新元素。使得线性表变为：(a1,a2,...ai-1,x,ai,...,an),线性表长度为n+1。2)插入过程：将ai至an依次后移一个位置(共移动n-i