计算机软件技术基础 软件基础之数据结构-线性表.ppt

1、计算机软件技术基础 数据结构篇,主讲 王文燕,2020/7/10,2,基本概念 线性表,2020/7/10,3,内容提要,一、数据结构 1。基本概念：数据、数据元素、数据项、数据结构、数据结构的形式化描述方法。 2。数据的逻辑结构： 逻辑结构的类别（集合、线性、树、图） 3。数据的物理结构及类别（顺序、链式、索引、散列） 4。算法的描述及评价 （1）算法的概念： （2）算法的特性：有限、确定、可行、输入、输出 （3）设计算法的要求：正确、可读、健壮、效率 （4）算法的评价：时间复杂性、空间复杂性,2020/7/10,4,内容提要,二、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱

2、、后继、 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述（数组、last） 3。顺序表的操作 （1）判空、判满、判合法 （2）插入（3）删除 4。顺序表的优缺点及适用场合 数据连续存放、随机存取 逻辑上相邻，物理上也相邻 存储结构简单、易实现 插入、删除操作不便 存储密度大，空间利用率高,2020/7/10,5,内容提要,三、链表 1。单链表 结点、指针域、数据域、头指针、头结点。 2。单链表的描述 3。单链表的操作 （1）指针操作、 指针说明、分配存储空间、判空、判满、释放空间 （2）查找操作 （3）插入 （4）删除 4。单链表的特点及适用场合 5。单循环链表、双向链表、双向循环链

3、表 描述、建立、判空、查找、插入、删除,2020/7/10,6,内容提要,四、栈队列数组的: 有关概念 逻辑结构及特点 存储结构 有关操作,2020/7/10,7,数据结构的发展简史及其在计算机科学中所处的地位,发展史： 1、 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 2、 1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门

4、课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,2020/7/10,8,什么是数据结构?,计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。 运算是由计算机来

5、完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。,2020/7/10,9,一、基本概念,数据（Data） 能存于计算机、并被计算机处理的符号的集合。它是客观事物的符号表示。 数据元素（Element） 是数据的基本单位、数据集合中的个体。 数据结构（Data Structure） 是带有结构特征的数据元素的集合；包括3方面的问题： 数据的逻辑结构、存储结构、数据的运算 数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。也可以说：

6、怎样去组织一批特定的数据。,数据结构：数据元素及其关系和操作的集合,2020/7/10,10,数据结构分类,线性表 堆栈 队列 串 数组,树 二叉树 图,线性结构,非线性结构,数据结构 DS,按某种逻辑关系组织起来的一批数据，按一定的存储方式把它存储在计算机存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构(Data Structures)。,2020/7/10,11,1. 数据的逻辑结构,概念：客观事物本身存在的结构形式及关系。 特点：描述数据间的顺序（逻辑）关系，抽象地反映数据元素的结构，而不管它们在计算机中如何存放。 与物理存放位置无关 描述方法：用二元组来描述： DS=（D

7、，R） 其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。,2020/7/10,12,数据结构举例举例,数据结构的形式化描述：定义DS如下： Group=（D，R） 其中： D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2 R=R1,R2 R1=|1 i n , 1 n 3 R2=|1in ,1 j m , 1 n 3 , 1 m 2 ,2020/7/10,13,数据元素之间的关系类型,（1）集合：属性相同 （2）线性结构：一对一关系 （3）树形结构：一对多关系 （4）图或网状结构：多对多关系,2020/7/10,14,2. 数据的存储结构,是指数据结构在计算机

8、中的表示(又称映象),即数据在计算机中的存放形式。 又称物理结构,2020/7/10,15,逻辑结构和物理结构的关系, 数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。 数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。,逻辑结构：独立于计算机。存储结构：依赖于计算机 算法设计考虑逻辑结构，算法实现依赖存储结构。,2020/7/10,16,数据存储结构分类,顺序存储结构 链式存储结构 索引存储结构 散

