【教学课件】第2章数据结构线性表.ppt

第二章 线性表,陈守孔 孟佳娜 陈卓,本章目录,2.1 线性表的类型定义 2.1.1 线性表的概念 2.1.2 线性表的抽象数据类型 2.2 线性表的顺序表示和实现 2.2.1 线性表的顺序表示 2.2.2 顺序表上基本运算的实现2.3 线性表的链式表示和实现 2.3.1 单链表的表示 2.3.2 单链表操作的实现2.4 线性表实现方法的比较2.5 循环链表2.6 双链表2.7 静态链表（*2.8 算法设计举例）,主要内容,知识点线性表的定义顺序表单链表双链表静态链表重点难点顺序表操作的实现单链表操作的实现顺序表和链表操作时间复杂度的分析静态链表,线性结构,在数据元素的非空的有限集合中：存在唯一的一个被称为“第一个”的数据元素；存在唯一的一个被称为“最后一个”的数据元素；除第一个元素外，集合中每个元素都有且仅有一个前驱；除最后一个元素外，集合中每个元素都有且仅有一个后继；,线性表(Linear List)定义,定义：n个具有相同特性的数据元素组成的有限序列；表示：a1,ai-1,ai,ai+1,anai必须具有相同特性，即属于同一数据对象ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素数据元素ai在线性表中有确定的位置i，i称为位序线性表中数据元素的个数n称为线性表的长度,n=0时，线性表称为空表,抽象数据类型定义,ADT List数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R=|ai,ai-1D,i=2,n基本操作：ListInit(L)；ListLength(L)；ListGet(L,i);ListLocate(L,x);ListClear(L);ListEmpty(L)；ListPrior(L,e)；ListNext(L,e)；ListInsert(L,i,e);ListDelete(L,i);ADT List,例如2.1 遍历线性表L,ListTraverse(List L，visit()/遍历线性表if(ListEmpty(L)printf(“空表n”);else for(i=1;i=ListLength(L);i+)visit(ListGet(L,i)；,例2.2 合并线性表,List ListMerge(List La,List Lb)/La和Lb是两个非递减有序的线性表，将线性表La和Lb合并成一个新的线性表Lc，Lc也非递减有序。ListInit(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)（接下页）,（接上页）while(i=La_len)/Lb已空，将La表的剩余部分复制到新表ai=ListGet(La,i+);ListInsert(Lc,+k,ai);while(j=Lb_len)/La已空，将Lb表的剩余部分复制到新表bj=ListGet(Lb,j+);ListInsert(Lc,+k,bj);return(Lc);/ListMerge,例2.2 合并线性表,逻辑结构是本质,通过上面两个例子可以看出：逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构,线性表的顺序表示和实现,线性表的顺序表示:线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。设 a的存储地址为Loc(a)，每个数据元素占L个存储单元，则第i个数据元素的地址为：Loc(ai)=Loc(a1)+(i-1)*L 1in,顺序存储结构的线性表的类型定义如下：#define MAXSIZE 100 顺序表的最大容量typedef structElemType dataMAXSIZE;存放线性表的数组int last;last是线性表的长度SeqList;,顺序表上基本运算的实现(1),SeqList SeqListInit(SeqList L)/构造一个空的顺序表 L.length=0;/初始化顺序表为空表 return L;,顺序表的初始化:,顺序表上基本运算的实现(2),插入运算:在第 i 个位置，插入元素e思想：把从第i个位置开始的元素，依次后移步骤：1.当前表是否已经满？2.输入是否有效？3.插入元素。,顺序表上基本运算的实现(2),SeqList SeqListInsert(SeqList L，int i，ElemType x)在顺序表中的第 i 个位置插入元素 x if(L.Last=MAXSIZE)printf(表满n);exit(0);表满，退出if(iL.Last+1)printf(插入位置错n);exit(0);插入位置错，退出 for(j=L.Last-1;j=i-1;j-)L.dataj+1=L.dataj;第i个位置后的数组元素逐一后移 L.datai-1=x;新元素插入到第i个位置 L.Last+;顺序表长度增1 return(L);返回插入元素后的顺序表,顺序表插入元素算法分析,插入运算的基本操作是移动数据。在第i（1in+1）个位置上插入x，需要移动n-i+1个元素。设在第i个位置上作插入的概率为 pi，则平均移动数据元素的次数（期望值）为 设：pi=1/(n+1)，即为等概率情况，则：pi=n/2,约需移动表中一半的数据元素。,时间复杂度：,O(n),顺序表上基本运算的实现(3),删除运算:删除第 i 个元素e思想：把第i1个位置开始的元素，依次前移步骤：1.要检查删除位置的有效性；2.依次移动元素；3.长度减1。,顺序表上基本运算的实现(3),void SeqListDelete(SeqList L,int i)/删除顺序表中的第i个元素 if(iL.last)printf(“位置非法”)exit(0);/检查空表及删除位置的合法性 for(j=i;j=L.last-1;j+)L.dataj-1=L.dataj;/向上移动 L.last-;/顺序表长度减1,时间复杂度：,O(n),删除元素:,顺序表删除元素算法分析,主要操作是移动元素。删除第i个元素时，向前移动n-i 个元素平均移动元素次数的期望值:在等概率情况下，pi=1/n，则：Edel=(n-1)/2,所以顺序表上的删除运算约需要移动表中一半的元素。,时间复杂度：,O(n),顺序表上基本运算的实现(4),int SeqListLocate(SeqList L,ElemType x)/在顺序表L中查找第一个与x值相等的元素。若查找成功，则返回它在顺序表中的位序；否则，返回0。i=1;while(i=L.last/查找失败,按值查找:,顺序表算法举例,顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类C语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。,顺序表算法举例（续）,void Union(SeqList LA,LB)/LA和LB是顺序存储的线性表，元素按非递减有序排列，本算法将LB合并到LA中，元素仍非递减有序。m=LA.last;n=LB.last;/m，n分别为线性表LA和LB的长度。k=m+n-1;/k为结果线性表的工作指针（下标）i=m-1;j=n-1;/i，j分别为线性表LA和LB的工作指针（下标）while(i=0,顺序表算法举例（续）,请写一个算法将顺序表（a1,.,an）逆置为(an,.,a1)。,void SeqInvert（ElemType a，int n）/a是具有n个元素的顺序表，本算法将其逆置。for（i=0；i=(n-1)/2；i+）t=ai；ai=an-1-i；an-1-i=t；/算法结束 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。,线性表的链式表示和实现,以链式结构存储的线性表称之为线性链表。线性表中的数据元素可以用任意的存储单元来存储，逻辑相邻的两元素的存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息之外，还需存储其后继的地址（即用指针表示逻辑关系）。这两部分信息组成数据元素的存储映象，称为结点。,可以认为利用小的零散空间“串”起来，表示线性表，即把线性表的元素分散插入到系统所控制的零散空间中，然后用“指针”串起来，组成一个有序的线性表，用指针表示数据元素的逻辑关系。元素的存储，可以是连续的，也可以不是连续的。结点至少包括数据元素和指针两个区域。,线性表的链式表示,单链表结构图示,链表,结点ai,单链表结构图示,单链表的头指针为H：LinkedList H;,单链表结点的类型定义,结点定义：typedef struct Node ElemType data;struct Node*next;LNode，*LinkedList；,几个概念：结点，首元结点，第一元素结点，头结点，指针，头指针,带头结点的单链表,通常情况下，为了运算的统一，常在第一个结点前附设一个结点，称为“头结点”，头指针具有标识作用，因而，常用作链表的名字,LNode*p;p=（LNode*）malloc(sizeof(LNode)；则完成了申请一块LNode类型的存储单元的操作，并将其地址赋值给变量p。,线性链表操作的实现(1),LinkedList LinkedListInit()/建立一个空的单链表 L=(LNode*)malloc(sizeof(LNode)；if(L=null)printf(“无内存空间可分配”);exit(0);L-next=NULL;return L;,带头结点的单链表的初始化：,线性链表操作的实现(2),int LinkedListLength(LinkedList L)/求带头结点的单链表的长度 p=L-next;/p指向第一结点 j=0;while(p)j+;p=p-next;/移动p指向下一结点 return j;,求表长:,线性链表操作的实现(3),LinkedList LinkedListGet(LinkedList L,int i);/在单链表L中查找第i个元素结点，返回该结点，否则返回空 if(inext;j=1;while(p!=NULL,取第i个元素:,线性链表操作的实现(4),LinkedList LinkedListLocate(LinkedList L,ElemType x)/在单链表L中查找值为x的结点，找到后返回其指针，否则返回空 p=L-next;while(p!=NULL,按值查找:,线性链表操作的实现(5),LinkedList LinkedListLocate(LinkedList L,LNode*p)/在单链表L中求p指向的结点(假定存在）的前驱 if(L-next=p)printf(“p指向第一元素结点，无前驱”);exit(0);pre=L;while(pre!=NULL,查找结点的前驱:,线性链表操作的实现(6),LinkedList LinkedListLocate(LinkedList L,LNode*p)/在单链表L中求p指向的结点(假定存在）的后继 pre=L;while(pre!=NULL,查找结点的后继:,线性链表操作的实现(7),p表示当前结点，pre表示前一个结点(的指针)。在p前插入元素ss-next=pre-next;pre-next=s;,插入元素：,线性链表操作的实现(7),插入算法:void LinkedListInsert(LinkedList L,LNode*p,ElemType x)/在结点p之前插入元素为x的结点pre=L;while(pre!=NULL/插入新结点,线性链表操作的实现(8),p表示当前结点，pre表示前一个结点。pre-next=p-next;free(p);/p=pre-next;,删除元素:,线性链表操作的实现(8),删除元素:void LinkedListDel(LinkedList L，int i)/删除单链表L上的第i个结点 if(inext/释放被删除结点,线性链表操作的实现(9),建立单链表头插法:,线性链表操作的实现(9),LinkedList LinkedListCreat1()/用头插法建立带头结点的单链表 LinkedList L;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;/初始化一个空链表，L为头指针 scanf(,头插法建立单链表算法:,线性链表操作的实现(10),建立单链表尾插法:,线性链表操作的实现(10),LinkedList LinkedListCreat3()/用尾插法建立带头结点的单链表 LinkedList L;L=(LNode*)malloc(sizeof(LNode);L-next=NULL;r=L;scanf(,尾插法建立单链表算法:,链表的遍历,void print(LinkedList la)/非递归LinkedList p=la-next;while(p)printf(“%c”,p-data);p=p-next;,void out(LinkedList p)/递归if(p)out(p-next);printf(“%c”,p-data);,链表算法举例 合并单链表,LinkedList Union(LinkedList la，LinkedList lb)将非递减有序的单链表la和lb合并成新的非递减有序单链表lc，并要求利用原表空间 lc=(LNode*)malloc(sizeof(LNode);申请结点 lc-next=NULL;初始化链表lc pa=la-next;pa是链表la的工作指针 pb=lb-next;pb是链表lb的工作指针 pc=lc;pc是链表lc的工作指针 while(pa la中元素插入lc,链表算法举例,（接上页）else pc-next=pb;pc=pb;pb=pb-next;lb中元素插入lc if(pa)pc-next=pa;若pa未到尾，将pc指向pa else pc-next=pb;若pb未到尾，将pc指向pbreturn(lc);Union,链式结构的特点,非随机存贮结构，所以取表元素要慢于顺序表。节约了内存适合于插入和删除操作实际上用空间换取了时间，结点中加入了指针，使得这两种操作转换为指针操作;,线性表实现方法的比较,实现不同顺序表方法简单，各种高级语言中都有数组类型，容易实现；链表的操作是基于指针的，相对来讲复杂些。存储空间的占用和分配不同从存储的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。而链表是动态分配存储空间的，不用事先估计存储规模。可见对线性表的长度或存储规模难以估计时，采用链表。线性表运算的实现不同 按序号访问数据元素，使用顺序表优于链表。插入删除操作，使用链表优于顺序表。,循环链表,单循环链表:,循环链表：链表尾结点的指针域指向头结点。这样形成的链表我们叫做循环链表。,循环链表往往只设尾指针,连接两个只设尾指针的单循环链表L1和L2,语句段如下：p=R1next;/保存L1 的头结点指针R1-next=R2-next-next;/头尾连接free(R2-next);/释放第二个表的头结点 R2-next=p;,双链表,如果希望查找前驱的时间复杂度达到O(1)，我们可以用空间换时间,每个结点再加一个指向前驱的指针域，使链表可以进行双方向查找。用这种结点结构组成的链表称为双向链表。,结点的结构图:,双向链表的逻辑表示,L,L,双向链表的类型定义,typedef struct DLNodeElemType data;struct DLNode*prior,*next;DLNode,*DLinkedList;,双向链表结点的类型定义如下：,双向链表的插入,p,s,p-prior=s;,1,2,s-prior=p-prior;,p-prior-next=s;,s-next=p;,3,4,双向链表的删除,p,1,2,p-prior-next=p-next;P-next-prior=p-prior;free(p);,循环链表算法举例（1）,假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（null）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。,void SToDouble（LinkedList la）while（la-link-pre=null）la-link-pre=la/将结点la后继的pre指针指向la la=la-link；/la指针后移/算法结束,循环链表算法举例（2）,已知一双向循环链表，从第二个结点至表尾递增有序，（设a1xan）如下图。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序,L,循环链表算法举例（2）,void DInsert（DLinkedList L）s=L；s暂存第一结点的指针 p=L-next；将第一结点从链表上摘下 p-prior=L-prior；p-prior-next=p；while（p-datanext；查插入位置 s-next=p；s-prior=p-prior；插入原第一结点s p-prior-next=s；p-prior=s；算法结束,链表算法举例（3）,L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。,链表算法举例（3）,LinkedList PatternInvert（LinkedList L1，L2）p=L1；p是每趟匹配时L1中的起始结点前驱的指针 q=L1-next；q是L1中的工作指针。s=L2-next；s是L2中的工作指针。while（p!=null 对应字母相等，指针后移。else p=p-next；q=p-next；s=L2-next；/失配时L1起始结点后移，L2从首结点开始。（接下页）,链表算法举例（接上页）,if（s=NULL）匹配成功，这时p为L1中与L2中首字母结点相同数据域结点的前驱，q为L1中与L2最后一个结点相同数据域结点的后继。r=p-next；r为L1的工作指针，初始指向匹配的首字母结点。p-next=q；将p与q结点的链接。while（r!=q）；逐结点倒置。s=r-next；暂存r的后继。r-next=p-next；将r所指结点倒置。p-next=r；r=s；恢复r为当前结点。else printf（“L2并未在L1中出现”）；算法结束,静态链表,有些高级程序设计语言并没有指针类型，如FORTRAN和JAVA。我们可以用数组来表示和实现一个链表，称为静态链表。可定义如下：#define MAXSIZE 1000/最多元素个数 typedef struct ElemType data;/数据元素 int next;/指向后继元素在数组中的位置 SLinkedListMAXSIZE;,静态链表图示,线性表L=（2，3，4，6，8，9）的静态链表图示,静态链表与动态链表,静态链表的操作和动态链表相似，只是以整型游标代替动态指针。设以Sa表示静态链表，通常可把Sa0理解为“头结点”，第1个元素的位置由Sa0.next指出,用全局整型变量av指出可利用空间的下标。初始时将整个静态链表看作一个“空表”，操作中用GetNode()和FreeNode()函数模拟C中的malloc()和free()函数。以下是初始化、取结点和释放结点3个函数。,静态链表的初始化,int Initilize()/*初始可利用空间表*/int i;for(i=0;imaxsize-1;i+)/链成可利用空间表 Sai.next=i+1;Samaxsize-1.next=-1;/*链表尾*/av=1;return av;/*返回可利用空间表的下标*/,静态链表的申请结点空间,int GetNode()/*取结点*/if(av!=-1)/*-1表示无空间*/p=av;av=Saav.next;/*p为可利用空间的下标*/return p;,静态链表的释放结点空间,int FreeNode(int p)/*将p归还到可利用空间表中*/Sap.next=av;av=p;return av;,静态链表的操作举例（1）,（1）查找值为x的结点int Locate(SLinkedList SL,ElemType x)p=SL0.next;while(p!=-1/元素下标,静态链表的操作举例（2）,(2)查找i第个结点ElemType Locate(SLinkedList SL,int i)int j=1;if(i0)printf(“参数错误”);exit(0);p=SL0.next;while(p!=-1,静态链表的操作举例（3）,(3)插入第i个结点void Insert(SLinkedList SL,ElemType x,int i)pre=0;/*前驱*/j=1;s=GetNode();if(s=-1)printf(“overflown”);exit(0);/*无空间*/else p=SL0.next;while(p!=-1/*所给i值太大*/,静态链表的操作举例（4）,(4)删除第i个结点 int Delete(SLinkedList SL,int i)/*在静态链表中删除第i个元素 i0*/pre=0;/*前驱*/j=1;p=SL0.next;/*查找删除元素*/while(p!=-1,静态链表算法举例,设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8,静态链表算法举例,void Insert（SLinkedList user,int av）user是静态双向链表，表示飞机票订票系统，元素包含data、Llink和Rlink三个域 结点按来客姓名排序。本算法处理任一乘客订票申请。scanf（“%s”，s）；s是字符数组，存放乘客姓名strcopy（userav.data，s）；p=1;p为工作指针（下标），p=0时表示链表尾 if(strcmp（userp.data，s）0）沿右链查找 while(p!=0,else 沿左链查找 while(p!=0 算法结束,