第二章 线性表.pps

《第二章 线性表.pps》由会员分享，可在线阅读，更多相关《第二章 线性表.pps（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面： 散列存储散列存储索引存储索引存储串及数组串及数组Data_Structure = (D,S)2第2章 线性表 了解线性表的特点及类型定义； 掌握线性表的顺序表示及实现，掌握线性表的链式表示及实现（单链表、双向链表和循环链表）； 算法设计（层次3）：熟练掌握两种线性表表示的创建、

2、插入、删除和查找等基本操作；链表合并与分解，有序表插入； 了解一元多项式的表示和相加。3第2章 线性表线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继2.1 线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一个线性表例 学生健康情况登记表数据元素元素文件姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平7

3、90633 男 21 健康张立立790634 男 17 神经衰弱 . . .5 特征： 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项6抽象数据类型 线性表的定义 P19类C描述 ADT List建空表，求长度，定位，插入等基本操作利用基本操作实现复杂操作 如线性表合并P20 例2-1 线性表合并 union 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。算法2.1 ListLength，GetElem，LocateElem，ListInsertvoid Unio

4、n(List &La, List Lb) / 算法2.1 / 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i; ElemType e; La_len = ListLength(La); / 求线性表的长度 Lb_len = ListLength(Lb); for (i=1; i=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal) / La中不存在和e相同的数据元素 ListInsert(La, +La_len, e); / 插入 / union

5、时间复杂度时间复杂度 for x LocateElem 即即O（ListLength(Lb)xListLength(La)）8P21 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。有序表合并到第三个表MergeList 算法2.2void MergeList(List La, List Lb, List &Lc) / 算法2.2 / 已知线性表La和Lb中的元素按值非递减排列。 / 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。 InitList(Lc); i=j=1; k=0

6、; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) / La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) ListInsert(Lc, +k, ai); +i; else ListInsert(Lc, +k, bj); +j; while (i = La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j = Lb_len) GetEle

7、m(Lb, j+, bj); ListInsert(Lc, +k, bj); / MergeList时间复杂度时间复杂度 O(ListLength(Lb) +ListLength(La) 10 数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。 顺序与链式存储结构11顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L一个元素占用的存储单元个数 LOC(ai)线性表第i个元素的地址P22 图2.22.2 线性表的顺序存储结构特点：实现逻辑上相邻物理地

8、址相邻随机存取实现：C语言的一维数组注意：C语言中的数组下标从“0”开始类类C描述描述 定义结构体类型定义结构体类型SqList#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; /存储空间基址存储空间基址int length; /当前长度当前长度int listsize; /当前分配的存储容量当前分配的存储容量SqList;P23 例例 算法算法2.3 初始化操作初始化操作Status InitList_Sq(SqList &L) / 构造一个空的线性表构造一个空的线性表L。 L.el

9、em = (ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); / 存储分配失败存储分配失败 L.length = 0; / 空表长度为空表长度为0 L.listsize = LIST_INIT_SIZE; /初始存储容量初始存储容量 return OK; / InitList_Sq 插入插入 定义：线性表的插入是指在第定义：线性表的插入是指在第i（1 i n+1）个）个元素之前插入一个新的数据元素元素之前插入一个新的数据元素x，使长度为，使长度为n的的线性表线性表niiaaaaa,

10、1,21 变成长度为n+1的线性表niiaaxaaa,1,21 需将第i至第n共（n-i+1)个元素后移 P24 算法2.4/ 算法2.4Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.

11、elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = &(L.elemi-1); / q为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; /

12、ListInsert_Sq内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x17 设设Pi是在第是在第i个元素之前插入一个元素的概率，则在个元素之前插入一个元素的概率，则在长度为长度为n的线性表中插入一个元素时，所需移动的的线性表中插入一个元素时，所需移动的元素次数的平均次数为：元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为算法评价，算法时间复杂度T(n) 删除定义：线性表的删除是指将第i（1i n

13、）个元素删除，使长度为n的线性表niiaaaaa,1,21 变成长度为n-1的线性表niiaaaaa,11,21 需将第i+1至第n共（n-i)个元素前移P24 算法算法2.5Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.el

