基本数据结构及其运算3线性链表.ppt
《基本数据结构及其运算3线性链表.ppt》由会员分享,可在线阅读,更多相关《基本数据结构及其运算3线性链表.ppt(97页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第二二章章 基基本本数数据据公安海警学院公安海警学院2023/2/21主讲:胡云琴主讲:胡云琴结结构构及及运运算算 第第 2 章章 基本数据结构及运算基本数据结构及运算2.1 2.1 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念2.22.2线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构线性表及其顺序存储结构2.32.3线性链表线性链表线性链表线性链表2.42.4线性表的索引存储结构线性表的索引存储结构线性表的索引存储结构线性表的索引存储结构 2.52.5 数组数组数组数组2.6 2.6 树与二叉树树与二叉树树与二叉树树与二叉树2.7 2.7 图
2、图图图复复 习习提问提问1 1:线性表顺序存储结构具有哪些:线性表顺序存储结构具有哪些优点?优点?1 1)线性表顺序存储结构具有简单、运算)线性表顺序存储结构具有简单、运算方便等优点方便等优点,随机存取(时间复杂度为随机存取(时间复杂度为O(1)O(1)););2 2)无需为表示表中元素之间的逻辑关系)无需为表示表中元素之间的逻辑关系而增加额外的存储空间;而增加额外的存储空间;3 3)适合小规模、长度固定的线性表)适合小规模、长度固定的线性表2.线性表顺序存储结构具有哪些缺点?线性表顺序存储结构具有哪些缺点?在插入、删除时要移动大量的节点,效率低在插入、删除时要移动大量的节点,效率低表的大小固
3、定,容量难扩充,易出现上溢表的大小固定,容量难扩充,易出现上溢原因:原因:顺序存储的存储结构与逻辑结构是一致的。顺序存储的存储结构与逻辑结构是一致的。解决方法:解决方法:突破突破离散存放离散存放用指针来表示元素之间的关系。用指针来表示元素之间的关系。引入线性链表引入线性链表链接存储的线性表链接存储的线性表用链表实现线性表(非连续存储)用链表实现线性表(非连续存储)线性表元素:线性表元素:a1、a2、a3、a4.链表链点链表链点线性关系:线性关系:a1a2a3a4指针域,指针关系指针域,指针关系链表概述:链表概述:链表是一种常见的重要的数据结构。链表是一种常见的重要的数据结构。它是动态地进行存储
4、分配的一种结构。它是动态地进行存储分配的一种结构。“头指针头指针”,以变量以变量headhead表示表示,是线性表中第一个数是线性表中第一个数据元素的存储地址;据元素的存储地址;每个结点都应包括两部分每个结点都应包括两部分:用户需要用的实际数据和用户需要用的实际数据和下一结点的地址下一结点的地址(指针域指针域);最后一个结点最后一个结点,该结点的指针域不再指向其他结点该结点的指针域不再指向其他结点,它称为它称为 表尾表尾,它的指针域放一个它的指针域放一个NULL(NULL(表示表示 空地空地址址),),链表到此结束。链表到此结束。head 1249 1356 1475 1021 1356 14
5、75 1021 NULL1249 A B C D2.3.1 线性链表的基本概念线性链表的基本概念线性链表线性链表2.32.3.2 线性链表的基本运算线性链表的基本运算2.3.3 带链的栈与队列带链的栈与队列2.3.4 循环链表循环链表2.3.5 多项式的表示与运算多项式的表示与运算特点:特点:(1)(1)定义:采用链式存储结构的线性表称为链定义:采用链式存储结构的线性表称为链表表 ,其采用一组任意的存储单元来存,其采用一组任意的存储单元来存放线性表的数据元素(可零散的分布放线性表的数据元素(可零散的分布于内存单元的任何位置上)。于内存单元的任何位置上)。2.3.1 线性链表的基本概念线性链表的
6、基本概念结点之间可以连续,可以不连续存储结点之间可以连续,可以不连续存储结点的逻辑顺序与物理顺序可以不一致结点的逻辑顺序与物理顺序可以不一致表可扩充表可扩充(2)结点结点(Node)组成组成 通过指针域,不论结点的物理次序通过指针域,不论结点的物理次序如何,都可将其按逻辑顺序依次链接在如何,都可将其按逻辑顺序依次链接在一起构成线性表。一起构成线性表。数据域数据域存储数据元素本身存储数据元素本身数据域数据域指针域指针域指针域指针域存储下一元素的存储位置存储下一元素的存储位置链链顺序表顺序表存储地址存储地址 存储状态存储状态 0031 赵赵 0033 钱钱 0035 孙孙 0037 李李 0039
7、 周周 0041 吴吴 0043 郑郑 0045 王王 链表链表 存储地址存储地址 存储状态存储状态 0001 李李 0007 钱钱 0013 孙孙 0019 王王 0025 吴吴 0031 赵赵 0037 郑郑 0043 周周 0043 0013 0001 NULL 0037 0007 0019 0025头指针头指针 H 数据域数据域 0031 指针域指针域 结点结点 指指针针链链表表 线性表顺序存储与链表存储比较线性表顺序存储与链表存储比较 H 赵赵钱钱孙孙李李周周吴吴郑郑王王 线线性性表表具具有有两两种种存存储储方方式式,即即顺顺序序方方式式和和链链接接方方式式。现现有有一一个个具具有有
8、五五个个元元素素的的线线性性表表L=23L=23,1717,4747,0505,3131,若若它它以以链链接接方方式式存存储储在在下下列列100100119119号号地地址址空空间间中中,每每个个结结点点由由数数据据(占占2 2个个字字节节)和和指指针(占针(占2 2个字节)组成,如下图所示。个字节)组成,如下图所示。其其中中指指针针X X,Y Y,Z Z的的值值分分别别为为多多少少?该该线线性性表表的的首首结点起始地址为多少?末结点的起始地址为多少?结点起始地址为多少?末结点的起始地址为多少?Z Z4747Y Y3131V V2323X X1717U U0505100100100100119
9、119119119104104104104108108108108116116116116112112112112答:答:X=Y=Z=X=Y=Z=首址首址=末址末址=。例例1:116116116116NULL(0)NULL(0)NULL(0)NULL(0)100100100100112112112112108108108108(3)链表分类)链表分类单链表:只设置一个指向后继结点地址的单链表:只设置一个指向后继结点地址的指针域。指针域。循环链表:将其首尾相接构成一个环状循环链表:将其首尾相接构成一个环状结构。结构。双向链表:有两个指针域,分别指向本双向链表:有两个指针域,分别指向本结点的前驱结
10、点和后继结点的链表。结点的前驱结点和后继结点的链表。a1(1(1)定义:)定义:所有结点的指针域中只包含一个所有结点的指针域中只包含一个指针指针(存储直接后继结点的存储位置存储直接后继结点的存储位置)的链表。的链表。a2an空指针空指针头指针头指针头指针头指针头结点头结点带头结点的单链表带头结点的单链表单链表常用头指针来命名,如单链表常用头指针来命名,如 La,Head.La,Head.2.3.2 线性链表线性链表(单链表单链表)的基本运算的基本运算(2(2)头结点)头结点 在单链表的第一个结点之前人为地附设的一个结点。在单链表的第一个结点之前人为地附设的一个结点。数据域数据域 L a1a2a
11、n L 头指针头指针 头结点头结点头指针头指针头指针头指针存放头结点的地址,指向链表中第一个结点存放头结点的地址,指向链表中第一个结点(或为头结点或第一个元素)的指针。(或为头结点或第一个元素)的指针。头结点头结点 不存放任何数据不存放任何数据 存放附加信息存放附加信息(链表的结点个数等链表的结点个数等)指针域指针域 存放第一个结点的地址存放第一个结点的地址 (若线性表为空表,则(若线性表为空表,则“空空”,用,用 表示。)表示。)可以看到,空表和非空表不统一可以看到,空表和非空表不统一heada1a2an非空表非空表head=NULL空表空表带头结点的非空表带头结点的非空表heada1a2a
12、n带头结点的空表带头结点的空表head设置头结点的好处:设置头结点的好处:起始结点位置存放在头结点起始结点位置存放在头结点指针域中,故在链表第一个位置上操作与表中其他指针域中,故在链表第一个位置上操作与表中其他位置上操作一致,无须特殊处理。位置上操作一致,无须特殊处理。头指针头指针HeadHead始终是指向头结点的非空指针,统一始终是指向头结点的非空指针,统一了空表与非空表的操作,简化链表操作的实现。了空表与非空表的操作,简化链表操作的实现。请写出该线性链表的逻辑顺序和链表结构图?请写出该线性链表的逻辑顺序和链表结构图?存存储储地址地址数据域数据域指指针针域域1D437B1313C119HNU
13、LL25F3731A737G1943E25头指针头指针H31AHBC头指针头指针头指针头指针例例2 2:一个线性表的逻辑结构为:(:一个线性表的逻辑结构为:(ZHAO,QIAN,SUN,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGLI,ZHOU,WU,ZHENG,WANG),其存储结构用单链表表),其存储结构用单链表表示如下,请问其头指针的值是多少?示如下,请问其头指针的值是多少?存储地址存储地址数据域数据域指针域指针域1 1LILI43437 7QIANQIAN13131313SUNSUN1 11919WANGWANGNULLNULL2525WUWU37373131
14、ZHAOZHAO7 73737ZHENGZHENG19194343ZHOUZHOU25257 7ZHAOZHAOH H31头指针头指针头指针头指针H H H H的值是的值是的值是的值是31313131在在线线性性链链表表中中包包含含指指定定元元素素的的结结点点之之前前插插入入一一个个新新元素。元素。在线性链表中删除包含指定元素的结点。在线性链表中删除包含指定元素的结点。将两个线性链表按要求合并成一个线性链表。将两个线性链表按要求合并成一个线性链表。将一个线性链表按要求进行分解。将一个线性链表按要求进行分解。逆转线性链表。逆转线性链表。复制线性链表。复制线性链表。线性链表的排序。线性链表的排序。
15、线性链表的查找。线性链表的查找。2.3.2 线性链表的基本运算线性链表的基本运算 1、线性链表的插入、线性链表的插入2、线性链表的删除、线性链表的删除3、线性链表类、线性链表类2.3.2 线性链表的基本运算线性链表的基本运算 1、线性链表的插入、线性链表的插入线性链表的插入是指在链式存储结构下的线性线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。表中插入一个新元素。为了插入一个新元素,首先要给该元素分配一个为了插入一个新元素,首先要给该元素分配一个新结点,以便用于存储该元素的值,新结点可从可新结点,以便用于存储该元素的值,新结点可从可利用栈中取得,然后将存放新元素值的结点链接到利用
16、栈中取得,然后将存放新元素值的结点链接到线性链表中指定的位置。线性链表中指定的位置。1、线性链表的插入、线性链表的插入可利用栈与线性链表可利用栈与线性链表 1、线性链表的插入、线性链表的插入(1)(1)从可利用栈取得一个结点,设该结点号为从可利用栈取得一个结点,设该结点号为p p。并置结点并置结点p p的数据域为插入的元素值的数据域为插入的元素值b b,即,即V(p)V(p)b b。(2)(2)在线性链表中寻找包含元素在线性链表中寻找包含元素x x的前一个结点的前一个结点q q。1、线性链表的插入、线性链表的插入(3)(3)将结点将结点p p插入到结点插入到结点q q之后:之后:使结点使结点p
17、 p指向包含元素指向包含元素x x的结点,即的结点,即 NEXT(p)NEXT(p)NEXT(q)NEXT(q)使结点使结点q q的指针域内容改为指向结点的指针域内容改为指向结点p p,即,即 NEXT(q)NEXT(q)p p#include stdlib.h#include stdlib.hstruct node /*struct node /*定义结点类型定义结点类型*/ET d ET d;struct node *nextstruct node *next;inslst(headinslst(head,x x,b)b)ET xET x,b b;struct node *headstru
18、ct node *head;struct node *p struct node *p,*q q;p p(struct node*)malloc(sizeof(struct node)(struct node*)malloc(sizeof(struct node);p pddb b;/*/*置结点的数据域置结点的数据域*/if(*head if(*headNULL)/*NULL)/*链表为空链表为空*/*head *headp p;p pnextnextNULLNULL;returnreturn;if(*head if(*headd)d)x)/*x)/*在第一个结点前插入在第一个结点前插入*/
19、p pnextnext*headhead;*headheadp p;returnreturn;q qlookst(*headlookst(*head,x)x);/*/*寻找包含元素寻找包含元素x x的前一个结点的前一个结点q*/q*/p pnextnextq qnextnext;q qnextnextp p;/*/*结点结点p p插到结点插到结点q q之后之后*/return return;2、线性链表的删除、线性链表的删除在链式存储结构下的线性表中在链式存储结构下的线性表中 删除包含指定删除包含指定元素的结点。元素的结点。为了在线性链表中删除包含指定元素的结点,首为了在线性链表中删除包含指定
20、元素的结点,首先要在线性链表中找到这个结点,然后将要删除结先要在线性链表中找到这个结点,然后将要删除结点放回到可利用栈。点放回到可利用栈。2、线性链表的删除、线性链表的删除其删除过程如下:其删除过程如下:(1)在线性链表中寻找包含元素在线性链表中寻找包含元素x的前一个结点,设的前一个结点,设该结点序号为该结点序号为q,则包含元素,则包含元素x的结点序号的结点序号p=NEXT(q)。2、线性链表的删除、线性链表的删除其删除过程如下:其删除过程如下:(2)将结点将结点q后的结点后的结点p从线性链表中删除,即让结从线性链表中删除,即让结点点q的指针指向包含元素的指针指向包含元素x的结点的结点p的指针
21、指向的结的指针指向的结点,即点,即NEXT(q)=NEXT(p)。2、线性链表的删除、线性链表的删除其删除过程如下:其删除过程如下:(3)将包含元素将包含元素x的结点的结点p送回可利用栈送回可利用栈。#include stdlib.h#include stdlib.hstruct node /*struct node /*定义结点类型定义结点类型*/ET d ET d;struct node *nextstruct node *next;delst(headdelst(head,x)x)ET xET x;struct node *headstruct node *head;struct nod
22、e *p struct node *p,*q q;if(*headif(*headNULL)/*NULL)/*链表为空链表为空*/printf(This is a empty list!n)printf(This is a empty list!n);returnreturn;if(*head if(*headd)d)x)/*x)/*删除第一个结点删除第一个结点*/p p*headheadnextnext;free(*head)free(*head);*headheadp p;returnreturn;q qlookst(*headlookst(*head,x)x);/*/*寻找包含元素寻找包
23、含元素x x的前一个结点的前一个结点q*/q*/if(q if(qnextnextNULL)/*NULL)/*链表中没有包含元素链表中没有包含元素x x的结点的结点*/printf(No this node in the list!n)printf(No this node in the list!n);returnreturn;p pq qnext next;q qnextnextp pnextnext;/*/*删除结点删除结点p*/p*/free(p)free(p);/*/*释放结点释放结点p*/returnp*/return;3、线性链表类、线性链表类/linked_List.h#inc
24、lude using namespace std;/定义结点类型定义结点类型template /T为虚拟类型为虚拟类型 struct nodeT d;node*next;3、线性链表类、线性链表类/定义单链表类定义单链表类template /模板声明,数据元素虚拟类型为模板声明,数据元素虚拟类型为Tclass linked_Listprivate:/数据成员数据成员node*head;/链表头指针链表头指针public:/成员函数成员函数linked_List();/构造函数,建立空链表构造函数,建立空链表 int flag_linked_List();void prt_linked_List
25、();/扫描输出链表中的元素扫描输出链表中的元素void ins_linked_List(T);/在包含元素在包含元素x的结点前插入新元素的结点前插入新元素T del_linked_List();/删除包含元素删除包含元素x的结点的结点;3、线性链表类、线性链表类/建立空链表建立空链表templatelinked_List:linked_List()head=NULL;return;/检测单链表检测单链表templateint linked_List:flag_linked_List()if(head=NULL)return(0);return(1);3、线性链表类、线性链表类/从头指针开始扫
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 数据结构 及其 运算 线性
限制150内