项目二线性表-顺序存储

项目二线性表项目二线性表任务一：线性表的定义和基本运算任务二：线性表的顺序存储结构任务三：线性表的链式存储结构线性表的逻辑结构、存储结构，及它们之间的相互关系；定义与之相适应的运算；设计相应的算法；分析算法的效率。任务一线性表的定义和基本操作一、线性表线性表是n个数据元素的有限序列，记为：L=(a1，a2，……，an)数据元素之间的关系是：ai-1领先于ai

，ai领先于ai+1

。称ai-1是ai的直接前驱元素；ai+1是ai的直接后继元素。除a1外，每个元素有且仅有一个直接前驱元素；除an外，每个元素有且仅有一个直接后继元素。线性表中数据元素的个数n（n>=0）称为线性表的长度，当n=0，称为空表。任务一线性表的定义和基本操作抽象数据类型线性表的定义：ADTList{

数据对象：D={ai|ai∈ElemSet,i=1,2,……n,n>=0}{称n为线性表的表长；

称n=0时的线性表为空表。}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}{设线性表为(a1，a2，……，an)，称i为ai在线性表中的位序}

基本操作：{结构初始化}

InitList(L)

操作结果：构造一个空的线性表

{销毁结构}

DestroyList(L)

初始条件：线性表已存在

操作结果：构造一个空的线性表任务一线性表的定义和基本操作抽象数据类型线性表的定义：{引用型操作}ListEmpty(L)ListLength(L)PriorElem(L,e)NextElem(L,e)GetElem(L,i)Locate(L,e)ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength（L）初始条件：线性表L已存在。操作结果：返回L中元素的个数。PriorElem（L,e）初始条件：线性表L已存在。操作结果：若e是L的元素，但不是第一个，则返回它的前驱，否则操作失败。NextElem（L,e）初始条件：线性表L已存在。操作结果：若e是L的元素，但不是最后一个，则返回e的后继，否则操作失败。GetElem（L，i）初始条件：线性表L已存在，1<=i<=LengthList(L)操作结果：返回L中第i个元素的值Locate（L，e）初始条件：线性表L已存在。操作结果：返回L中e的位序。若这样的元素不存在，则返回值0任务一线性表的定义和基本操作抽象数据类型线性表的定义：{加工型操作}ClearList(L)InsertList(L，i,e)DeleteList(L，i,e)ClearList（L）初始条件：线性表L已存在。操作结果：将L重置为空表。InsertList（L，i，e）初始条件：线性表L已存在。1<=i<=LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。DeleteList（L，i，e）初始条件：线性表L已存在。1<=i<=LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。利用上述定义的线性表，可以完成其他更复杂的操作。任务一线性表的定义和基本操作例2-1求两个集合的并集，即A=A∪B分析：设A、B分别由两个线性表LA、LB表示，要求将LB中存在而LA中不存在的数据元素插入到表LA中任务一线性表的定义和基本操作算法描述如下（类C）：voidUnion(Liner_List

LA,Liner_ListLB){LA.len=ListLength(LA);

LB.len=ListLength(LB);//求线性表的长度

for(i=1;i<=LB.len;i++){//LB中第i个元素在LA中不存在，则将其插入到LA中

if(!Locate(LA,GetElem(LB,i)))

InsertList(&LA,++LA.len,GetElem(LB,i));}}算法思想：依次从LB中取出一个元素；判断LA中是否存在；若不存在，则插入到LA中。任务一线性表的定义和基本操作例2-2归并两个有序的线性表LA和LB为一个新的线性表算法思想：（1）初始化：置LC为空表，设置变量i，j，初值为1，分别指向LA和LB的第一个元素，k表示LC的长度，初值为0

。（2）当i<=LENGTH(LA)ANDJ<=LENGTH(LB)时，判断：若i所指的元素<=j所指的元素，则将i所指的元素插入在LC的k+1，并且i，k的值分别加1；否则，将j所指的元素插入在LC的k+1前，并且j，k的值分别加1（3）重复（2）直到某个表的元素插入完毕。（4）将未插入完的表的余下的元素，依次插入在LC后。任务一线性表的定义和基本操作算法设计如下（类C）：voidMerge_List(Liner_List

LA,Liner_List

LB,Liner_ListLC){LA.len=ListLength(LA);

LB.len=ListLength(LB);//求线性表的长度

InitList(LC);//初始化线性表LC

while(i<=LA.len&&j<=LB.len)//如果LA中第i个元素小于LB中//第j个元素,把LA中第i个元素插入到LC中，否则将LB中第j个元素插入到

if(GetElem(LA,i)<=GetElem(LB,j)){InsertList(LC,k+1,GetElem(LA,i));

k++;i++;}else{InsertList(LC,k+1,GetElem(LB,j));

k++;j++;}

while(i<=LA.len){InsertList(LC,k+1,GetElem(LA,i));

k++;i++;}

while(j<=LB.len){InsertList(LC,k+1,GetElem(LB,j));

k++;j++;}}任务一线性表的定义和基本操作算法分析：该算法中包含了三个WHILE语句，其中，第一个处理了某一张表的全部元素和另一张表的部分元素；后两个WHILE循环只可能有一个执行，用来完成将未归并到LC中的余下部分元素插入到LC中，“插入”是估量归并算法时间复杂度的基本操作，其语句频度为：

