因此,该算法的时间耗费T(n)是矩阵阶数n的函数,T(n)=O(n3)。
【课堂实践】分析并计算下面程序段执行的时间复杂度。
i=1;k=0;
while(i<=n-1)
{k+=10*i;
i++;
}
第2章线性表
线性表是最常用且最简单的一种数据结构,一个线性表是n个数据元素的有序系列,每个数据元素可以是一个数或一个符号,也可以使一页书,甚至其他更复杂的信息。
如26个字母的字母表:
(A,B,C,D…..,Z)在复杂的线性表中,一个数据元素可以由若干个数据项组成,在这种情况下,常把数据元素称为一个记录,含有大量记录的线性表又称文件。
如图
综合上述例子,可以将线性表描述为:
线性表是由n个数据元素的有限序列(a1,a2,…,an)组成的,其中每一个数据元素ai的具体含义可以按不同的情况和要求定义具体的内容,它可以是一个数、一个符号、一串文字,甚至是其他更复杂的信息。
线性表中数据元素的个数n称为线性表的长度。
2.1线性表的逻辑结构及基本运算
1.线性表简单的定义
n个数据元素的有限序列其特点是除了表头和表尾外,表中的每一个元素有且仅有唯一的前驱和唯一的后继,表头有且只有一个后继,表尾有且只有一个前驱。
线性表中的数据元素不仅可以进行访问,还可进行插入和删除。
若n=0,则表示一个空表,即没有任何数据元素的线性表;若n>0,则除a1和an外,有且仅有一个直接前驱和一个直接后继,即ai(其中1
称a1称为起始结点,an称为终端结点,i称为ai在线性表中的序号或位置。
线性表中结点的之间的关系就是上述的邻接关系,由于该关系是线性的,我们称线性表是一种线性结构。
2.线性表的基本运算
(1)线性表初始化
格式:
InitList(L)
初始条件:
线性表L不存在。
操作结果:
构造一个空的线性表L。
(2)求线性表的长度
格式:
LengthList(L)
初始条件:
线性表L存在。
操作结果:
返回线性表L中所有元素的个数。
(3)取表元
格式:
GetList(L,i)
初始条件:
线性表L存在,且1≤i≤LengthList(L)。
操作结果:
返回线性表L的第i个元素(ai)的值。
(4)按值查找
格式:
LocateList(L,x)
初始条件:
线性表L存在,x有确定的值。
操作结果:
在线性表L中查找值为x的数据元素,并返回该元素在L中的位置。
若L中有多个元素的值与x相同,则返回首次找到的元素的位置;若L中没有值为x的数据元素,返回一个特殊值(通常为-1)表示查找失败。
(5)插入操作
格式:
InsertList(L,i,x)
初始条件:
线性表L存在,i为插入位置(1≤i≤n+1,n为插入前的表长)。
操作结果:
在线性表L的第i个元素(ai)位置上插入值为x的新元素,原序号为i,i+1,…,n的数据元素的序号插入后变为i+1,i+2,…,n+1,插入后表长=原表长+1。
(6)删除操作
格式:
DeleteList(L,i)
初始条件:
线性表L存在,i(1≤i≤n)为给定的待删除元素的位置值。
操作结果:
在线性表L中删除序号为i的数据元素(ai),删除后,原序号为i+1,i+2,…,n的数据元素的序号变为i,i+1,…,n-1,删除后表长=原表长-1。
注:
以上给出的是线性表的基本运算,并不是全部运算,其它运算可用这些基本运算来实现,这些运算都是定义在逻辑结构层次上的运算,只有确定了存储结构之后,才能具体实现这些运算。
例1假设两个线性表LA,LB分别代表两个集合A和B:
求A=AUB
voidunion(List&La,List&Lb){
//将所有在线性表Lb中,但不在La中的数插入到La中
La.len=ListLength(La);
Lb.len=ListLength(Lb);//求两表的长度
for(i=1;i<=Lb.len;i++)
GetElem(Lb,i,e);//取Lb中第i个的元素复制给e
If(!
LocateElem(La,e,equal))
ListInsert(La,++La.len,e);//若其中不存在相同的,则插入
}//union
例2已知线性表la,lb中的数据元素按值非递减有序排列,现要求将la,lb归并为一个新的线性表lc且lc按值非递减。
例如la=(3,5,8,11),
Lb=(2,6,8,9,11,15,20)
则lc=(2,3,5,6,8,8,9,11,11,15,20)
分析:
由于两表都是按照一定顺序进行排列,所有设置2个指针,分别指向a、b表,先分别比较比较最初指向的两数据,比较一下大小,谁小就放入到c表中,然后数小的指针向下移动,再进行比较。
直到2表有一表结束,再将剩余的表存放到c中。
VoidMergeList(ListLa,ListLb,List&Lc){
//已知线性表la和lb中的数据元素
InitList(Lc);//初始化表c
Inti=j=1;k=0;
La.len=ListLength(La);
Lb.len=ListLength(Lb);
While((i<=La.len)&&((j<=Lb.len)){
GetElem(La,i,ai);
GetElem(Lb,j,bj);//获取数值
If(ai<=bj){
ListInsert(Lc,++k,ai);
i++;
}else{
ListInsert(Lc,++k,bj);
j++;
}//if结束
}//whie结束,其中一表结束;
While(i<=La.len){//表B数据全访问完,表a未到最后
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
While(j<=Lb.len){//表a数据全访问完,表b未到最后
GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
}
}//程序结束
分析:
上述2个算法的时间复杂度(基本操作的执行时间),例1为O(ListLength(La)*ListLength(Lb)),例2的时间复杂度为O(ListLength(La)+ListLength(Lb))。
2.2线性表的顺序存储结构
线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。
设线性表中每个元素需占用r个存储单元则
loc(ai+1)=loc(ai)+r
loc(ai)=loc(a1)+(i-1)*r
线性表的这种机内表示称做线性表的顺序存储结构或顺序映像,通常,称这种存储结构的线性表为顺序表。
只要确定了存储线性表的起始位置,线性表中任一数据元素可随机存储,所以线性表的顺序结构是一种随机存储的存储结构。
//======线性表的动态顺序存储结构
#defineLIST_INIT_SIZE100//初始分配量
#defineLISTINCREMENT10//分配增量
Typedefstruct{
Elemtype*elem;//存储空间基址
Intlength;//当前长度
Intlistsize;//当前分配的存储容量
}SqList;
Elem表示基地址,length指示线性表的当前长度。
上述的含义是为顺序表分配一个预定义大小的数据空间,并将当前的长度设为0;
StatusInitList_sq(SqList&L){
//====创建一个空的线性表
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//ElemType指数据类型,malloc新分配空间
If(!
L.elem)exit(OVERFLOW);//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
Returnok;
}//InitList_sq
在这种存储方式下,容易实现对表的遍历。
要在表的尾部插入一个新元素,也很容易。
但是要在表的中间位置插入一个新元素,就必须先将其后面的所有元素都后移一个单元,才能腾出新元素所需的位置。
StatusListInsert_sq(SqList&L,intI,ElemTypee){
//在顺序表中插入一个新元素e
If(i<1||i>L.length+1)returnError;
If(L.length>=L.listsize){//当前存储空间已满,增加分配
Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));//ElemType指数据类型,realloc再次分配,L.elem存储基地址
}//if
q=&(L.elem[i-1]);//q为插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p){
*(p+1)=*q;
}//for
*q=e;//插入e
++L.length;
Returnok;
}
执行删除运算的情形类似。
如果被删除的元素不是表中最后一个元素,则必须将它后面的所有元素前移一个位置,以填补由于删除所造成的空缺。
这两种运算的时间复杂度均为O(n)n为表的长度。
StatusListDelete_sq(SqList&L,intI,ElemType&e){
//在顺序表中插入一个新元素e
If(i<1||i>L.length+1)returnError;
p=&(L.elem[i-1]);//p为删除位置
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p){
*(p-1)=*p;
}//for
--L.length;
Returnok;
}
2.3线性表的链式存储结构
线性表顺序结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存储表中的任一元素,但是在插入删除时须移动大量元素。
而线性表的链式存储由于其不要求逻辑上相邻,因此它没有顺序存储结构的弱点,但同时也失去了顺序表可随机存取的优点。
1.单链表
线性链表的特点是用一组任意的存储单元存储线性表的元素,用指针将存储表元素的那些单元依次串联在一起。
这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或删除运算时,不再需要移动元素来腾出空间或填补空缺。
然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销。
为了将存储表元素的所有单元用指针串联起来,我们让每个单元包含一个元素域和一个指针域如图所示:
其中,存储单元由两部分构成,即数据域存储数据元素,指针域存储下一个元素所在的单元
如果表是a1,a2,…,an,那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n-1)。
含有an的那个单元中的指针是空指针null。
此外,通常我们还为每一个表设置一个表头单元header,其中的指针指向开始元素中所在的单元,但表头单元header中不含任何元素。
设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。
这一点我们在后面可以看到。
如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况,也可以简单地用一个指向表的第一个单元的指针来代替表头单元。
上述这种用指针来表示表的结构通常称为单链接表,或简称为单链表或链表。
单链表的逻辑结构如图1所示。
表示空表的单链表只有一个单元,即表头单元header,其中的指针是空指针null。
图1单链表示意图
为了便于实现表的各种运算,在单链表中位置变量的意义与用数组实现的表不同。
在单链表中位置i是一个指针,它所指向的单元是元素ai-1所在的单元,而不是元素ai所在的单元(i=2,3,…,n)。
位置1是指向表头单元header的指针。
位置End(L)是指向单链表L中最后一个单元的指针。
这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦,因为在单链表中只设置指向后继元素的指针,而没有设置指向前驱元素的指针。
单链表存储结构
TypedefstructLnode{
ElemTypedata;
StructLnode*next;//指向后继节点的指针
}Lnode,*LinkList;//线性链表的实质就是指针
基本运算
(1)ListInsert.L(L,i,e)
功能:
在表L的位置p处插入元素x,并将原来占据位置p的元素及其后面的元素都向后推移一个位置。
例如,设L为a1,a2,…,an,那么在执行Insert(x,p)后,表L变为a1,a2,…ap-1,x,ap,…,an。
若p为End(L),那么表L变为a1,a2,…,an,x。
若表L中没有位置p,则该运算无定义。
实现P为指向a节点的指针,s为指向X节点的指针:
s->next=p->next;p->next=s;
上述算法中,链表指针的修改情况见图2
图2(a)是执行Insert运算之前的情况。
我们要在指针p所指的单元之后插入一个新元素x。
图2(b)是执行Insert运算以后的结果,其中的虚线表示新的指针。
在上述Insert算法中,位置变量p指向单链表中一个合法位置,要插入的新元素x应紧接在p所指单元的后面。
指针p的合法性应在执行Insert运算之前判定。
往一个单链表中插入新元素通常在表头或表尾进行,因此p的合法性容易判定。
Insert运算所需的时间显然为O
(1)。
(2)Delete(p)
功能:
从表L中删除位置p的下一元素。
例如,当L为a1,a2,…,an时,执行Delete(p)后,L变为a1,a2,…,ap-1,ap+1,…,an。
当L中没有位置p或p=End(L)时,该运算无定义。
实现:
p.next=p.next.next;
这个过程很简单,其指针的修改如图3所示。
若要从一个表中删除一个元素x,但不知道它在表中的位置,则应先用Locate(x,L)找出指示要删除的元素的位置,然后再用Delete删除该位置指示的元素。
Delete过程所需的时间显然也为O
(1)。
2.静态链表
静态链表:
用游标指示数组单元地址的下标值,它属整数类型数组元素是记录类型,记录中包含一个表元素和一个作为游标的整数;具体说明如下:
typejid=record
data:
datatype;
next:
integer;
end;
varalist=array[0..maxsize]ofjid
游标即我们可以用游标来模拟指针,对于一个表L,我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。
。
这样,我们就可以用游标来模拟指针,实现单链表中的各种运算。
当i>1时,表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值,用p:
=alist(p).next后移。
照此,我们虽然是用数组来存储表中的元素,但在作表的插人和删除运算时,不需要移动元素,只要修改游标,从而保持了用指针实现表的优点。
因此,有时也将这种用游标实现的表称为静态链表。
3.循环链表
循环链表是另一种链式存储结构,特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
因此,可由表中任一结点出发均可找到表中其他结点。
如图6所示的是一个单链的循环链表或简称为单循环链表。
(a)非空表
(b)空表
图6单循环链表
在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。
它们仅在循环终止条件上有所不同:
前者是p或p^.next指向表头单元;后者是p或p^.next指向空(nil)。
在单链表中我们用指向表头单元的指针表示一个表L,这样就可以在O
(1)时间内找到表L中的第一个元素。
然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。
在单循环链表中,我们也可以用指向表头单元的指针表示一个表L。
但是,如果我们用指向表尾的指针表示一个表L时,我们就可以在O
(1)时间内找到表上中最后一个元素。
同时通过表尾单元中指向表头单元的指针,我们也可以在O
(1)时间内找到表L中的第一个元素。
在许多情况下,用这种表示方法可