9、列存储结构,2020/7/10,17,顺序存储结构,概念：把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构: 特点: 连续存放;逻辑上相邻,物理上也相邻。 结构简单，易实现。 插入、删除操作不便（需大量移动元素）。,d1 d2 dn,数据域,2020/7/10,18,链式存储结构,概念：以链表形式将数据元素存放于任意存储单元中。可连续存放，也可以不连续存放。以指针实现链表间的联系。数据结点结构: 特点: 非连续存放,借助指针来表示元素间的关系; 插入、删除操作简单，只要修改指针即可； 结构较复杂，需要额外存储空间。,d1,.,d2,dn ,数据域 指针域,2020/7/1

10、0,19,链式存储举例,存储单元,字符串：A B C D E,顺序存储,插入：C+,删除：C+,head,链式存储,2020/7/10,20,索引存储结构,数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。数据结点结构: 序 号： 1 2 3 4 5 6 7 数据项： 索引号： 特点： 非连续存放； 检索速度快； 增、删操作简单。,12 21 35 2 45 5 10,4 3 2 7 1 6 5,数据域 索引顺序号,2020/7/10,21,散列存储结构,在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可

11、以得到它的存储地址，即D=F（E）。 哈希查找中的哈希表就是这样一种存储结构。 特点： 数据元素间无内在联系； 存储形式不定。,2020/7/10,22,3. 数据运算,数据运算：是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。 常见操作有： 创建、插入、删除、修改、检索、排序等。,2020/7/10,23,4、算法与算法分析,算法（Algorithm） 是对特定问题求解步骤的一种描述； 是一组指令的有限集合。 算法的特性 有穷性: 一个算法必须总是在执行有穷步后结束，且每一步都可在有穷时间内完成； 确定性: 算法中的每一个指令必须有明确的含义，不能有二义性； 可行性: 算法中描

12、述的操作都是可通过已经实现的基本运算、执行有限次实现的； 输入: 一个算法应有0个或多个输入； 输出: 一个算法应有1个或多个输出。,2020/7/10,24,算法的设计要求,正确性 可读性 健壮性 高效率与低存储量,有4个层次：A. 程序不含语法错误；B. 程序对几组输入数据能够得出满足规格要求的结果；C. 程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；D. 程序对一切合法的输入数据都能产生满足规格要求的结果。,算法的第一目的是为了阅读和交流； 可读性有助于对算法的理解； 可读性有助于对算法的调试和修改。,当输入非法数据时，算法也能适当地作出反应或进行

13、处理；并且，处理出错的方法应该是返回一个表示错误或错误性质的值并中止程序的执行，以便在更高的抽象层次上进行处理。,处理速度快 存储容量小 时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。,2020/7/10,25,算法的描述,算法的描述方式（常用的）： 自然语言: 流程图 特定的表示算法的图形 符号 算法描述 伪语言 包括程序设计语言的三 大基本结构及自然语言 的一种语言 类语言 类似高级语言的语言， 例如，类PASCAL、类 C语言。,2020/7/10,26,流程图,是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作.常用流程图符号：,2020/7

14、/10,27,算法的评价,算法评价的标准：时间复杂度和空间复杂度。 时间复杂度 指在计算机上运行该算法所花费的时间。常以基本运算的重复次数来衡量。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1） O（logn） O（n） O（n2 ） O（2n ） 常数阶 对数阶 线性阶 平方阶 指数阶 空间复杂度 指算法在计算机上运行所占用的存储空间的大小。（程序、常变量、输入、辅助）,2020/7/10,28,时间复杂度举例,（a） X=X+1 ； O（1） （b） FOR I=1 TO n X= X+1； O（n） （c） FOR I= 1 TO n FOR J= 1 TO n O（

