《第二章线性表.ppt》由会员分享,可在线阅读,更多相关《第二章线性表.ppt(80页珍藏版)》请在三一文库上搜索。
1、第二章 线性表,学习要点 了解线性表的逻辑结构是数据元素之间存在着线性关系。 熟练掌握线性表的两种存储结构,即顺序存储结构和链式存储结构。 熟练掌握线性表的两种存储结构的基本算法:查找、插入、删除等。,线性表是一种最简单的线性结构,线性结构的基本特征为:,1存在唯一的一个“第一元素”;,2存在唯一的一个 “最后元素” ;,3除最后元素在外,均有 唯一的后继;,4除第一元素之外,均有 唯一的前驱。,在数据元素的非空有限集中,2.1 线性表的类型定义,2.3 线性表的链式表示和实现,2.4 一元多项式的表示及相加,2.2 线性表的顺序表示和实现,2.1 线性表的类型定义,线性表是n 个类型相同数据
2、元素的有限序列,例如 英文字母表 学校计算机数量 学生健康情况登记表,例1. 26个英文字母组成的字母表 (A,B,C,Z) 例2. 某校从1985年到1990年各种型号的计算机拥有量的变化情况。 (6,17,28,50,92,188) 例3. 学生健康情况登记表如下:,.,.,.,神经衰弱,17,男,790634,张立立,健康,21,男,790633,刘建平,一般,20,女,790632,陈 红,健康,18,男,790631,王小林,健康情况,年龄,性 别,学 号,姓 名,若将线性表记为 (a1, . , ai -1, ai , ai+1, , an),1) 不同线性表中数据元素的类型可以是
3、各种各样的,但同一线性表中的元素必须是同一类型的; 2) 在表中 ai-1 领先于ai ,ai 领先于ai+1 ,称ai-1是ai的直接前驱, ai+1是ai的直接后继;,3) 在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前驱,有且仅有一个直接后继,这是所有线性结构的共同特征。线性表是一种线性数据结构;,4) 线性表中元素的个数n 称为线性表的长度,n=0 时称空表; 5) ai是线性表的第i 个元素,称i为数据元素ai 的位序,每一个元素在线性表中的位置,仅取决于它的位序;,抽象数据类型线性表的定义如下:,ADT List ,数据对象:,D ai | ai Elem
4、Set, i=1,2,.,n, n0 ,数据关系:,R1 |ai-1 ,aiD, i=2,.,n ,基本操作:,结构操作,引用型操作,加工型操作, ADT List,结构操作,InitList( &L ),操作结果:构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList( &L ),初始条件:线性表 L 已存在。,操作结果:销毁线性表 L。,ListEmpty( L ),ListLength( L ),GetElem( L, i, &e ),引用型操作:,LocateElem( L, e, compare( ) ),ListEmpty( L ),初始条件: 操作结果:,线性表
5、L已存在。,若L为空表,则返回 TRUE,否则FALSE。,(线性表判空),ListLength( L ),初始条件: 操作结果:,线性表L已存在。,返回L中元素个数。,(求线性表的长度),GetElem( L, i, &e ),初始条件: 操作结果:,线性表L已存在, 且 1iLengthList(L)。,用e 返回L中第 i 个元素的值。,(求线性表中某个数据元素),LocateElem( L, e, compare( ) ),初始条件: 操作结果:,线性表L已存在,e为给定值, compare( )是元素判定函数。,返回L中第1个与e满足关系 compare( )的元素的位序。 若这样的
6、元素不存在, 则返回值为0。,(定位函数),加工型操作,ListInsert( &L, i, e ),ListDelete(&L, i, &e),ListInsert( &L, i, e ),初始条件: 操作结果:,线性表L已存在, 且 1iLengthList(L)+1 。,在L的第i个元素之前插入 新的元素e,L的长度增1。,(插入数据元素),ListDelete(&L, i, &e),初始条件: 操作结果:,线性表L已存在且非空, 1iLengthList(L) 。,删除L的第i个元素,并用e返回其值,L的长度减1。,(删除数据元素),利用上述定义的线性表 可以实现其它更复杂的操作,例
7、2-2,例 2-1,例 2-1 假设:有两个集合A和B分别用两个线性表 LA 和 LB 表示(线性表中的数据元素即为集合中的成员)。 现要求一个新的集合AAB。,例 2-2 已知线性表 LA 和 LB 中的数据元素按非递减有序排列。现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按非递减有序排列。,如何在计算机中存储线性表?如何在计算机中实现线性表的基本操作?,存储线性表,至少要保存两类信息: 1)线性表中的数据元素; 2)线性表中数据元素的顺序关系;,2.2 线性表的顺序表示和实现,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表
8、的起始地址 称作线性表的基地址,以“存储位置相邻”表示有序对 即:LOC(ai) = LOC(ai-1) + l 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)l 基地址,顺序映像的 C 语言描述,typedef struct SqList;,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量,ElemType *elem; / 存储空间基址,int length; / 当前长度,int list
9、size; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),#include “stdlib.h“ /malloc头文件 / 函数结果状态代码 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; / 定义ElemType的类型 typedef int ElemType;,C语言数组的下标从0开始,则表中第i个数据元素是L.elemi-1,设L是SqList 类型的结构变量,则L在内存中的状态如图所示:,线性表的基本操作在顺序表中的实现,InitList_Sq(&L) / 结构初始化,
10、ListInsert _Sq(&L, i, e) / 插入元素,ListDelete _Sq(&L, i) / 删除元素,malloc(int size) 功能:在系统内存中分配size个的存储单元,并返回该空间的基址。 使用方法: . int m = 100; float *p; p = (float*) malloc(m*sizeof(float );,0 1 2 99,p,常用函数说明,free (p) 功能:将指针变量p所指示的存储空间回收到系统内存空间中去。 使用方法: int m = 100; float *p; p = (float*) malloc(m*sizeof(float
11、); / 一旦p所指示的内存空间不再使用 /调用free( ) 将其回收 free(p);,调用free ( p ),常用函数说明,函数realloc() 格 式: void *realloc(void *p,unsigned size) 功 能:将p所指向的已分配内存区域的大小改为size。size可以比原来分配的空间大或小。,常用函数说明,Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq,L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType); if (!L
12、.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE; return OK;,线性表操作 ListInsert_Sq(&L, i, e)的实现:,首先分析:,插入元素时, 线性表的逻辑结构发生什么变化?,例如:ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,q = ,插入操作移动元素的平均情况:,假设在第 i 个元素之前插入的概率为 , 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的
13、期望值为:,线性表操作 ListDelete_Sq(&L, i, &e)的实现,首先分析:,删除元素时, 线性表的逻辑结构发生什么变化?,删除操作移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为:,若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:,在顺序存储结构的线性表中插入或删除一个数据元素平均约移动表中的一半元素。若表长为n,则算法ListInsert_Sq和ListDelete_Sq的时间复杂度均为O(n)。,void union( List &La, List Lb ) / InitL
14、ist_Sq,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); ,int LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType,ElemType) / / LocateElem_Sq,i=1; / 第1个元素的位序 p=L.elem; /第1个元素的存储位置 while(i=L.len
15、gth,void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /,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) exit(OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;,while(pa=pa_last,/ MergeList
16、_Sq,作业一 已知线性表按顺序结构存储,每个元素都是整数,试设计用最少时间把所有为负的元素移到全部正数元素前面的算法。 已知一个线性表中的元素按元素值非递减有序排列,编写一个函数删除线性表中多余的值相同的元素,2.3.1 线性链表,2.3.2 循环链表,2.3 线性表的链式表示和实现,2.3.3 双向链表,用一组地址任意的存储单元存放线性表中的数据元素。,2.3.1 线性链表,以数据域(存储数据元素的信息) + 指针域(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,线性表:(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZH
17、ENG,WANG),存储地址 数据域 指针域,结 点,数据域,指针域,以线性表中第一个数据元素 的存储地址作为线性表的地址,称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。,空指针,线性表为空表时, 头结点的指针域为空,Typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,线性链表的C语言描述,LinkList L; / L 为单链表的头指针,线性链表的基本操作,GetElem(L, i, e
18、) / 取第i个数据元素,ListInsert(&L, i, e) / 插入数据元素,ListDelete(&L, i, e) / 删除数据元素,ClearList(&L) / 重置线性表为空表,CreateList(&L, n) / 生成含 n 个数据元素的链表,线性表的操作 GetElem(L, i, &e) 在单链表中的实现:,j,1,2,3,Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针,以 e 返回第 i 个元素 / GetElem_L,算法时间复杂度为: O(n),p = L-next; j = 1;
19、 / p指向第一个结点,j为计数器,while (p / 顺指针向后查找,直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;,线性表的操作 ListInsert(&L, i, e) 在单链表中的实现:,有序对 改变为 和,Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针,本算法 / 在链表中第i 个结点之前插入新的元素 e / LinstInsert_L,p
20、= L; j = 0; while (p / i 大于表长或者小于1,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;,s,p,算法的时间复杂度为: O(n),线性表的操作ListDelete (&L, i, &e)在链表中的实现:,有序对 和 改变为 ,Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 / ListDel
21、ete_L,算法的时间复杂度为:O(n),p = L; j = 0; while (p-next / 删除位置不合理,q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;,操作 ClearList(&L) 在链表中的实现:,void ClearList(&L) / 将单链表重新置为一个空表 / ClearList,while (L-next) p=L-next; L-next=p-next; free(p); ,算法时间复杂度: O(n),如何创建一个单链表?,链表是一个动态的结构,它不需要予分配空间,因此
22、生成链表的过程是一个结点“逐个插入” 的过程。,头插法建表示意图,void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素,建立带头结点的单链表 / CreateList_L,算法的时间复杂度为: O(n),L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( / 插入 ,尾插法建表示意图,void CreateList_L(Li
23、nkList &L, int n) / 尾插法 / CreateList_L,L = (LinkList) malloc (sizeof (LNode);,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(,如何将两个有序链表归并一个有序链表?,void MergeList_L(LinkList ,静态链表,#define MAXSIZE 1000 typedef struct ElemType data; / 存储数据元素 int cur; / 游标 component,SLinkListMAXSIZE;,针对
24、不设“指针” 的编程语言,怎样用不连续的内存区域来描述线性表?我们想到用一维数组来表示这种情况下的链表。,用数组的一个分量表示一个结点,同时用游标cur代替指针指示结点在数组的相对位置。,(a) 修改前状态,8,9,(b) 修改后状态,在Li后插入Shi;删除元素Zheng,最后一个结点的指针域的指针又指回第一个结点的链表,2.3.2 循环链表,和单链表的差别仅在于,判别链表中最后一个结点的条件不再是“后继是否为空”,而是“后继是否为头结点”。,p=A-next; q=B -next;,A -next=q -next;,B -next=p;,free(q);,算法的时间复杂度为: O(1),循
25、环链表的合并,2.3.3 双向链表,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,双向循环链表,空表,非空表,双向链表的操作特点:,“查询” 和单链表相同。,“插入” 和“删除”时需要同时修改两个方向上的指针。,Status ListInsert_DuL(DULinkList &L, int i,ElemType e) / ListInsert_DuL,if(!(p=GetEl
26、emP_DuL(L,i) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DulNod) return ERROR;,s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK;,Status ListDelete_DuL(DULinkList &L, int i,ElemType e) / ListDelete_DuL,if(!(p=GetElemP_DuL(L,i) return ERROR;,p-prior-next=p-next; p-next-prio
27、r=p-prior; e=p-data; free(p); return OK;,用单链表实现线性表的操作时,存在的问题:,改进链表的设置:,1单链表的表长是一个隐含的值;,1增加“表长”、“表尾指针” 和 “表头指针” 三个数据域;,2在单链表的最后一个元素之后插入元素时, 需遍历整个链表;,3在链表中,元素的“位序”概念淡化,结点的 “位置”概念加强。,2将基本操作中的“位序 i ”改变为“指针 p ”。,一个带头结点的线性链表类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position
28、;,typedef struct / 链表类型 Link head, tail; / 分别指向头结点和 / 最后一个结点的指针 int len; / 指示链表长度 LinkList;,在计算机中,可以用一个线性表来表示: P = (p0, p1, ,pn),一元多项式,但是对于形如 S(x) = 1 + 3x10000 2x20000 的多项式,上述表示方法是否合适?,2.4 一元多项式的表示及相加,一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中:pi 是指数为ei 的项的非零系数, 0 e1 e2 em = n,可以下列线性表表示: (
29、p1, e1), (p2, e2), , (pm,em) ),P999(x) = 7x3 - 2x12 - 8x999,例如:,可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示,T,一元多项式的实现:,typedef struct / 项的表示 float coef; / 系数 int expn; / 指数 term, ElemType;,typedef LinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,void CreatPolyn ( polynomail &P, int m ) / 输入m项的系数和
30、指数,建立表示一元多项式的有序链表P / CreatPolyn,InitList (P); h=GetHead(P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 设置头结点的数据元素,for ( i=1; i=m; +i ) / 依次输入 m 个非零项 ,scanf (e.coef, e.expn); if (!LocateElem ( P, e, q,(*cmp)() ) if ( MakeNode ( s, e ) ) InsFirst(q,s);,注意: 1.输入次序不限; 2.指数相同的项只能输入一次。,用指针qa、qb分别扫描两个
31、多项式,比较结点指数,有三种情况:, qb的指数值 qa的指数值,取qa指针所指结点插入到”和多项式”, qa的指数值 qb的指数值,取qb指针所指结点插入到”和多项式”, p-expq-exp。,将两结点系数相加: 和为0 删除结点qa、qb 和不为0 修改qa系数并插入,删除qb,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法,以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,作业二 四、基础知识题(2.12.3) P13 设有一个由正整数组成的无序单链表,编写算法完成以下功能: 找出最小值结点,且输出该数值; 将链表排列为奇数在前,偶数在后。 编写一算法将单循环链表逆置。 编写一在双向循环链表中值x结点之前插入值为y结点的算法。,
链接地址:https://www.31doc.com/p-2559475.html