数据结构第2章数据结构课件

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

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

3、 ai-1，ai, ai1 ，, an-1）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点数据结构第2章数据结构5 （ A, B, C, D, , Z）学号学号姓名姓名性别性别成绩成绩年龄年龄001张东张东女女7023002赵玉凤赵玉凤女女 8020003王王 泽泽男男 9019004薛薛 荃荃男男 8121005王 春男 88 8822： ：例例2 分析学生档案表是什么结构。分析学生档案表是什

4、么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。数据结构第2章数据结构6、线性表抽象数据类型、线性表抽象数据类型 它包括两个方面：它包括两个方面： 数据集合：数据集合： a0, a1, , an-1 ai的数据类型为的数据类型为DataType 操作集合操作集合： (1) InitList(List) 初始化线性表初始化线性表,

5、建一空线性表建一空线性表List (2) ListLength(L) 求当前数据元素个数求当前数据元素个数 (3) GetElement(List,i) 取线性表中第取线性表中第 i个元素（个元素（1，n） (4) ListInsert(L,i,x) 插入数据元素插入数据元素 (5)ListDelete(L,i,x) 删除数据元素删除数据元素 (6)ListGet(L,i,x) 取数据元素等取数据元素等数据结构第2章数据结构73 3、线性表的存储结构、线性表的存储结构(1)顺序存储结构顺序存储结构: :它是使用一片它是使用一片地址连续地址连续的有限内存单的有限内存单元空间存储数据元素的一种计算

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

7、邻，数据元素的逻辑次序是通过链中的指针，数据元素的逻辑次序是通过链中的指针链接实现的。链接实现的。数据结构第2章数据结构82.2 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法一一 、顺序表的存储结构顺序表的存储结构二、二、 顺序表的实现顺序表的实现三、三、 顺序表的运算效率分析顺序表的运算效率分析数据结构第2章数据结构9一、一、 顺序表的存储结构表示顺序表的存储结构表示 1、顺序表顺序表：用一组用一组地址连续地址连续的存储单元依次存储线的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储

8、。表。它通常采用静态数组实现数据元素的存储。可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1数据结构第2章数据结构10(1) 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2) 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称为称为首地址首

9、地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示2 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)+

10、(n-1)L Lb +(MaxSize-1)+(MaxSize-1)L L3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图数据结构第2章数据结构124 4、用、用C C语言描述语言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SeqList是该结构体的名字。*/数据结构第2章数据结构13设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用相邻的

11、每个数组元素用相邻的个字节个字节存储。存储器存储。存储器按字节编址，设存储数组元素按字节编址，设存储数组元素 的第一个的第一个字节的地址是字节的地址是，则，则 的第一个字节的的第一个字节的地址是多少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a0) + L *i例例1 1数据结构第2章数据结构14 char V30;void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1;

12、核心语句：核心语句：例例2用数组用数组V来存放来存放26个英文字母组成的线性表个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。数据结构第2章数据结构15void main(void) /*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/ n=26; /* n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build( );display( );void display( ) /*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ in

13、t i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 核核心心语语句：句：2)2)插入插入数据结构第2章数据结构18在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入数据结构第2章数据结构19实现步骤：实现步骤： 将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。注意：事

14、先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; j=n-1; j+ )aj-1=aj; n-;/ / 元素前移一个位置元素前移一个位置/ / 表长减表长减1 1 核心语句：核心语句：3)3)删除删除数据结构第2章数据结构20123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：数据结构第2章数据结构21例：建立一个线性表，先依次输入数据元素1，2，3，4，10

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

16、而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。时间效率分析时间效率分析:数据结构第2章数据结构23推导：推导：假定在每个元素位置上插入假定在每个元素位置上插入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种种! !数据结构第2章数据结构24同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T T（n)=(n-1)/2 n)=(n-1)/2 插入插入效率：效率：删除删除效率：效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin即插入、删除算法的平