数据结构第2章-线性表

第2章线性表

2.1线性表的基本概念

2.2顺序表2.3链表2.4顺序表和链表的比较2.5链表的应用2.1.1线性表的定义线性表是一种线性结构，是某类数据的集合，每个线性表的数据元素都具有以下共性：（1）集合中的所有元素都是同一种数据类型；（2）这些集合具有有限的大小；（3）集合中的元素都是线性排列的，即存在一个首元素和一个尾元素；除了尾元素外，每个元素都有一个后继；除了首元素外，每个元素都有一个前驱。2.1线性表的基本概念

可以用以下形式来表示线性表：(a1，a2，…ai-1，ai，ai+1，…an)其中ai表示线性表中的任意一个元素，n表示元素的个数。表中相邻元素之间存在着顺序关系。将ai-1

称为ai

的直接前驱，ai+1

称为ai

的直接后继。而a1是表中第一个元素，没有前驱；an

是最后一个元素，无后继。2.1线性表的基本概念

一种典型的线性表的逻辑结构示例：2.1线性表的基本概念

a1ai-1aianai+12.1.2线性表的存储结构（1）顺序存储结构该存储结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。如下图所示：2.1线性表的基本概念

2.1.2.线性表的存储结构（2）链式存储结构该结构不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由额外的引用域来表示的。如下图所示：2.1线性表的基本概念

2.1.3线性表的运算2.1线性表的基本概念

运算含义InitList(L)线性表初始化Length(L)求线性表的长度Get(L,i)取表元Locate(L,x)查找Insert(L,i,x)插入操作Delete(L,i)删除操作Empty(L)线性表判空DispList(L)显示表元素第2章线性表

2.1线性表的基本概念 2.2顺序表2.3链表2.4顺序表和链表的比较2.5链表的应用2.2.1顺序表的定义顺序表是指采用顺序存储的方式来存储数据元素的线性表。在顺序表中，我们通常将结点依次存放在一组地址连续的存储空间中，由于待存储空间连续且每个数据元素占用的空间相同，因此可以综合上述信息并通过计算得出每个元素的存储位置。2.2顺序表假设对于线性表(a1，a2，…an)，该类型数据所需的内存单元数为d，首元素a1的物理地址为LOC(a1)，第i个数据元素的物理地址LOC(ai)与LOC(a1)存在如下关系：LOC(ai)=LOC(a1)+(n-1)d此关系解释如下图，其中，b表示LOC(a1)。2.2顺序表2.2.2顺序表的运算（1）类型说明算法2.1初始化顺序表2.2顺序表classSeqList(object):def__init__(self):#初始化顺序表self.MAX=20#SeqList类列表的数据元素最大长度self.SequenceList=[]self.Length=0#Length是列表中元素的实际个数（2）顺序表创建算法2.2顺序表创建2.2顺序表defCreateSeqList(self):print("请输入数据，若想结束输入请按’#’。")Element=input("请输入元素：")whileElement!='#':self.SequenceList.append(int(Element))Element=input("请输入元素：")（3）查找元素算法2.3查找元素2.2顺序表defLocate(self):key=eval(input('请输入要查找的元素值：'))ifkeyinself.SequenceList:ipos=self.SequenceList.index(key)print(“查找成功！元素{}位于当前顺序表的第{}个位置。”.format(key,ipos+1))else:print("查找失败！当前顺序表中不存在值为",key,"的元素")（4）指定位置插入元素算法2.4指定位置插入元素2.2顺序表defInsert(self):iPos=int(input('请输入待插入元素的位置：'))element=int(input('请输入待插入的元素值：'))self.SequenceList.insert(iPos,element)print("插入元素后，当前顺序表为：\n",self.SequenceList)（5）删除指定位置的元素算法2.5删除顺序表中指定位置的元素2.2顺序表defDelete(self):dPos=int(input('请输入待删除元素的位置：'))print(“即将删除元素",self.SequenceList[dPos],"...")self.SequenceList.pop(dPos)print("删除后顺序表为：\n",self.SequenceList)2.2.3遍历遍历是数据结构中最重要的运算之一，所有关于数据结构的运算都建立在遍历的基础上，所以把这个内容独立成节。遍历一个顺序表就是从顺序表的第一个元素起，依次访问表中的每一个元素。每个元素只访问一次，直到访问完所有元素为止。2.2顺序表2.2.3遍历通过SeqList类的成员函数Traverse(self)，遍历当前顺序表中的元素，其算法思路如下：（1）调用Python内置函数len()函数得到当前顺序表的长度SeqListLen。（2）使用变量i来指示当前元素的下标位置。（3）从变量i=0开始到i=SeqListLen-1为止，循环调用print()函数输出下标位置i处的元素值。2.2顺序表2.2.3遍历算法2.6顺序表的遍历算法2.2顺序表defTraverse(self):print("******遍历顺序表中元素******")foriinrange(0,self.Length):print("第{}个元\

