数据结构实用ppt课件 第一章.ppt

第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）线性表是一种最常用且最简单的数据结构。 含有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）ListLength(L) 求长度,返回线性表中数据元素个数3）GetElem(L,i,&e) 取表L中第i个数据元素赋值给e4）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(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 一般来说，线性表的第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 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(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 10typedef struct ElemType *elem; int length; int listsize; SqList;SqList L;说明：elem数组指针指向线性表的基地址；length指示线性表的当前长度；listsize指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType),2) 几个基本操作初始化,23算法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所指向的已分配内存区域的大小 改为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,查找,25p26算法2.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 100Status CreateList_Sq(SqList ,递增插入,Status OrderInsert_Sq(SqList ,递减插入,Status DeOrderInsert_Sq(SqList ,4. 顺序表的分析,1）优点顺序表的结构简单顺序表的存储效率高，是紧凑结构顺序表是一个随机存储结构（直接存取结构）2）缺点在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。原因：数组的静态特性造成,作业,2.1 编写程序，建立并显示一个有10个数据元素的顺序线性表。2.2 实现顺序线性表的插入、查找、删除等 算法。,顺序表之整体概念：,elem,0,1,length-1,listsize,length,数组下标,内存状态,变量,操作算法,listsize-1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. . .,. . .,. . .,空闲,表区,elem,顺序表之整体概念：,顺序表有下列缺点：（1）插入、删除操作时需要移动大量元素， 效率较低；（2）最大表长难以估计，太大了浪费空间， 太小了容易溢出。因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结构，数据元素之间的逻辑关系由结点中的指针来指示。,2.3 线性表的链式表示和实现1. 线性链表,特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作结点。结点：数据域 + 指针域（链域）链式存储结构：n个结点链接成一个链表线性链表（单链表）：链表的每个结点只包含一个指针域。,data,next,单链表 (Singly Linked List),first 头指针last 尾指针, 指针为空单链表由头指针唯一确定，因此常用头指针的名字来命名。如表first.,单链表的存储映像,1）线性链表的描述 p28,typedef struct LNode ElemType data; Struct LNode *next; LNode, *LinkList;LinkList L; /L是LinkList类型的变量， 表示单链表的头指针,2）术语,头指针：指向链表中第一个结点第一个数据元素结点（开始结点）头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。说明：头结点的next域指向链表中的第一个数据元素结点。对于头结点数据域的处理： a.加特殊信息 b.置空 c.如数据域为整型，则在该处存放链表长度信息。,3）带头结点的单链表示意图 p28图2.7,由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处理。无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操作的实现。,非空表 空表,2. 基本操作,1）取元素 p29 算法2.82）插入元素 p30 算法2.9 3）删除元素 p30 算法2.104）建立链表 p30p31 算法2.115）有序链表的合并 p31 算法2.126）查找（按值查找）7）求长度8）集合的并运算,取元素（按序号查找） p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下搜索，直至找到第i个结点为止（j=i),Status GetElem_L(LinkList L, int i,ElemType ,插入元素p30 算法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;,从带表头结点的单链表中删除第一个结点,建立链表（头插法建表）p31 算法2.11在链表表头插入新结点，结点次序与输入次序相反。,void CreateList_L(LinkList 尾插法建表：将新结点插到链表尾部，须增设一个 尾指针last，使其始终指向当前链表 的尾结点。,合并有序链表p31 算法2.12,void MergeList_L(LinkList La,LinkList Lb,LinkList ,查找（按值查找）,int LinkLocate_L (LinkList L, int x) int i; LinkList p; p=L-next; i=1; while (p!=NULL ,求长度,int LinkLength_L (LinkList L) int j; LinkList p; p=L-next; j=0; while (p) p=p-next;j+; return(j); 注意：p=NULL与p-next =NULL是不同的。总结： 带头结点：链表置空 L-next = NULL； 判断是否为空的条件 if (L-next = NULL) 不带头结点：则置空 L=NULL; 判空条件 if (L=NULL),集合并运算5-2 A=AB,void UnionList_L(LinkList ,说明：,first的位置始终不变；插入位置在La表的表头元素之前；查找不会在刚刚插入的结点间进行，只能从first指向的原始La表中进行 （因为每次查找时均有q=first）时间复杂度： O(m*n)；,3. 循环链表,1）循环链表是一种首尾相接的链表。 循环链表最后一个结点的next指针不为 0 (NULL)， 而是指向了表头结点。在循环链表中没有NULL 为简化操作，在循环链表中往往加入表头结点。 特点：循环链表中，从任一结点出发都可访问到表中 所有结点；而在单链表中，必须从头指针开始， 否则无法访问到该结点之前的其他结点。,循环链表与单链表不同的是链表中表尾结点的 指针域不是NULL，而是链表头结点的指针H（链表指针）循环链表的示例（循环条件：p!=H)带表头结点的循环链表（循环条件：p-next != H）,2）循环链表的操作,合并两个单链表 p=La; while (p-next) p=p-next; p-next = Lb-next; free(Lb);时间复杂度 O(m),合并两个循环链表,=La;while (p-next!=La) p=p-next;p-next=Lb-next;p=p-next;while (p-next!=Lb) p=p-next;p-next=La; free(Lb);时间复杂度 O(m+n),循环链表的建立算法,void CreateList_L(LinkList ,显示输出算法（带头结点）循环链表,void PrintList_LC(LinkList L) LinkList p; p=L-next; printf(L-); while (p!=L) printf(%d-,p-data); p=p-next; printf(Ln);,4.双向链表 (Doubly Linked List),双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。1) 双向链表的结点结构： 前驱方向 (a)结点结构 后继方向双向链表通常采用带表头结点的循环链表形式。,对双向循环链表中任一结点的指针，有：p = ppriornext = pnextprior置空表： pprior = p ; pnext = p;,(b) 非空双向循环链表 (c) 空表,2）双向循环链表存储结构的 描述 p35p36,typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList;DuLinkList d,p;,pprior = current;(1)pnext =currentnext; (2)currentnext = p; (3)pnextprior = p; (4),双向循环链表的插入算法,currentnextprior = currentprior; currentpriornext = currentnext;,双向循环链表的删除算法,3）基本操作：双向循环链表的建立,void CrtList_DuL(DuLinkList ,显示输出,void PrtList_DuL(DuLinkList L)DuLinkList p; p=L-next;printf(L-);while (p!=L)printf(%d-,p-data);p=p-next; printf(n);,2.4 一元多项式的表示和相加,n阶多项式Pn(x)有n+1项。 系数 a0, a1, a2, , an 指数 0, 1, 2, , n。按升幂排列在计算机中，可以用一个线性表来表示 P=(a0,a1, , an),1. 第一种表示方法Pn=(a0,a1, , an)适用于指数连续排列、 “0”系数较少的情况。但对于指数不全的多项式，如P20000(x) = 3 + 5x50 + 14x20000, 会造成系统空间的巨大浪费。,2. 第二种表示方法一般情况下，一元多项式可写成：Pn(x)=p1xe1+p2xe2+pmxem其中：pi是指数为ei的项的非零系数， 0e1 e2 em n 二元组表示 (p1,e1),(p2,e2), ,(pm,em)例：P999(x) = 7x3 - 2x12 -8x999 表示成: (7,3),(-2,12),(-8,999),ADT Polynomial 数据对象: D=ai|ai TermSet, i=1,2,m, m0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|ai-1,ai D,且ai-1中的指数值ai中的指数值, i=2,n 基本操作：ADT Polynomial,3. 一元多项式的抽象数据类型定义,typedef struct float coef; int expn;term, ElemType;/term用于本ADT, ElemType为LinkList的数据对象名typedef LinkList polynomial;,4. 抽象数据类型(Polynomial)的实现,多项式链表的相加,AH = 1 - 10 x6 + 2x8 +7x14BH = - x4 + 10 x6 - 3x10 + 8x14 +4x18,两个多项式的相加,结果多项式另存扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。,