第2章线性表1(顺序表)

1、1线性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。接后继。 可表示为：（可表示为：（a a1 1 , a, a2 2 , , a, , an n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继

2、。线性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1)232.1 线性表的基本概念线性表的基本概念、线性表、线性表它是一种最简单的线性结构。是一种可以在任它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由意位置进行插入和删除数据元素操作的，由n（n0)个相同类型数据元素个相同类型数据元素a0, a1, , an-1组成的线组成的线性结构。性结构。4（a0, a1, ai-1，ai, ai1 ，, an-1）n=0时称为时称为数据元素数据元素线性起点线

3、性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点5 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男 192003级电信级电信0301班班012003010704赵玉凤赵玉凤女女 182003级电信级电信0302班班012003010813王王 泽泽男男 192003级电信级电信0303班班012003010906薛薛 荃荃男男 192003级电信级电信0304班班0120

4、03011018王 春男 19 192003级电信级电信0305班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。6.线性表抽象数据类型线性表抽象数据类型 它包括两个方面：它包括两个方面： 数据集合：数据集合： a0, a1, , an-1 ai的数据类型为的数

5、据类型为DataType 操作集合操作集合：(1)ListInitiate(L) 初始化线性表初始化线性表 (2)ListInsert(L,i,x) 插入数据元素插入数据元素 (3)ListLength(L) 求当前数据元素个数求当前数据元素个数 (4)ListDelete(L,i,x) 删除数据元素删除数据元素 (5)ListGet(L,i,x) 取数据元素等取数据元素等73.3.线性表的存储结构线性表的存储结构(1)顺序存储结构顺序存储结构: :它是使用一片它是使用一片地址连续地址连续的有限内存的有限内存单元空间存储数据元素的一种计算机存储数据方法。单元空间存储数据元素的一种计算机存储数据

6、方法。特点：特点：( (任意两个在逻辑上相邻的数据元素在物理位置任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻上也必然相邻) )逻辑上相邻的元素，物理上也相邻。逻辑上相邻的元素，物理上也相邻。(2)(2)链式存储结构链式存储结构: :它是把数据元素和指针定义成一个它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。的一种计算机存储数据方法。特点：特点：任意两个在任意两个在逻辑上相邻逻辑上相邻的数据元素在的数据元素在物理上不物理上不一定相邻一定相邻，数据元素的逻辑次序是通过链中的指针，数据元素的逻辑

7、次序是通过链中的指针链接实现的。链接实现的。82.2 线性表的顺序表示和实现线性表的顺序表示和实现一一 、 顺序表的存储结构顺序表的存储结构二、二、 顺序表的实现顺序表的实现三、三、 顺序表的运算效率分析顺序表的运算效率分析9一、一、 顺序表的存储结构表示顺序表的存储结构表示 1、顺序表顺序表：用一组用一组地址连续地址连续的存储单元依次存储线的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。表。它通常采用静态数组实现数据元素的存储。可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C

8、C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-110(1) 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2) 若已知表中首元素在存储器中的位置，则其他若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出元素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数

9、据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示2 2、线性表顺序存储特点：、线性表顺序存储特点：11a a0 0a a1 1a ai ia ai+1i+1a an-1n-1 地址地址 内容内容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空闲区空闲区i+1i+1Lb=LOC(a0)b + + L Lb +i+iL Lb +(n-1)+(n-1)L Lb +(MaxSize-1)+(MaxSize-1)L L3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图124 4、用、用C

10、 C语言描述语言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SeqList是该结构体的名字。*/13设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储器存储。存储器按字节编址，设存储数组元素按字节编址，设存储数组元素 的第一个的第一个字节的地址是字节的地址是，则，则 的第一个字节的的第一个字节的地址是多

11、少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a0) + L *i例例1 114二、二、 顺序表的实现（或操作）顺序表的实现（或操作）数据结构的基本运算：数据结构的基本运算： 修改、插入、删除、修改、插入、删除、查找、排序查找、排序1) 1) 修改修改 通过数组的下标便可访问某个特定元素并通过数组的下标便可访问某个特定元素并修改之。修改之。核心语句核心语句: : Vi=x;显然，顺序表修改操作的时间效率是显然，顺序表修改操作的时间效率是 O(1)15在线性表（在线性表（n n个元素）的第个元素

12、）的第i i个位置个位置前前插入一个元素插入一个元素实现步骤：实现步骤： 将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置； 将要插入的元素写到第将要插入的元素写到第i个位置；个位置； 表长加表长加1。事先应判断事先应判断: 插入位置插入位置i 是否合法是否合法?表是否已满表是否已满? 2)2)插入插入16int ListInsert(SeqList *L,int i,DataType x) int j; if(L-size=MaxSize) printf(“顺序表已满无法插入顺序表已满无法插入!n”); return 0; else if(iL-size) print

13、f(“参数参数i不合法不合法!n”); return 0; else for (j=L-size; ji; j) L-listj=L-listj-1 ; L-listi=x; L-size+; return 1; 插插入入数数据据元元素素17在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入18实现步骤：实现步骤：n将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；n表长减表长减1。注意：事先需要判断，注意：事先

14、需要判断，删除位置删除位置i 是否合法是否合法?删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; jsize-1; j+ ) L-listj-1= L-listj ;L-size-;return 1;/ / 元素前移一个位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：3)3)删除删除19123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：20例：建立一个线性表，先依次输入数据元素1，2，3，4，10，然后删除

15、，最后依次显示当前线性表中的数据元素。假设该线性的数据元素个数最坏情况下不会超过100个。实现方法：1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中，通过 #include “SeqList.h” ）21三、三、 顺序表操作的效率分析顺序表操作的效率分析n算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动移动元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除

16、元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。时间效率分析时间效率分析:22推导：推导：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都一样（即的可能性都一样（即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：若在首结点前插入，需要移动的元素最多，后

17、移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1n-1; ;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计所有可能的元素移动次数合计： 0+1+n0+1+n = n(n+1)/2 = n(n+1)/2故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种! !23同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 插入效率：插入效率：删除效率：删除效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材有对执行效率的推导：有对执行效率的推导：即插入、删除算法的平均即插入、删除算法的