数据结构线性表课件

第二章数组2.1线性表2.2顺序表2.3单链表2.4线性链表的其他变形2.5单链表的应用：多项式及其运算2.1线性表线性表(LinearList)

：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)()这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例子例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓名学号性别年龄

健康情况王小林790631

男18

健康陈红790632

女20

一般刘建平790633

男21

健康张立立790634

男17

神经衰弱

……..

……..…….…….

…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1

线性表的逻辑结构：线性结构数据的运算是定义在逻辑结构上的。运算的具体实现则是在（物理）存储结构上进行的。线性表只能“顺序存取”数组与线性表的异同：数组id与位置的对应。线性表是线性排列的“对象”。线性表的特点线性表上实现的基本操作1.构造2.随机访问：取第i个位置上的元素。3.插入：线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x。4.删除：线性表的删除运算是指将表的第i(1≦i≦n)结点删除。5.查找：寻找具有特定数据的节点。6.归并、复制、计数、排序。线性表的实现顺序表：用顺序方法存储的线性表叫顺序表。顺序存储： 用一组连续的存储空间，依

次存储线性表的元素。特点： 其逻辑结构与物理结构（顺 序结构相同。注意:

顺序表是顺序存储，随机存 取。实现顺序存储一种最好的方式是用数组。[例]顺序表{a0,a1,a2,…,an-1}地址bb+cb+2cb+3cb+icb+(n-1)C元素a0a1a2a3…an-1空闲区位置0123…n-1Loc(a[i])=loc(a[0])+i*c顺序表的抽象数据结构p43顺序表上实现的基本运算1.查找例：在顺序表{12，15，33，45，67，89，57，78}查找57（找到），查找66（找不到）。121533456789577801234567程序实现Templet<classtype>intSeqlist<type>::Find(type&x)const{Inti=0；

while(i<=last&&data[i]!=x)i++;If(i>last)return-1;//没找到

Elsereturni;//找到}查找算法的时间复杂度问题规模：表的长度，设它的值为n。算法的时间：主要化费在循环比较语句上。比较结点的次数依赖于（表的长度，被查找元素位置）。最好情况：a0=x；这时，其时间复杂度O（1）；最坏情况：找不到；比较语句将循环执行n次，其时间复杂度O（n）平均复杂度：在长度为n的线性表中第i个位置上找到一个结点，令Efd(n)表示找到结点的期望值（即比较的平均次数），则在第i个位置上找到一个结点的比较次数为i+1。故Efd(n)=∑pi(i+1)假设在表中任何位置(0≦i≦n-1)上查找结点的机会是均等的，则

p0=p1=p2=…=pn-1=1/n因此，在等概率插入的情况下，

Efd(n)=∑(i+1)/n=(n+1)/2

在顺序表上做查找运算，算法的平均时间复杂度为O(n)。2.插入例：在顺序表{12，15，33，45，67，89，57，78}的第三个元素处插入元素44。12153345678957780123456744程序实现Templet<classtype>intSeqlist<type>::Insert(type&x,inti){If(i<0||i>last+1||last==MaxSize-1)return0;//procondition校验Else{last++;for(intj=last;j>i;j--)data[j]=data[j-1];data[i]=x;//插入return1;插入算法的时间复杂度问题规模：表的长度，设它的值为n。算法的时间：主要化费在循环的结点后移语句上。移动结点的次数（依赖于表的长度，插入位置）。最好情况：i=n；由于循环变量的终值大于初值，结点后移语句将不进行；这是，其时间复杂度O（1）；最坏情况：当i=1时，结点后移语句将循环执行n次，其时间复杂度O（n）；平均复杂度：在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故Eis(n)=∑pi(n-i+1)

假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则

p1=p2=p3=…=pn+1=1/(n+1)

因此，在等概率插入的情况下，

Eis(n)=∑(n-i+1)/(n+1)=n/2

在顺序表上做插入运算，算法的平均时间复杂度为O(n)。3.删除：在上例完成后，再删除44121544334567895778012345678完成后121533456789577801234567程序实现Templet<classtype>intSeqlist<type>::Remove(type&x){inti=find（x）//查找if(i>0){last--;for(intj=i;j<=last;j++)data[j]=data[j+1];//依次前移

return1;}renturn0;//找不到，不能删除}算法的平均复杂度=0(n)顺序表的使用Templet<classtype>voidUnion(SeqList<type>&La,SeqList<type>&Lb){intn=La.Length();intm=Lb.Length();for(inti=1;i<=m;i++){typex=Lb.Get(i);//取值

intk=La.Find(x);//查找

if（k==-1）La.Insert(x;n+1);//找不到

n++;}}线性表的链式表示和实现顺序表的优点：取数方便快速。缺点：删除、插入平均要移o(n)个元素。适应性不强。

