2第二章线性表

第二章线性表,Chapter2LinearList,数据结构课程涉及数学、计算机硬件和软件数据结构定义指相互有关联的数据元素的集合，用D_S=(D,R)表示数据结构内容数据的逻辑结构、存储结构和运算算法效率指标时间效率和空间效率,要点回顾,逻辑结构唯一,存储结构不唯一,运算的实现依赖于存储结构,线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构（单链表）应用实例,本章内容,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为：（a0,a1,an-1）,线性结构的定义：,线性结构的特点：,只有一个首结点和一个尾结点；除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型最常用的是-,（a0,a1ai-1，ai,ai1，,an-1）,2.1线性表的逻辑结构,1.线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点（首结点）,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,空表,线性终点（尾结点）,n为元素总个数，即表长,例1分析26个英文字母组成的英文表,（A,B,C,D,Z）,例2分析学生情况登记表,每个数据元素由5个数据项组成;元素之间的关系是线性的,数据元素都是字母;元素之间的关系是线性的,同一线性表中的元素必定具有相同特性,2.线性表的基本操作Initiate(L)初始化操作。建立一个空线性表L。Length(L)求表长。求给定线性表L中数据元素的个数。Get(L,i)读取元素。读取线性表L中第i个数据元素。Insert(L,i,x)前插。在线性表L中第i个数据元素ai之前插入一个新的数据元素x。Delete(L,i,x)删除。删除线性表L中第i个的数据元素,并将其保存在x中。Locate(L,x)定位函数。返回线性表L中元素值等于x的数据元素ai的序号i。,2.2线性表的顺序存储结构顺序表,一、顺序表用一组地址连续的存储单元存储线性表的各个数据元素，称作线性表的顺序存储结构，简称顺序表。,顺序表的特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标，参见存储结构示意图）。,线性表的顺序存储结构示意图,每个元素占K字节,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是,113,例1：,因此：LOC(M3)=98+53=113,解：地址计算通式为：,LOC(ai)=LOC(a0)+L*i,用c语言定义顺序表,#defineMaxlen100typedefstructcharname10;charsex3;intage;elemtype;elemtypeListMaxlen;intnum=-1;,/*定义数据类型*/,/*定义顺序表*/,/*最后一个数据元素的下标*/,/*顺序表最大长度*/,typedefstructelemtypeListMaxlen;intnum;SeqList;,L-num,L-List0,L-List1,L-List2,L-ListMaxlen-1,SeqLista;SeqList*L;,a.num，a.List0,用c语言定义顺序表,二、顺序表的基本操作,1.初始化ListInitiate(L),voidListInitiate(SeqList*L)L-num=-1;,/*num表示线性表最后一个元素的下标*/,2.求表长ListLength(L),intListLength(SeqListL)returnL.num+1;,3.取数据元素ListGet(L，i，x),intListGet(SeqListL,inti,elemtype*x)if(iL.num)printf(“ERROR!n”);return0;else*x=L.Listi;return1;,4.插入（在第i个（0num+1)printf(“errorn”);return0;if(L-num)=Maxlen-1)printf(“overflown”);return0;for(j=L-num;j=i;j-)L-listj+1L-Listj;L-Listix;L-numL-num+1;return1;,判断i是否合法,判断表是否已满,若i合法，元素后移,将元素x存放在i位置,当前数据元素下标加1,用c语言描述插入算法,该算法的时间复杂度：,Eis:插入一个元素所需平均移动次数:则因此,该算法的时间复杂度为O(n)。,5.删除（删除第i个（0=i=n-1）数据元素,并将其保存在x中）,a0,a1,ai-1,01i-1ii+1n-1Maxlen-1,an-1,ai+1,ai,ai,删除算法流程图,位置非法？,N,Y,表空？,Y,for(j=i+1;jnum)printf(“nthepositionisinvalid”);return0;else*x=L-listi;for(j=i+1;jnum;j+)L-listj-1=L-listj;L-num-;return1;,/*删除顺序表L中的第i个元素,并将其保存在x中*/,/*判断表是否为空*/,/*若i合法，元素依次前移*/,/*当前数据元素下标减1*/,/*判断i值是否合法*/,该算法的时间复杂度：,Edl：删除一个元素所需平均移动次数因此,该算法的时间复杂度为O(n)。,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)移动元素的个数取决于插入或删除元素的位置.,顺序表时间效率分析:,顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）,顺序表空间效率分析:,三、顺序存储结构的特点,顺序表的优点：无需为表示数据元素间的逻辑关系而增加额外的存储空间可以方便地随机存取表中的任一数据元素顺序表的缺点：插入和删除运算不方便,需要移动大量的数据元素。由于要求占用连续的存储空间，存储分配只能预先进行,作业：编写顺序表的删除操作算法ListDeleteMore（L,x），要求删除线性表L中所有等于x的数据元素。,如何克服顺序表的这些缺点呢？,第二章线性表,线性结构的特点：仅有一个首、尾结点，除首、尾结点外，其余元素都仅有一个直接前驱和一个直接后继。,2.线性表,逻辑结构：“一对一”或1:1存储结构：顺序存储、链式存储,3.顺序表,特征：逻辑上相邻，物理上一定相邻优点：随机查找快缺点：插入、删除慢（O（n）；需要预先知道线性表的长度,单链表基本概念单链表基本操作,线性表的链式存储结构链表,单链表的基本概念,线性表链式存储结构的一种。用一组不一定连续的存储单元来存放数据元素。,数据域,指针域,结点,头指针,空指针,a0,1475,130A,a1,10CB,1475,a2,10CB,数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。,结点,数据域,指针域,typedefstructNodeDataTypedata;structNode*next;SLNode；,2.3.1单链表的存储结构,不带头结点的单链表,不带头结点的空单链表,head=NULL,头指针,首元结点,带头结点的单链表,带头结点的空单链表,head-next=NULL,头指针,头结点,首元结点,何谓头指针、头结点和首元结点？,头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a0的结点。,首元结点,a0,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,例：,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,头指针的值是31,上例链表的逻辑结构示意图有以下两种形式：,区别：无头结点有头结点,相关知识,动态内存分配,设计人员根据具体问题的具体需要，在程序运行时再具体确定数组的个数或占用内存单元的大小，从而在程序运行时具体确定所需要的内存单元空间。,malloc()函数,free()函数,头文件malloc.h,#include,malloc()函数,free()函数,函数原型：void*malloc(unsignedsize),函数功能：用于向系统动态申请size个字节的内存单元空间，函数返回值为所申请的内存空间首地址。,函数原型：voidfree(void*p),函数功能：用于释放动态分配的内存空间。,sizeof运算符：,sizeof(已定义的数据类型),功能：返回括号中给出的已定义数据类型占用的字节个数。,MemoryAllocation,如：sizeof(int),例如：定义结构体类型typedefstructnodetypeintdata;structnodetype*next;SLNode;,p=(SLNode*)malloc(sizeof(SLNode);,SLNode*p;p=malloc(sizeof(SLNode);,强制类型转换,（1）指针后移操作p=p-next,1475,（2）指向指针的指针SLNode*h;,130A,*h,*h,1000,h,1000,一级指针,二级指针,intListInitiate(SLNode*head)if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)return0;(*head)-next=NULL;return1;,（1）初始化,2.3.2单链表的操作实现,12EF,head,*head,NULL,main()SLNode*h;ListInitiate(,头结点,12EF,(2)求当前数据元素个数,intListLength(SLNode*head)SLNode*p=head;intsize=0;while(p-next!=NULL)p=p-next;size+;returnsize;,(3)取元素（寻找到第i个结点ai并返回该结点的数据元素）,p=p-next;j+;,while(p-next!=NULL,intListGet(SLNode*head,inti,DataType*x)SLNode*p;intj=-1;phead;while(p-next!=NULL),/*找第i个结点*/,/*判断是否找到该结点*/,/*将数据元素值赋给*x*/,步骤:（1）找插入位置，指针p指向ai的前一个结点，即ai-1（2）申请新结点s，将其数据域的值置为x（3）插入：1、s结点指针域指向ai结点2、ai-1结点的指针域指向s结点,(2),(3.1),(3.2),（4）插入运算（在ai（0in）之前插入一个数据元素x）,不可以！,（3.1）和（3.2）可不可以交换？为什么？,？,p=p-next;j+;,while(p-next!=NULL,1614,10CB,s-next=p-next;,s-data=x;,s=(SLNode*)malloc(sizeof(SLNode);,intListInsert(SLNode*head,inti,DataTypex)SLNode*p,*s;intj;p=head;j=-1;while(p-next!=NULL),用c语言实现的单链表插入算法,定义变量并初始化,搜索表，寻找ai-1结点,if(j!=i-1)printf(“n插入位置不合理！”);return0;if(s=(SLNode*)malloc(sizeof(SLNode)=NULL)return0;s-data=x;s-next=p-next;p-next=s;return1;,插入位置不合理,判断是否申请到新结点,将该结点插入到ai结点之前,（5）单链表的删除（删除第i（0in-1）个结点）,1500,s=p-next;,p-next=s-next;,free(s);,p=p-next;j+;,while(p-next!=NULLreturn0;s=p-next;*x=s-data;p-next=p-next-next;free(s);return1;,删除位置不合理,将ai结点删除,释放s结点空间,作业：,编写单链表的删除操作算法ListDeleteMore（L,x），要求删除线性表L中所有等于x的数据元素。,(6)单链表的创建尾接法,130A,1475,for(j=0;jdata=aj;s-next=NULL;p-next=s;p=s;,开始,N,Y,尾接法创建单链表流程图,intCreatL1(SLNode*h,DataTypea,intn)SLNode*p,*s;inti,j;i=ListInitiate(h);if(i=0)return0;p=*h;for(j=0;jdata=aj;s-next=NULL;p-next=s;p=s;return1;,a0,NULL,130A,a1,130A,1475,for(j=0;jdata=aj;s-next=(*h)-next;(*h)-next=s;,(6)单链表的创建头插法,开始,N,Y,头插法创建单链表流程图,intCreatL2(SLNode*h,DataTypea,intn)SLNode*s;inti,j;i=ListInitiate(h);if(i=0)return0;for(j=0;jdata=aj;s-next=(*h)-next;(*h)-next=s;return1;,2.3.5循环单链表,非空表,空表,head-next=head,2.3.6双向循环链表,typedefstructNodeDataTypedata;structNode*prior,*next;DLNode;,要点回顾,线性表的链式存储链表,单链表结点,数据域,指针域,单链表的初始化、插入、删除、头插法及尾插法创建单链表,讨论,线性表逻辑结构特点是：只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。,问1：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点分别是什么？,答：,顺序存储时，相邻数据元素的存放地址也相邻（逻辑结构与物理结构统一）；要求内存中可用存储单元的地址必须是连续的。,链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。,顺序存储的优点是存储密度大(1)，存储空间利用率高。缺点是插入或删除元素时不方便。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（Listj=x)for(k=j;knum;k+)la-Listk=la-Listk+1;la-num-;j-;,删除顺序表a中第i(i0)个元素起的k个元素。,#defineMAX100typedefintDataType;typedefstructDataTypeListMAX;intnum;/*最后一个数据元素的下标*/SeqList;,应用实例2,intDeleteK(SeqList*a,inti,intk)intj;if(a-numa-num)return0;elsefor(j=i;jnum-k;j+)a-Listj=a-Listj+k;a-num=a-num-k;return1;,/*判断表是否为空*/,/*判断删除位置、个数是否合理*/,/*删除从第i个元素开始的k个元素*/,在有序顺序表(递增)中插入值为x的数据元素以保持顺序表的有序性。,#defineMAX100typedefintDataType;typedefstructDataTypeListMAX;intnum;/*最后一个数据元素的下标*/SeqList;,应用实例3,intOrderlnsert(SeqList*L,DataTypex)inti;if(L-num=MAX-1)printf(“顺序表已满”);return0;elsefor(i=L-num;i=0,实现单链表的就地逆序。设其头结点的指针为head，编写一个算法将单链表逆置。,应用实例4,typedefstructnodeDataTypedata;structnode*next;SLNode;,单链表的就地逆置,p,q,q,q,p,p,p,voidreverse(SLNode*head)SLNode*p,*q;p=head-next;head-next=NULL;while(p!=NULL)q=p;p=p-next;q-next=head-next;head-next=q;,已知线性表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素合并为一个新的线性表lc，lc中的数据元素仍按非递减有序排列，并要求不破坏la和lb表。,例如：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),应用实例5,typedefstructDataTypeListMaxlen;intnum;qltype;,方法一：采用顺序表结构,intmergeql(qltypela,qltypelb,qltype*lc)inti,j,k;if(la.num+1+lb.num+1Maxlen)printf(“n数组下界溢出！”);return0;i=j=k=0;while(ilistk+=la.listi+;elselc-listk+=lb.listj+;,while(ilistk+=la.listi+;while(jlistk+=lb.listj+;lc-num=k-1;return1;,typedefstructnodeDataTypedata;structnode*next;slnode;,方法二：采用单链表结构,La,Pa、Pb用于搜索La和Lb，Pc指向新链表当前结点,intmergesl(slnode*la,slnode*lb,slnode*lc)slnode*pa,*pb,*pc;if(*lc=(slnode*)malloc(sizeof(slnode)=NULL)printf(“n分配内存失败！”);return0;pa=la-next;pb=lb-next;pc=*lc;,whil