中国科学技术大学：《数据结构与数据库》课程教学课件（PPT讲稿）第二章 线性表

第二章线性表2.1线性表的类型定义2.2线性表的顺序存储2.3线性表的链式存储2.4一元多项式的表示和相加中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 1 中国科学技术大学 第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加

2.1线性表的类型定义线性表的定义线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同地属性，表中相邻元素间存在“序偶”关系。记做(ai,a2......aj1,a,ai+1...,an-1,an)ai-,称为a的直接前驱元素，aii是a;的直接后继元素线性表的长度：表中的元素个数n位序：称元素ai在线性表中的位序中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 2 中国科学技术大学 2.1线性表的类型定义 线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1 ,a2 ,.ai-1 ,ai ,ai+1 ,.,an-1 ,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继 元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序

线性表的ADT定义ADT List:数据对象:D={ala;eElemset,i=1,2...n,n≥0)数据关系:R=[<ai-1,a;>ai-1,a; E D, i=2,...n)基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)1<=i<= ListLength (L)LocateItem(L,e,compareO)PriorElem(L,Cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e) 1<-i<= ListLength (L)+1ListDelete(&L,i,&e) 1<=i<=ListLength (L)ListTraverse(L,visitO)1ADT List2P3ypb@ustc.edu.cn中国科学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学 ADT List{ 数据对象: D={ai |aiElemset,i=1,2.n, n≥0} 数据关系: R={<ai-1 ,ai>|ai-1 ,ai  D, i=2,.n} 基本操作: InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e,compare()) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) 1<=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L,visit()) }ADT List 线性表的ADT定义

【例】对两个线性表La、Lb表示的集合A和B，求一个新集合A=AUB／/算法2.1a）从Lb中取一个元素（重复直至遍历全部Lb元素）b)在La中查询c）若La中不存在，则将其插入La【例】对一个非纯集合B，构造一个纯集合A，使A中只包涵B中不同值的成员。同上，只是创建La。【例】判断两个集合是否相等。构造C一A【例】已知线性表La、Lb中数据元素按值非递减排列现要求将La和Lb归并为一新的线性表Lc，且Lc也非递减排列。//算法2.2中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 4 中国科学技术大学 【例】对两个线性表La、Lb表示的集合A和B，求一个 新集合A＝AUB //算法2.1 a) 从Lb中取一个元素(重复直至遍历全部Lb元素) b) 在La中查询 c) 若La中不存在，则将其插入La 【例】对一个非纯集合B，构造一个纯集合A，使A中只包 涵B中不同值的成员。同上，只是创建La。 【例】判断两个集合是否相等。构造C＝A 【例】已知线性表La、Lb中数据元素按值非递减排列， 现要求将La和Lb归并为一新的线性表Lc,且Lc也非 递减排列。 //算法2.2

2.2线性表的顺序表示和实现顺序表线性表的顺序存储表示(C规范)#define LIST INIT SIZE 100#define LISTINCREMENT 10Typedef Struct * elem,Elemtypeintlength,intlistsize;fSqList;5中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 5 中国科学技术大学 2.2线性表的顺序表示和实现 顺序表——线性表的顺序存储表示 #define LIST_INIT_SIZE 100 (C规范) #define LISTINCREMENT 10 Typedef Struct { Elemtype * elem; int length; int listsize; }SqList;