线性逻辑结构

1、2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作1第第2章章 线线 性性 表表q2.1 线性表的逻辑结构q2.2 线性表的顺序存储结构q2.3 线性表的链式存储结构q2.4 顺序表和链表的比较q2.5 习题2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作22.1 线性表的逻辑结构o 1线性表的定义q线性表是n(n0)个结点组成的有限序列。从这个定义中应当理解到以下几点：q线性表中的元素是有顺序的；q线性表中的元素个数可以为0，即可以是空的线性表；q线性表中的元素可以是多个，但不能是无穷多个；q同一个线性

2、表中元素的类型相同，因此元素长度也相同。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作3o 2线性表的特点q 任意一个非空的线性表都具有以下特点：q 只有一个排在第一个的元素，称为线性表的起始元素。q 只有一个排在最后的元素，称为线性表的终端元素。q 除起始元素外，线性表中的其他元素仅有一个直接前驱元素；除终端元素外，线性表中的其他元素仅有一个直接后继元素。o 3线性表的逻辑表示形式q 线性表的逻辑表示形式如下:q l1=( )：l1是一个空的线性表；q l2=(a,b,c,d,e)：l2线性表中有5个元素，a是起始元素、e是终端元素，c的直接前

3、驱元素是b，c的直接后继元素是d。a元素的序号是1，c元素的序号是3。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作4w 4线性表的基本运算q initlist(l)：初始化运算，其功能是创建了一个空的线性表l。q listlength(l)：求线性表l的长度运算。q getnode(l,i)：读元素运算，函数值是线性表l的第i个元素。q locatenode(l,x)：定位运算，是线性表l中x元素的位置。q insertlist(l,x,i)：插入运算，其功能是将x插入线性表l中，作为线性表l的第i个元素。q deletelist(l,i)：删

4、除运算，将线性表l的第i个元素删除。q clear(l)：清除表元素运算，其功能是删除 l表中的元素，使线性表l成为空表。q empty(l)：判断l表是否是空表，其功能是l表为空时函数值为1，否则为0。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作52.2 线性表的顺序存储结构o 2.2.1 线性表顺序存储结构的概念q 顺序表:q 将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元内，采用这种方法存储的线性表简称为顺序表。 顺序表的虚拟存储是采用程序设计语言的一维数组来存储线性表。 顺序表是存储在一段连续的空间内，逻辑上相邻的元素在存储位

5、置上也相邻。 q 提示：用loc(ai)表示线性表元素ai的存储空间的起始地址，若l表示一个元素的长度，则对于正整数i有：loc(ai+1)= loc(ai)+ l若线性表的起始地址是b，则：loc(ai)=b+(i-1)*l 或者 loc(ai)= loc(a1)+(i-1)*l2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作62007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作72007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作81顺序表的类型定义struct

6、 sqlist datetype elemmaxlen; int length;其中datetype表示线性表元素的抽象数据类型，用程序设计语言上机实现算法时，再定义为具体的数据类型。maxlen表示线性表最多允许的元素个数。length表示线性表的当前长度。其值是0至maxlen间的一个整数。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作92. 运算的算法插入运算的算法(算法2.1) insert_sqlist(struct qlist l, datetype x, int i) if(il.length+1) error(illegal va

7、lue of i); /*插入位置i不正确*/ else if(l.length = maxlen) error(list overflow) ; /*表满*/ else /*将线性表的最后一个元素至第i个元素均向后移一个位置*/ for(k=l.length-1; k=i-1; k-) l.elemk+1= l.elemk; l.elemi-1=x ; /*将x插入线性表的第i个位置*/ l.length+ ; /*线性表长度加1*/ 插入算法的时间复杂度为o(n)。 2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作102. 运算的算法删除运算的

