《第2章 常用数据结构及其运算1(线性结构)》由会员分享，可在线阅读，更多相关《第2章 常用数据结构及其运算1(线性结构)（86页珍藏版）》请在金锄头文库上搜索。
1、第2章 常用数据结构及其运算,石油工程学院,概述,图,查找,排序,2.6,2.8,2.7,本章主要内容,概述,2.1,2.2,2.3,2.4,2.5,树与二叉树,数组,栈与队,线性表,算法和数据结构是计算机科学的两大支柱。,2.1 数据结构概述,早期定义为：研究算法的科学 近期定义为：研究数据的科学,数据结构是程序设计的基础。,例1： 040105467392756257061370502821126326,结论：杂乱的数据不能表达信息,2.1.1 什么是数据结构,例2：电话号码薄:(a1,b1)(a2,b2)(an,bn) 其中：ai为姓名，bi为电话号码 要求：设计一个算法，给定一个人的姓
2、名时，能查出此人电话号码。,如果姓名和电话号码是无规律的，则只能逐个比较姓名和电话号码 如果姓名按照字典顺序排列，查找就快捷多了。,结论：数据之间是有联系的，这些联系常常影响算法的效率。数据结构就是研究数据之间的联系,2.1.1 什么是数据结构,例3：大学生管理机构：,结论：数据是有结构的 数据结构就是研究数据的各类结构,2.1.1 什么是数据结构,例2：电话号码薄:(a1,b1)(a2,b2)(an,bn) 其中：ai为姓名，bi为电话号码,对电话号码薄的操作： 查找：给定一个人的姓名时，能查出此人电话号码。 插入：插入新的联系人和电话号码 删除：删除无用的项,结论：在某种数据结构上可以定义
3、一组运算 数据结构就是要研究各类数据结构上各类运算,2.1.1 什么是数据结构,2.1 概述,2.1.2 数据结构的基本概念和术语,数据(Data):所有能被计算机处理的符号的集合。,数据元素(Data Element):是数据的基本单位，也称之为结点(node)或记录(record),在计算机程序中通常作为一个整体进行考虑和处理。 如数据集合N=1,2,3,4,5中1-5均为数据元素。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,个人书库,数据元素,2.1 概述,2.1.2 数据结构的基本概念和术语,数据对象(Data Object)：是性质相同的数据元素的集合。是
4、数据的一个子集。数据对象可以是有限的，也可以是无限的。 例:整数的数据对象是-3，-2，-1，0，1，2，3， 英文字符类型的数据对象是A，B，C，D，E，F，,数据结构(Data Structure)：是指带有结构的数据元素的集合。结构: 数据元素之间存在的关系。,集合论方法定义结构S为一个二元组： S=(D，R)其中：D是数据元素的非空有限集，R是定义在D上关系的非空有限集。 如n维向量的数据元素集合为D=x1,x2,xn，D上的关系R=,即为线性表。,2.1 概述,2.1.2 数据结构的基本概念和术语,数据的逻辑结构：数据元素及其关系的数学特性(逻辑关系)，建成数据结构 数据的物理结构(
5、存储结构)：是逻辑结构在计算机中的存储表示(映象)。也就是具体实现。分为顺序存储结构、链式存储结构。,数据类型(Data type)：在一种程序设计语言中，变量所具有的数据种类。在C中数据类型：基本类型和构造类型; 基本类型：整型、浮点型、字符型; 构造类型：数组、结构、联合、指针、枚举型、自定义。,算法：是解决某一特定类型问题的有限运算序列，其实现必须借助程序设计语言提供的数据类型及其运算。,2.1 概述,2.1.2 数据结构的基本概念和术语,数据结构与算法,算法的基本特性： (1)有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 (2)确定性 每一步必须是明确的，
6、不存在二义性。 (3)可行性 可以通过基本运算执行有限次来实现。,2.1 概述,2.1.2 数据结构的基本概念和术语,算法和程序的区别： 算法是解决问题的一种方法或过程，考虑的是如何讲输入转换为输出。一个问题可以有多种算法 程序是某种程序设计语言对算法的具体实现。,主要区别在于：有穷性，正确性，和描述方法。 程序可以是无穷的，如OS，算法是有穷的 程序可以是错误的，算法必须是正确的 程序是用程序设计语言描述，可在计算机上执行；算法还可以用框图、自然语言等形式来描述。,2.1 概述,2.1.3 算法分析技术初步,评价算法优劣的标准：时间复杂度和空间复杂度,频度：是指该语句重复执行的次数 算法的时
7、间复杂度:一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度,简称时间复杂度。,时间复杂度函数： 常量型：O(1) 多项式型： O(n), O(n2), O(nk) 对数型： O(log2n), O(nlog2n) 指数型： O(2n)， O(en),2.1 概述,2.1.3 算法分析技术初步,空间复杂度：在算法中所需的辅助空间单元，而不包括问题的原始数据占用的空间(因为这些单元与算法无关)。S(n)=O(f(n),时间与空间是一对矛盾，要节约空间往往要消耗较多的时间，反之亦然。 目前，内存空间足够，应重点考虑时间
8、。,int x=10,y=20; int t; t=x; x=y; y=t; printf(“%d%dn“,x,y);,int x=10,y=20; x+=y; y=x-y; x-=y; printf(“%d%dn“,x,y);,概述,图,查找,排序,2.6,2.8,2.7,第二章 常用的数据结构及其运算,概述,2.1,2.2,2.3,2.4,2.5,树与二叉树,数组,栈与队列,线性表,2.2 线性表,在计算机程序中最常用、最简单的一种数据结构是线性表，它是一种线性结构。,线性表的定义和运算 线性表的顺序存储结构（顺序表） 线性表的链式存储结构（链表） 顺序表和链表的比较,一、线性表的定义和运
9、算,例1、26个英文字母组成的字母表（A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）,例3、学生健康情况登记表如下：,一、线性表的定义和运算,线性表是由n个数据元素组成的有限序列。记作：L= (a1，a2，an),数据元素之间的关系ai-1领先于ai，ai领先于ai+1ai-1是ai的直接前驱元素，ai1是ai的直接后继元素除a1外，每个元素有且只有一个直接前驱元素。除an外，每个元素有且只有一个直接后继元素。线性表中数据元素的个数n(n0)称为表的长度。 n=0时称为空表,一、线性表的定义和运算,所有数据元素ai在
10、同一个线性表中必须是相同的数据类型。,若ai =ai-1,i=2,3,，n，则称有序表，否则称无序表。,一、线性表的定义和运算,0.初始化一个线性表 1.求出线性的长度; 2.存放一个新的数据元素于表的第i个位置; 3.在第i-1和第i个元素之间插入一个新的数据元 素; 4.删除第i个数据元素; 5.将两个或两个以上的线性表合并成一个线性表; 6.将一个线性表折成两个以上的线性表; 7.复制一个线性表; 8.按某个特定的值查找线性表; 9.对线性表中的数据元素按某个数据项值递增或递减的顺序重新排列;,线性表的基本运算,二、顺序存储线性表,顺序存储结构(顺序表/向量),把线性表的结点按逻辑顺序依
11、次存放在一组地址连续的存储单元里。,假设线性表的每个元素需占用k个存储单元，且第一个数据元素的存储地址为LOC(a0)则线性表中第i个元素的存储地址: LOC( a i) = LOC (a0)+i*k,由于许多语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。,二、顺序存储线性表,二、顺序存储线性表,线性表顺序存储结构的特点: (1)占用连续的内存; (2)数据元素的逻辑结构和物理结构保持一致; (3)只要确定存储顺序表的起始位置,表中任意元素可随机存取; 故该结构亦称随机存储结构。 线性表顺序存储结构的缺点: (1)在插入或删除操作时,需移动大量的元素; (2)在给长度变化
12、较大的线性表分配空间时,必须按最大空间分配;使存储空间不能得到充分利用; (3)表的容量难以扩容;,二、顺序存储线性表,顺序存储结构的插入、删除运算,1、插入,算法步骤: ai，,an的元素依次向下移动一个位置; 把x插到空出的位置上; 线性表的长度发生变化,要修改容积.,二、顺序存储线性表,顺序表的插入INSERTLIST(v(),n,i,x) 设有长度为n的线性表a1，,an,顺序存放在数组v()中.在表的第i(1in+1)个位置上，插入一个新结点x， 1 若in 2.输出 没有这个元素 3.否则 y V(i) 循环 j以1为步长,从i 到n-1,执行v(j) V(j+1)4. n n-1
13、 算法结束,总结:在顺序表上做插入和删除运算，平均要移动表中约一半的结点，要花费大量时间。,三、线性链表(Linked List),链表:是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 结点:数据元素ai的存储映象.它包括两个域: 数据域:存储每个结点值; 指针域:存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,三、线性链表(Linked List),Typedef structElementype data;Struct node
14、 *next; node,*linklist;,链表是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。,三、线性链表(Linked List),单链表中每个结点的存储地址是存放在其前趋结点next域中。 头指针:开始结点无前趋，故应设头指针head指向开始结点，表示链表中第一个结点的存储位置。 终端结点无后继，故终端结点的指针域为空，即null（图示中可用nil或表示)。,带表头结点的链表在第一个结点之前再附加一个结点，称为头结点，它的数据域不存放数据元素，指针域指向第一个元素。这样，空循环链表仅有一个自成循环的头结点表示。,空表,三、线性链表(Linked List),三、线性链表(Linked List),线性链表的基本运算,由线性链表的存储结构可知，对线性链表进行插入、删除操作时，不必移动元素，而是修改指针的指向和动态生成或回收链表的结点。,三、线性链表(Linked List),插入运算 后插：当前指针指向第i个结点ai，将值为x的新结点插入到第i个结点之后。首先生成一个数据域为x的新结点*s，并令结点ai的指针域指向新结点，新结点的指针域指向结点ai1。从而实现三个结点ai，x和ai1之间的逻辑关系的变化。,next(s) next(p) next(p) s,
