数据结构及单链表.pptx

1例3 一张登记表DL 序号 姓 名 性 别 年 龄 1 李 刚 男 25 记录1 2 王 霞 女 29 记录2 3 刘大海 男 40 记录3 4 李爱林 男 44 记录4 其中：姓名、性别、年龄是数据项(item)、数据域(field)；(姓名，性别，年龄)是记录(record),C语言将记录(record)定义为”结构”(struct)；登记表也是一个线性表。第1页/共70页2例4 树状结构 其中:A、B、C等是结点(node)；A与B,B与E,A与C之间是层次关系或父子关系。河南工业大学(A)电气学院(B)管理学院(C)理学院(D)自动化系(E)电气系(F)测控系(G)第2页/共70页3例5 图状结构ABDCEFG其中：A、B、C 等是顶点(vertex),图中任意两个顶点之间都可能有关系。第3页/共70页4例6田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。姓姓 名名项目项目 项目项目 项目项目 丁丁 一一跳高跳高跳跳 远远 100 100 马马 二二标标 枪枪铅铅 球球张张 三三标标 枪枪100 100 200 200 李李 四四铅铅 球球200 200 跳跳 高高王王 五五跳跳 远远200 200 第4页/共70页5用如下六个不同的代号代表不同的项目：跳高 跳远 标枪 铅球 100米 200米 A B C D E F用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）。对图上的每个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。同色可以同时比赛。姓名姓名项目项目1 项目项目2 项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B F第5页/共70页6姓名姓名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B FA AE EB BF FD DC C比赛比赛时间时间比赛项比赛项目目1A，C2B，D3E4F 只需安排四个单位时间进行比赛第6页/共70页7综上几个例子可见，描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。第7页/共70页8计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法+数据结构=程序1976年，瑞士 N.Wirth教授第8页/共70页91.2 基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。第9页/共70页10数据结构 数据结构 定义1-在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D，S)(1-1)其中：D 是数据元素的有限集，S 是D上关系的有限集。数据结构主要指逻辑结构和物理结构第10页/共70页11数据之间的相互关系称为逻辑结构，即从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。通常分为四类基本结构：集合 结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构 结构中的数据元素之间存在一对一的关系。树形结构 结构中的数据元素之间存在一对多的关系。图状结构或网状结构 结构中的数据元素之间存在多对多的关系第11页/共70页12物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），依赖于计算机。存储结构可分为4大类：顺序、链式、索引、哈希第12页/共70页13顺序存储结构顺序存储结构顺序存储结构顺序存储结构 数据结点结构数据结点结构 把逻辑上相邻的结点存储在物理位置相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现，通常在程序设计中用数组表示。顺序存储是把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。连续存放。逻辑上相邻，物理上也相邻；结构简单，易实现；插入、删除操作不便（需大量移动元素）。第13页/共70页14链式存储结构链式存储结构链式存储结构链式存储结构 数据结点结构数据结点结构 逻辑上相邻的结点在物理位置可不相邻。结点之间的逻辑关系是由附加的指针字段表示的。即在每一格数据元素中增加一个存放地址的指针，用指针来表示数据元素之间的逻辑关系。以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。通常用程序设计语言中的指针类型来描述。非连续存放，借助指针来表示元素间的关系；插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。第14页/共70页15索引存储结构索引存储结构索引存储结构索引存储结构 数据结点结构数据结点结构 在建立结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字、地址），关键字是唯一标识一个结点的那些数据项。每个结点在索引表中对应一个索引项，称该索引表为稠密索引，一组结点在索引表中对应一个索引项称该索引表为稀疏索引。通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。非连续存放；检索速度快；增、删操作简单。第15页/共70页16散列存储结构散列存储结构散列存储结构散列存储结构在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到的存储地址，即D=F（E）。哈希查找中的哈希表就是这样一种存储结构。特点：数据元素间无内在联系；存储形式不定。第16页/共70页17例：复数3.02.3i 的两种存储方式：2.303043.00300040803043.0030004082.3法1：地址 内容法2：地址 内容第17页/共70页18同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求数据结构基本操作的实现：基本操作在计算机上的实现（方法）第18页/共70页19第19页/共70页20逻辑结构和存储结构的关系逻辑结构和存储结构的关系逻辑结构和存储结构的关系逻辑结构和存储结构的关系数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。第20页/共70页21如何描述存储结构可以借用高级程序语言中提供的“数据类型”来描述它.例如:可以用“一维数组”类型来描述顺序存储结构，以C语言提供的“指针”来描述链式存储结构假如把C语言看成是一个执行C指令和C数据类型的虚拟处理器，那么讨论的存储结构是数据结构在C虚拟处理器中的表示，不妨称它为虚拟存储结构第21页/共70页22数据的存储结构可用C语言的数据类型描述（定义）的，主要用到下列数据类型：数组，结构，指针1 数组数组类型变量（数组变量）由一组类型相同的数据元素组成数组的类型定义和变量定义typedef 数组元素类型名 数组类型名常量表达式；数组类型名 数组变量名；例 某班30个学生的数学成绩，可以用有30个分量的整型数组变量存储。Typedef int Scores30;Scores class051;第22页/共70页23该数组在内存中的存储示意图class051 0 xFF00 0 xFF04 0 xFF08 0 xFF74 85 77 68 82第23页/共70页242 结构结构类型变量（结构变量）由一组类型可以不同的数据元素组成结构的类型定义和变量定义typedef 结构定义 结构类型名；结构类型名 结构变量名；例 一本书可以用有2个成员（数据域）的结构变量存储。Typedef struct int no;char title40;BookType;BookType book1;第24页/共70页25该结构变量在内存中的存储示意图 0 xFF00 0 xFF04 0 xFF05 0 xFF2B154685(0 x00025C3D)DATASTbook1notitle3D5C0200第25页/共70页263 指针指针类型变量（指针变量）用于存储变量地址（或称指向该变量）指针的类型定义和变量定义 typedef 结构定义 *指针的类型名；指针的类型名 指针变量名例typedef struct int no;char title;*BookPtr;BookPtr pbook;第26页/共70页27该变量在内存中的存储示意图 0 xAF00 0 xAF04 0 xAF05 0 xAF2B 154685 D A T A S T 0 xAF00notitle0 xEF20pbookbook1第27页/共70页28线性表线性结构的特点熟练掌握两种存储结构的描述方法。链表是本章的重点和难点熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构第28页/共70页292.1 线性表的类型定义（a1,a2,ai-1，ai,ai1，,an）1.线性表的定义：是n个数据元素的有限序列n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点第29页/共70页30例例 分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表 （A,B,C,D,Z）学号姓名性别年龄班级2001011810205于春梅女 18计016班2001011810260何仕鹏男 18计017班2001011810284王 爽女 18计011班2001011810360王亚武男 18计012班：例 分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性第30页/共70页31线性表的抽象数据类型（ADT）其中只是一些基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void union(List&La，List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=lb-len;i+)GetElem(lb，i，e);if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e)第31页/共70页32例2-2 有线性表LA和LB，其元素均按非递减有序排列，编写一个算法将它们合并成一个线性表LC，且LC的元素也是按非递减有序排列。算法思路：依次扫描通过LA和LB的元素，比较当前的元素的值，将较小值的元素赋给LC，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给LC即可。LC的容量要能够容纳LA、LB两个线性表相加的长度第32页/共70页332.2 线性表的顺序表示和实现线性表的顺序表示又称为顺序存储结构或顺序映像逻辑上相邻，物理上也相邻用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）第33页/共70页34 线性表(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-最大长度,为某个常数。a1a1 a2a2 .aiai .anan /第34页/共70页35线性表顺序结构在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;第35页/共70页36线性表的顺序存储结构定义（动态）#define List_Init_size 100#define Listincrement 10struct SqList ElemType*elem;int length;int listsize;第36页/共70页37 顺序存储结构的寻址公式 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 a1a1a2a2.aiai.anan/第37页/共70页38插入算法实现举例设 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 第38页/共70页39算法2.4（p.24）插入操作移动元素次数的分析在（a1,a2,.,ai,.an)中ai之前插入新元素e(1=inext =first;first=newnode;（插入前）（插入后）newnodenewnodefirst first第50页/共70页51datanextqdatanextdatanextdatanull firstdatanextdatanextdatanull firstdatanextq第51页/共70页52在链表中间插入newnode-next=current-next;current-next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent第52页/共70页53datanextdatanextdatanull datanextqpdatanextdatanextdatanull datanextq第53页/共70页54在链表末尾插入newnode-next =current-next;current-next =newnode；(插入前)(插入后)newnodenewnodecurrentcurrent第54页/共70页55在链表中设置头结点在链表的首元结点之前附设的一个头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表第55页/共70页56带头结点的单链表 第一个结点前插入新结点firstnewnodefirstnewnode插入firstnewnodefirstnewnode插入ppppnewnode-next =p-next;p-next =newnode;第56页/共70页57从带头结点的单链表中删除第一个结点 q=p-next;p-next =q-next;delete q;firstfirst(非空表）firstfirst(空表）pqpq第57页/共70页58P30-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头结点第58页/共70页592.3.2 循环链表(Circular List)循环链表是单链表的变形。循环链表最后一个结点的 next 指针不 为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址第59页/共70页60循环链表的示例带表头结点的循环链表a1a2a3anfirstanfirsta2a1first(空表)(非空表)第60页/共70页61循环链表的运算与单链表类似，只是在涉及到链头与链尾的处理时稍有不同表尾插入第61页/共70页62用循环链表求解约瑟夫问题约瑟夫问题的提法 n 个人围成一个圆圈，首先第s个人从1开始逐个顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。Lab I第62页/共70页63void CreaList(NodeType*,const int);/*创建单向循环链表*/void CreaList(NodeType*&,const int);void StatGame(NodeType*,int,int);/*运行约瑟夫环问题*/void PrntList(NodeType*);/*打印循环链表*/void main()int n,s,m;NodeType*pHead=NULL;printf(请输入人数n（最多%d个）:,MAX_NODE_NUM);scanf(%d,&n);printf(初始s:);scanf(%d,&s);printf(“报数周期m:);scanf(%d,&m);CreaList(&pHead,n);PrntList(pHead);/循环链表原始打印 StatGame(&pHead,m);/出队情况打印第63页/共70页642.3.3 双向链表(Doubly Linked List)逆向扫描单链表困难双向链表是指在前驱和后继方向都能遍历的线性链表双向链表结点结构前驱方向 后继方向lLink data rLink第64页/共70页65带表头结点的双向循环链表结点指向p=p-lLink-rLink=p-rLink-lLink非空表 空表abfirstfirstp-lLinkp-rLinkp第65页/共70页66双向循环链表的插入算法(非空表)newnode-lLink=current;newnode-rLink=current-rLink;current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;firstfirst314815current后插入25current31482515newnode第66页/共70页67双向循环链表的插入算法(空表)first插入插入25currentcurrent25firstnewnode-lLink=current;newnode-rLink=current-rLink;(=first)current-rLink=newnode;current=current-rLink;current-rLink-lLink=current;(first -lLink=current)第67页/共70页68P37-38 带头节点的链表类型定义typedef struct LNode int data;LNode*next;*Position;typedef struct LNode*Head,*Tail;int len;*LinkList;第68页/共70页69第69页/共70页70感谢您的观看。第70页/共70页