树结构综合版1——7数据结构ch2线性表

1、数 据 结 构 Data Structure,主讲人： 刘 玮,第二章 线性表,线性表的定义,2.1,线性表的顺序表示和实现,2.2,线性表的链式表示和实现,2.3,一元多项式的表示及相加,2.4,2.1 线性表的定义,线性表是n个数据元素的有限序列。记为：,线性结构的基本特征： 存在唯一一个“第一元素” 存在唯一一个“最后元素” 除最后元素外，均有唯一的直接后继 除第一元素外，均有唯一的直接前驱,2.1.1 定义,2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,ADT List 数据对象: D ai | ai ElemSet, i=1,2,.,n, n0 /称n为线性表的表长； 当n=0时，线性表为空表； 数据关系: R1 |ai-1 ,aiD, i=2,.,n /设线性表为(a1,a2,ai,an)， 称i为ai在线性表中的位序,2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,基本操作： 结构初始化操作 结构撤销操作 引用型操作 加工型操作 ADT List,2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,结构初始化操作 InitList(

2、 &L ) 操作结果： 构造一个空的线性表L,2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,结构撤销操作 DestroyList( &L ) 初始条件： 线性表L已存在。 操作结果： 当线性表L存在，撤销线性表L。,2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,引用型操作 ListEmpty( L ) ListLength( L ) GetElem( L, i, &e ) LocateElem(L, e, compare() PriorElem(L, cur_e, &pre_e) NextElem(L, cur_e, &next_e) ListTraverse(L,visit( ),2.1 线性表的定义,2.1.2 线性表的抽象数据类型ADT,加工型操作 ClearList(&L) PutElem(&L,i,e) ListInsert(&L, i, e) ListDelete(&L, i, &e),Void union(List ,时间复杂度:O(Length（La）Length(Lb),例2-1：假设利用两个线性表LA和LB分别表示两个集合A和B，先要

3、求一个新的集合A=AB。,算法思想：逐一取出LB的元素，判断是否在LA中，若不在则插入。,Void MergeList(List La, List Lb, List +j ,例2-2：线性表LA和LB是非递减的，将两表合并成新的线性表LC，且LC也是非递减的。,算法思想：将LA和LB两表中的元素逐一按序加入到一个新表LC中。,while(i=La_len) GetElem(La,i+,ai); ListInsert(Lc, +k, ai); while(j=Lb_len) GetElem(Lb,j+,bj); ListInsert(Lc, +k, bj); /MergeList,时间复杂度:O(Length(La)+ Length(Lb),2.2 线性表的顺序表示和实现,用一组地址连续的存储单元依次存储线性表的数据元素，这种机内表示即为线性表的顺序存储结构，又叫顺序表。,2.2 线性表的顺序表示和实现,一般情况下，(a1,a2,.,ai-1,ai,.,an)的顺序存储：,2.2.1 线性表的存储方式,如何求得任意元素的存储地址？,2.2 线性表的顺序表示和实现,以“存储位置相邻”表示有

4、序对，即：,一个数据元素所占的存储量,所有数据元素的存储位置均取决于第一个数据元素的存储位置(基地址),基地址,基地址,顺序表的特点：,逻辑上相邻，且物理地址相邻；,随机存取的存储结构。只要确定了存储线性表的起始位置，线性表中任一数据元素可随机存取。,2.2 线性表的顺序表示和实现,通常用数组来表示顺序表,2.2.2 线性表的表示（C语言描述）,# define List_Init_Size 100 /线性表的最大容量设为100 # define ListIncrement 10 /线性表数据元素的长度 typedef struct ElemType *elem; /存储空间的基地址 int length; / 线性表当前长度 int listsize; /线性表当前分配的存储容量 SqList;,2.2 线性表的顺序表示和实现,顺序表的几种基本操作,2.2.3 线性表的基本操作（C语言描述）,InitList(&L) /初始化顺序表 ListInsert(&L,i,e) /插入元素 ListDelete(&L,i) /删除元素,顺序表初始化,Status InitList(SqLis

5、t ,算法复杂度：O(1),算法思想：构造一个空表。设置表的起始位置、表长及可用空间。,插入元素操作,25,25,n=8,n=9,算法思想：将第n至第i个元素逐一向后移动一个位置，在第i个位置上插入一个新元素。,插入算法：,判断i值的合法性，1i表长+1 ；,判断表的空间满否？若满则不能插入；,从表长n到i，依次后移；,将e插入第i个位置，表长度增1。,Status Insert_SqList (SqList *L，int i，ElemType x) /在顺序表L的第 i 个位置上插入一个值为 x 的新元素 if (iL-length+1) /检查插入位置的正确性 printf (“插入位置i不合理! ”); exit(1); /不合理，中止程序运行 if (L-length = L-ListSize) / 顺序表是否已满 printf (“顺序表已满，不能再插入！”); exit(1); / 表满,不能插入 for (m=L-length-1; m= i-1; - -m) L-data m+1 = L-datam; / 结点后移 L-data i-1 = x; /新元素插入 L-le

6、ngth+; /表长+1 return Ok; /插入成功，返回 ,算法复杂度分析 时间主要耗费在移动元素上, 移动元素个数与插入位置 i 有关，问题规模为n=L.length 最好：当 i=n+1, 结点后移语句不执行，T(n)=O(1) 最坏：当 i=1, 结点后移语句执行n次，T(n)=O(n) T(n)=O(n),在顺序表中插入一个元素时，平均移动表的一半元素，当n很大时，效率很低。,删除元素操作,30,12,13,21,24,28,30,42,77,a1,a2,a3,a4,a5,a6,a7,a8,a9,n=8,n=7,算法思想：删除第i个元素，将第（i+1）至第n（共n-i）个元素逐一向前移动一个位置。,删除算法：,判断i值的合法性，1i表长；,从i+1到表长n，依次前移；,表长度减1；,算法复杂度分析 时间主要耗费在移动元素上, 移动元素个数与删除位置 i 有问题规模：n=L.length 最好：当 i=n, 结点前移语句不执行，T(n)=O(1) 最坏：当 i=1, 结点前移语句执行n次，T(n)=O(n) 平均： T(n)=O(n),在顺序表中删除一个元素时，平均移动表

7、的一半元素，当n很大时，效率很低。,2.2 线性表的顺序表示和实现,顺序表的优缺点：,缺点 插入和删除操作时需要移动大量元素； 建立表时，预先分配空间需按最大空间分配，利用不充分； 表容量无法扩充。,优点 逻辑相邻，物理相邻； 可以随机存取任一元素； 容易查找一个结点的前驱和后继； 存储空间使用紧凑。,2.3 线性表的链式表示和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。 链表中的数据元素称为结点，包含两个域：数值域和指针域。,根据链接方式不同，分为：单链表、循环链表、 双向链表 根据链表实现不同，分为：静态链表、动态链表,2.3 线性表的链式表示和实现,2.3.1 单链表 链表的每个结点中只包含一个指针域，则称其为单链表，又称线性链表。,2.3.1.1 特点,单链表中每个结点的结构为：,单链表的简化示意图如下，设单链表L= (a1,a2,a3 ,a4),结点可以不连续存储,表容易扩充,单链表是非随机存储结构,单链表的存储映像,(a) 未使用的存储空间,(b)

8、建立单链表后的存储空间,2.3.1.2 带头结点的单链表 在实际应用中，往往在第一个结点前设置一个头结点。该结点的数值域可自行定义，指针域指向第一个结点。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。,2.3.1.3 单链表的表示（C语言描述） typedef struct Lnode ElemType data; /数据域 Struct Lnode *next; /指针域 Lnode， *LinkList;,LinkList L；,L-next L-next-data,2.3.1.4 单链表基本操作的实现,2. 插入结点操作,3. 删除结点操作,4. 创建单链表,1. 初始化单链表,1. 初始化单链表,建立一个带头结点的空表；,Void InitList(LinkList ,2. 插入结点操作,在第i个结点前插入新元素x,(a) 插入前,(b) 插入后,插入算法：（在第i个位置前插入元素）,生成结点x ；,x的指针指向第i个结点；,第i-1个结点的指针指向x；,找到第i-1个结点 ；,插入位置i的合法性 ；,Status ListInsert (LinkList

9、,算法复杂度 :T(n) =O(n),3. 删除结点操作,删除表中第i个结点,(a) 删除前,(b) 删除后,删除算法：（删除表中第i个结点）,让第i-1的指针直接指向第i+1；,释放第i个结点所分配的资源；,找到第i-1个结点 ；,删除位置i的合法性 ；,Status ListDelete (LinkList L, int I,ElemType ,算法复杂度 :T(n) =O(n),4. 创建单链表操作,建立一个长度为n的单链表，L为头指针，从键盘输入n个元素的数值。,用上述定义的单链表实现线性表操作时存在的问题：,单链表的表长是一个隐形的值；,在单链表的最后一个元素后插入元素时，需遍历整个链表；,在链表中，元素的“位序”概念淡化，结点的“位置”概念强化；,改进链表的设置：,增加“表长”，“表尾指针”和“当前位置指针”三个数据域；,将基本操作由“位序”改为“指针”；,2.3.1.5 带头结点的单链表类型定义如下： typedef struct Lnode ElemType data; /数据域 Struct Lnode *next; /指针域 *Link， *Position;,typedef struct Link head, tail; int len; /指针域 Link current; LinkList;,单链表的特点：,是一种动态结构；,不需预先分配空间；,指针占用额外存储空间；,不能随机存取，查找速度慢；,2.3.2 静态链表,静态链表

《树结构综合版1——7数据结构ch2线性表》由会员E****分享，可在线阅读，更多相关《树结构综合版1——7数据结构ch2线性表》请在金锄头文库上搜索。