第2章线性数据结构.

第2章线性数据结构1065865姓名学号成绩班级李红976105995机97.6第2章线性数据结构第2章线性数据结构2.1基本概念2.1.1数据和数据结构2.1.2算法的描述和评价2.2线性表2.2.1线性表的定义及操作2.2.2线性表的顺序存储结构2.2.3线性表的链式存储结构2.2.4循环链表和双向链表2.3栈和队列2.3.1栈2.3.2队列第2章线性数据结构2.1基本概念2.1.1数据和数据结构数据就是信息的载体,它可以用计算机表示并加工。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如字符、文字、表格、图形、图像、声音等也属于数据的范畴。返回本章目录第2章线性数据结构数据元素是数据集合中的一个个体，它是组成数据的基本单位。例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。数据元素可以是一个数或字符串，也可以由若干数据项组成(数据的最小单位)，在这种情况下，通常把数据元素称为记录。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。返回本章目录第2章线性数据结构表2-1学生学籍登记表学号姓名性别民族籍贯专业1王安男汉北京计算机通信2李华男回河北软件3张莉女汉山西计算机应用4张平女汉广东软件返回本章目录第2章线性数据结构数据结构就是研究数据及数据元素之间关系的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容：●数据的逻辑结构。●数据的存储结构。●数据的运算。返回本章目录第2章线性数据结构1.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储B.链式存储线性表栈队树形结构图形结构数据结构的三个方面反映数据元素之间的逻辑关系数据元素在计算机内部的组织方式C.散列结构（散列表）D.索引结构（索引表）第2章线性数据结构1.数据的逻辑结构数据的逻辑结构就是数据元素之间的逻辑关系。可以用一个二元组，给出其形式定义为DataStructure=(D，R)其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。根据数据元素之间关系的不同特性，数据结构又可分为两大类：线性数据结构和非线性数据结构。返回本章目录第2章线性数据结构图2-1数据结构分类线性表栈队列串数组线性数据结构树图非线性数据结构数据结构返回本章目录第2章线性数据结构2．数据的存储结构数据的逻辑结构是从逻辑上来描述数据元素之间的关系的，是独立于计算机的。还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结构。计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。数据的存储结构要讨论的就是数据结构在计算机存储器上的存储映像方法。返回本章目录第2章线性数据结构实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说，数据在存储器中的存储有四种基本的映像方法。(1)顺序存储结构。这种存储方式主要用于线性数据结构，就是把数据元素按某种顺序放在一块连续的存储单元中。其特点是逻辑上相邻的数据元素存储在物理上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。返回本章目录第2章线性数据结构(2)链式存储结构。链式存储结构可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。即可用一组任意的存储单元来存储数据元素，这些存储单元可以是连续的，也可以是不连续的。链式存储结构的特点就是将存放每个数据元素的结点分为两部分：一部分存放数据元素(称为数据域),另一部分存放指示存储地址的指针(称为指针域)，借助指针表示数据元素之间的逻辑关系。第2章线性数据结构(3)索引存储结构。在线性表中，数据元素可以排成一个序列：R1、R2、R3、…、Rn，每个数据元素Ri在序列里都有对应的位置数据i，这就是元素的索引。索引存储结构就是通过数据元素的索引号i来确定数据元素Ri的存储地址。一般索引存储结构的实现方法是建立附加的索引表，索引表里第i项的值就是第i个元素的存储地址。第2章线性数据结构(4)散列存储结构。这种存储方法就是在数据元素与其在存储器上的存储位置之间建立一个映像关系F。根据这个映像关系F，已知某数据元素就可以得到它的存储地址。即D=F(E)，这里E是要存放的数据元素，D是该数据元素的存储位置。可见，这种存储结构的关键是设计这个函数F。但函数F不可能解决数据存储中的所有问题，还应有一套意外事件的处理方法，它们共同实现数据的散列存储结构。本书第4章中介绍的哈希表，就是散列存储结构的一个实例。返回本章目录第2章线性数据结构3.数据的运算数据的运算是定义在数据逻辑结构上的操作，每种数据结构都有一个运算的集合。常用的运算有检索、插入、删除、更新、排序等。运算的具体实现要在存储结构上进行。返回本章目录第2章线性数据结构2.2线性表2.2.1线性表的定义及操作定义2-1线性表(Linear-list)是n(n≥0)个数据元素的有限序列。记为：(a1，a2,...,an)其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。第2章线性数据结构线性表的逻辑结构：若线性表是非空表，则第一个元素a1无前趋，最后一个元素an无后继，其它元素ai(1in)均只有一个直接前驱ai-1和一个直接后继ai+1。第2章线性数据结构线性表的特点:同一性。线性表中每个数据元素ai的具体含义，在不同情况下各不相同，它可以是一个数，或是一个符号，甚至是其它更复杂的信息。但在同一个线性表中的数据元素必须具有相同的特性(或者说具有相同的类型)。有穷性。线性表中数据元素的个数是有限的。有序性。若线性表是非空表，(a1，a2,...,an),ai-1领先于ai(1in)，称ai-1是ai的直接前驱元素,ai是ai-1的直接后继元素。除了第一个元素a1外,每个元素ai有且仅有一个被称为其直接前驱的结点ai-1,除了最后一个元素an外,每个元素ai有且仅有一个被称为其直接后继的结点ai+1。这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。第2章线性数据结构线性表的基本操作有以下几种：(1)INITIATE(L)。初始化操作，设定一个空的线性表L。(2)LENGTH(L)。求表长，求出线性表L中数据元素个数。(3)GET(L，i)。取元素函数，若1≤i≤LENGTH(L)，则函数值为给定线性表L中第i个数据元素，否则为空元素NULL。第2章线性数据结构(4)PRIOR(L，elm)。求前趋函数，若elm的位序大于1，则函数值为elm的前趋，否则为空元素。(5)NEXT(L，elm)。求后继函数，若elm的位序小于LENGTH(L)，则函数值为elm的后继，否则为空元素。(6)LOCATE(L，x)。定位函数，返回元素x在线性表L中的位置。若L中有多个x，则只返回第一个x的位置，若在L中不存在x，则返回0。(7)INSERT(L，i，x)。插入操作，若1≤i≤LENGTH(L)+1，则在线性表L中的第i个位置上插入元素x，运算结果使得线性表的长度增加1。否则空操作第2章线性数据结构2.2.2线性表的顺序存储结构在计算机内可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素。第2章线性数据结构线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。(1)设有线性表(a1，a2，...，an)，若1个数据元素只占1个存储单元，则这种分配方式如图2-2所示。若用Loc表示某元素的地址，则线性表中第i个数据元素的存储地址为：Loc(ai)=Loc(a1)+(i-1)其中，Loc(a1)是线性表第一个数据元素的存储地址，通常称做线性表的起始地址或者基地址。第2章线性数据结构(2)若1个数据元素占d个存储单元，则有Loc(ai)=Loc(a1)+(i-1)*dLoc(ai+1)=Loc(ai)+d可见，线性表中每个元素的存储地址是该元素在表中序号i的线性函数。只要确定了线性表的起始地址和每个元素所占存储单元的多少，就可以计算出任一数据元素的存储地址,从而实现对顺序表中任一数据元素的随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。第2章线性数据结构图2-2线性表顺序存储结构示意图(设每个数据元素占有1个存储单元)a1a2aian………内存状态存储地址元素序号12…i…n空闲bb＋1b＋(maxlen－1)b＋(i－1)b＋(n－1)第2章线性数据结构顺序存储结构是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间相邻的逻辑关系。在C语言中，可用一维数组V[n]来描述顺序存储结构。因此,可以借助一维数组来描述顺序表。除了用来存储线性表的元素外,还应该用一个变量来表示线性表的长度属性。注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]第2章线性数据结构线性表的顺序存储结构两种实现方法(1)数组表示法：数组中的分量下标即为元素在线性表中的序号#definemaxlen100datatypeelem[maxlen];intlast;其中，maxlen是线性表的最大长度，它可以根据实际需要而修改。datatype抽象数据类型，可用int,float,double,char或结构体类型等代替如：typedefintdatatype第2章线性数据结构数据域elem描述了线性表中数据元素占用的数组空间，线性表的各个元素a1，a2，…，an依次存放在一维数组elem的各个分量elem[0]，elem[1]，…，elem[last-1]中。数据域last表示线性表的当前长度。第2章线性数据结构typedef定义类型Ｃ语言不仅提供了丰富的数据类型，而且还允许由用户自己定义类型说明符，也就是说允许由用户为数据类型取“别名”。类型定义符typedef即可用来完成此功能。例如，有整型量a,b,其说明如下：inta,b;其中int是整型变量的类型说明符。int的完整写法为integer，为了增加程序的可读性，可把整型说明符用typedef定义为：typedefintINTEGER例如：INTEGERa,b;它等效于：inta,b;第2章线性数据结构2）将last与data封装在一起，单独定义一种顺序表类型—用结构体建立,last与data作为该结构体的成员项。#definemaxlen100typedefstruct{datatypeelem[maxlen];intlast;}sqlisttp;返回本章目录用变量方式定义两个顺序表L和PsqlisttpL,P;L.last=2;L.elem[0]=91;L.elem[1]=82;P.last=10;P.elem[0]=93;P.elem[1]=78;……第2章线性数据结构结构体1、结构体类型的定义2、结构体变量的定义及引用第2章线性数据结构结构体类型的引入问题：为了描述一个事物的不同属性，需要用到各种不同类型的数据，这些数据彼此相关，形成一个有机的整体。例如：一个教师的基本信息由姓名、性别、年龄、职称、工资等几项组合而成。如何描述一个教师的情况呢？变量之间是相互独立的，无任何联系；而数组只能用来表示一批相同类型的数据。因此，若用单个变量分别表示教师的姓名、性别、年龄等属性，则难以反映他们之间的内在联系；若用数组，则根本无法表示，因为姓名、性别、年龄等不属同一种数据类型。C语言中用“结构体”来描述由多个不同类型的数据组成的数据集合。相当于其他高级语言中的“记录”.第2章线性数据结构表教师信息登记表教工号姓名性别职称年龄工资000100020003…张忠王平李林…男女男…讲师助教助教…322223……………第2章线性数据结构1.结构体类型的定义与基本数据类型不同的是，结构体是又一种构造