素:{}“.format(i,self.SequenceList[i]))2.2.5线性表的顺序存储的主要特点逻辑上相邻的元素，物理位置上也相邻。可随机存取线性表中任一元素，只要知道其下标。必须按最大可能长度分配存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存储结构。插入、删除元素时，需移动大量元素，平均移动元素为n/2（n为表长）。长度变化较大时，需按最大空间分配，势必造成存储空间的浪费。2.2顺序表第2章线性表

2.1线性表的基本概念 2.2顺序表2.3链表2.4顺序表和链表的比较2.5链表的应用采用链式存储结构的线性表称为链表。只有一个引用的叫单链表，其作用专门用于指向其后继元素，第一个元素指向第二个元素，第二个指向第三个，……，最后一个数据元素结点的指针为空，因为它的后面没有元素。有两个引用的叫双链表，通常一个引用用来指向其后继，另一个引用用来指向其前驱。2.3链表2.3.1单链表的定义单链表只有一个引用域，其结构可以表示如下：2.3链表其中：data部分存放线性表的一个元素值。next部分存放一个引用，指向线性表中下一元素的结点位置。如果没有下一个元素，则使用一个特殊的空值（None）2.3.2单链表的基本运算（1）类型说明定义2.2单链表中的结点定义2.3链表classNode(object):def__init__(self,data):self.data=dataself.next=None（2）单链表初始化算法2.7单链表初始化2.3链表classSingleLinkedList(object):def__init__(self):self.head=Node(None)#创建头结点（3）创建单链表算法2.8创建单链表2.3链表defCreateSingleLinkedList(self):print(“请输入数据，结束输入请按“#”！")cNode=self.headElement=input("请输入当前结点的值：")whileElement!="#":nNode=Node(int(Element))cNode.next=nNodecNode=cNode.nextElement=input("请输入当前结点的值：")（4）求单链表的长度算法2.9求单链表的长度2.3链表defLength(self):p=self.head.nexti=0whilep:i+=1p=p.nextreturni（5）查找指定元素并返回其位置算法2.10查找指定元素并返回其位置2.3链表defLocate(self):Pos=0;cNode=self.headkey=int(input('请输入想要查找的元素值：'))ifself.IsEmpty():print("当前单链表为空！");return-1whilecNode.next!=NoneandcNode.data!=key:cNode=cNode.next;Pos=Pos+1

（5）查找指定元素并返回其位置算法2.10查找指定元素并返回其位置2.3链表defLocate(self):#上述程序续ifcNode.data==key:print("查找成功，值为",key,"的结点位于该单链表的第",Pos,"个位置。")return1else:print(“查找失败！”)return-1（6）单链表尾端插入算法算法2.11单链表尾端插入算法2.3链表defInsertAtTail(self):element=(input("请输入待插入结点的值："))ifelement=="#":returncNode=self.headnNode=Node(int(element))whilecNode.next!=None:cNode=cNode.nextcNode.next=nNode（7）单链表首端插入算法算法2.12单链表首端插入算法2.3链表defInsertAtHead(self):element=input("请输入待插入结点的值：")ifelement=="#":returncNode=self.headnNode=Node(int(element))nNode.next=cNode.nextcNode.next=nNode（8）单链表任意位置插入元素算法算法2.13单链表任意位置插入元素算法2.3链表defInsert(self):element=input("请输入待插入结点的值：")i=int(input("请输入待插入结点的位置："))ifelement=="#":returnifi<1:#待插入的位置不合法returnp=self.head（8）单链表任意位置插入元素算法算法2.13单链表任意位置插入元素算法2.3链表defInsert(self):#上述程序续

