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

《算法与数据结构讲义二(数据结构——线性表)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十二课数据结构——线性表12.0数据结构概述12.1线性表12.2栈12.3队列12.4串12.0数据结构概述是否掌握数据结构，是区分一个程序设计人员水平高低的标志，也是在高中阶段信息学竞赛中，能否获得一等奖的分水岭。无论在国内还是国外，《数据结构》一直是大学计算机专业的一门专业基础课，但是，对于学习程序设计的中学生，在学习完一门程序设计语言后，为了学习更多的算法以进一步提高编程能力，《数据结构》就成了必须突破的对象。掌握《数据结构》的目的，是充分利用数据之间的内在联系，降低数据的检索、插入、删除、更新

2、、排序等操作的时间复杂度，从而提高算法的效率。从而，避免了大量的穷举式操作。一、什么是数据结构：简而言之，就是“数据+结构”。1、数据：数据是客观事物的符号表示。是我们在解决问题的过程中，对客观事物对象所进行的定量、定性的数值或文字表达，以便于我们输入计算机中进行模拟、计算、处理。例如：我们要对这次期中考试成绩进行总分计算、名次排序、优秀率等统计，就需要将考试结果用分数量化，并加上姓名等信息后，输入到计算机中进行处理，我们将所有输入的这些内容，成为一个“期中考试成绩数据”。数据元素、数据项：数据项：数据中

3、补课分割的最小单元。例如：上例中的某个学生的语文成绩。数据元素：是数据的基本单位，是由若干个数据项组成。例如：上例中某一个学生的考试各科成绩。2、结构：数据中各数据元素之间的关系，分为逻辑结构和物理结构。逻辑结构：数据之间的内在关系。例如：一家人参加旅行团去某地旅游，在旅行车上，无论他们是否坐在一起，他们之间的父子、母子等内在关系依然存在。物理结构：数据在计算机中的存储方式，又称为存储结构。物理结构的种类：顺序存储、链式存储、索引存储、散式存储。顺序存储：把逻辑相邻的结点存储在物理相邻的存储单元内链式存储

4、：结点之间的逻辑关系由附加指针来表示。索引存储：存储结点信息的同时，建立索引表。散列存储：按结点的关键字直接计算出存储地址。物理结构与逻辑结构之间的关系：（1）逻辑结构是具体问题抽象出来的数学模型，物理结构是逻辑结构的计算机语言的实现。（2）有什么样的逻辑结构，就应该选择相应的物理结构。（3）选择的物理结构要方便基于逻辑结构上的数据运算。（1）物理结构不等同于逻辑结构，反之，逻辑结构也不等于物理结构，因此，对数据结构的设计，不仅要进行逻辑结构的设计，也还要进行物理结构的设计。数据的运算：各种逻辑结构上的运

5、算集合。常用的有：检索、插入、删除、更新、排序。一、数据结构的分类：序号名称结构特点常用物理结构1集合无任何关系的一组数据例如：互不相识的若干人乘坐同一辆公交车。顺序索引2线性表元素间存在严格的一对一的关系例如：按顺序排列的26个英文字母，B前面只能是A，后面只能是C。顺序散列3树元素间严格的一对多关系例如：磁盘中的文件夹和文件。顺序索引、散列4图元素间为多对多的关系例如：一个班级同学之间的关系。一个人可以有多个朋友，也可以是多个人的朋友。顺序索引12.1线性表一个线性表是n个数据元素的有限序列。线性表是

6、最常用且最简单的一种数据结构。一、线性表的结构特点在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。a1……ai-1aiai+1……anai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数

7、据元素ai在线性中的位序。二、线性表的操作：1、求长度：L:=a[0];2、清空：a[0]:=0;3、判断线性表是否为空：(a[0]=0)=true4、线性表存在且未满：a[0]

8、除表中第k个元素c:=a[k];2、按值查找：在表中查找值为b的元素，返回序号。如未找到，返回0functionfind(b:integer):integer;beginfind:=1;while(a[i]<>b)and(find<=a[0])doinc(find);iffind>a[0]thenfind:=0;end;一、线性表应用实例：1、顺序表倒置：算法思路：把第一个元素与最后一个元素交换，把第二个元素与倒数第二个元素交