严蔚敏、吴伟民编著 清华大学出版社 学习网站：中国网页设计

Presentation on theme: "严蔚敏、吴伟民编著 清华大学出版社 学习网站：中国网页设计"— Presentation transcript:

1 严蔚敏、吴伟民编著 清华大学出版社 学习网站：中国网页设计 http://www.xin126.cn/list.asp?id=301
数 据 结 构 （C语言版） 严蔚敏、吴伟民编著 清华大学出版社 学习网站：中国网页设计

2 第2章 线性表 主要内容： 一、线性表的类型定义 二、线性表的顺序表示和实现 三、线性表的链式表示和实现 四、一元多项式的表示及相加（略）

3 一、线性表的类型定义 1、线性表的定义：是由n(n≧0)个数据元素组成的有限序列。如：（a1,a2,…,an） 当n=0时，称为空表。
当n>0时，将非空的线性表记作： (a1，a2， … ai…an) a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。 a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱; ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai的直接后继。

4 2、线性表的特点 ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前驱；
① 存在一个唯一的被称为“第一个”的数据元素； ② 存在一个唯一的被称为“最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一一个直接前驱； ④ 除最后一个元素外，每个元素均有唯一一个直接后继。

5 线性表实例 线性表的定义：是由n(n≧0)个数据元素组成的有限序列。如：（a1,a2,…,an）
线性表是最常用且最简单的一种数据结构。其中每个数据元素的具体含义，在不同的情况下各不相同，可以是一个数或一个符号甚至更复杂的信息等。如： 英文字母表（A,B,C,…..Z)是一个线性表 int a[5]={2,5,7,9,12}; 例 数据元素

6 ◆ 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。 ◆ 对线性表的数据元素可以访问、插入和删除。

7 第2章 线性表 3、抽象数据类型线性表的定义（参见P19）