8、算法(算法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个元素至最后一个元素均向前移一个位置*/ for(k=i;knext=null; /* l指向的结点作为链表的表头结点，空链表表头结点的指针域为空 */2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，

9、欢迎收藏电子信息系黄力明制作14q 求表长运算的算法(算法2.4)int listlength(list l) p=l ; /* p是指针类型变量，开始时p指向表头结点*/ j=0; /* j是整型变量，用它记录着结点的个数*/ while(p-next!=null) p=p-next ; /* 让指针变量p指向链表的下一个结点*/ j+; /* j记录的个数加1*/ return(j); /* j的最后的值是链表的长度*/2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作15q 读元素运算的算法(算法2.5)pointer getnode(list

10、 l, int i) p=l;j=0;while(p-next!=null)&(jnext; j+;if(i=j) return(p); /* 找到了第i个结点，返回p指针*/else return(null); /* 返回空指针*/2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作16q 插入运算的算法(算法2.6)void insertlist(list l, datatype x, int i) p=l;j=0;while(p!=null)&(jnext;j+; /* 使指针p指向第i-1个结点*/if(p=null) prin

11、tf(第i-1个结点不存在); /* i值不正确*/else s=(struct node *)malloc(sizeof(struct node);/* 申请一个结点s */ s-data=x; /* 将x送入新结点 */ s-next=p-next; /* 使新结点指向链表的原第i个结点 */ p-next=s; /* 使链表的原第i-1个结点指向新结点 */2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作17q 删除运算的算法(算法2.7)datatype deletelist(list l, int i)p=l;j=0;while(p!=n

12、ull)&(jnext;j+; /* 使指针p指向第i-1个结点*/if(!p & p-next!=null) printf(第i-1个结点不存在); /* i值不正确*/else q=p-next; /*使指针q指向第i个结点 */ p-next=q-next; /*使链表的原第i-1个结点指向第i+1个结点*/ x=q-next; /*使删除结点的值赋给x */ free(q); /*释放被删除结点的空间 */ return(x); /*返回被删除结点的值 */2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作18q2.3.2 循

13、环链表q提示：单链表的尾结点的指针域(next)是空指针，如果将该指针域改为指向表头结点的指针，则该链表就是循环链表。q提示：循环链表的算法与单链表的算法基本相同，只是单链表l是空链表的条件是:ql-next=null，而循环链表l是空链表的条件是l-next=l。图2.4 循环链表2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作19w 2.3.3 双向链表o 提示：如果将循环链表的每个结点都设置指向前驱和指向后继的指针，则该链表就是双向循环链表。o 1双向链表结点的数据结构o typedef struct dulnode *pointer;o t

14、ypedef struct dulnodeo o datatype data;o pointer prior,next;o dulnode;2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作20图2.5 双向链表2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作212双向链表运算的算法双向链表删除的算法(算法2.8)datatype deletelist_dul(dulnode *l,dulnode *p)/*删除双向链表l中p指针所指的元素，并将被删除的结点的值作为函数值返回*/ x=p-data; /*

15、 使删除结点的值赋给x */ p-prior-next=p-next; /* 使p结点的前驱结点的后继指针指向p结点的后继结点*/ p-next-prior=p-prior; /* 使p结点的后继结点的向前指针指向p结点的前驱结点*/ free(p); /* 释放p所指被删除的结点 */ return (x); /* 返回被删除结点的值 */2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作22在双向链表l中插入元素的算法(算法2.9)inserterlist_dul(dulnode *l,dulnode *p, datatype e) /*将e元素

16、插入到双向链表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结点的前驱指针指向新结点*/ 2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力

17、明制作232.5 习 题一、填空题(1) 链表中逻辑上相邻的元素的物理位置_相连。(2) 在单链表中除首结点外，任意结点的存储位置都由_结点中的指针指示。(3) 在单链表中，设置头结点的作用是在插入或删除首结点时不必对_进行处理。(4) 已带表头结点的单链表l，指针p指向l链表中的一个结点，指针q是指向l链表外的一个结点，则： 在指针p所指结点后插入q所指结点的语句序列是_； 在指针p所指结点前插入q所指结点的语句序列是_； 将q所指结点插入在链表首结点的语句序列是_； 将q所指结点插入在链表尾结点的语句序列是_。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信

18、息系黄力明制作24(5) 已知带表头结点的单链表l，指针p指向l链表中的一个结点(非首结点非尾结点)，则： 删除指针p所指结点的直接后继结点的语句是_； 删除指针p所指结点的直接前驱结点的语句序列是_； 删除指针p所指结点的语句序列是_； 删除首结点的语句序列是_； 删除尾结点的语句序列是_。(6) 已知指针p指向双向链表中的一个结点(非首结点，非尾结点)，则： 将结点s插入在指针p所指结点的直接后继位置的语句是_； 将结点s插入在指针p所指结点的直接前驱位置的语句是_； 删除指针p所指结点的直接后继结点的语句序列是_； 删除指针p所指结点的直接前驱结点的语句序列是_； 删除指针p所指结点的语

19、句序列是_。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作25(7) 线性表的存储结构有顺序存储和_存储两种。(8) 线性表的元素长度为4，在顺序存储结构下loc(ai)=2000，则loc(ai+1)= _。(9) 线性表a的元素长度为l，在顺序存储结构下loc(ai)=loc(a1)+_。(10) 在线性表的链式存储结构中，某结点的指针字段指向该结点的_两种存储。(11) 线性表的元素长度为4，loc(a1)=1000，则loc(a3)= _。(12) 在下图所示的链表中，若在指针p所指的结点之后插入数据字段相继为a和b的两个结点，则可用下列

20、两个语句实现该操作，它们依次是_和_。2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作262007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作27二、选择题2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作282007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作292007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作302007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分

21、享，欢迎收藏电子信息系黄力明制作312007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作322007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作33三、简答题（1）在什么情况下使用顺序表比链表好？（2）已知带表头的单链表l，简述下列对l链表操作算法的功能。 status a(l)if(l-next & l-next-next) q=l-next;l=q-next;p=q; while(p-next) p=p-next;p-next=q; q-next=null;return ok;2007年8月12日星期日行业报告 多媒体课件 豆丁网友友情分享，欢迎收藏电子信息系黄力明制作34(3) 已知带表头的循环链表l，简述下列对l链表操作算法的功能。void