14、em+L.length-1; / 表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK; / ListDelete_Sq内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+221 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：niideinQE1)( nOnTninnEnQnidei121)(11则若认为故在顺序

15、表中插入或删除顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低算法评价，算法时间复杂度T(n)22例2-1 例2-2 顺序存储结构例例2-1 取决于取决于LocateElemint LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 算法算法2.6 / 在顺序线性表在顺序线性表L中查找第中查找第1个值与个值与e满足满足compare()的元素的位序。的元素的位序。 / 若找到，则返回其在若找到，则返回其在L中的位序，否则返回中的位序，否则返回0。 int i; ElemT

16、ype *p; i = 1; / i的初值为第的初值为第1个元素的位序个元素的位序 p = L.elem; / p的初值为第的初值为第1个元素的存储位置个元素的存储位置 while (i = L.length & !(*compare)(*p+, e) +i; if (i = L.length) return i; else return 0; / LocateElem_Sqvoid MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 算法算法2.7 / 已知顺序线性表已知顺序线性表La和和Lb的元素按值非递减排列。的元素按值非递减排列。 / 归并

17、归并La和和Lb得到新的顺序线性表得到新的顺序线性表Lc，Lc的元素也按值非递减排列。的元素也按值非递减排列。 ElemType *pa,*pb,*pc,*pa_last,*pb_last; 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

18、.length-1; pb_last = Lb.elem+Lb.length-1; while (pa = pa_last & pb = pb_last) / 归并（复制）归并（复制） if (*pa = *pb) *pc+ = *pa+; else *pc+ = *pb+; while (pa = pa_last) *pc+ = *pa+; / 插入插入La的剩余元素的剩余元素 while (pb data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNode);系统回收p结点：fre

19、e(p)线性链表头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空La1a2an 头结点.L空表29 取元素：GetElem_L P29 算法 2.8 时间复杂度 T(n) = O(n)Status GetElem_L(LinkList L, int i, ElemType &e) / 算法2.8 / L为带头结点的单链表的头指针。 / 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p = L-next; j = 1; / 初始化，p指向第一个结点，j为计数器 while (p & jnext; +j; if ( !p | ji ) return ERRO

20、R; / 第i个元素不存在 e = p-data; / 取第i个元素 return OK; / GetElem_L单链表的基本运算Status ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e p = L; j = 0; while (p & j next; +j; / 寻找第i-1个结点 if (!p | j i-1) return ERROR; / i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode); / 生成新结点 s-data = e;

21、 s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_Lpabxs 插入：在线性表两个数据元素插入：在线性表两个数据元素a和和b间插入间插入x，已知，已知p指向指向as-next=p-next;p-next=s; P30 算法 2.9 时间复杂度 T(n) = O(n)Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 p = L; j = 0; while (p-next & j next; +j; if

22、(!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK; / ListDelete_L P30 算法2.10pabc时间复杂度 T(n) = O(n) 删除：单链表中删除删除：单链表中删除b，设，设p指向指向ap-next=p-next-next;void CreateList_L(LinkList &L, int n) / 算法2.11 / 逆位序输入n个元素的值，建立带表头结点的单链线性表L L = (LinkList)

23、malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i=n; i0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新结点 scanf(&p-data); /输入元素值 p-next = L-next; L-next = p; / 插入到表头 / CreateList_Lh头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0 nOnT 动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针 CreateList_

24、L P30 算法 2.11 算法评价合并有序链表MergeList_L P31 算法 2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 已知单链线性表La和Lb的元素按值非递减排列。 / 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 pa = La-next; pb = Lb-next; Lc = pc = La; / 用La的头结点作为Lc的头结点 while (pa & pb) if (pa-data data) pc-next = pa; pc = pa; pa = pa-next; e

25、lse pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; / 插入剩余段 free(Lb); / 释放Lb的头结点 / MergeList_L算法2.2 的两种实现：算法2.7 顺序，算法2.12 链接34 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢静态链表 无指针类型语言 BASIC大数组 用游标（指示器cur）代替指针P32 图2.10备用链表：未使用的分量（数组元素）P33 例2-3 (A-B)U(B-A)算法2.14-2.17图2.11 数组静态链

26、表1 备用链表 0单链表特点内存中的顺序表与单链表ha1a2an 头结点.内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1typedef structElemType *elem; /存储空间基址存储空间基址int length; /当前长度当前长度 nint listsize; /当前分配的存储容量当前分配的存储容量SqList;SqList L； L.elm -pqtypedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;LinkList h；36 循环链表是表中最后

27、一个结点的指针指向头结点，循环链表是表中最后一个结点的指针指向头结点，使链表构成环状使链表构成环状 特点：从表中任一结点出发均可找到表中其他结特点：从表中任一结点出发均可找到表中其他结点，提高查找效率点，提高查找效率 操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同 单链表单链表 p或或p-next=NULL 循环链表循环链表 p或或p-next=HHH空表循环链表(circular linked list)尾指针 合并简化 P35 图2.13temp = B-next;B-next = A-next;A-next = temp-next;A = B;free(temp);在

28、很多实际问题，用尾指针在很多实际问题，用尾指针rear来表示单循环链表，来表示单循环链表，则查找开始结点则查找开始结点a1和终端结点和终端结点an都很方便，它们的存都很方便，它们的存储位置分别是储位置分别是(rearnext) next和和rear38单（循环）链表具有单向性的缺点双向结点 typedef struct DuLNode ElemType data; struct DulNode *prior,*next; DuLNode, *DuLinkList;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-

29、proir;双向链表（double linked list） 删除P37 算法2.19 ListDelete_DuL算法评价：T(n)=O(n)p-prior-next=p-next;p-next-prior=p-prior;Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) / 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1i表长 if (!(p = GetElemP_DuL(L, i) / 在L中确定第i个元素的位置指针p return ERROR; / p=NULL, 即第i个元素不存在 e = p-data; p

30、-prior-next = p-next; p-next-prior = p-prior; free(p); return OK; / ListDelete_DuLbcapDuLinkList GetElemP_DuL(DuLinkList L, int i) / L为带头结点的双向链表的头指针。 / 当第i个元素存在时，返回该元素指针，否则返回NULL DuLinkList p; p = L-next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p!=L & jnext; +j; if (p = = L | ji) return NULL; / 第i个元素

31、不存在 else return p; / GetElem_LListInsert_DuL 1. s-prior = p-prior; 2. p-prior-next = s; 3. s-next = p; 4. p-prior = s;xsbap 插入P36 算法2.18Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) / 在带头结点的双链循环线性表L的第i个元素之前插入元素e， / i的合法值为1i表长+1。 if (!(p = GetElemP_DuL(L, i) / 在L中确定第i个元素的位置指针p return ERROR;

32、 / p=NULL, 即第i个元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode) return ERROR; s-data = e; s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; return OK; / ListInsert_DuL 算法评价：T(n)=O(n)小结：带头结点的线性链表 取消参数i 位序算法改写 算法2.20 2.2143一元多项式的表示及相加一元多项式的表示及相加一元多项式的表示：一元多项式的表示：nnnxPxPxPPxP2210)(),(210n

33、PPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示 emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表2.4 线性表的应用举例 单链表的结点定义coefexpnext17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef stru

34、ct LNode float coef; int exp; struct LNode *next;LNode, *polynomail;设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-exp exp: p结点是和多项式中的一项 p后移,q不动p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可 运算规则q-1pa7 0 3 1

35、 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述Status

36、 cmp(LNode a, LNode b) if (a.expn!=b.expn) return 1; else return 0;void CreatPolyn(polynomail &P, int m) / 算法2.22 / 输入m项的系数和指数，建立表示一元多项式的有序链表P 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,

37、 e, q, cmp) / 当前链表中不存在该指数项 if (MakeNode(s,e) InsFirst(q, s); / 生成结点并插入链表 / CreatPolynvoid AddPolyn(polynomail &Pa, polynomail &Pb) / 算法2.23 / 多项式加法：Pa = PaPb，利用两个多项式的结点构成和多项式。 ha = GetHead(Pa); hb = GetHead(Pb); / ha和hb分别指向Pa和Pb的头结点 qa = NextPos(Pa,ha); qb = NextPos(Pb,hb); / qa和qb分别指向La和Lb中当前结点 whi

38、le (qa & qb) / Pa和Pb均非空 a = GetCurElem (qa); b = GetCurElem (qb); / a和b为两表中当前比较元素 switch (Compare(a,b) case -1: / 多项式PA中当前结点的指数值小 ha = qa; qa = NextPos (Pa, qa); break; case 0: / 两者的指数值相等 sum = a.coef + b.coef ; if (sum != 0.0) / 修改多项式PA中当前结点的系数值 temp.coef=sum; temp.expn=a.expn; SetCurElem(qa, temp)

39、 ; ha = qa; else / 删除多项式PA中当前结点 DelFirst(ha, qa); FreeNode(qa); DelFirst(hb, qb); FreeNode(qb); qb = NextPos(Pb, hb); qa = NextPos(Pa, ha); break; case 1: / 多项式PB中当前结点的指数值小 DelFirst(hb, qb); InsFirst(ha, qb); qb = NextPos(Pb, hb); ha = NextPos(Pa, ha); break; / switch / while if (!Empty(Pb) Append(Pa, qb); / 链接Pb中剩余结点 FreeNode(hb); / 释放Pb的头结点 / AddPolyn作业2.32.52.82.13