资源描述：
《第2章 基本数据结构及其运算ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.1数据结构的基本概念2.2线性表及其顺序存储结构第2章基本数据结构及其运算2.1数据结构的基本概念2.1.1例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构数据结构三个方面的问题：①数据的逻辑结构②数据的存储结构③对各种数据结构进行的运算目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间2.1.1两个例子例1：分别在有序表和无序表中查找无序表的顺序查找,查找431871045269有序表的对分查找,查找212345678910数据元素在
2、表中的排列顺序对查找效率是有很大影响例2：学生情况登记表以学号为顺序排列以学生成绩为参考分表组织排列结论在对数据进行处理时,可以根据所做的运算不同,将数据组织成不同的形式,以便于做该种运算,从而提高数据处理的效率2.1.2什么是数据结构数据结构是指相互有关联的数据元素集合1.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构①表示数据元素的信息;②表示各数据元素之间的前后件关系一般来说,数据元素之间的任何关系都可以用前后件关系来描述数据的逻辑结构有两个要素：数据元素的集合D;反映D中各数据元素之间
3、的前后件关系R数据结构可以表示成B=（D,R）其中B表示数据结构为了反映D中各数据元素之间的前后件关系,一般用二元组来表示数据结构举例设a与b是D中的两个数据,则二元组 （a,b） 表示a是b的前件,b是a的后件例如 B=（D,R） D={春,夏,秋,冬} R={(春,夏),(夏,秋),(秋,冬)}2.数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构,其数据处理的效率是不同的数据集合D中的每一个数据元素用中间标
4、有元素值的方框表示（数据结点）用一条有向线段从前件结点指向后件结点2.1.3数据结构的图形表示用图形表示数据结构B=（D,R）D={di
5、1≤i≤7}={d1,d2,d3,d4,d5,d6,d7}R={(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)}d3d1d7d6d4d2d5线性结构：线性结构又称线性表①有且只有一个根结点;②每一个结点最多有一个前件,也最多有一个后件说明：在一个线性结构中插入和删除任何一个结点后还应是线性结构2.1.4线性数据结构与非线性数据结构春
6、夏秋冬如果一个数据结构不是线性结构,则称之为非线性结构父亲儿子女儿数据结构从逻辑上分为四类：⑴集合：数据元素之间就是“属于同一个集合”；⑵线性结构：数据元素之间存在着一对一的线性关系；⑶树结构：数据元素之间存在着一对多的层次关系；⑷图结构：数据元素之间存在着多对多的任意关系。2.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用2.2.1线性表及其运算1.什么是线性表(LinearList)n维向量(x1,x2,…,xn)是一个长度为n的线性表学生情况登记表是
7、一个复杂的线性表由若干数据项组成的数据元素称为记录(record)由多个记录构成的线性表又称为文件(file)线性表是由n(n≥0)个数据元素a1,a2,…,an组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即线性表或是一个空表,或可以表示为 (a1,a2,…,ai,…,an) 其中ai(i=1,2,…,n)是属于数据对象的元素,通常也称其为线性表中的一个结点线性表的定义非空线性表结构特征：(1)有且只有一个根结点a1,它无前件;(2)有
8、且只有一个终端结点an,它无后件;(3)除根结点与终端结点外,其它所有结点有且只有一个前件,也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时,称为空表2.线性表的顺序存储结构线性表的顺序存储结构基本特点：①线性表中所有元素所占的存储空间是连续的②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的长度为n的线性表(a1,a2,…,ai,…,an)顺序存储结构线性表中第i个元素ai在计算机存储空间中的存储地址为：ADR(ai)=ADR(a1)+(i-1)k长度为8的线性表(29,1
9、8,56,63,35,24,31,47)存储在长度为12的存储空间中。存储空间的长度要定义的比线性表的实际长度大，以便对线性表进行各种运算，特别是插入运算。建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间）#include"stdlib.h"voidinitsl(v,m,n)/*初始化顺序表*/ET*v;intm,*n;/*v返回顺序表空间的首地址,ET表示元素的数据类型,m为顺序表的空间容量（字节数）,n返回线性表的长度*/{v=malloc(m*sizeo
