数据结构实用幻灯片-第一章

《数据结构实用幻灯片-第一章》由会员分享，可在线阅读，更多相关《数据结构实用幻灯片-第一章（68页珍藏版）》请在金锄头文库上搜索。

1、第2章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,2.1 线性表的类型定义,线性结构的特点： 在数据元素的非空有限集中，1）有且仅有一个开始结点；2）有且仅有一个终端结点；3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱；4）除最后一个结点外，集合中的每个数据元素均有且只有一个后继。 线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为(a1,ai,ai+1,an),2.1 线性表的类型定义,1. 线性表 1）线性表是n(n 0)个数据元素的有限序列。 2）线性表是一种最常用且最简单的数据

2、结构。 含有n个数据元素的线性表是一个数据结构： List = (D,R) 其中：D = ai | aiD0,i=1,2,n,n0 R = N, N = | ai-1 , ai D0 , i = 2,3,n D0 为某个数据对象数据的子集 特性：均匀性，有序性（线性序列关系）,2.1 线性表的类型定义,1. 线性表 3）线性表的长度及空表 线性表中数据元素的个数n（n0）定义为线性表的长度 当线性表的长度为0 时，称为空表。 ai 是第i个数据元素，称i为ai 在线性表中的位序。,2. 线性表的基本操作 p19p20,1）InitList(&L) 初始化，构造一个空的线性表 2）ListLen

