算法与数据结构义二(数据结构——线性表).doc

膆第十二课数据结构——,是区分一个程序设计人员水平高低的标志,也是在高中阶段信息学竞赛中,能否获得一等奖的分水岭。蚇无论在国内还是国外,《数据结构》一直是大学计算机专业的一门专业基础课,但是,对于学习程序设计的中学生,在学习完一门程序设计语言后,为了学习更多的算法以进一步提高编程能力,《数据结构》就成了必须突破的对象。节掌握《数据结构》的目的,是充分利用数据之间的内在联系,降低数据的检索、插入、删除、更新、排序等操作的时间复杂度,从而提高算法的效率。从而,避免了大量的穷举式操作。袂什么是数据结构:蝿简而言之,就是“数据+结构”。蒇数据:数据是客观事物的符号表示。是我们在解决问题的过程中,对客观事物对象所进行的定量、定性的数值或文字表达,以便于我们输入计算机中进行模拟、计算、处理。例如:我们要对这次期中考试成绩进行总分计算、名次排序、优秀率等统计,就需要将考试结果用分数量化,并加上姓名等信息后,输入到计算机中进行处理,我们将所有输入的这些内容,成为一个“期中考试成绩数据”。芄数据元素、数据项:羀数据项:数据中补课分割的最小单元。例如:上例中的某个学生的语腿文成绩。膈数据元素:是数据的基本单位,是由若干个数据项组成。例如:上例莅中某一个学生的考试各科成绩。莃结构:数据中各数据元素之间的关系,分为逻辑结构和物理结构。薈逻辑结构:数据之间的内在关系。例如:一家人参加旅行团去某地旅游,袈在旅行车上,无论他们是否坐在一起,他们之间的父子、母子膂等内在关系依然存在。蒁物理结构:数据在计算机中的存储方式,又称为存储结构。肈 物理结构的种类:顺序存储、链式存储、索引存储、散式存储。莅顺序存储:把逻辑相邻的结点存储在物理相邻的存储单元内膄链式存储:结点之间的逻辑关系由附加指针来表示。蕿索引存储:存储结点信息的同时,建立索引表。蒇散列存储:按结点的关键字直接计算出存储地址。膅物理结构与逻辑结构之间的关系:芅逻辑结构是具体问题抽象出来的数学模型,物理结构是逻辑结构的计算机语言的实现。羂有什么样的逻辑结构,就应该选择相应的物理结构。膀选择的物理结构要方便基于逻辑结构上的数据运算。袅物理结构不等同于逻辑结构,反之,逻辑结构也不等于物理结构,因此,对数据结构的设计,不仅要进行逻辑结构的设计,也还要进行物理结构的设计。肃数据的运算:各种逻辑结构上的运算集合。常用的有:检索、插入、删除、肀更新、排序。薀数据结构的分类:薆序号膄名称蒂结构特点罿常用物理结构莆1膅集合薁无任何关系的一组数据蒈例如:互不相识的若干人乘坐同一辆公交车。肆顺序羃索引羃2袈线性表袇元素间存在严格的一对一的关系肄例如:按顺序排列的26个英文字母,B前面只能是A,后面只能是C。肂顺序芇散列薇3肅树膀元素间严格的一对多关系羁例如:磁盘中的文件夹和文件。莈顺序袃索引、散列薂4莀图肈元素间为多对多的关系羄例如:一个班级同学之间的关系。一个人可以有多个朋友,也可以是多个人的朋友。 一个线性表是n个数据元素的有限序列。线性表是最常用且最简单的一种数据结构。艿线性表的结构特点芅在数据元素的非空有限集中,螃(1)存在唯一的一个被称做“第一个”的数据元素;膁(2)存在唯一的一个被称做“最后一个”的数据元素;蚈(3)除第一个之外,集合中的每个数据元素均只有一个前驱;肅(4)除最后一个之外,集合中每个数据元素均只有一个后继。袄a1芀……肇ai-1螅ai羆ai+1蚂……薇an薆ai是ai+1的直接前驱元素,ai+1是ai的直接后继元素。螃线性表中元素的个数n定义为线性表的长度,为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素,把i称为数据元素ai在线性中的位序。螀线性表的操作:芀求长度:L:=a[0];芆清空:a[0]:=0;螄判断线性表是否为空:(a[0]=0)=true膃线性表存在且未满:a[0]<maxn蚀插入操作:将b插入到线性表中第k个的前面肇ifa[0]<maxnthen薂 begin芁fori:=a[0]downtokdoa[i+1]:=a[i];聿a[k]:=b;螇inc(a[0]);蚃 end;莀删除操作:删除线性表中第k个元素蒈fori:=ktoa[0]-1doa[i]:=a[i+1];蒇dec(a[0]);蚅取表元:去除表中第k个元素螂c:=a[k];羈按值查找:在表中查找值为b的元素,返回序号。如未找到,返回0芈functionfind(b:integer):integer;蒂begin袀 find:=1;莇 while(a[i]<>b)and(find<=a[0])doinc(find);羈 iffind>a[