数据结构第2章线性表.ppt

1,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,an）,简言之，线性结构反映结点间的逻辑关系是的。,特点只有一个首结点和尾结点；特点除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,见第2章,一对一(1:1),2,（a1,a2,ai-1，ai,ai1，,an）,2.1线性表的逻辑结构,1.线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,3,例1分析26个英文字母组成的英文表是什么结构。,（A,B,C,D,Z）,例2分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,4,2.2.1顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现。,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从V0Vn-1,5,线性表顺序存储特点：,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）,对上述公式的解释如图所示：,6,线性表的顺序存储结构示意图,地址内容元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,b+(max-1)L,7,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,113,例1,因此：LOC(M3)=98+5(3-0)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,8,2.2.2顺序表的实现（或操作）,回忆：数据结构基本运算操作有：修改、插入、删除、查找、排序,1)修改通过数组的下标便可访问某个特定元素并修改之。,核心语句:Vi=x;,显然，顺序表修改操作的时间效率是T(n)=O(1),9,2)插入在线性表的第i个位置前插入一个元素,实现步骤：将第n至第i位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。注意：事先应判断:插入位置i是否合法?表是否已满?应当有1in+1或i=1,n+1,for(j=n;j=i;j-)aj+1=aj;ai=x;n+;,/元素后移一个位置,/插入x,/表长加1,核心语句：,10,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,11,实现步骤：将第i+1至第n位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i是否合法?应当有1in或i=1,n,3)删除删除线性表的第i个位置上的元素,for(j=i+1;jdata=a;p-next=q;方式3：p指向结点首地址，然后(*p).data=a；(*p).nextq,22,3.补充结构数据类型的C表示法,类型定义和变量说明可以合写为：typedefstructchy/chy是自定义结构类型名称chardata;/定义数据域的变量名及其类型structchy*next;/定义指针域的变量名及其类型node，*head;/node是chy结构类型的变量,*head是chy结构类型的头指针/,对于指向结构变量node首地址的指针，可说明为：structnode*p,*q;/或用structchy*p,*q;/注：上面已经定义了node为用户自定义的chy类型。,23,介绍三个有用的库函数（都在中）：sizeof(x)计算变量x的长度；malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)释放指针p所指变量的存储空间，即彻底删除一个变量。,设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。,练习：,p-data,ai的值,p-next,ai+1的地址,24,sizeof(x)计算x的长度malloc(m)开m字节空间free(p)删除一个变量,问1：自定义结构类型变量node的长度m是多少？,问2：结构变量node的首地址(指针p）是多少？,问3：怎样删除结构变量node？,msizeof(node),p(node*)malloc(m),free(p)/只能借助其指针删除！,p-data=a;p-next=q,25,2.3.2链表的实现,1.单链表的建立和输出2.单链表的修改3.单链表的插入4.单链表的删除5.链表插入删除实例6.其他链表形式,26,1.单链表的建立和输出,实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址也要及时送给前面的指针。,先挖“坑”,后种“萝卜”！,27,将全局变量及函数提前说明：,#include#includetypedefstructnodechardata;structnode*next;node;node*p,*q,*head;/一般需要3个指针变量intn;/数据元素的个数intm=sizeof(node);/结构类型定义好之后，每个变量的长度就固定了，m求一次即可*/,28,voidbuild()/字母链表的生成。要一个个慢慢链入,inti;head=(node*)malloc(m);/m=sizeof(node)前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点“挖坑”！p=p-next；/让指针变量P指向后一个结点p-data=i+a-1;/最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！,29,voiddisplay()/*字母链表的输出*/,p=head;while(p)/当指针不空时循环，仅限于无头结点的情况printf(%c,p-data);p=p-next;/让指针不断“顺藤摸瓜”,讨论：要统计链表中数据元素的个数，该如何改写？,sum+;,sum=0;,30,2.单链表的修改(或读取）,思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能：p-data=new_value。,缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取。,核心语句：见教材的函数说明,StatusGetElem_L(LinkListL,inti,ElemType,31,3.单链表的插入,在链表中插入一个元素x的示意图如下：,链表插入的核心语句：,Step1：s-next=p-next;Step2：p-next=s；,p-next,s-next,思考：Step1和2能互换么？,x结点的生成方式：S=(node*)malloc(m);S-data=x;S-next=p-next,32,4.单链表的删除,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q=p-next;/首先保存b的指针，靠它才能找到c；p-next=q-next;/将a、c两结点相连，淘汰b结点；free(q)；/彻底释放b结点空间,p-next,思考：省略free(q)语句行不行？,(p-next)-next,q,33,讨论1：链表能不能首尾相连？怎样实现？,答：能。只要将表中最后一个结点的指针域指向头结点即可(P-next=head;)。这种形成环路的链表称为循环链表。,特别：带头结点的空循环链表之样式,参见教材P27,特点：1、从任一结点出发均可找到表中其他结点。2、操作仅循环条件与单链表不同：单链表-p=NULL或p-next=NULL循环链表-p=head或p-next=head,34,讨论2：单链表只能查找结点的直接后继，若想查找结点的直接前驱，该如何设计？,答：只要把单链表再多开一个指针域即可(如用*next和*prior)。,这种链表称为双向链表。其特点是可以双向查找表中结点。参见教材P16。,特别：带头结点的空双向循环链表样式：,想一想：双链表和双向链表有何不同？,35,2.3.3链表的运算效率分析,1.查找因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。,时间效率分析,2.插入和删除因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。,但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是O(n)。,36,练：,空间效率分析,链表中每个结点都要增加一个指针空间，相当于总共增加了n个整型变量，空间复杂度为O(n)。,在n个结点的单链表中要删除已知结点*P，需找到它的，其时间复杂度为。,前驱结点的地址,O(n),37,2.4应用举例,一元多项式的数学通式？用抽象数据类型如何描述它的定义？用C语言如何描述它的定义？如何编程实现两个一元多项式相加？,一元多项式的计算(参见教材P3436),讨论：,38,但当多项式的次数很高且零系数项很多时，更适于用链表存储。,1.一元多项式的数学通式？,一元多项式的通式可表示为：,分析：一元多项式在计算机内存储时，一般用顺序表存储。,顺序表（只存系数项）,链表形式,或,通常