链表：是指用一组任意的存储单元来存放线性表的结点，这组存储单元可以是零散分布在内存中的任意位置上的。任意的存储单元如何存放线性表例：（a1,a2,a3,a4)链表中的结点结构：

datalink单链表（SingleLinked):每一个结点只有一个链域，将各节点按顺序联系在一起的链表。链式存储的优点：存储方便。空间使用性好。取用不方便（一定是顺序取用）。链表：非顺序存储，顺序取用例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示意图如下：165………………110hat200………….……130cat135135eat170……….……160matNull165bat130170fat110………………200jat205205lat160………………heatheadbatcateatmat^…单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。

单链表的类定义1.复合类定义法：Classlist;Templete<classType>ClasslistNode{friendclasslist;private:Type*data;listNode*link;};Templet<classtype>classlist{private:listNode*first,*last;public://公共线性表操作}；嵌套类Templet<classtype>classlist{private:classlistNode{public:type*data;listNode*link;}listNode*first;*last;public://公共线性表操作}；对象和对象指针对象指针：用于存放对象地址的变量声明形式：类名*对象指针名。Point*p;Pointp1;p=&p1;对象成员的引用：p1.x,p1.y;通过对象指针引用对象成员：p->x,p->y单链表的插入与删除插入（表首、中间、最后）gathatcatpSS->link=p->link;P->link=S;删除算法（表首、中间、最后）gathatcatPSp->link=s->link;DeleteS;单链表的实现不带表头的单链表结构x2xn∧x1first判断空表的条件：first=NULLlast带表头的单链表结构x1xn∧∧first判断空表的条件：first->link=NULLlast建立单链表

1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。2、尾插法建表

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。查找运算

1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域link逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：Templete<classtype>listNode<type>*list<type>::find(inti){If(i<-1)returnNULL;If(i==-1)returnfirst;listNode<type>*p=first->link;intj=0;while(p!=NULL&&j<i){p=p–>link;j++;}returnp;}2、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：Templete<classtype>listNode<type>*list<type>::find(typevalue){listNode<type>*p=first->link;while(p!=NULL&&p->data!=value)p=p–>link;returnp;}算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。三、插入运算

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：

Templete<classtype>intlist<type>::insert(typevalue,inti){listNode<type>*p=find(i-1);If(p==NULL）return0;listNode<type>*newNode=GetNode(value,p->link);if(p->link==NULL)last=newNode;p->link=newNode;return1;}算法的时间主要耗费在查找操作find上，故时间复杂度亦为O(n)。四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点aai-1的指针域link中，所以我们必须首先找到ai-1的存储位置p。然后令p–>link指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。

设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点即p–>link!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。单链表的游标指针的抽象：first；current；last；仿真：模仿人的工作。应用的方便性：在几乎不损失效率的前提下，可以利用游标直接完成多种运算。它是一种利用单链表的基本方式。(求和、求平均、求最大值。。。）O静态链表数组中的每一个元素附加一个链接指针，就形成了一个静态链表。静态链表是利用数组实现的，在运算过程中存储空间大小不变（静态）如何利用空间：分成两个链表1.可利用空间链表2.已用空间链表(实例)循环链表单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：

a1an

….first⑴非空表⑵空表

在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)first

在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针last来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(last–>link)—>link和last，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。判断表尾的条件：P->link==first;判断空表的条件：first->link==first;由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>link是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。算法：

templete<classT>Circlist<T>*Circlist<T>::Merge(Circlist<T>&A，

Merge(Circlist<T>&B){CirclistNode<T>*p=A->last->link;A->last->link=(B->last->link)->link;deleteB->last->link;B->last->link=p;returnA);}x1xn∧firstx1xn∧lastfirstlast用循环链表解约瑟夫问题约瑟夫问题：旅行社用循环余数方法选择旅客，提供免费旅行。例子：n=8,m=3双链表问题的提出:双向遍历（删除）双链表的结构1节点的结构llinkdatarlink2双链表结构∧axfirst双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域llink。这样就形成的链表中有两个方向不同的链，故称为双向链表。双链表与单链表的区别判断表空的条件：

first==first->llink==first->rlink==last;判断表尾的条件：

p->rlink==first;双链表的对称性：p->llink->rlink=p->rlink->llink=p

和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。

向后插入算法双向链表的向后操作算法：

{q->llink=p->lling;q->rlink=p;p->rlink->llink=q;p->rlink=q;}向前插入算法双向链表的前插操作算