数据结构实用ppt课件 第一章.ppt
《数据结构实用ppt课件 第一章.ppt》由会员分享,可在线阅读,更多相关《数据结构实用ppt课件 第一章.ppt(68页珍藏版)》请在三一办公上搜索。
1、第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)线性表是一种最常用且最简单的数据结构。
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、长度,返回线性表中数据元素个数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 和
4、 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的存储位置为:
5、 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 len
6、gth; 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) ex
7、it(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指示顺序表当前分配的存储空间大小。当空间不足时,再分配的存储空间增量为
8、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可以比原来分配的空间
9、大或小。,插入(续),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)
10、 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 DeOrd
11、erInsert_Sq(SqList ,4. 顺序表的分析,1)优点顺序表的结构简单顺序表的存储效率高,是紧凑结构顺序表是一个随机存储结构(直接存取结构)2)缺点在顺序表中进行插入和删除操作时,需要移动数据元素,算法效率较低。对长度变化较大的线性表,或者要预先分配较大空间或者要经常扩充线性表,给操作带来不方便。原因:数组的静态特性造成,作业,2.1 编写程序,建立并显示一个有10个数据元素的顺序线性表。2.2 实现顺序线性表的插入、查找、删除等 算法。,顺序表之整体概念:,elem,0,1,length-1,listsize,length,数组下标,内存状态,变量,操作算法,listsize-
12、1,初始化操作,插入操作,删除操作,查找操作,排序操作,. . . . . .,. . .,. . .,. . .,空闲,表区,elem,顺序表之整体概念:,顺序表有下列缺点:(1)插入、删除操作时需要移动大量元素, 效率较低;(2)最大表长难以估计,太大了浪费空间, 太小了容易溢出。因此,在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适,此时可以选用链式存储结构,数据元素之间的逻辑关系由结点中的指针来指示。,2.3 线性表的链式表示和实现1. 线性链表,特点:在内存中用一组任意的存储单元来存储线性表的数据元素,用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实用ppt课件 第一章 数据结构 实用 ppt 课件
链接地址:https://www.31ppt.com/p-1520082.html