8 2.1.3 线性表的抽象数据类型定义 ADT List{ ListLength( L ) 初始条件：线性表L已存在；
线性表的抽象数据类型定义 ADT List{ 数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L； ListLength( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回TRUE，否则返回FALSE； ….

9 … } ADT List GetElem( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L)；
ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List

10 第2章 线性表 4、线性表的操作示例 （1）两个线性表LA、LB分别表示两个集合A和B，现要求一个新的集合A=A ∪ B。
第2章 线性表 4、线性表的操作示例 （1）两个线性表LA、LB分别表示两个集合A和B，现要求一个新的集合A=A ∪ B。 (2)已知线性表LA和LB中的数据元素按值非递减有序排列，求LA和LB归并为一个新的线性表LC，且LC仍按值非递减有序排列。

11 A=A ∪ B void union(List *La,List Lb)
{ La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++) { GetElem(Lb,i,e); if(!LocateElem(La,e,equal)) ListInsert(La,++La_len,e); }

12 第2章 线性表 二、线性表的顺序表示和实现 1、线性表的顺序表示
第2章 线性表 二、线性表的顺序表示和实现 1、线性表的顺序表示 又称为顺序表示或顺序映像，是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中。 特点: (1)逻辑上相邻的元素，物理位置上也相邻； (2)若已知首元素的存储位置，则其它元素的位置可以求出，计算方法如下：每个元素占用L个存储单元 Loc(ai)=Loc(a1)+L*(i-1) 其中Loc(a1)为首地址 Loc(ai+1)=Loc(ai)+L

13 第2章 线性表 例：一个一维数组M，下标范围是0-9，每个数组元素用相邻5个字节存储。存储器按字节编址，设M[0]的第一个字节地址是98，则M[3]的第一个字节的首地址是_______

14 第2章 线性表 LOC( M[3] ) = 98 + 5 ×(3-0) =113 2、顺序表（数组）的实现
第2章 线性表 LOC( M[3] ) = ×(3-0) =113 2、顺序表（数组）的实现 #include <stdio.h> #define LIST_INIT_SIZE //线性表存储空间的初始分配量 #define LISTINCREMENT //线性表存储空间的分配增量 #define OK 1 #define ERROR -1 typedef int Status ; typedef int ElemType; typedef struct list { ElemType *elem; //存储空间地址 int length; //当前长度 int listsize; //当前分配的存储量(以sizeof(ElemType)为单位) }SqList;

15 Status InitList(SqList *L )
{ L-> elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L-> elem) exit(0); //分配失败 L-> length=0; //空表长度为零 L-> listsize=LIST_INIT_SIZE; //初始存储容量 printf( "顺序表初始化完成!\n "); printf( "表长为 %d,初始分配量为 %d ",L-> length,L-> listsize); return OK; }

16 第2章 线性表 3、顺序表的操作或实现 （主要讨论插入和删除操作在顺序表中的实现） （1）插入操作 在线性表的第i个位置前插入一个元素 长度为n的线性表变为长度为n+1的线性表 （a1,a2,…,ai-1,ai,…,an）            （a1,a2,…,ai-1,x,ai,…,an） 实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 算法：见教材P24 算法2.4

17 Status ListInsert(SqList *L,int i,ElemType e)
{ ElemType *newbase,*q,*p; if(i<1||i>L->length+1) return ERROR; if(L->length>=L->listsize){ newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(0); printf(" 增加空间成功"); L->elem=newbase; L->listsize+=LISTINCREMENT;}

18 newbase=(ElemType*)realloc
(L->elem,(L->listsize+LISTINCREMENT) *sizeof(ElemType)); 指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）。//新的大小一定要大于原来的大小不然的话会导致数据丢失！

19 q=&(L->elem[i-1]);
for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L->length; return OK; } 改写？

20 for(j=L->length;j>=i;j--)
{ L->elem[j]=L->elem[j-1]; } L->elem[i-1]=e; ++L->length;

21 完善GetElem 函数 ElemType GetElem(SqList *L,int i,int x)

22 ElemType GetElem(SqList *L,int i,int x)
{ if(i<1||i> L-> length) { printf( "查找位置错误"); exit(ERROR) ;} else printf( " 你查找的数是 %d ! ",L-> elem[i-1]); x=L-> elem[i-1]; return OK; printf( "\n "); }

23 int main() { int y=0; SqList* L =NULL; L= (SqList *)malloc(sizeof(SqList)); //使用指针前一定要初始化 InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,5); printf( "表长为 %d,现分配量为 %d ",L-> length,L-> listsize); GetElem(L,3,y); }

24

25 第2章 线性表 （2）删除操作 删除线性表的第i个位置上的元素使：长度为n的线性表变为长度为n-1的线性表。 （a1,a2,…,ai-1,ai,ai+1,…,an）            （a1,a2,…,ai-1,ai+1,…,an） 实现步骤： 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 算法见教材P24 算法2.5

26 Status ListDelete(SqList *L,int i,int e)
{ int j; j=i; if(i<1||i> L-> length){ printf( "请输入位置%d不正确",i); return ERROR;} e=L-> elem[i-1]; for(;i <L-> length;i++) L-> elem[i-1]=L-> elem[i]; L-> length--; printf( "第%d 元素 %d 删除成功!\n ",j,e); return OK; }

27 3.顺序表操作的效率分析 算法时间主要耗费在移动元素的操作上因此计算时间复杂度的基本操作(最深层语句频度) T(n)= O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i. 若i=length+1，则根本无需移动（特别快）； 若i=1，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。

28 同理可证:顺序表删除一元素的时间效率为:
设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则 插入时的平均移动次数为: n(n+1)/2÷（n+1）＝n/2≈O(n) 同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 ≈O(n)

29 顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1)
主要优点是：空间单元利用率高,能随机存取表中任一元素； 主要优缺点 主要缺点：插入和删除时需要移动大量的数据元素。

30 第2章 线性表 三、线性表的链式表示和实现 顺序存储结构的特点…… 1、链式存储结构的特点 2、结点 3、链表
第2章 线性表 三、线性表的链式表示和实现 顺序存储结构的特点…… 1、链式存储结构的特点 用一组地址任意的单元存放线性表的数据元素。任何两个元素的存储位置之间没有固定的联系。每个元素的存储位置包含在其直接前驱结点的信息中。[参见P27图示] 2、结点 结点（数据元素的存储映像）==数据域（数据元素的信息）+指针域（指示直接后继的存储地址） 3、链表 以n个结点的序列表示的线性表

31 第2章 线性表 含义： 存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。
第2章 线性表 含义： 存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。 以线性表的第一个数据元素a1的存储地址作为线性表的地址，称为线性表的头指针 。 有时为了操作方便，在第一个结点之前“虚”加一个“头结点”。

32 由于此链表每个结点只包含一个指针域，故又称线性链表或单链表

33 图2-3 带头结点的单链表的逻辑状态、物理存储方式
3695 head fat 1100 bat 1300 …… cat 1305 eat 3700 hat NULL hat ⋀ 图2-3 带头结点的单链表的逻辑状态、物理存储方式 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 例1、线性表L=(bat，cat，eat，fat，hat) 其带头结点的单链表的逻辑状态和物理存储方式如图2-3所示。

34 第2章 线性表 4、线性表的操作 对线性表可以进行遍历，查找，插入和删除等基本操作。 单链表的数据结构
第2章 线性表 4、线性表的操作 对线性表可以进行遍历，查找，插入和删除等基本操作。 单链表的数据结构 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList

35 第2章 线性表 （1）插入操作 算法：P29-30 （2）删除操作 算法：P30

36 插入操作 Status ListInsert(LinkList L, int i,ElemType e) { LinkList S,pre;
int j=0; pre=L; while(pre->next!=NULL&&j<i-1){ pre=pre->next; ++j; } if(j!=i-1){ printf("输入的I的位置不合法"); return 0;}

37 S = (LinkList)malloc(sizeof(LNode));//为新结点分配空间
if(S==NULL) { printf("Out of space!"); return ERROR; } S->data=e; S->next = pre->next; pre->next = S; return OK; }

38 删除操作 Status ListDelete(LinkList L,int i,ElemType &e) { LinkList pre,q;
pre=L; int j=0; while(pre->next!=NULL&&j<i-1){ pre=pre->next; ++j; } if(j!=i-1){ printf("输入的I的位置不合法"); return 0;}

39 q= pre->next; pre->next = q->next; e=q->data; free(q); printf("第%d个要删除的元素是%d\n",i,e); return OK; }

40 int main() { int i=0,j=0,k=0; LinkList L=NULL; L = (LinkList)malloc(sizeof(LNode)); //为链表的头结点分配空间 InitList(L); ListInsert(L,1,5) ; ListInsert( L, 2,3) ; i=(L->next)->data; printf("第一个元素是%d\n",i); j=L->next->next->data; printf("第二个元素是%d\n",j); ListLength(L); ListInsert(L,4,4) ; ListDelete(L,1,k); }

41

42 第2章 线性表 5、循环链表 （3）单链表的建立 有两种方法建立单链表：头插法、尾插法 头插法建立单链表：P30算法2.11
第2章 线性表 （3）单链表的建立 有两种方法建立单链表：头插法、尾插法 头插法建立单链表：P30算法2.11 （4）两个单链表的归并 P31算法2.12 5、循环链表 （1）特点：表中最后一个结点的指针指向头结点，整个链表形成一个环。分为单循环链表和多循环链表两种 从任何一个结点出发都可以找到其他任何结点。 对于需要循环遍历的场合比较适用。

43 第2章 线性表 （2）循环链表判空： 双向循环链表

44 第2章 线性表 6、双向链表 为了克服单向链表的单向性（查找某结点的后继结点的时间为O（1），查找某结点的前驱结点的时间O（n））。
第2章 线性表 6、双向链表 为了克服单向链表的单向性（查找某结点的后继结点的时间为O（1），查找某结点的前驱结点的时间O（n））。 特点：每个数据结点中都有两个指针，分别指向直接后继和直接前驱，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 双向链表存储结构 typedef struct DuLNode 　{ 　 ElemType data; 　　 struct DuLNode *prior,*next; 　　}DuLNode,*DuLinkList;

45

46 第2章 线性表 判空： L->next==L&&L->prior==L 插入结点

47 第2章 线性表 删除结点