数据结构及单链表.ppt

1,3.2 数据结构定义及概念,1.1什么是数据结构建立数学模型是分析具体问题的过程，包括：分析具体问题中操作对象找出这些对象间的关系，并用数学语言描述数学模型分两类：1）数值计算类：例：根据三条边，求三角形面积。假定：三条边依次为a,b,c三个实型数，满足：a0,b 0,c0,a+bc,b+ca,c+ab,则 s=area=,2,2）非数值计算类：例1:5个整数组成的集合：D=20,-5，66,15,44其中:20,-5,66等称为数据元素(元素)，元素与元素之间关系是它们同属于集合D。D=20,-5,66,15,44是一个数据对象例2:一列整数：(线性结构)L=(20,-5，66,15,44）其中:元素与元素之间在L中是前后关系或线性关系。L=(20,-5,66,15,44)是一个线性表。,3,例3 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将记录(record)定义为”结构”(struct)；登记表也是一个线性表。,4,例4 树状结构,其中:A、B、C等是结点(node)；A与B,B与E,A与C之间是层次关系或父子关系。,5,例5 图状结构,A,B,D,C,E,F,G,其中：A、B、C 等是顶点(vertex),图中任意两个顶点之间都可能有关系。,6,例6田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,7,用如下六个不同的代号代表不同的项目：跳高 跳远 标枪 铅球 100米 200米 A B C D E F用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）。对图上的每个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。同色可以同时比赛。,8,A,E,B,F,D,C,只需安排四个单位时间进行比赛,9,综上几个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。,10,计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法+数据结构=程序1976年，瑞士 N.Wirth教授,11,1.2 基本概念和术语,数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。,12,数据结构 数据结构 定义1-在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D，S)(1-1)其中：D 是数据元素的有限集，S 是D上关系的有限集。数据结构主要指逻辑结构和物理结构,13,数据之间的相互关系称为逻辑结构，即从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。通常分为四类基本结构：集合 结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构 结构中的数据元素之间存在一对一的关系。树形结构 结构中的数据元素之间存在一对多的关系。图状结构或网状结构 结构中的数据元素之间存在多对多的关系,14,物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），依赖于计算机。存储结构可分为4大类：顺序、链式、索引、哈希,15,顺序存储结构,数据结点结构,把逻辑上相邻的结点存储在物理位置相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现，通常在程序设计中用数组表示。顺序存储是把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。,连续存放。逻辑上相邻，物理上也相邻；结构简单，易实现；插入、删除操作不便（需大量移动元素）。,16,链式存储结构,数据结点结构,逻辑上相邻的结点在物理位置可不相邻。结点之间的逻辑关系是由附加的指针字段表示的。即在每一格数据元素中增加一个存放地址的指针，用指针来表示数据元素之间的逻辑关系。以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。通常用程序设计语言中的指针类型来描述。,非连续存放，借助指针来表示元素间的关系；插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。,17,索引存储结构,数据结点结构,在建立结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字、地址），关键字是唯一标识一个结点的那些数据项。每个结点在索引表中对应一个索引项，称该索引表为稠密索引，一组结点在索引表中对应一个索引项称该索引表为稀疏索引。通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。,非连续存放；检索速度快；增、删操作简单。,18,散列存储结构,在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到的存储地址，即D=F（E）。哈希查找中的哈希表就是这样一种存储结构。特点：数据元素间无内在联系；存储形式不定。,19,例：复数3.02.3i 的两种存储方式：,法1：地址 内容,法2：地址 内容,20,同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求数据结构基本操作的实现：基本操作在计算机上的实现（方法）,21,22,逻辑结构和存储结构的关系,数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。,23,如何描述存储结构可以借用高级程序语言中提供的“数据类型”来描述它.例如:可以用“一维数组”类型来描述顺序存储结构，以C语言提供的“指针”来描述链式存储结构假如把C语言看成是一个执行C指令和C数据类型的虚拟处理器，那么讨论的存储结构是数据结构在C虚拟处理器中的表示，不妨称它为虚拟存储结构,24,数据的存储结构可用C语言的数据类型描述（定义）的，主要用到下列数据类型：数组，结构，指针1 数组数组类型变量（数组变量）由一组类型相同的数据元素组成数组的类型定义和变量定义typedef 数组元素类型名 数组类型名常量表达式；数组类型名 数组变量名；例 某班30个学生的数学成绩，可以用有30个分量的整型数组变量存储。Typedef int Scores30;Scores class051;,25,该数组在内存中的存储示意图,class051,0 xFF00 0 xFF04 0 xFF08 0 xFF74,85 77 68 82,26,2 结构结构类型变量（结构变量）由一组类型可以不同的数据元素组成结构的类型定义和变量定义typedef 结构定义 结构类型名；结构类型名 结构变量名；例 一本书可以用有2个成员（数据域）的结构变量存储。Typedef struct int no;char title40;BookType;BookType book1;,27,该结构变量在内存中的存储示意图,0 xFF00 0 xFF04 0 xFF05 0 xFF2B,154685(0 x00025C3D)DATAST,book1,notitle,3D5C0200,28,3 指针指针类型变量（指针变量）用于存储变量地址（或称指向该变量）指针的类型定义和变量定义 typedef 结构定义*指针的类型名；指针的类型名 指针变量名例typedef struct int no;char title;*BookPtr;BookPtr pbook;,29,该变量在内存中的存储示意图,0 xAF00 0 xAF04 0 xAF05 0 xAF2B,154685 D A T A S T 0 xAF00,notitle,0 xEF20,pbook,book1,30,线性表,线性结构的特点熟练掌握两种存储结构的描述方法。链表是本章的重点和难点熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构,31,2.1 线性表的类型定义,（a1,a2,ai-1，ai,ai1，,an）,1.线性表的定义：是n个数据元素的有限序列,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,32,例 分析26 个英文字母组成的英文表,（A,B,C,D,Z）,例 分析学生情况登记表,数据元素都是记录;元素间关系是线性,数据元素都是字母;元素间关系是线性,同一线性表中的元素必定具有相同特性,33,线性表的抽象数据类型（ADT）其中只是一些基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现,例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void union(List if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e),34,例2-2 有线性表LA和LB，其元素均按非递减有序排列，编写一个算法将它们合并成一个线性表LC，且LC的元素也是按非递减有序排列。算法思路：依次扫描通过LA和LB的元素，比较当前的元素的值，将较小值的元素赋给LC，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给LC即可。LC的容量要能够容纳LA、LB两个线性表相加的长度,35,2.2 线性表的顺序表示和实现,线性表的顺序表示又称为顺序存储结构或顺序映像逻辑上相邻，物理上也相邻用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）,36,线性表(a1,a1,a2,.an)顺序存储结构的一般形式 序号 存储状态 存储地址 1 b 2 b+p i b+(i-1)*p n b+(n-1)*p 自由区 maxleng b+(maxleng-1)*p其中:b-表的首地址/基地址/元素a1的地址。p-1个数据元素所占存储单元的数目。maxleng-最大长度,为某个常数。,37,线性表顺序结构在C语言中的定义 其中：SqList-结构类型名 La-结构类型变量名 La.length-表长 La.elem0-a1 La.elemLa.length-1-an,#define maxleng 100 struct SqList ElemType elemmaxleng;/下标:0,1,.,maxleng-1 int length;/表长;SqList La;,38,线性表的顺序存储结构定义（动态）,#define List_Init_size 100#define Listincrement 10struct SqList ElemType*elem;int length;int listsize;,39,顺序存储结构的寻址公式 i=1 2 i n 地址=b b+1 b+(i-1)p b+(n-1)p 假设:线性表的首地址为b,每个数据元素占p个存储 单元,则表中任意元素ai(1in)的存储地址是:LOC(i)=LOC(1)+(i-1)*p=b+(i-1)*p(1in)例:假设 b=1024,p=4,i=35 LOC(i)=b+(i-1)*p=1024+(35-1)*4=1024+34*4=1160,40,插入算法实现举例设 L.elem0.maxleng-1中有legth个元素，在 L.elemi-1之插入新元素e，1=i=length 例.i=3,e=6,length=6 插入6之前：2 5 8 20 30 35/0 1 2 3 4 5 6 7 8 35,30,20,8 依次后移一个位置 插入6之后：2 5 6 8 20 30 35/0 1 2 3 4 5 6 7 8,41,算法2.4（p.24）插入操作移动元素次数的分析在（a1,a2,.,ai,.an)中ai之前插入新元素e(1=i=n+1)，当 i=1 2 3 j n n+1移动元素次数个数:n n-1 n-2 n-i+1 1 0假定在各位置插入元素的概率相同，则插入一个元素时移动元素的平均值是n/2删除操作移动元素次数的分析当 i=1 2 3.i.n 移动元素次数个数=n-1 n-2.n-i.0假定在各位置插入元素的概率相同，则删除一个元素时移动元素的平均值是(n-1)/2算法2.7（p.26）,42,顺序存储结构的评价优点：(1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快；(2)结构简单，逻辑上相邻的元素在物理上也是相邻的；(3)不使用指针，节省存储空间。缺点：(1)插入和删除元素要移动大量元素，消耗大量时间；(2)需要一个连续的存储空间；(3)插入元素可能发生“溢出”；(4)自由区中的存储空间不能被其它数据共享,43,2.3 线性表的链式存储结构,顺序表：随机存取链表：逻辑相邻，物理不一定相邻特点每个元素(表项)由结点(Node)构成。线性结构结点可以不连续存储表可扩充适用于存储空间需求不定、插入或删除频繁的情形,data next,a1,a2,a3,a4,a5,first,44,free,(a)可利用存储空间,a0,a2,a1,a3,free,first,(b)经过一段运行后的单链表结构,单链表的存储映像,45,2.3.1 线性链表,用一组任意的存储单元存储线性表的数据元素，可以是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的地址（或位置）信息，这个信息称为指针(pointer)或链(link)结点数据域：元素本身信息指针域：指示直接后继的存储位置,46,31,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,H,例 线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,31,H,头指针,47,结点：数据元素的存储映像。由数据域和指针域两部分组成；链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。,48,头指针、头结点和首元结点头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点,49,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,例：,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,头指针的值是31,50,上例链表的逻辑结构示意图有以下两种形式：,区别：无头结点 有头结点,51,单链表的C定义,或,typedef struct node*LPointer;struct node int data;LPointer next;,typedef struct node int data;node*next;*LinkList;,52,单链表的插入,在第一个结点前插入newnode-next=first;first=newnode;,53,data,next,q,data,next,data,next,data,null,first,data,next,data,next,data,null,first,data,next,q,54,在链表中间插入newnode-next=current-next;current-next=newnode；,55,data,next,data,next,data,null,data,next,q,p,data,next,data,next,data,null,data,next,q,56,在链表末尾插入newnode-next=current-next;current-next=newnode；,57,在链表中设置头结点在链表的首元结点之前附设的一个头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表,58,带头结点的单链表 第一个结点前插入新结点,first,newnode,first,newnode,插入,first,newnode,first,newnode,插入,p,p,p,p,newnode-next=p-next;p-next=newnode;,59,从带头结点的单链表中删除第一个结点,q=p-next;p-next=q-next;delete q;,first,first,(非空表）,first,first,(空表）,p,q,p,q,60,P30-31 算法2.9、2.10、2.11、2.12就地逆置一个带头结点的链表静态链表（自学）,LNode*p,*head=new LNode;/(LPointer)malloc(sizeof(LNode)/创建新头结点while(h!=NULL)p=h;h=h-next;/摘下h链头结点 p-next=head-next;head-next=p;/插入head链前端h=head-next;delete head;/重置h,删去head头结点,61,2.3.2 循环链表(Circular List),循环链表是单链表的变形。循环链表最后一个结点的 next 指针不 为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址,62,循环链表的示例,带表头结点的循环链表,63,循环链表的运算与单链表类似，只是在涉及到链头与链尾的处理时稍有不同表尾插入,64,用循环链表求解约瑟夫问题,约瑟夫问题的提法 n 个人围成一个圆圈，首先第s个人从1开始逐个顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。Lab I,65,void CreaList(NodeType*,const int);/*创建单向循环链表*/void CreaList(NodeType*/出队情况打印,66,2.3.3 双向链表(Doubly Linked List),逆向扫描单链表困难双向链表是指在前驱和后继方向都能遍历的线性链表双向链表结点结构,67,带表头结点的双向循环链表,结点指向p=p-lLink-rLink=p-rLink-lLink,68,双向循环链表的插入算法(非空表),newnode-lLink=current;newnode-rLink=current-rLink;current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;,69,双向循环链表的插入算法(空表),newnode-lLink=current;newnode-rLink=current-rLink;(=first)current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;(first-lLink=current),70,P37-38 带头节点的链表类型定义,typedef struct LNode int data;LNode*next;*Position;typedef struct LNode*Head,*Tail;int len;*LinkList;,