900线性表.pptx
《900线性表.pptx》由会员分享,可在线阅读,更多相关《900线性表.pptx(45页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、本章要点本章要点l线性表的两种存储方式l顺序表和单链表的插入、查找、删除操作及效率分析l双向链表、循环链表l线性表两种存储方式的比较本章难点本章难点l单链表的存储方式及各种操作l线性表的两种存储方式的比较学习目标学习目标l掌握线性表的定义和各种操作l掌握线性表的两种种存储方式l掌握顺序表、单链表、循环链表、双向链表2.1 线性表的概念和基本操作线性表的概念和基本操作 l线性表是具有相同数据类型的n(n=0)个数据元素的有限序列,通常记为:(a1,a2, ai-1,ai,ai+1,an),其中n为表长,n0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前驱,ai+1称为ai
2、的直接后继。l线性表上的基本操作有:(1)INIT_LIST(L) 线性表初始化,当表L不存在时,构造一个空的线性表。 (2)LENGTH_LIST(L) 求线性表的长度,当表L存在时,返回线性表中的所含元素的个数。(3)GET_LIST(L,i) 取表元,当表L存在且1iLength_List(L)时,返回线性表L中的第个元素的值或地址。(4)LOCATE_LIST(L,x) 按值查找,是给定的一个数据元素。当线性表L存在时,在表L中查找值为的数据元素,其结果返回在L中首次出现的值为的那个元素的序号或地址,称为查找成功;否则,即在L中未找到值为的数据元素时,返回一特殊值表示查找失败。2.1
3、线性表的概念和基本操作线性表的概念和基本操作 (5)INSERT_LIST(L,i,x) 插入操作,当线性表L存在,插入位置正确 (1in+1,为插入前的表长)时,在线性表L的第 i 个位置上插入一个值为 x 的新元素,这样使原序号为 i , i+1, . , n 的数据元素的序号变为 i+1,i+2, . , n+1,插入后表长 = 原表长+1。(6)DELETE_LIST(L,i) 删除操作,当线性表L存在,1in时,在线性表L中删除序号为i的数据元素,删除后使序号为 i+1, i+2, . , n 的元素变为序号为 i , i+1, . , n-1,新表长原表长-。2.1 线性表的概念和
4、基本操作线性表的概念和基本操作 2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 2.2.1 顺序表的定义顺序表的定义l线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称其为顺序表。 线性表的顺序存储示意图 l第i个数据元素的地址为: Loc(ai)=Loc(a)+(i-1)*d 1inl从结构性上考虑,通常将data和last封装成一个结构体作为顺序表的类型,具体描述如下表示:2.2.1 顺序表的定义 #define MAXSIZE 100 #define datatype int typedef struct datatype
5、 dataMAXSIZE ; int last ; SEQLIST ;2.2.1 顺序表的定义l顺序表的初始化问题,顺序表的初始化即构造一个空表,这对表是一个加工型的运算,因此,将L设为指针参数,首先动态分配存储空间,然后,将表中 last 设置为0,表示表中没有数据元素。算法如下: SEQLIST *init_seqlist( ) SEQLIST *L; L=(SEQLIST *)malloc(sizeof(SEQLIST); L-last=0; return L; 2.2.1 顺序表的定义l线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素,插入后使原表长为 n的表(a1,a2,
6、.,ai-1,ai,ai+1,.,an)成为表长为 n+1表(a1,a2,.,ai-1,x,ai,ai+1,.,an)。i 的取值范围为1in+1。 步骤如下: 将aian 顺序向下移动,为新元素让出位置; 将 x 置入空出的第i个位置; 修改 last 指针(相当于修改表长),使之增加1。 2.2.2 顺序表上元素的插入顺序表上元素的插入 l算法如下: int insert_seqlist(SEQLIST *L,int i,datatype x) int j; if (L-last=MAXSIZE) printf(表已满); return(-1); /*表空间已满,不能插入*/ if ( i
7、 L-last+1 ) /*检查插入位置的正确性*/ printf(位置错);return(0); 2.2.2 顺序表上元素的插入顺序表上元素的插入 for(j=L-last ; j=i ; j- ) L-dataj=L-dataj-1; /* 结点依次向后移动 */ L-datai-1=x; /*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1); /*插入成功,返回*/ 2.2.2 顺序表上元素的插入顺序表上元素的插入l设在第i个位置上作插入的概率为pi,则平均移动数据元素的次数:l设:pi=1/ (n+1) ,即为等概率情况,则:l在顺序表上做插入操作
8、需移动表中一半的数据元素。显然时间复杂度为(n) 11)1(Eniiininp11112)1(11)1(Eniniiinninninp2.2.2 顺序表上元素的插入顺序表上元素的插入l顺序表上元素的删除 线性表的删除运算是指将表中第 i 个元素从线性表中去掉,删除后使原表长为 n 的线性表(a1,a2,. ,ai-1,ai,ai+1,.,an)成为表长为 n-1 的线性表(a1,a2,. ,ai-1, ai+1,. ,an)。i 的取值范围为:1in 。l顺序表上完成这一运算的步骤如下: 将ai+1an 顺序向上移动。 修改last指针(相当于修改表长),使之减1。 2.2.2 顺序表上元素的
9、顺序表上元素的删除删除l顺序表上元素的定位 顺序表上元素的定位主要为按值查找,按值查找是指在线性表中查找与给定值x相等的数据元素。在顺序表中完成该运算最简单的方法是:从第一个元素 a1 起依次和x比较,直到找到一个与x相等的数据元素,则返回它在顺序表中的存储下标或序号(二者差一);或者查遍整个表都没有找到与 x 相等的元素,返回0。2.2 线性表的顺序存储定位线性表的顺序存储定位2.3 线性表的链式存储结构线性表的链式存储结构l顺序表的存储特点是用物理上的相邻实现了逻辑上的相邻,它要求用连续的存储单元顺序存储线性表中各元素,因此,对顺序表插入、删除时需要通过移动数据元素来实现,影响了运行效率。
10、l 本节介绍线性表链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理上也相邻,它是通过“链”建立起数据元素之间的逻辑关系来,因此对线性表的插入、删除不需要移动数据元素。l单链表的定义 为建立起数据元素之间的线性关系,对每个数据元素ai,除了存放数据元素的自身的信息ai之外,还需要和ai一起存放其后继ai+1所在的存储单元的地址,这两部分信息组成一个“结点”,结点的结构如图所示每个元素都如此。存放数据元素信息的称为数据域,存放其后继地址的称为指针域。n个元素的线性表通过每个结点的指针域拉成了一个“链子”,称之为链表。因为每个结点中只有一个指向后继的指针,所
11、以称其为单链表。datanext2.3.1 单链表的定义和操作实现单链表的定义和操作实现l链表是由一个个结点构成的,结点定义如下: typedef struct node datatype data; struct node *next; LINKLIST;l作为线性表的一种存储结构,我们关心的是结点间的逻辑结构,而对每个结点的实际地址并不关心,所以通常的单链表用下图表示。 2.3.1 单链表的定义和操作实现单链表的定义和操作实现l建立单链表 (1)头插入法建立链表 链表与顺序表不同,它是一种动态管理的存储结构,链表中的每个结点占用的存储空间不是预先分配,而是运行时系统根据需求而生成的,因此建
12、立单链表从空表开始,每读入一个数据元素则申请一个新结点,然后将此结点放在链表中已有结点的前面,作为新链表的第一个结点,因此称为头部插入法。如图所示:2.3.1 单链表的定义和操作实现单链表的定义和操作实现l算法如下: LINKLIST *creat_linklist1( ) LINKLIST *H=NULL; /*空表*/ LINKLIST *s; int x; /*设数据元素的类型为int*/ scanf(%d,&x); while (x!=flag) s=( LINKLIST *)malloc(sizeof(LINKLIST); s-data=x; s-next=H; H=s; scanf
13、 (%d,&x); return H; 头插入建立单链表简单,但读入的数据元素的顺序与生成的链表中元素的顺序是相反的,若希望次序一致,则用尾插入的方法。2.3.1 单链表的定义和操作实现单链表的定义和操作实现l(2)尾插入建立链表 尾插入算法建立链表的过程和头插入法正好相反,它每次都将新结点放在已有链表的最后面,成为新链表的尾结点。因为每次是将新结点插入到链表的尾部,需要先找到旧链表的尾结点,然后才能将新结点放在其后面,所以为了提高程序效率,需加入一个指针 r 用来始终指向链表中的尾结点,以便能够将新结点快速插入到链表的尾部。2.3.1 单链表的定义和操作实现单链表的定义和操作实现l算法如下:
14、 LINKLIST *creat_linklist2( ) LINKLIST *L=NULL; LINKLIST *s,*r=NULL; int x; /*设数据元素的类型为int*/ scanf(%d,&x); while (x!=flag) s=( LINKLIST *)malloc(sizeof(LINKLIST); s-data=x; if (L=NULL) L=s; /*第一个结点的处理*/ else r-next=s; /*其它结点的处理*/ r=s; /*r 指向新的尾结点*/ scanf(%d,&x); if ( r!=NULL) r-next=NULL; /*对于非空表,最后
15、结点的指针域放空指针*/ return L; 2.3.1 单链表的定义和操作实现单链表的定义和操作实现l头结点 在上面的算法中,第一个结点的处理和其它结点是不同的,原因是第一个结点加入时链表为空,它没有直接前驱结点,它的地址就是整个链表的指针,需要放在链表的头指针变量中;而其它结点有直接前驱结点,其地址放入直接前驱结点的指针域。 为了方便操作,有时在链表的头部加入一个“头结点”,头结点的类型与数据结点一致,标识链表的头指针变量L中存放该结点的地址,这样即使是空表,头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在,也使得“空表”和“非空表”的处理成为一致。 下图是带头结点的单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 900 线性
限制150内