15、 n2 ） X= X+1；,2020/7/10,29,二、线性表,是指数据元素之间的关系为一一对应的线性关系的数据结构。例如，一星期七天的英文缩写表示： （Sun，Mon，The，wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。 线性表虽然简单，但是应用范围非常广泛。,2020/7/10,30,二、线性表,（一）线性表的逻辑结构 定义： 线性表是n（n0）个元素a1,a2,an 组成的有限序列;表中每个数据元素,除了第1个和最后1个外,有且仅有一个前趋元素和后继元素。 例如：一星期七天的英文缩写表示： （Sun，Mon，The，wed，Thu，Fri，Sat）是

16、一个线性表，其中的元素是字符串，表的长度为7。 形式定义： 含有n个数据元素的线性表是一种数据结构，表示为： Linear_list=( D , R ) 其中: D=ai | aiD0,i=1,2,3,n,n 0 R=N, N=|ai-1,ai D ,i=1,n D是数据元素的有限集合,R是D上逻辑关系的有限集合。关系N是一个有序偶对的集合。,2020/7/10,31,相互关系描述,1）L的长度为n（n 0），当n为0时， 表示是空表； 2）每个元素（除了第1个和最后一个元素 外），有唯一的前趋和后继； 3）线性表中各元素间存在着线性关系； 4）均匀性；各元素数据类型必须相同； 5）有序性；各

17、元素是有序的，不可交换次序。 线性表：n（=0）个数据元素的有限序列。,2020/7/10,32,线性表的基本操作,线性表的主要操作有如下几种： 1 Initiate(L) 初始化：构造一个空的线性表L。 2 Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。 3 Delete(L,i) 删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。 4 Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。 5 Length(L) 求长度：对给定

18、的线性表L，返回线性表L的数据元素的个数。,2020/7/10,33,6 Get(L,i) 存取：对给定的线性表L，返回第i（0iLength(L)-1）个数据元素，否则返回Null。 7 Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。 8 Copy(L,C) 复制：将给定的线性表L复制到线性表C中。 9 Merge(A,B,C) 合并：将给定的线性表A和B合并为线性表C。 上面我们定义了线性表的逻辑结构和基本操作。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法。,2020/7/

19、10,34,（二）、线性表的顺序存储结构,线性表的顺序存储结构 将表中元素一个接一个地存入一组连续的存储单元中，这种存储结构是顺序结构。即:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。 顺序表:即采用顺序存储结构的线性表简称为“顺序表”。 顺序表的存储特点： 只要确定了起始位置，表中任一元素的地址都通过下列公式得到： LOC（ai）=LOC（a1）+（i-1）*L 1i n 其中，L是每个元素占用存储单元的长度。,假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：

20、 Loc(ai)= Loc(a0)+id,2020/7/10,35,线性表元素存储示意图,a1,a2,.,ai,.,元素序号 内存状态 存储地址,1,2,.,i,.,LOC(a1),LOC(a1)+1L,.,LOC(a1)+(i-1)L,.,2020/7/10,36,线性表在顺序存储结构下的运算,可用C语言描述顺序存储结构下的线性表（顺序表）如下： #define TRUE 1 #define FALSE 0 #define MAXNUM Elemtype ListMAXNUM ; /*定义顺序表List*/ int num=-1; /*定义当前数据元素下标，并初始化*/ 我们还可将数组和表长

21、封装在一个结构体中： struct Linear_list Elemtype ListMAXNUM; /*定义数组域*/ int length; /*定义表长域*/,2020/7/10,37,在数组中插入元素,顺序表的插入操作:,2020/7/10,38,【算法： 顺序表的插入】 int Insert(Elemtype List ,int *num,int i,Elemtype x) /*在顺序表List中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FALSE。*/ int j; if (i*num+1) printf(“Error!”); /*插

22、入位置出错*/ return FALSE; if (*num=MAXNUM-1) printf(“overflow!”); return FALSE; /*表已满*/ for (j=*num;j=i;j-) Listj+1=Listj; /*数据元素后移*/ Listi=x; /*插入x*/ (*num)+; /*长度加1*/ return TRUE; 注：顺序表List的最大数据元素个数为MAXNUM，num标识为顺序表的当前表尾（numMAXNUM-1）。,2020/7/10,39,在数组中删除元素,顺序表的删除操作:,2020/7/10,40,【算法2.2 顺序表的删除】 int Del