3、gth(L) 求长度,返回线性表中数据元素个数 3）GetElem(L,i,&e) 取表L中第i个数据元素赋值给e 4）LocateElem(L,e) 按值查找，若表中存在一个或多个值为e的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。 5）ListInsert(&L,i,e) 在L中第i个位置前插入新的数据元素e，表长加1。 6）ListDelete(&L,i,e) 删除表中第i个数据元素，e返回其值，表长减1。,线性表的基本操作举例,例2-1 求A = A B P20算法2.1 时间复杂度：LocateElem()执行次数 O(ListLength(A)*ListLength(

4、B) 例2-2 合并LA 和 LB 到LC中 P20-21算法2.2 时间复杂度：ListInsert()执行次数O(ListLength(LA)+ListLength(LB),2.2 线性表的顺序表示和实现 1.顺序表线性表的顺序存储结构,1）在计算机内存中用一组地址连续的存储单元依次 存储线性表中的各个数据元素。 2）假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系： Loc(ai+1) = Loc(ai) + L 一般来说，线性

5、表的第i个元素ai的存储位置为： Loc(ai) = Loc(a1) + (i-1)*L 其中Loc(a1)是线性表的第一个数据元素a1的存储位置，通常称作线性表的起始位置或基地址。,1.顺序表线性表的顺序存储结构,3）线性表的顺序存储结构示意图p22图2.2 用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。 根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺序存储结构是一种随机存取的存储结构。,#define LIST_MAX_LENTH 100/或者N/或者是一 个 常数 typedef struct ElemType

6、 int *elem; int length; SqList; SqList L;,2.顺序存储线性表的描述,C语言中静态分配描述 p22,求置空表 Status ClearList( ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,求长度 Status List length( SqList L ) length= L. length; return OK; ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,初始化 Status InitList_ SqList( SqList L ) L.elem=(*int) malloc(LIST_MAX_LENGTH *sizeof

7、(int) ); if(!L.elem) exit(Overflow) ; L. length=0; return OK; ,2.顺序存储线性表的描述,C语言中静态分配描述 p22,2. 顺序表的描述 1) C语言中动态分配描述 p22,#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList; SqList L; 说明：elem数组指针指向线性表的基地址；length指示线性表的当前长度；listsize指示顺序表当前分

8、配的存储空间大小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType),2) 几个基本操作 初始化,p23算法2.3 Status InitList_SqList(SqList ,插入 p24算法2.4,Status ListInsert_sq(SqList 需将第n(即L.length)至第i个元素向后移动一个位置。注意：C语言中数组下标从0开始，则表中第i个数据元素是L.elemi-1。,插入 p24算法2.4,函数realloc的格式及功能 格式： void *realloc(void *p,unsigned size) 功能：将p所指向的已

9、分配内存区域的大小 改为size。 size可以比原来分配的空间大或小。,插入（续）,q= ,删除 p24p25算法2.5,Status ListDelete_sq(SqList return OK 需将第i+1至第L.length个元素向前移动一个位置,插入和删除算法时间分析,用“移动结点的次数”来衡量时间复杂度。与表长及插入位置有关。 插入： 最坏：i=1，移动次数为n 最好: i=表长+1，移动次数为0 平均：等概率情况下，平均移动次数n/2 删除： 最坏：i=1，移动次数为n-1 最好: i=表长，移动次数为0 平均：等概率情况下，平均移动次数(n-1)/2,查找,p25p26算法2.

10、6 int LocateElem_Sq(SqList L, ElemType e) i=1; while ( i=L.length ,查找的另一种描述,i=1; p=L.elem; while (i=L.length ,合并 P26算法2.7的另外一种描述,void MergeList_Sq(SqList La,SqList Lb,SqList ,合并 P26算法2.7,void MergeList_Sq(SqList La,SqList Lb,SqList ,建立,#define LIST_INIT_SIZE 100 Status CreateList_Sq(SqList ,递增插入,Sta

11、tus OrderInsert_Sq(SqList ,递减插入,Status DeOrderInsert_Sq(SqList ,4. 顺序表的分析,1）优点 顺序表的结构简单 顺序表的存储效率高，是紧凑结构 顺序表是一个随机存储结构（直接存取结构） 2）缺点 在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。 对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。 原因：数组的静态特性造成,作业,2.1 编写程序，建立并显示一个有10个数据元素的顺序线性表。 2.2 实现顺序线性表的插入、查找、删除等 算法。,顺序表之整体概念：,elem,0,1,

12、length-1,listsize,length,数组下标,内存状态,变量,操作算法,listsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. . .,. . .,. . .,空闲,表区,elem,顺序表之整体概念：,顺序表有下列缺点： （1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。 因此，在插入和删除操作是经常性操作的应用场合 选用顺序存储结构不太合适，此时可以选用链式存储结 构，数据元素之间的逻辑关系由结点中的指针来指示。,2.3 线性表的链式表示和实现 1. 线性链表,特点：在内

13、存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作结点。 结点：数据域 + 指针域（链域） 链式存储结构：n个结点链接成一个链表 线性链表（单链表）：链表的每个结点只包含一个指针域。,data,next,单链表 (Singly Linked List),first 头指针 last 尾指针, 指针为空 单链表由头指针唯一确定，因此常用头指针的名字来命名。如表first.,单链表的存储映像,1）线性链表的描述 p28,typedef struct LNode ElemType data; Struct LN

14、ode *next; LNode, *LinkList; LinkList L; /L是LinkList类型的变量， 表示单链表的头指针,2）术语,头指针：指向链表中第一个结点 第一个数据元素结点（开始结点） 头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。 说明：头结点的next域指向链表中的第一个数据元素结点。 对于头结点数据域的处理： a.加特殊信息 b.置空 c.如数据域为整型，则在该处存放链表长度信息。,3）带头结点的单链表示意图 p28图2.7,由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。 无论链表是否为

15、空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操作的实现。,非空表 空表,2. 基本操作,1）取元素 p29 算法2.8 2）插入元素 p30 算法2.9 3）删除元素 p30 算法2.10 4）建立链表 p30p31 算法2.11 5）有序链表的合并 p31 算法2.12 6）查找（按值查找） 7）求长度 8）集合的并运算,取元素（按序号查找） p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下搜索，直至找到第i个结点为止（j=i),Status GetElem_L(LinkList L, int i,ElemType ,插入元素p30 算

16、法2.9 在第i个元素之前插入，先找到第i-1个结点,Status ListInsert_L(LinkList ,e,s,P-next=s,(2),(3),p,s-next=p-next,a,(1),b,在带表头结点的单链表 第一个结点前插入新结点,newnodenext = pnext; if ( pnext =NULL ) last = newnode; pnext = newnode;,删除元素p30 算法2.10,Status ListDelete_L(LinkList ,q = pnext; pnext = qnext; delete q; if ( pnext = NULL ) last = p;,从带表头结点的单链表中删除第一个