forjinrange(1,i):p=p.nextnNode=Node(int(element))nNode.next=p.nextp.next=nNode（9）删除值为x的结点算法2.14删除值为x的结点2.3链表defDelete(self):x=input("请输入需要删除的元素值:")p=self.head.nextwhilep.data!=xandp:t=p;p=p.nextifp:t.next=p.next;

return1else:print("Nodexnotfound!\n");return-1（10）带头结点的单链表的遍历算法2.15带头结点的单链表的遍历算法2.3链表defTraverse(self):cNode=self.headifcNode.next==None:print(“当前单链表为空！”);

returnprint("您当前的单链表为：")whilecNode!=None:cNode=cNode.nextprint(cNode.data,"->",end="")单链表应用举例例2.1删除单链表中结点值重复的冗余结点，使其成为每个结点的值在单链表中唯一存在。2.3链表defdelete_sameNode(head):q=head.next

whileq:r=q

whiler.next:

p=r.next

ifp.data==q.data:r.next=p.next

else:r=r.nextq=q.next2.3.3循环单链表单链表的各种操作只能从表头向表尾进行，达到尾结点后，指针无法回到表头，如果要回到表头，这种链表已经无能为力。必须使用专门的办法，把链表的首尾连接起来，这样指针自然就可以回到表头来，形成一个循环链表，其结构如图2.14所示2.3链表（1）创建循环单链表算法2.16创建带头结点的循环单链表2.3链表defCreateCSLinkedList(self):print("请输入数据后按回车键确认，结束请输入'#'")data=input("请输入结点的值:")cNode=self.head（1）创建循环单链表算法2.16创建带头结点的循环单链表2.3链表defCreateCSLinkedList(self):#上述程序续whiledata!='#':nNode=Node(int(data));cNode.next=nNodenNode.next=self.head;cNode=cNode.nextdata=input("请输入结点的值:")（2）删除算法2.17删除循环单链表结点操作的核心算法2.3链表ifself.head.next==None:#循环链表为空

print("Empty!")else:p=q.next#q为p的前驱

ifp==self.head:#单结点循环链表

self.head.next=Noneelse:q.next=p.next#含2个以上结点的循环链表2.3.4双向链表单链表的结点中只有一个指向其后继结点的指针域next，若查找结点的前驱则只能从该链表的头指针开始，顺着各结点的next域进行，因此找前驱的时间复杂度是O(n)。如果希望找前驱的时间性能达到O(1)，则每个结点再增加一个指向前驱的指针域，结点的结构变成图2.18的结构，用这种结点组成的链表称为双向链表，简称双链表。2.3链表其中，data域叫数据域，与线性表的数据元素值对应，prior和next部分为指针域，用于存放指向前驱和后继元素的指针。2.3链表双向链表的运算（1）类型说明定义2.3双向链表中的结点定义2.3链表classDoubleLinkedNode(object):def__init__(self,data):#初始化结点

self.data=data#数据域

self.next=None#后继指针

self.prior=None#前驱指针（2）创建双链表算法2.18创建双链表算法2.3链表defCreateDoubleLinkedList(self):print("请输入数据后按回车键确认，若想结束输入请

按“#”。")data=input("请输入元素：")q=self.head

（2）创建双链表算法2.18创建双链表算法2.3链表defCreateDoubleLinkedList(self):#上述程序续whiledata!='#':p=DoubleLinkedNode(int(data))q.next=p;p.prior=qq=q.next;data=input("请输入元素：")（3）插入算法2.19在双链表中值为x的结点前插入新结点2.3链表defInsert(self,x):y=input("请输入元素：")ify=='#’:returns=DoubleLinkedNode(int(y))p=self.head（3）插入算法2.19在双链表中值为x的结点前插入新结点2.3链表defInsert(self,x):#上述程序续whilep.data!=xandp.next:t=p;p=p.nexts.prior=p.prior;

