线性表.ppt

《线性表.ppt》由会员分享，可在线阅读，更多相关《线性表.ppt（79页珍藏版）》请在三一文库上搜索。

1、第2章 线性表,主要内容,线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 一元多项式的表示及相加,重点与难点,本章的重点 掌握顺序表和单链表上实现基本操作的算法。 本章的难点 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。,线性结构的特点,在数据元素的非空有限集中 存在唯一的一个被称做“第一个”的数据元素； 存在唯一的一个被称做“最后一个”的数据元素； 除第一个之外，集合中的每个数据元素均只有一个前驱； 除最后一个之外，集合中每个数据元素均只有一个后继。,2.1 线性表的逻辑结构,线性表的定义 线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有

2、限序列:（a1,a2,a3,an） 数据元素可以是一个数、一个符号、也可以是一幅图、一页书等。 数据元素也可由若干个数据项组成,这时常把数据元素称为记录,含有大量记录的线性表又称文件。,在数据元素的非空有限集中线性表中的数据元素类型多种多样； 同一线性表中的元素必定具有相同特性，即属同一数据对象； 相邻数据元素之间存在着序偶关系：ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。,2.1 线性表的逻辑结构,抽象数据类型线性表的定义如下： ADT List 数据对象: D=ai| ai(-ElemSet,i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D,i=2,

3、.,n 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表已经存在。 操作结果：销毁线性表L。,2.1 线性表的逻辑结构,ClearList(&L) 初始条件：线性表已经存在。 操作结果：将L重置为空表。 ListEmpty(L) 初始条件：线性表已经存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。 ListLength(L) 初始条件：线性表已经存在。 操作结果：返回L中数据元素的个数。 GetElem(L,i,&e) 初始条件：线性表已经存在，1=i=ListLength(L). 操作结果：用e返回第i

4、个数据元素的值。,2.1 线性表的逻辑结构,LocateElem(L,e,compare() 初始条件：线性表已经存在，compare()是数据元素的判定函数。 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，若这样的数据元素不存在则返回值为0。 PriorElem(L,cur_e,&pre_e) 初始条件：线性表已经存在。 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 NextElem(L,cur_e,&next_e) 初始条件：线性表已经存在。 操作结果：若cur_e是L的数据元素，且不是最后一个，则

5、用next_e返回它的后继，否则操作失败，next_e无定义,2.1 线性表的逻辑结构,ListInsert(&L,i,e) 初始条件：线性表已经存在，=i=ListLength(L)+1. 操作结果：在中第i个元素位置之前插入新的数据元素e，的长度加。 ListDelete(&L,i,&e) 初始条件：线性表已经存在且非空，=i=ListLength(L). 操作结果：删除的第i个数据元素，并用e返回其值，的长度减。 ListTraverse(L,visit() 初始条件：线性表已经存在。 操作结果：依次对的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。 ADT L

6、ist,2.1 线性表的逻辑结构,2.1 线性表的逻辑结构,部分操作的类C实现（详见2-1.c） 例2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。 例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。,2.1 线性表的逻辑结构,例2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。 LA=(3,20,67,5,8, 55,32) LB=(60,5,30,22,8) LA=( 3,20,67,5,8, 55,32,60,30,22)

7、,2.1 线性表的逻辑结构,步骤描述（用自然语言描述） 1 从B中取出一个元素e; 2 查找A中是否存在该元素e？ 3 若A中有元素e，转向4；否则，将该元素e插入到A； 4 判断B中元素是否取完？ 5 若没有取完，转向1；否则，转向6； 6 结束。,2.1 线性表的逻辑结构,步骤描述（用类C语言描述） void union(List ,2.1 线性表的逻辑结构,例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 LA=(3,5,8,11)/非递减有序 LB=(2,6,8,9,11,15,20)

8、LC=(2,3,5,6,8,8,9,11,11,15,20),2.1 线性表的逻辑结构,步骤描述（用自然语言描述） 1 初始化一张新的线性表LC; 2 分别从LA、LB中取出元素ai、bj; 3 比较ai、bj的大小？ 4 若ai小，则将ai插入到LC，取LA中的下一个元素；否则将bj插入到LC，取LB中的下一个元素； 5 若LA、LB中的元素均未取完，转向3；否则转向6； 6 若LA未取完元素，将剩余元素依次插入到LC； 7 若LB未取完元素，将剩余元素依次插入到LC； 8 结束。,2.1 线性表的逻辑结构,步骤描述（用类C语言描述） void MergeList(List La,List

9、Lb,List ,2.2 线性表的顺序表示和实现,线性表的顺序表示 用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。,2.2 线性表的顺序表示和实现,C语言中的数组即采用顺序存储方式。,2.2 线性表的顺序表示和实现,2.2 线性表的顺序表示和实现,顺序表的特点 以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem;/存储空间基址 int length;

10、 /当前长度 int listsize;/当前分配的存储容量以一数据元素存储长度为单位 SqList;,2.2 线性表的顺序表示和实现,顺序表的插入与删除操作,2.2 线性表的顺序表示和实现,顺序表的插入算法ListInsert( /*ListInsert Before i */,2.2 线性表的顺序表示和实现,顺序表的删除算法ListDelete( ,2.2 线性表的顺序表示和实现,顺序表的构造算法 Status InitList_sq(SqList ,2.2 线性表的顺序表示和实现,顺序表中指定元素的定位算法 int LocateElem_sq(SqList l,ElemType e, S

11、tatus(*compare)(ElemType,ElemType) /在顺序线性表L中查找第1个值与e满足compare()的元素的位置,若找到返回该元素位置,若找不到,返回0 i=1;/初始查找位置 p=L.elem;/p的初值为第1个元素的存储位置 while(i=L.length ,2.2 线性表的顺序表示和实现,例2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。(顺序存储) void UnionList(SqList La, SqList Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i

12、=0;iLb_len;i+)/从Lb中依次取出元素，若不在La中则插入。 GetElem(Lb,i, ,2.2 线性表的顺序表示和实现,例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 (顺序存储) void MergeList(SqList La,SqList Lb,List /将Lb中的所有剩余元素插入到Lb ,2.2 线性表的顺序表示和实现,算法设计典型题目 集合的相关运算：并集、交集、差集 两张表的按条件合并 删除指定位置或指定条件的元素 一张表的有条件拆分 算法的核心操作 插入 删除,

13、2.3 线性表的链式表示和实现,顺序存储结构： 优点无需为表示结点间的逻辑关系而增加额外的存储空间；可方便地随机存取表中的任一元素。 缺点插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低； 由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。,2.3 线性表的链式表示和实现,线性链表的特点 该线性表中的数据元素可用任意的存储单元来存储。线性表中逻辑相邻两元素的存储空间可以是不连续的。 除存储本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素的存储映象，称为结

14、点。(D,R),2.2 线性表的链式表示和实现,C语言中的链表即采用非顺序存储方式,2.3 线性表的链式表示和实现,用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示。,2.3 线性表的链式表示和实现,线性链表的分类： 从实现角度看，链表可分为：动态链表、静态链表； 从链接方式的角度看，链表可分为：单向链表、单向循环链表、双向链表、双向循环链表。,2.3 线性表的链式表示和实现,线性单向链表的存储实现： #define LIST_INIT_SIZE 100 struct LNODE ElemType data; struct LNODE *next; ; typedef str

15、uct LNODE LNode; typedef struct LNODE * LinkList;,2.3 线性表的链式表示和实现,注意： 区别指针变量、结点变量 区别头指针、头结点（不带头结点链表、带头结点链表） 内存分配： p=(LNode *)malloc(sizeof(LNode); 内存释放： free(p)；,2.3 线性表的链式表示和实现,初始化操作InitList( /分配失败 ,2.3 线性表的链式表示和实现,取某序号元素操作GetElem(L,i, /GetElem_L,2.3 线性表的链式表示和实现,插入操作ListInsert(&L,i,e),2.3 线性表的链式表示和

16、实现,插入操作ListInsert( /ListInsert_L,2.3 线性表的链式表示和实现,删除操作ListDelete( /ListDelete_L,2.3 线性表的链式表示和实现,删除操作ListDelete(&L,i,&e),2.3 线性表的链式表示和实现,建立单链表操作createlist (LinkList &L） 后接法createlistr(LinkList &L) 前插法createlistf(LinkList &L),2.3 线性表的链式表示和实现,后接法建立链表createlistr(LinkList ,?,2.3 线性表的链式表示和实现,前插法建立链表createl

17、istf(LinkList ,?,2.3 线性表的链式表示和实现,逆置。有一个带头结点的单链表L，其头指针为L，设计一个算法将L逆置，即最后一个结点变成第一个结点。 void invert(LinkList L) p=L-next; L-next=NULL; while (p) q=p-next; p-next=L-next; L-next=p; p=q; ,2.3 线性表的链式表示和实现,例2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB，要求不破坏原有的结点。(链式存储) void UnionList_L(LinkList La,LinkList Lb,

18、LinkList /Lc最后结点的next置为NULL,2.3 线性表的链式表示和实现,例2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 (链式存储) void MergeList_L(LinkList La,LinkList Lb,LinkList /MergeList_L,2.3 线性表的链式表示和实现,其他典型的线性链表 带头结点的单向循环链表(Circular Linked List) 是一个首尾相接的链表，即将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就

19、得到了单链形式的循环链表，并称为循环单链表。,2.3 线性表的链式表示和实现,其他典型的线性链表 带头结点的双向链表(Double Linked List)：在单链表的每个结点里再增加一个指向其前趋的指针域prior，这样形成的链表中就有两条方向不同的链，称双（向）链表。结构定义如下： typedef struct Dnode ElemType data； struct DNode *prior，*next； DNode, *DoubleList； 带头结点的双向循环链表：,2.3 线性表的链式表示和实现,线性链表判空条件小结 不带头结点的单链表、单向循环链表、双向链表、双向循环链表 带头结点

20、的单链表、单向循环链表、双向链表、双向循环链表,2.2 线性表的链式表示和实现,算法设计典型题目 集合的相关运算：并集、交集、差集 两张表的按条件合并 删除指定位置或指定条件的元素 一张表的有条件拆分 应用：约瑟夫环问题、多项式的相加、相乘等 算法的核心操作 插入 删除,顺序表和链表的比较,2.4 一元多项式的表示和相加,一元多项式Pn(x)可按升幂的形式写成： Pn(x)=p0+p1x+p2x2+p3x3+ +pnxn 在计算机内，可以用一个线性表P来表示： P=（p0，p1，p2， ，pn） Qm(x)： Q=(q0，q1，q2，qm) 不失一般性，设mn，则Rn(x)=Pn(x)+Qm(

21、x) R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,pn),2.4 一元多项式的表示和相加,Pn(x)： P=（p0，p1，p2， ，pn） Qm(x)： Q=(q0，q1，q2，qm) 不失一般性，设mn，则Rn(x)=Pn(x)+Qm(x) R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,pn),2.4 一元多项式的表示和相加,用单链表存储多项式的结点结构如下： typedef struct Polynode /项的表示 float coef; /系数 int expn; /指数 Polynode *next; Polynode, *Polylist;,2

22、.4 一元多项式的表示和相加,输入多项式的系数和指数，用尾插法建立一元多项式的链表: Polylist polycreate() rear=head =(Polynode *)malloc(sizeof(Polynode); /建立多项式的头结点， rear 始终指向单链表的尾 scanf(“%d,%d”, ,2.4 一元多项式的表示和相加,两个多项式相加: A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8,2.4 一元多项式的表示和相加,两个多项式相加的运算规则:两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄

23、到“和多项式”中。 若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移； 若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移； 若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。,2.4 一元多项式的表示和相加,两个多项式相加的运算规则:两个多项式中所有指数相同的项的对应系数相加;若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。 void polya

24、dd(Polylist polya;Polylist polyb) /p和q分别指向polya和polyb链表中的当前计算结点 /pre指向和多项式链表中的尾结点 while (p & q） if (p-exp exp) /将p结点加入到和多项式中 else if ( p-exp= =q-exp） /若指数相等，则相应的系数相加。若系数为0则删除p，q节点 else /将q结点加入到和多项式中 /将多项式polya或polyb中剩余的结点加入到和多项式中 ,第2章作业,P20P45 以下题目做在书本上： 2.4.1、2.4.2 以下题目做在习题本上，必须抄题： 例2.5、 例2.10、 2.4

25、.4（2.、3.、7.、10.）,The End,Data Structure,实验一参考源程序,#include #include #include #define ERROR 0 #define OK 1 #define EQUAL 1 #define OVERFLOW -1 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10,实验一参考源程序,struct STU char name20; char stuno10; int age; int score; stu50; typedef struct STU ElemType; stru

26、ct LIST ElemType *elem; int length; int listsize; ; typedef struct LIST List;,int init(List *L); int ListLength(List L); void GetElem(List L,int i,ElemType *e); int EqualList(ElemType e1,ElemType e2); int Less_EqualList(ElemType e1,ElemType e2); int LocateElem(List La,ElemType e,int type); int ListI

27、nsert(List *L,int i, ElemType e); void MergeList(List La,List Lb,List *Lc); void UnionList(List *La, List Lb); int printlist(List L);,实验一参考源程序,main() ElemType e; List La,Lb,Lc; clrscr(); printf(“nn-List Demo is running-nn“); printf(“First is InsertList function.n“); init(,实验一参考源程序,strcpy(e.name,“stu

28、1“); strcpy(e.stuno,“100001“); e.age=80; e.score=1000; ListInsert(,实验一参考源程序,strcpy(e.name,“stu5“); strcpy(e.stuno,“100003“); e.age=80; e.score=1000; ListInsert(,实验一参考源程序,init(,实验一参考源程序,strcpy(e.name,“stu6“); strcpy(e.stuno,“100001“); e.age=80; e.score=1000; ListInsert(,实验一参考源程序,MergeList(La,Lb, ,实验一

29、参考源程序,int init(List *L) L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L-elem) exit(OVERFLOW); L-length=0; L-listsize=LIST_INIT_SIZE; return OK; /*init */,实验一参考源程序,int ListLength(List L) return L.length; void GetElem(List L,int i,ElemType *e) *e=L.elemi; ,实验一参考源程序,int EqualList(ElemT

30、ype e1,ElemType e2) if (strcmp(e1.name,e2.name)=0) return 1; else return 0; int Less_EqualList(ElemType e1,ElemType e2) if (strcmp(e1.name, e2.name)=0) return 1; else return 0; ,实验一参考源程序,int LocateElem(List La,ElemType e,int type) int i; switch (type) case EQUAL: for (i=0;iLa.length;i+) if (EqualLis

31、t(La.elemi,e) return 1; break; default: break; return 0; ,实验一参考源程序,void MergeList(List La,List Lb,List *Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La.elem; pb=Lb.elem; Lc-listsize = Lc-length = La.length + Lb.length; pc = Lc-elem = (ElemType *)malloc(Lc-listsize * sizeof(ElemType); if (!Lc-elem)

32、 exit(OVERFLOW); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while(pa=pa_last ,实验一参考源程序,void UnionList(List *La, List Lb) int La_len,Lb_len; int i; ElemType e; La_len=ListLength(*La); Lb_len=ListLength(Lb); for(i=0;iLb_len;i+) GetElem(Lb,i, ,实验一参考源程序,int printlist(List L) int i; printf(“name stuno age scoren“); for (i=0; iL.length; i+) printf(“%-10s %st%dt%dn“, L.elemi.name, L.elemi.stuno, L.elemi.age, L.elemi.score); printf(“n“); ,实验一参考源程序,int ListInsert (List *L,int ElemType e) ElemType *p,*q; if (iL-length+1) return ERROR; q= /*ListInsert Before i */,实验一参考源程序,