(1) 线性表的定义。
零个或多个数据元素的有限序列
序列线性表中有直接后继元素,有且仅有一个直接后继,有且仅有一个直接前驱,数据元素之间的关系是一对一的关系
常用的List操作:
Operation
InitList(*L)://初始化操作,简历一个空的线性表L
ListEmpty(L)://若线性表为空,返回true,否则返回Falser
GetElme(L,i,e)://将线性表L中的第i个位置元素值返回给e
LocateElme(L,e)://在线性表中L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中的序号表示成功;否则,返回0表示失败
ListInsert(*L,i,e)://在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e)://删除线性表中L中第i个位置元素,并用e返回其值
ListLength(L)://返回线性表L的元素个数
(2) 线性
表的顺序存储结构和主要算法实现,如查找、插入和删除算法。
定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元一次存储线性表的数据元素
顺序存储方式:通过占位的形式,将内存空间占位,然后把相同数据类型的数据元素依次存放在里面,一维数组来实现顺序存储结构
#define MAXSIZE 20 /*储存空间初始分配量*/typedef int ElemType;/*ElemType类型根据实际情况而定,假设为int*/typedef struct {ElemType data[MAXSIZE]/*据存储数据元素,最大值为MAXSIZE*/int length; /*线性表当前长度*/}sqlist;
*存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
*线性表的最大存储容量:数组长度MaxSize
*线性表的当前长度:length
顺序存储结构的插入与删除:
获得元素操作:实现GetElem操作,就是将线性表中的第i个位置元素值返回
#define OK1#define ERROR 0#define TRUE 1#define FALSE typedef int status;/*status是函数的数据类型,其值是函数结构状态代码,如OK等*//*初始条件:顺序线性表L一存在,1<=i<=ListLength(L)*//*操作结构:用e返回L中第i个数据元素的值*/
线性表顺序储存结构插入操作:
线性表的插入操作是指在线性表的第i个数据元素之前插入一个新的数据元素n
插入算法的思路:
插入算法的时间复杂度:
时间复杂度的推导可知,插入操作的平均时间复杂度为O(n)。
*如果插入位置不合理,抛出异常
*如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
*从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置
*将要插入的元素填入到位置i出
*表长加1
/*初始条件:顺序线性表L以存在1<=i<=ListLength(L),*//*操作结构:在L中第i个位置之前插入新的数据元素e,L的长度加1*/status ListInsert(Sqlist *L,int i,ELemType e){int k;if(L->length==MAXSIZE)/*顺序线性表已经满*/return ERROR;if(i<=L->length)/*若插入数据位置不在表尾*/{for(k=L->length-1;k>=i-1;k--/*将要插入位置后数据元素向后移动一位*/L->data[k+1]=L->data[k];}L->data{i-1]=e;/将新元素插入*/L->length++;return OK;}
线性表顺序存储结构的删除:线性表的删除是指将表中第i(0<=i<=n-1)的数据元素删去,使长度位n的线性表变成长度为n-1的线性表,需将第i+1至第n-1个元素向前移动一个位置
删除算法的思路:
删除算法的时间复杂度:
时间复杂度的推导可知,删除操作的平均时间复杂度也为O(n)。
*如果删除位置不合理,抛出异常
*取出删除元素
*从删除元素位置开始遍历到最后一个元素位置,为别将它们都向前移动一个位置
*表长减1
线性表的顺序存储结构的特点:
优点:
*无序为表示表中元素之间的逻辑关系而增加额外的存储空间
*可以快速地存取表中任一位置的元素
缺点:
*插入和删除操作需要移动大量元素
*当线性表长度变化较大时,难以确定存储空间的容量
*造成存储空间的“碎片”