23、ete(Elemtype List,int *num,int i) /*在线性表List 中，*num为表尾元素下标位置，删除第i个元素，线性表的元素减1，若成功，则返回TRUE；否则返回FALSE。*/ int j; if(i*num) printf(“Error!”); return FALSE; /*删除位置出错！*/ for(j=i+1;j=*num;j+) Listj-1=Listj; /*数据元素前移*/ (*num)-; /*长度减1*/ return TRUE; 从上述两个算法来看，很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。而移动

24、元素的次数取决于插入或删除元素的位置。 假设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为,2020/7/10,41,顺序存储结构的优缺点,数据连续存放、随机存取 逻辑上相邻，物理上也相邻 存储结构简单、易实现 插入、删除操作不便 存储密度大，空间利用率高 结论： 顺序存储结构适合于表中元素变动较少的情况。,2020/7/10,42,（三 ）线性表的链式存储结构,线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。 顺序表缺点是： 难于插入、删除操作； 需要预先分配空间，不管这些空间能否最大限度地利用。 链表存储结构在这两个方面

25、恰好是优点： 容易插入、删除操作 不需要预分空间。,2020/7/10,43,1、链表有关基本概念,结点（NODE） 表中元素的存储单元。由数据域和指针域组成。数据域存放元素数据，指针域存放指向下一结点位置的指针。 结点形式为： 结点的C语言描述为： struct node int data ; struct node *next ; ; typedef struct node NODE；,data next,数据域 指针域,2020/7/10,44,链表（Link）：由结点组成的表。 头指针（head）： 指向链表中第1个结点的指针。 头结点 ： 为方便操作，在头指针和第1个结点之间设置的结

26、点。（引入头结点是为操作方便） 首元结点 第一个结点（a1）。,基本概念,head,a1,头指针,头结点,首元结点,a i,.,第i个结点,2020/7/10,45,设置头结点的优点：表示形式的统一,空表和非空表表示形式在头结点上得到统一 插入和删除操作的统一 空表的形式 : 非空表的形式:,head,头结点,head,头结点,2020/7/10,46,链表举例,由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam) 不带头结点。,biscuit,butter,cheese,jam,grapes,eggs,head,头指针,2020/7/10,47,单

27、链表在存储区的物理状态,Grapes 60,biscuit 61,cheese 13,eggs 1,jam NULL,butter 12,存储地址 数据域（data） 指针域（next）,1 11 12 13 60 61,11,头指针 head,（biscuit,butter,cheese,eggs,grapes,jam),2020/7/10,48,2、单链表的操作,指针的基本操作 单链表的查找get 单链表的的插入insert 单链表的删除delete,2020/7/10,49,指针的基本操作,设指针变量p、q的定义为： NODE *p，*q； 对链表的操作实际上是对指针的操作。例如，要删除

28、结点ai，首先要使指针P指向ai，即：,a1,.,.,head,ai,an,p,指针p是存储单元的地址，地址内的内容可以通过 P-data得到，指向下个元素的指针用p-next得到,2020/7/10,50,指针的基本操作列表,p=（NODE*）malloc（sizeof（NODE） 申请一个结点空间,并将地址送入p中. free（p） 释放p指针所指结点的空间 p=q 指针p指向指针q所指的结点 p=q-next 指针p指向指针q所指结点的后继 p=p-next 指针p向后移动一个结点 p-next=q 将指针q所指结点改接为指针p所 指结点的后继 p-next=NULL 将指针p所指结点与

