线性表-数据结构.ppt

1、第二章 线性表,课前导学,2.1 线性表的类型定义 2.2 线性表的顺序表示与实现 2.3线性表的链式表示与实现 2.4 一元多项式的表示及相加,学习目标,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。,重点和难点,链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的

2、头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。,线性结构的特点,在数据元素的非空有限集中 存在唯一一个被称做“第一个”的数据元素； 存在唯一一个被称做“最后一个”的数据元素； 除第一个数据元素之外，每个元素都只有一个前驱； 除最后一个数据元素之外，每个元素都只有一个后继。,线性表的定义,一个线性表是n个数据元素的有限序列。 除了第一个元素没有直接前驱和最后一个元素没有直接后继之外，其余的每个数据元素只有一个直接前驱和一个直接后继。,线性表的特征,有穷性：由有限个元素组成，元素个数n表长度，n=0空表。设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称

3、 i 为 ai 在线性表中的位序。 有序性：线性表元素之间存在序偶关系，1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 同一性：线性表属于同类数据元素组成，每一个对象都属于同一数据对象,抽象数据类型线性表的定义如下：,ADT List 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： （1）InitList（ GetElem(LB, i)e 依值在线性表LA中进行查访; LocateElem(LA, e, equal( ) 若不存在，则插入之。 ListI

4、nsert(LA, n+1, e) 算法的时间复杂度： O（ListLength(LA) ListLength(LB)）,思路：,实现：void union(List ,结构体类型的使用,结构体的定义方式： struct 结构体名 成员列表 变量名称； 例如： typedef struct student int num; /学号 char name20; int age; stu; /定义一种学生结构体类型，并将此类型重新定义名称为stu类型,结构体变量的引用：,结构体变量名.成员名。student1.num=20; 指向结构体变量的指针的使用 stu *p;/p为指向结构体类型的指针 p=

5、 则*p代表的结构体变量student1 通过p引用结构体变量的成员为 p-num 或者（*p）.num。,2.2线性表的顺序存储结构,定义：线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素。 使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。采用顺序存储结构的线性表通常称为顺序表。 假设线性表中有n个元素，每个元素占L个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址Loc(ai)： loc(ai+1) =loc(ai)+L loc(ai) =loc(a1)+(i-1)L (2-2) 其中loc(a1) 称为基址。,线性表

6、的顺序存储结构是一种随即存取的存储结构，只要确定了起始位置，就可以访问表中的任何一个元素。,数据结构学习的误区,只动眼、耳，不动手 学习数据结构的有效方法是动手，动脑。 (2)有的同学认为，数据结构是C语言的延续，这是一种错误的想法。 C语言仅仅是一个程序设计工具，而数据结构则是程序设计的思想和灵魂，在学习数据结构的过程中经常会接触到C语言的知识，这只不过是借用C语言这个工具来表达数据结构的思想而已，我们也可以不选用C语言，而选择其它语言，如PASCAL、JAVA等，所以，不应该把数据结构当成C语言来学习。 死记硬背 分析每一种数据结构的特点、存储方式和操作算法，养成提出问题、分析问题和解决问

7、题的思维习惯，提升自己分析问题和解决问题的能力。,课程回顾,线性表的顺序存储结构 线性表的初始化 线性表插入操作,顺序存储结构的C语言定义,#define LIST_INT_SIZE 100 #define LISTINCREAMENT 10 typedef struct ElemType *elem； / 线性表占用的数组空间。 int length；/ 线性表的长度 int listsize； /当前分配的存储容量 SeqList；,线性表的基本操作在顺序表中的实现,InitList( If (! L-elem) exit(OVERFLOW); /存储分配失败 L-length=0; /空

8、表长度为0 L-listsize= LIST_INIT_SIZE; /初始存储容量 return OK; /InitList_Sq,二、线性表的顺序表插入操作 ListInsert( if (i L.length+1) return ERROR; / 插入位置不合法 if (L-length = L- listsize) . q = ,newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType); If(!newbase) return OVERFLOW;/ 当前存储空间已满 L- elem=

9、newbase; L- list size+=LISTINCREMENT;,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率为 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,线性表操作 ListDelete( i elemi-1= L- elemi; / 被删除元素之后的元素左移 -L- length; / 表长减1 return OK;,*e= L-elemi-1; / 被删除元素的值赋给 e k= L- length-1; / 表尾元素的位置,if (i L.length) re

10、turn ERROR; / 删除位置不合法,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,int LocateElem_Sq(SqList L, ElemType e,) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq,if (i = L.length) return i; else return 0;,int i i= 1; / i 的初值为第 1 元素的位

11、序,while (i = L.length ,/找到满足条件的元素,/ 没有找到满足条件的元素,时间复杂度为：0(L.length),线性表的查找操作,例如：顺序表,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是， 将顺序表中的元素 逐个和给定值 e 相比较。,顺序存储结构的优缺点：,优点： 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素,顺序表习题作业：,学号结尾为1，3，5的同学交作业，作业内容：教材算法2.7，完整的c程序结构。,线性表的合并问题,例1、已知线性表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB

12、归并为一个新的链表LC，且LC中的数据元素仍按非值递减有序排序。 例如：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）,线性表的一般算法： Void MergeList（List La，List Lb，List Lc） InitList（Lc）； ij1；k0； La_lenListLength（La）；Lb_lenListLength(Lb)； While（(i=La_len) /Mergelist,顺序表中的实现 Void MergeList(SqList La, SqList Lb, SqList *Lc)

13、 int *pa,*pb,*pc,* pa_last,* pb_last; pa=La.elem;pb=La.elem; Lc-listsize=Lc.length=La.length+ Lb.length; pc=Lc-elem=(ElemType*)malloc(Lc-istsize*sizeof(ElemType); If(!Lc-elem) exit(overfiow); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last ,2.3 线性表的链式表示与实现,特点： 用一组任意的存储单元存储

14、线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 结点:数据元素ai 的存储映像。 数据域：元素本身信息 指针域：指示直接后继的存储位置,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,2.3.1 单链表 (或线性链表),1. 定义：结点中只含一个指针域的链表。 2. 特征 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充,data next,3. 单链表的存储映像,free,(a)

15、可利用存储空间,a1,a3,a2,a4,free,first,(b) 经过一段运行后的单链表结构,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针,空指针,线性表为空表时， 头结点的指针域为空,4. 单链表存储结构的实现用C语言中的“结构指针”来描述,typedef struct LNode ElemType data; struct LNode *next; LNode ，*LinkList;,struct LNode ElemType data; stru

16、ct LNode *next; ; typedef LNode * LinkList;,单链表特点: 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢,生成一个LNode型新结点：p=(LinkList)malloc(sizeof(LNode); 系统回收p结点：free(p),线性表的操作 GetElem(L, i, j = 1; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在

17、 *e = p-data; / 取得第 i 个元素 return OK;,单链表中的插入与删除,插入 第一种情况：在第一个结点前插入 s = (LinkList)malloc(sizeof(LNode);/ 生成新结点 if ( s = null) return ERROR; s-data = e; s-next = first ; first = s;,（插入前） （插入后）,a1,a2,first,e,s,e,s,a1,first,a2,ai,e,(插入前) (插入后),第二种情况：在链表中间插入 s-next = p-next; p-next = s；,ai,ai-1,p,e,ai-1,

18、s,p,s,第三种情况：在链表末尾插入 s-next= p-next; p-next = s；,(插入前) (插入后),e,s,e,s,p,p,单链表的插入算法,int ListInsert_L ( LinkList L, int i, int e ) / 在带头结点的单链线性表L中第 i 个位置之前插入元素 e LNode *p,*s; int j; p = L; j = 0; while ( p ,删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素,在单链表中删除含ai的结点,ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,删除前,删除后,p-next =

19、 q-next,单链表的删除算法,int ListDelete_L ( LinkList L, int i, int *e ) / 在带头结点的单链线性表 L 中，删除第 i 个元素，并由 e 返回其值 LNode *p,*q; int j; p = L; j = 0; while ( p-next / LinkDelete_L,T(n)=O(n),5. 动态建立单链表算法：,动画2-3-2.swf演示,算法评价,算法思路： （1）创建头结点 （2）逆序创建结点n，修改结点指针，再创建结点n-1,直到结点1,void CreateList_L ( LinkList *L, int n ) /

20、逆位序输入 n 个数据元素的值，建立带头结点的单链表 L LNode *p; int i; * L = ( LinkList ) malloc ( sizeof ( LNode ) ); (*L)-next = NULL; / 先建立一个带头结点的空链表 for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新结点 scanf (%d , / 修改单链表头结点的指针域 ,/单链表的建立算法,void init_linklist(LinkList *l) /*对单链表进行初始化*/ *l=(LinkLis

21、t)malloc(sizeof(Node); (*l)-next=NULL; void CreateList_L ( LinkList L, int n ) / 逆位序输入 n 个数据元素的值，建立带头结点的单链表 L LNode *p; int i; for ( i = n; i 0; -i ) p = ( LinkList ) malloc ( sizeof ( LNode ) ); / 生成新结点 scanf (%d , / 修改单链表头结点的指针域 ,线性表的合并问题,例1、已知线性表LA和LB中的数据元素按值非递减有序排列，现要将LA和LB归并为一个新的链表LC，且LC中的数据元素仍

22、按非值递减有序排序。 例如：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）,线性表的一般算法： Void MergeList（List La，List Lb，List Lc） InitList（Lc）； ij1；k0； La_lenListLength（La）；Lb_lenListLength(Lb)； While（(i=La_len) /Mergelist,顺序表中的实现 Void MergeList(SqList La, SqList Lb, SqList *Lc) Pa=La.elem;pb=La.elem

23、; Lc-listsize=Lc.length=La.length+ Lb.length; Pc=Lc-elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); If(!Lc.elem) exit(overfiow); Pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; While(pa=pa_last ,例: 将两个有序链表归并为一个有序链表,void MergeList_L ( LinkList La, LinkList Lb, LinkList *Lc, ) / 归并 La 和

24、 Lb 得到新的单链表 Lc ，Lc 的元素也按非递减排列 Node *pa,*pb; pa = La-next; pb = Lb-next; *Lc = pc = La; / 用 La 的头结点作为 Lc 的头结点 while ( pa / 释放 Lb 的头结点 / MergeList_L,一、概念题 在顺序表中要插入一个元素平均需要移动_次元素，具体移动元素的个数与_ _ _ _ _有关。,n/2,元素的具体位置, 单链表中，除头节点外，任一节点的存储位置由_确定。,其前驱节点指针域的值,头结点、头指针、和第一个结点的区别。,顺序存储结构是通过（ ）表示元素之间的关系的，链式存储结构是通过

25、（ ）表示元素之间的关系的。（北京理工2001）。 在单链表L中，指针p所指结点有后继结点的条件是（ ）。（合肥工业大学1999）。 在单链表p所指结点之后插入s节点的基本操作是（ ）。（青岛大学）。 对于一个头指针为head的带头结点的单链表，判定该表为空的条件是（ ）。 线性表的顺序存储结构是一种（ ）。（北京理工2006）. 对于一个线性表即要求能够进行较快速的插入和删除操作，又要求存储结构能够反映出来数据之间的逻辑关系，则应该采用（ ）存储结构。（哈工大2005） 对于顺序表，访问元素和增加、删除元素的时间复杂度是分别是（ ）、（ ）。,画出下列各语句执行后各指针及链表的示意图。,L(

26、LinkList)malloc(sizeof(LNode); P=L;,for(I=1；Inext= (LinkList)malloc(sizeof(LNode) P=P-next; P-data=I*2-1; ,P-next=NULL;,For(I=4;I=1;I+) ins_Linklist(L,I+1,I*2),For(I=1;I=3;I+) Del_Linklist(L,i);,有一个单链表，头指针为head，编写一个函数，计算数据域为x的节点的个数。 设计思想： 遍历链表，设立一个计数器，每当遇到一个数据域为X的节点，计数器加1。 自己动手写。,int count(Linklist

27、head,int x) node *head， node *p; int j=0; p=head; while(p!=NULL) if(p-data=x) j+; p=p-next; return (j); ,实现单链表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,an）逆置为(an,an-1,a1)。 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 编写程序，删除线性表a中第i个元素起的k个元素。,下面我们将看几个在线性表中经常会出现的算法和概念题。 练习1、把L中值为奇数的结点删除，并用来生成新表L1。,算法思想： 生成一个新的节点，表示新的链表头节

28、点。 从第一个节点开始，判断其奇偶性。 若为奇数，则将其链到新的链表上，否则比较下一个。,status List_L(LinkList L) p = L; q = p-next; (p为前驱结点地址指针变量） s = (LinkList) malloc ( sizeof (Lnode); s-next = NULL; L1 = S ; while (q!= NULL) if （q -data mod 2 = 0） p = q ; q = q-next ; else p-next = q-next; q-next = s-next ;s-next = q ; q = p-next ; retur

29、n OK; ,8. 静态链表,动态链表 链表中的结点空间都是动态申请和释放的。 在有些高级语言（如BASIC）中，没有提供指针类型，此时若仍想采用链表作为线性表存储结构? 则只能借助一维数组来模拟链表，,定义：用数组描述的链表叫静态链表 存储结构： #define MAXSIZE = 100; /静态链表的最大长度 typedef struct ElemType data; int cur; /游标,代替指针指示结点在数组中的位置 component,SLinkListMAXSIZE; 目的是为了在不设指针类型的高级程序设计语言中使用链表结构。树的双亲表示法、图的邻接表表示法、表插入排序、等都

30、用到了静态链表。,静态链表结构示例,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,插入shi,修改前的状态,修改后的状态,删除zheng,S0.cur指示第一个结点在数组中的位置,shi,9,5,5,8,游标cur PK 指针next,1、指针next是个地址，游标cur是？ int cur；指示后继元素在数组中的相对位置 2、指针后移实现了，游标cur后移呢？ p = p-next； 已知：SLinkList S； i = Si.cur;,一般情况下，对静态链表S，如果Si.data=ak，则 ak+1= S?.data,Si.cur,静态链表的

31、存储结构,#define MAXSIZE = 100; /静态链表的最大长度 typedef struct ElemType data; int cur; /游标,代替指针指示结点在数组中的位置 component,SLinkListMAXSIZE;,在静态链表中查找第1个具有给定值e的结点,int LocateElem_SL ( SLinkList, S,ElemType e ) i = S 0.cur; /i 指向表第一个结点,相当于p=p-next while ( i /LocateElem_SL,2.3.2 循环链表 (Circular List),循环链表是单链表的变形。 循环链表最

32、后一个结点的 link 指针不 为NULL，而是指向了表的前端。 为简化操作，在循环链表中往往加入头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,循环链表的示例 带头结点的循环链表,a1,a2,a3,an,first,an,first,a2,a1,first,(空表),(非空表),搜索成功,搜索不成功,循环链表的搜索算法,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,current,current,current,current,current,current,current,current,循环链表的操作和

33、单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,带尾指针的循环链表,rear,31,48,15,57,22,如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。 在表尾插入，时间复杂性 O(1) 在表尾删除，时间复杂性 O(n) 在表头插入，相当于在表尾插入 在表头删除，时间复杂性 O(1),头指针指向表尾的好处是既能立即找到链表的尾结点，也容易找到链表中的第一个结点。 P35页图2.13 链表A，B直接合并： trilA-next=trilB-next; trilB-next=trilA-next;,静态链表 单循环链

34、表,2.3.3 双向链表 (Doubly Linked List),双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点有两个指针域, 结构如下： 双向链表通常采用带头结点的循环链表形式。,前驱方向 后继方向,prior data next,双向链表C语言的定义,typedef struct node ElemType data; struct node *prior,*next; JD;,空双向循环链表：,非空双向循环链表：,结点指向 p-prior-next = p = p-next-prior,p-prior,p-next,p,prior,next,双向循环链表的搜

35、索算法,搜索成功,搜索不成功,first,first,31,31,48,48,15,15,57,57,搜索15,搜索25,双向链表插入算法描述,void ins_dulist(JD* p,int x) JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; ,算法实现,算法评价：T(n)=O(n),双向链表的插入操作算法: Status ListInsert_DuL ( DuLinkList / ListInsert_DuL,算法评价：T(n)=O(n

36、),双向链表删除算法描述,void del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); ,算法实现,p-prior-next=p-next;,p-next-prior=p-prior;,双向链表的删除操作算法: Status ListDelete_DuL ( DuLinkList / ListDelete_DuL,算法评价：T(n)=O(n),2.3.4 顺序表与链表的比较,（1）基于空间的比较 存储分配的方式 顺序表的存储空间是一次分配的 链表的元素的存储空间是动态分配的 存储密度 = 结点数据本身所占的

37、存储量/结点结构所占的存储总量 顺序表的存储密度 = 1 链表的存储密度 1,（2）基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表,如何选择存储结构呢？,若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。 对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。 在求长度，查找元素时不如顺序表。,用上述定义的单链表实现线性表的操作时， 存在的问题：,1单链表的表长是一个隐含的值；,2在单链表的

38、最后一个元素之后插入元素时， 需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的 “位置”概念加强。,四、一个带头结点的线性链表类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position;,typedef struct / 链表类型 Link head, tail; / 分别指向头结点和 最后一个结点的指针 int len; / 指示链表长度 LinkList;,课程回顾,上机出现问题 调试 链表和顺序表的区别 循环链表 双向链表,2.4 一元多项式的表示及相加,1. 一元多项式

39、的表示,n 阶多项式 Pn(x) 有 n+1 项。 系数 P0, P1, P2, , Pn 指数 0, 1, 2, , n。按升幂排列,若： 对S(x)这样的多项式采用全部存储的方式则浪费空间。怎么办？ 一般n次多项式可以写成：,因此可以用数据域含两个数据项的线性表来表示：,ADT Polynomial 数据对象： 数据关系：,抽象数据类型一元多项式的定义如下：,D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 ,R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 ,CreatPolyn ( struct node *next; JD, *Polylist ;,（2） 通过键盘输入一组多项式的系数和指数，以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从大到小的顺序排列。 算法描述：从键盘接受输入的系数和指数； 用尾插法建立一元多项式的链表。,Polylist polycreate() Polynode *head, *rear, *s; int c