p.prior=ss.next=p;t.next=s（4）删除算法2.20删除双链表中值为x的结点2.3链表defDelete(self,x):p=q=self.headwhilep.data!=x:q=p;p=p.nextifp:q.next=p.next;

p.next.prior=p.priorreturn1else:print("Nodenotfound!");return-1循环双向链表循环双链表是把首尾相接的双链表，带头结点的循环双链表的一般形态如图2.24所示。2.3链表第2章线性表

2.1线性表的基本概念 2.2顺序表2.3链表2.4顺序表和链表的比较2.5链表的应用本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。通过对它们的讨论可知它们各有优缺点，顺序存储有三个优点：①方法简单，可以用各种高级程序语言中的数组实现。②不用为表示结点间的逻辑关系而增加额外的存储开销。③顺序表具有按元素序号可随机访问的特点。2.4顺序表和链表的比较但它也有一个缺点：在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。链表的优缺点恰好与顺序表相反。2.4顺序表和链表的比较在实际中怎样选取存储结构呢？通常有以下几点考虑：1．基于存储空间的考虑在Python中，顺序表是用列表（list）来表示的，其存储空间的大小事先不需要确定。链表不用事先估计存储规模，但链表的存储密度小于１2.4顺序表和链表的比较在实际中怎样选取存储结构呢？通常有以下几点考虑：2．基于运算的考虑在顺序表中按序号访问ai的时间性能是O(1)，而链表中按序号访问的时间性能是O(n)，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素数量很大时效率较低；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。2.4顺序表和链表的比较在实际中怎样选取存储结构呢？通常有以下几点考虑：3．基于环境的考虑顺序表容易实现，任何高级语言中都有数组（Python中是列表）类型，链表的操作是基于指针的，从操作的角度看前者简单些。2.4顺序表和链表的比较在实际中怎样选取存储结构呢？通常有以下几点考虑：4．基于空间的考虑当线性表的长度变化较大，难以估计其存储规模时，适宜采用链表作为存储结构。反之，当线性表的长度变化不大，易于事先确定其大小，为了节约存储空间，宜采用顺序表作为存储结构。2.4顺序表和链表的比较在实际中怎样选取存储结构呢？通常有以下几点考虑：5．基于时间的考虑若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。2.4顺序表和链表的比较总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。2.4顺序表和链表的比较第2章线性表

2.1线性表的基本概念 2.2顺序表2.3链表2.4顺序表和链表的比较2.5链表的应用一元多项式(polynomial)P(x)的形式为：

P(x)=a0+a1x+…+an-1xn-1+anxn

称P(x)为ｎ项多项式,aiｘi是多项式的项（0≤i≤n）,其中ai为系数,ｘ为变数,i为指数,P(x)的阶等于多项式中x（系数不为零）的幂的最大值；例如，多项式：P(x)=5+7x-8x3+4x5是一个5阶多项式。2.5链表的应用一个多项式可以看作一个系数组成的线性表

（a0,a1,a2,…,an）本节讨论链表实现多项式相加的运算。多项式中的每一项有系数、指数，要表示多项式中结点间的逻辑关系，还需要一个链来指向多项式的下一项。这样，数据结构具有如图2.25所示的形式。2.5链表的应用coefexpnext图2.25表示多项式结点的结构定义2.4多项式中每个结点的逻辑结构2.5链表的应用classPoly_Node(object): #多项式中每个结点def__init__(self,coef,exp):self.coef=coef#每一项的系数

self.exp=exp#每一项的指数

self.next=None#指向下一项的指针定义2.5多项式链表2.5链表的应用classPolyLinkList(object):#多项式链表类

def__init__(self):#初始化

self.head=Poly_Node(None,None)#创建多项式链表函数详见后面算法2.23，此处略#算法2.22原地进行多项式相加的算法2.5链表的应用defpoly_add(h1,h2):p=h1.next #p指向A的第一个结点

q=h2.next #q指向B的第一个结点

t=h1 #t指向p的前驱

pc=h1 #pc指向A