ListLength(LA）+ListLength(LB）该算法的时间复杂度为：

O（ListLength(LA）+ListLength(LB）），若LA和LB的元素个数为同数量级n，则该算法的时间复杂度为O（n）任务二线性表的顺序存储结构一、顺序存储结构

用一组地址连续的存储单元依次存储线性表的元素。设线性表的每个元素占用k个存储单元，则第i个元素ai的存储位置为：Loc(ai)=Loc（a1）+（i-1）*k,其中，Loc（ai）为线性表的起止线性表的顺序存储结构是一种随机存取的存储结构。

若已知线性表的起始位置（基地址）和表中每个数据元素所占存储单元的大小k，就可以计算出线性表中任意一个数据元素的存储地址，这种存取元素的方法称为随机存取法任务二线性表的顺序存储结构任务二线性表的顺序存储结构线性表顺序存储结构的定义为：#defineMAXSIZE100//线性表的最大长度typedef

struct

{

ElemType

elem[MAXSIZE];//存储线性表中数据元素的数组

intlength;//线性表的当前长度}SeqList;typedef

struct

{

ElemType*elem;//线性表中数据元素的基地址

intlength;//线性表的当前长度

int

listsize；//当前为线性表分配的存储容量}SeqList;定义一个顺序表的方法有两种：方法一：SeqListL，表示将L定义为SeqList类型的变量；方法二：SeqList*L，表示将L定义为指向SeqList类型的指针。对表中数据元素进行操作应使用L.elem[i]

对表中数据元素进行操作应使用L->elem[i]（（*L）.elem[i]）

任务二线性表的顺序存储结构任务二线性表的顺序存储结构顺序表的优缺点优点：随机存取元素、简单直观缺点：插入和删除结点困难、扩展不灵活、容易造成浪费二、顺序表的基本操作1．初始化顺序表2．插入数据元素3．删除数据元素4．查找数据元素任务二线性表的顺序存储结构任务二线性表的顺序存储结构1、初始化顺序表StatusInitList(SeqList*L){//初始化顺序表

L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));//分配存储空间If(!L->elem)returnOVERFLOW;//存储空间分配失败L->length=0;//当前线性表长度为0L->listsize=MAXSIZE;//初始化存储容量returnTRUE;}算法思想：给顺序表分配存储空间，elem指针指向该顺序表；判断分配空间是否成功；设置顺序表的长度为0；初始化存储容量；任务二线性表的顺序存储结构2、插入和删除操作(1)插入数据元素InsertList（L，i，e）插入前：L=(a1，a2，…ai-1，ai…，an)插入后：L=(a1，a2，…ai-1，e，ai…，an)为了在顺序表中第i（1≤i≤n）个位置插入数据元素e，需先将第i个至第n个元素（共n－i＋1个）依次向后移动一个位置，再将e插入到第i个位置。若i＝n＋1，则只需在线性表的末尾插入e即可。任务二线性表的顺序存储结构算法描述如下：StatusInsertList(SeqList*L,int

i,ElemTypee){//在顺序表L中第i个位置插入数据元素e，其中1<=i<=n+1

intj；

if（i<1||i>L->length+1）

returnFALSE;//i值不合法，出错处理

if(L->length=L.listsize)returnOVERFLOW;//当前存储空间满

for(j=L->length-1;j>=i-1;j--)L->elem[j+1]=L-elem[j];//第i个位置之后的元素依次向后移L->elem[i-1]=e;//将e插入到第i个位置L->length++;//表长增1returnTRUE;}算法思想：进行合法性检查，1<=i<=n+1；判断线性表是否已满；将第n个至第i个元素逐一后移一个单元；在第i个位置处插入新元素；将表的长度加1.任务二线性表的顺序存储结构插入算法时间复杂度分析：最坏情况是在第1个元素前插入（i=1），此时要后移n个元素，因此T（n）=O(n)任务二线性表的顺序存储结构(2)删除运算DeleteList（L,i）删除前：L=(a1，a2，…ai-1，ai,，ai+1…，an)插入后：L=(a1，a2，…ai-1，ai+1，…，an)删除顺序表中第i（1≤i≤n）个数据元素，需将第i＋1个至第n个元素（共n－i个）依次向前移动一个位置。顺序表进行删除操作的前后，其数据元素在存储空间中的位置变化如图2-3所示。任务二线性表的顺序存储结构算法描述如下：StatusDeleteList(SeqList*L,inti){//在顺序表L中删除第i个数据元素e，其中1<=i<=n

intj；

if（i<1||i>L->length）

returnFALSE;//i值不合法，出错处理

for(j=i;j<L->length;j++)L->elem[j-1]=L->elem[j];//第i个位置之后的元素依次向前移L->length--;//表长减1returnTRUE;}算法思想：进行合法性检查，1<=i<=n；将第i+1个至第n个元素逐一向前移一个位置；将表的长度减1.任务二线性表的顺序存储结构删除算法时间复杂度分析：最坏情况是删除第1个元素，此时要前移n-1个元素，因此T（n）=O(n)任务二线性表的顺序存储结构(3)查找运算Locate（L,e）在顺序表中查找值为e的数据元素，并返回该元素在表中的位置。方法：从第一个数据元素开始，依次将表中的元素与e进行比较，若相等，则返回该元素在表中的位置；否则，查找失败。任务二线性表的顺序存储结构顺序表查找算法描述如下：int

Locate(SeqList*L,ElemTypee){//在顺序表L中查找值为e的数据元素查找成功，返回该元素位置，否则返回0

intj；for(j=0;j<L->length;j++)if（L->elem[j]==e）

returnj+1;return0;}算法思想：将第0个至第n-1个元素逐一与元素e比较，如值相等，返回该元素在表中位置，否则返回0；例3一个线性表L中的数据元素按升序排列，编写一个算法，实现在线性表中插入一个数据元素item，使得线性表仍然保持升序排列。算法设计如下：voidInsert(SqListL,ElemTypeitem){int