第三讲顺序表课件

数据结构数据结构信息工程系信息工程系第二章第二章 线性表线性表线性表概述线性表概述顺序表的存储及基本操作顺序表的存储及基本操作2024/7/161滨州学院计算机科学技术系本本讲内容内容一、一、线线性表的性表的逻辑结逻辑结构特点构特点二、二、线线性表的性表的ADT定定义义三、三、线线性表的性表的顺顺序存序存储储-顺顺序表序表2信息工程系信息工程系线性结构的线性结构的基本特征基本特征为为:1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3除最后元素除最后元素之之外，均有外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。是一个数据元素的是一个数据元素的有序有序(次序次序)集集线性表线性表是一种最简单的线性结构线性结构 一、线性表的逻辑结构线性表的逻辑结构3信息工程系信息工程系线性表的基本术语线性表的基本术语w定义：定义：n（n=0）个）个具有相同特性的具有相同特性的数据元素数据元素 组成成的有限序列的有限序列；w表示：表示：L=a1,ai-1,ai,ai+1,an w ai必必须具有相同特性，即属于同一数据具有相同特性，即属于同一数据对象象 w ai-1是是ai的的直接前直接前驱，ai+1是是ai的的直接后直接后继 w 数据元素数据元素ai在在线性表中有确定的位置性表中有确定的位置i，i称称为位序位序（除有特（除有特别说明外，一般从明外，一般从1开始开始计数）数）w 线性表中数据元素的个数性表中数据元素的个数n称称为线性表的性表的长度度,n=0时，线性表称性表称为空表空表4信息工程系信息工程系（抽象数据类型定义）抽象数据类型定义）抽象数据类型抽象数据类型线性表线性表的定义如下：的定义如下：二、线性表的线性表的ADT定义定义5信息工程系信息工程系ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称称 n 为线性表的为线性表的表长表长;称称 n=0 时的线性表为时的线性表为空表空表。数据关系数据关系：R1|ai-1,aiD,i=2,.,n 设线性表为设线性表为(a1，a2,.，ai，.，an),称称 i 为为 ai 在线性表中的在线性表中的位序位序。6信息工程系信息工程系 基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List7信息工程系信息工程系GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）（求线性表中某个数据元素）8信息工程系信息工程系LocateElem(L,e,compare()初始条件：操作结果：线性表L已存在，e为给定值，compare()是元素判定函数。返回L中第中第1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）（定位函数）9信息工程系信息工程系 ListTraverse(L,visit()初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）（遍历线性表）10信息工程系信息工程系PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）（改变数据元素的值）11信息工程系信息工程系 ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)+1。在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）（插入数据元素）12信息工程系信息工程系ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，1iLengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）（删除数据元素）13信息工程系信息工程系三、线性表的顺序存储实现三、线性表的顺序存储实现1.顺序存储顺序存储(映象映象)2.顺序顺序表的表的C语言描述语言描述3.线性表线性表的基本操作在顺序表中的实现的基本操作在顺序表中的实现14信息工程系信息工程系最简单的一种顺序映象方法是：最简单的一种顺序映象方法是：令令 y y 的的存储位置和存储位置和 x x 的存储位置的存储位置相邻相邻。1.1.顺序存储顺序存储 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系。15信息工程系信息工程系 用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的起始地址线性表的起始地址称作线性表的基地址基地址线性表的顺序存储线性表的顺序存储16信息工程系信息工程系以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai)=LOC(ai-1)+C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址17信息工程系信息工程系2.顺序存储的顺序存储的 C 语言描述语言描述typedef struct SqList;/俗称俗称 顺序表顺序表#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10#define LISTINCREMENT 10 /线性表存储空间的分配增量 ElemType *elem;/存放线性表的存放线性表的数组空间基地址数组空间基地址 int length;/当前表的长度当前表的长度int listsize;/当前分配的容量当前分配的容量18信息工程系信息工程系顺序表的基本形序表的基本形态 定定义义：SqList L;l空表空表 L.length=0 可插入不可可插入不可删删除除l表表满满 L.length=L.listsize 可可删删除不可插入除不可插入 (空空间间需再分配需再分配)l表不空不表不空不满满 0L.lengthL.listsize 可可删删除可插入除可插入19信息工程系信息工程系3.线性表线性表的基本操作在顺序表中的实现的基本操作在顺序表中的实现结构结构初始化初始化查找查找插入插入元素元素删除删除元素元素20信息工程系信息工程系Status InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_INIT_ SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;21信息工程系信息工程系 int Locate(SqList L,ElemType e)/在顺序表中查询第一个在顺序表中查询第一个等于等于e e的数据元素，的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/Locate O(n)算法的算法的时间复杂度时间复杂度为：为：i=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序for(;i0&i=L.length)e=L.elemi-1;return OK;else return ERROR;23信息工程系信息工程系线性表插入线性表插入操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，插入元素时，线性表的逻辑结构线性表的逻辑结构发生什么变化发生什么变化？24信息工程系信息工程系(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加25信息工程系信息工程系需考需考虑的的问题（步（步骤）1.当前表是否已当前表是否已满？2.输入（插入位置）是否有效？入（插入位置）是否有效？3.移移动元素并插入元素并插入26信息工程系信息工程系 Status ListInsert(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1 if(L.length=L.listsize)/表满 newbase=(ElemType*)realloc (L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;if(i L.length+1)return ERROR;27信息工程系信息工程系算法时间复杂度算法时间复杂度为为:O(n)/插入位置及之后的元素右移插入位置及之后的元素右移for(j=L.length;j=i;-j)L.elemj=L.elemj-1;L.elemi-1=e;/插入插入e e+L.length;/表长增表长增1 1return OK;/ListInsert_Sq28信息工程系信息工程系线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？29信息工程系信息工程系(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 30信息工程系信息工程系Status ListDelete_Sq (SqList&L,int i,ElemType&e)if(iL.length)return ERROR;/i值不合法 e=L.elemi-1;for(j=i;j=L.length-1;j+)L.elemj-1=L.elemj;/元素前移 -L.length;return OK;/ListDelete_Sq算法时间复杂度算法时间复杂度为为:O(n)31信息工程系信息工程系顺序表操作的效率分析顺序表操作的效率分析 时间效率时间效率分析分析:算法时间主要耗费在移动元素的操作上，算法时间主要耗费在移动元素的操作上，而移动元素的个数取决于插入或删除元素的而移动元素的个数取决于插入或删除元素的位置。位置。以插入为例分析：以插入为例分析：若插入在尾元素之后，则根本无需移动若插入在尾元素之后，则根本无需移动（特别快）；（特别快）；若插入在首元素之前，则表中元素全部若插入在首元素之前，则表中元素全部要后移（特别慢）；要后移（特别慢）；32信息工程系信息工程系 推推导导：假定在每个元素位置上插入假定在每个元素位置上插入x x的可能性都的可能性都一样（即概率一样（即概率P P相同），则应当这样来计算平相同），则应当这样来计算平均执行时间：均执行时间：将所有位置的执行时间相加，然后取平均将所有位置的执行时间相加，然后取平均 若在首元素前插入，需要后移若在首元素前插入，需要后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素；个元素；若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1个元素；个元素；若在尾元素若在尾元素a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；33信息工程系信息工程系所有可能的元素移动次数合计所有可能的元素移动次数合计：0+1+n=n(n+1)/2 0+1+n=n(n+1)/2 共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种!故插入时的平均移动次数为：故插入时的平均移动次数为：n(n+1)/2 n(n+1)/2（n+1n+1）n/2 n/2 顺序表插入操作的时间复杂度为顺序表插入操作的时间复杂度为T(nT(n)=)=O(n)O(n)34信息工程系信息工程系同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为:f f(n)=(n-1)/2(n)=(n-1)/2 T(nT(n)=)=O(n)O(n)即即插入、删除算法的时间复杂度为插入、删除算法的时间复杂度为 O(n)35信息工程系信息工程系顺序表序表-算法分析算法分析算法算法插入插入删除删除基本基本操作操作移动元素移动元素移动元素移动元素平均移平均移动次数动次数时间复时间复杂度杂度O(n)O(n)最好情最好情况况在在n+1处插入，不处插入，不需移动需移动删除第删除第n个，不需移动个，不需移动36信息工程系信息工程系小结：小结：线性表顺序存储结构特点：逻辑关系上相线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；邻的两个元素在物理存储位置上也相邻；优点优点:可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大在插入或删除某一元素时，需要移动大量元素量元素;需要预先确定数据元素的最大个数。需要预先确定数据元素的最大个数。解决问题的思路：解决问题的思路：改用另一种线性存储方式改用另一种线性存储方式链式存储结构链式存储结构37信息工程系信息工程系复复习内容内容1.线性表的性表的逻辑结构特点构特点2.顺序表的存序表的存储实现3.顺序表的基本操作序表的基本操作实现及性能分析及性能分析设计以下算法，用类设计以下算法，用类C语言描述语言描述：在非递减有序的顺序表在非递减有序的顺序表L中插入元素中插入元素e，使其仍保持有序。使其仍保持有序。书面作业书面作业38信息工程系信息工程系思考思考1 编写一算法，编写一算法，从一顺序表中删除自第从一顺序表中删除自第 i 个元素开始的个元素开始的 k 个元素个元素39信息工程系信息工程系数据结构数据结构信息工程系信息工程系下节课我们将要学习：下节课我们将要学习：v顺序表的简单应用顺序表的简单应用v单链表的存储实现单链表的存储实现v单链表的基本操作实现及单链表的基本操作实现及特点特点v单链表与顺序表的区别单链表与顺序表的区别2024/7/1640滨州学院计算机科学技术系