29、后继结点断开,2020/7/10,51,指针操作的举例,p=q-next p指向q所指结点的后继,ai,ai-1,ai-1,ai,ai-1,ai+1,q,q,p,p,操作前状态,操作后状态,2020/7/10,52,单链表的查找算法,查找第i个元素，返回指向它的指针 算法操作步骤: step1 初始化,指针P指向头指针, 计数器置0 step2 P非空且计数器小于i循环 step3 每循环一次,P后移一个位置, 计数器加1 step4 循环结束,返回指向ai 的指针P.,2020/7/10,53,单链表查找算法程序,NODE *get(NODE *head,int） NODE *p; int

30、counter = 0; /计数器 p=head-next; /p指向第1个结点 while(p!=NULL) /没找到 ,2020/7/10,54,单链表插入算法,在第I个位置插入 算法操作步骤: step1 找到ai-1的位置,使指针p指向ai-1 step2 申请并生成新结点s step3 使s插入到ai-1和ai之间 s-data=x s-next=p-next p-next=s,ai-1,ai,p,x,s,示例,2020/7/10,55,单链表的插入算法程序,insert(NODE *head, int i, int x) NODE *p,*s; if(i=1) p=head; el

31、se p=get(head,i-1); if(p=NULL) printf(“插入位置错n”); exit(0); else s=(NODE*)malloc(sizeof(NODE); s-data=x; s-next=P-next; p-next=s; ,/* 令P指向A i-1 */,/* 若i=1，P指向头指针 */,/* P为空，说明找不到i位置 */,/* P定位成功 */,2020/7/10,56,单链表删除算法,算法操作步骤: step1 找到ai-1的位置,使指针p指向ai-1 step2 使指针t指向p所指结点的后继 step3 使t所指结点ai 脱链 step4 释放t t

32、=p-next p-next=t-next free(t),p,t,a i-1,ai,a i+1,示例,2020/7/10,57,单链表的删除算法程序,delete(NODE *head, int i) NODE *p,*t; if(i=1) p=head; else p=get(head,i-1); if(p=NULL) printf(“i表长+1, 无此结点n”); exit(0); if(p-next=NULL) printf(“i=表长+1,无此结点n”); exit(0); else t = p- next; p-next = t-next; free(t) ; ,/* P定位操作*

33、/,/* P定位成功 */,2020/7/10,58,在C语言中，定义链表结点的形式如下： struct 结构体名 数据成员表； struct 结构体名 * 指针变量名； 例如，下面定义的结点类型中，数据域包含三个数据项：学号、姓名、成绩。 Struct student char num8; /*数据域*/ char name8; /*数据域*/ int score; /*数据域*/ struct student *next; /*指针域*/ ,2020/7/10,59,P,s,q,P,sp q next(p),p next(p),2020/7/10,60,P,P,s,s,q,P,s,s,he

34、ad,head,p,next(s) next(p) next(p) s,q head While(next(q)p)do q next(q) next(q) s next(s) p,2020/7/10,61,3、循环单链表和双向链表,链表检索只能从头指针开始,且只能顺链表方向移动。 如果让链表首尾相接，构成环形，这就是单循环链表。 在单链表中,从表的任一结点ai找其前趋结点,时间复杂度是O（n）。 如果在结点中增加一个指向前一个结点的指针域，链表可以从两个方向检索，效果更佳；这就是双向循环链表。,2020/7/10,62,单循环链表,单循环链表表示形式： 单循环链表为空的条件: 表示形式为:,

35、head,.,head,a1,a2,an,单循环链表特点:,从表中任一结点出发,均可以找到表中其它结点。 找其前趋结点的时间复杂度是O（n）。,2020/7/10,63,双向循环链表,在单向循环链表中，也存在检索前趋结点费时的问题（所需时间是O（n）。 双向循环链表，其存储结构： struct dnode int data； struct dnode *prior，*next； ； typedef struct dnode DNODE；,2020/7/10,64,双向循环链表结点结构,prior data next,指向后继结点 指针域,数据域,指向前趋结点 指针域,2020/7/10,65,双向循环链表表示形式,双向循环链表表示形式：