《线性表逻辑结构ppt课件》由会员分享，可在线阅读，更多相关《线性表逻辑结构ppt课件（38页珍藏版）》请在金锄头文库上搜索。
1、第第2章章 线线 性性 表表q2.1 线性表的逻辑构造q2.2 线性表的顺序存储构造q2.3 线性表的链式存储构造q2.4 顺序表和链表的比较q2.5 习题2.1 线性表的逻辑构造o1线性表的定义o线性表是n(n0)个结点组成的有限序列。从这个定义中该当了解到以下几点：o线性表中的元素是有顺序的；o线性表中的元素个数可以为0，即可以是空的线性表；o线性表中的元素可以是多个，但不能是无穷多个；o同一个线性表中元素的类型一样，因此元素长度也一样。o2线性表的特点o恣意一个非空的线性表都具有以下特点：o只需一个排在第一个的元素，称为线性表的起始元素。o只需一个排在最后的元素，称为线性表的终端元素。o
2、除起始元素外，线性表中的其他元素仅有一个直接前驱元素；除终端元素外，线性表中的其他元素仅有一个直接后继元素。o3线性表的逻辑表示方式o线性表的逻辑表示方式如下:oL1=( )：L1是一个空的线性表；oL2=(a,b,c,d,e)：L2线性表中有5个元素，a是起始元素、e是终端元素，c的直接前驱元素是b，c的直接后继元素是d。a元素的序号是1，c元素的序号是3。w4线性表的根本运算wInitList(L)：初始化运算，其功能是创建了一个空的线性表L。wListLength(L)：求线性表L的长度运算。wGetNode(L,i)：读元素运算，函数值是线性表L的第i个元素。wLocateNode(L
3、,X)：定位运算，是线性表L中X元素的位置。wInsertList(L,X,i)：插入运算，其功能是将X插入线性表L中，作为线性表L的第i个元素。wDeleteList(L,i)：删除运算，将线性表L的第i个元素删除。wClear(L)：去除表元素运算，其功能是删除 L表中的元素，使线性表L成为空表。wEmpty(L)：判别L表能否是空表，其功能是L表为空时函数值为1，否那么为0。2.2 线性表的顺序存储构造o2.2.1 线性表顺序存储构造的概念o顺序表:o将线性表的结点按逻辑次序依次存放在一组地址延续的存储单元内，采用这种方法存储的线性表简称为顺序表。o顺序表的虚拟存储是采用程序设计言语的一
4、维数组来存储线性表。o顺序表是存储在一段延续的空间内，逻辑上相邻的元素在存储位置上也相邻。 o提示：用LOC(ai)表示线性表元素ai的存储空间的起始地址，假设L表示一个元素的长度，那么对于正整数i有：LOC(ai+1)= LOC(ai)+ L假设线性表的起始地址是b，那么：LOC(ai)=b+(i-1)*L 或者 LOC(ai)= LOC(a1)+(i-1)*L1顺序表的类型定义struct sqlist datetype elemmaxlen; int length;其中datetype表示线性表元素的笼统数据类型，用程序设计言语上机实现算法时，再定义为详细的数据类型。maxlen表示线性
5、表最多允许的元素个数。length表示线性表的当前长度。其值是0至maxlen间的一个整数。2. 运算的算法插入运算的算法(算法2.1) Insert_sqlist(struct qlist L, datetype x, int i) if(iL.length+1) error(illegal value of i); /*插入位置i不正确*/ else if(L.length = Maxlen) error(List overflow) ; /*表满*/ else /*将线性表的最后一个元素至第i个元素均向后移一个位置*/ for(k=L.length-1; k=i-1; k-) L.ele
6、mk+1= L.elemk; L.elemi-1=x ; /*将x插入线性表的第i个位置*/ L.length+ ; /*线性表长度加1*/ 插入算法的时间复杂度为O(n)。 2. 运算的算法删除运算的算法(算法2.2)elemtype Delete_sqlist(struct sqlist L, int i) if(iL.length) error(illegal value of i); /*删除元素的序号i不 正确*/ else if(L.length = 0) error(List empty); /*表空*/ else x=L.elemi-1; /*将线性表的第i+1个元素至最后一个
7、元素均向前移一个位置*/ for(k=i;knext=null; /* L指向的结点作为链表的表头结点，空链表表头结点的指针域为空 */q求表长运算的算法(算法2.4)qint ListLength(LIST L)q q p=L ; /* p是指针类型变量，开场时P指向表头结点*/q j=0; /* j是整型变量，用它记录着结点的个数*/q while(p-next!=null)q q p=p-next ; /* 让指针变量P指向链表的下一个结点*/q j+;q /* j记录的个数加1*/q return(j); /* j的最后的值是链表的长度*/qq读元素运算的算法(算法2.5)qpoint
8、er GetNode(LIST L, int i) qqp=L;qj=0;qwhile(p-next!=null)&(jnext;q j+;qqif(i=j) return(p); /* 找到了第i个结点，前往P指针*/qelse return(null); /* 前往空指针*/qq插入运算的算法(算法2.6)qvoid InsertList(LIST L, datatype x, int i) qqp=L;qj=0;qwhile(p!=null)&(jnext;qj+;q /* 使指针p指向第i-1个结点*/qif(p=null) printf(第i-1个结点不存在); /* i值不正确*/
9、qelse qq s=(struct node *)malloc(sizeof(struct node);/* 恳求一个结点s */q s-data=x; /* 将x送入新结点 */ q s-next=p-next; /* 使新结点指向链表的原第i个结点 */q p-next=s; /* 使链表的原第i-1个结点指向新结点 */qqq删除运算的算法(算法2.7)qDatatype DeleteList(LIST L, int i)qqp=L;qj=0;qwhile(p!=null)&(jnext;qj+;q /* 使指针p指向第i-1个结点*/qif(!p & p-next!=null) pr
10、intf(第i-1个结点不存在); /* i值不正确*/qelse qq q=p-next; /*使指针q指向第i个结点 */q p-next=q-next; /*使链表的原第i-1个结点指向第i+1个结点*/q x=q-next; /*使删除结点的值赋给x */q free(q); /*释放被删除结点的空间 */q return(x); /*前往被删除结点的值 */qqq2.3.2 循环链表q提示：单链表的尾结点的指针域(next)是空指针，假设将该指针域改为指向表头结点的指针，那么该链表就是循环链表。q提示：循环链表的算法与单链表的算法根本一样，只是单链表L是空链表的条件是:qL-next
11、=null，而循环链表L是空链表的条件是L-next=L。图2.4 循环链表w2.3.3 双向链表w提示：假设将循环链表的每个结点都设置指向前驱和指向后继的指针，那么该链表就是双向循环链表。w1双向链表结点的数据构造wtypedef struct DuLNode *pointer;wtypedef struct DuLNodewwdatatype data;wpointer prior,next;w DuLNode;图2.5 双向链表2双向链表运算的算法双向链表删除的算法(算法2.8)Datatype DeleteList_DuL(DuLNode *L,DuLNode *p)/*删除双向链表L
12、中p指针所指的元素，并将被删除的结点的值作为函数值前往*/ x=p-data; /* 使删除结点的值赋给x */ p-prior-next=p-next; /* 使p结点的前驱结点的后继指针指向p结点的后继结点*/ p-next-prior=p-prior; /* 使p结点的后继结点的向前指针指向p结点的前驱结点*/ free(p); /* 释放p所指被删除的结点 */ return (x); /* 前往被删除结点的值 */在双向链表L中插入元素的算法(算法2.9)InserterList_DuL(DuLNode *L,DuLNode *p, Datatype e) /*将e元素插入到双向链表
13、L中p指针所指的元素的前边*/s=(struct DuLNode *)malloc(sizeof(struct DuLNode); /* 恳求一个结点，让指针s指向它*/s-data=x; /* 将x送入新结点*/ s-next=p; /* 使新结点的后继指针指向p结点*/s-prior=p-prior; /* 使新结点的前驱指针指向p结点的前驱结点*/p-prior-next=s; /* 使p结点的前驱结点的后继指针指向新结点*/p-prior=s; /* 使p结点的前驱指针指向新结点*/ 2.5 习 题一、填空题(1) 链表中逻辑上相邻的元素的物理位置_相连。(2) 在单链表中除首结点外，
14、恣意结点的存储位置都由_结点中的指针指示。(3) 在单链表中，设置头结点的作用是在插入或删除首结点时不用对_进展处置。(4) 已带表头结点的单链表L，指针p指向L链表中的一个结点，指针q是指向L链表外的一个结点，那么： 在指针p所指结点后插入q所指结点的语句序列是_； 在指针p所指结点前插入q所指结点的语句序列是_； 将q所指结点插入在链表首结点的语句序列是_； 将q所指结点插入在链表尾结点的语句序列是_。(5) 知带表头结点的单链表L，指针p指向L链表中的一个结点(非首结点非尾结点)，那么： 删除指针p所指结点的直接后继结点的语句是_； 删除指针p所指结点的直接前驱结点的语句序列是_； 删除
15、指针p所指结点的语句序列是_； 删除首结点的语句序列是_； 删除尾结点的语句序列是_。(6) 知指针p指向双向链表中的一个结点(非首结点，非尾结点)，那么： 将结点s插入在指针p所指结点的直接后继位置的语句是_； 将结点s插入在指针p所指结点的直接前驱位置的语句是_； 删除指针p所指结点的直接后继结点的语句序列是_； 删除指针p所指结点的直接前驱结点的语句序列是_； 删除指针p所指结点的语句序列是_。(7) 线性表的存储构造有顺序存储和_存储两种。(8) 线性表的元素长度为4，在顺序存储构造下LOC(ai)=2000，那么LOC(ai+1)= _。(9) 线性表a的元素长度为L，在顺序存储构造
16、下Loc(ai)=Loc(a1)+_。(10) 在线性表的链式存储构造中，某结点的指针字段指向该结点的_两种存储。(11) 线 性 表 的 元 素 长 度 为 4， Loc(a1)=1000， 那 么 Loc(a3)= _。(12) 在以下图所示的链表中，假设在指针p所指的结点之后插入数据字段相继为a和b的两个结点，那么可用以下两个语句实现该操作，它们依次是_和_。二、选择题三、简答题1在什么情况下运用顺序表比链表好？2知带表头的单链表L，简述以下对L链表操作算法的功能。 Status a(L)if(L-next & L-next-next) q=L-next;L=q-next;p=q; wh
17、ile(p-next) p=p-next;p-next=q; q-next=NULL;return OK;(3) 知带表头的循环链表L，简述以下对L链表操作算法的功能。void BB(s,q) /* s、q是指向结点类型的指针 */p=s;while(p-next!=q) p=p-next;p-next=s;void AA(pa,pb) /* pa、pb是指向单向循环表中的两个结点的指针 */BB(pa,pb;BB(pb,pa);(4) 分别画出线性表L=(a，b，c)存储在单链表、循环链表、双向循环链表中的表示图。(5) 哪些链表从尾指针出发可以访问到链表中的恣意结点？四、算法设某带头结点的
18、单链表的结点构造阐明如下：typedef struct node1 int data; struct node1 *next;node;试设计一个算法：void copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个以head2为头指针的单链表中。(2) 设有两个按升序陈列的单链表X和Y，其头指针分别为p、q，结点构造阐明如下：typedef struct node1 intdata; struct node1 * next node;试设计一个算法void concat(node p, q)，将它们合并成一个以p为头指针的单链表Z，使其依然有序。
