数据结构1.2章

数据结构第一章绪论1.1基本概念和术语1.1.1基本概念1数据：○1对客观事物的符号表示；○2被计算机处理的符号的总称；○3计算机程序加工的“原料”。内容：数值与非数值例如：数值、字符、图像、动画、声音等。2数据元素：○1数据的基本单位；○2在程序中作为一个整体而加以考虑和处理；○3数据元素又称元素、结点、顶点或记录。3数据项：○1数据元素可由若干数据项组成；○2数据项是数据不可分割的最小单位；○3又称字段或域。4数据对象：性质相同数据元素的集合，是数据的子集；举例：整形数据对象：整数的集合5数据结构：DataStructure○1简单解释：相互之间存在一种或多种特定关系的数据元素的集合；○2定义：二元组Data_structure=(D,S)D是数据元素的有限集；S是D上关系的有限集；○3四类基本（逻辑）结构：集合、线性、树形、网状结构1.1.2数据的逻辑结构1逻辑关系：○1数据元素之间的关联方式；○2一个结点代表一个元素，结点之间的线性代表逻辑关系；○3参图1.5，四种基本结构关系图。2逻辑结构：○1概念：a.数据元素之间逻辑关系称为数据的逻辑结构；b.从具体问题抽象出来的数学模型；c.数据结构的数学描述。○2分类：集合：结点之间无关系；（同属于一个集合）线性：结点之间是线性关系；（元素之间一对一）树形：结点之间是层次关系；（元素之间一对多）网状：结点之间是网状关系；（元素之间多对多）○3逻辑结构的特性：逻辑结构与数据元素本身的形式、内容无关；逻辑结构与数据元素的相对位置无关；逻辑结构与所含结点个数无关；独立于计算机的硬件结构。○4逻辑结构的作用：即数学模型a.重新组织数据；b.进行算法设计；c.构造数据的机内表示提供“依据”1.1.3数据的存储结构1存储结构：物理结构○1数据结构在计算机中的表示；（包括数据元素和关系的表示）数据结构○2数据单位：位和字节；数据域：字段；结点/元素：一个记录；2存储结构的分类○1顺序存储结构：借助元素在存储器的相对位置来表示数据元素之间的逻辑关系；○2链式存储结构：借助元素存储地址（指针）来表示数据元素之间的逻辑关系；○3散列存储结构○4索引存储结构4存储结构的描述：高级语言（数据类型，C语言）数组：描述顺序存储结构指针：描述链式存储结构5存储结构和逻辑结构的关系算法的设计取决于逻辑结构算法的实现取决于存储结构1.2算法和算法分析1.2.1算法1概念：对特定问题求解的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作；程序：完成既定任务的一组指令序列2重要特性：有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成确定性：算法中每条指令必须有确切的含义，读者在理解上不会产生二义性。并且，在任何条件下，算法只有唯一一条执行路径，即对相同的输入只能得出相同的输出可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入：算法有0个或多个输入，这些输入取自于某个特定对象的集合输出：一个算法有1个或多个输出。3算法描述：自然语言、数学公式、流程图、伪代码、程序设计语言C语言作为算法描述：程序4算法与程序算法的含义与程序十分相似，但又有区别：程序必须是机器可执行的，但算法无此限制；算法代表对问题的求解，而程序则是算法在计算机上的特定实现；算法用C语言描述，就是程序1.2.2算法的设计要求1正确性；2可读性；3健壮性；4高效性：时空性能时间性能：指算法包含的计算量空间性能：指算法需要的存储量1.2..3算法的时间复杂度1度量程序执行时间○1事后分析；○2事前分析估算2算法度量：○1时间复杂度；○2空间复杂度数据结构3时间复杂度：○1一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),记作T(n)=O(f(n));它表示随问题规模的增大，算法执行时间的增长率和f(n)相同○2常用时间复杂度常量阶：O(1），线性阶：O(n），平方阶：O(n2)，对数阶：O(logn)，指数阶O(2n)。1.2.4算法的空间复杂度1空间复杂度：表示：S(n)=O(f(n))n表示问题规模的大小2评价：数据占有存储的空间附加的存储空间第二章线性表2.1线性表的类型定义1线性结构○1基本特征：除第一个和最后一个数据元素，每个结点至多只有一个直接前驱并且只有一个直接后继；○2结点要求：一个结点代表一个元素所有结点具有相同的特性2线性表的定义：最简单、最基本、最常用的一种数据结构；它的逻辑结构是线性结构；定义：○1n≥0个数据元素的有限系列；○2同一线性表的元素有相同特性（属同一数据对象），相邻数据元素存在着序偶关系；○3所含结点个数为线性表的长度；○4结点为0的线性表为空表。3表示：(a1,…,a1i,ai,a1i,…,an)i为ai在线性表中的位序，ai为线性表的第i个元素。a1i是ai的直接后继元素。4线性表的基本操作初始化、删除表、置空表、判断表空、求表长、插入、读表、查找、排序、删除结点、合并两个线性表、拆分线性表、复制线性表、2.2线性表的顺序表示和实现1顺序表（采用顺序存储结构的线性表）机内表示称作线性表的顺序存储结构（随机存取）或顺序映象。○1概念：顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。数据结构○2特点：逻辑结构中相邻的结点在存储结构中仍相邻，以元素在计算机的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系：LOC(ai)=LOC(a1)+(i-1)*L(每个元素占用L个存储单元)2顺序表的类型说明，存储结构描述：3顺序表的引用：（数组下标从0开始）○1第i个元素：L.elem[i-1]○2表长度：L.length○3终结点：L.elem[length-1]4顺序表的基本操作：○1初始化：a.功能：构造一个空表或给L分配存储空间b.算法分析：等概率情况下，平均时间复杂度O(n)c.算法○2插入a.功能：在线性表的第i-1个和第i个数之间插入一个新的数据元素，是表长增1；b.步骤：节点后移，腾出第i个位置；将e置入表；表长加1。c.算法分析平均移动次数n/2时间复杂度O(n)d.算法数据结构○3删除a.功能删除第i个元素b.步骤结点前移；表长减1；c.算法分析平均移动次数(n-1)/2时间复杂度O(n)d.算法○4查找a.功能在顺序表中查找第1个与给定值e相等的位置b.基本操作进行2个元素比较c.算法分析时间复杂度O（n）;d.算法数据结构5顺序表小节○1特点：逻辑上相邻的元素，存储位置也相邻○2优点：可随机存取表结点无需额外存储空间○3缺点效率低（插入、删除需要移动大量的元素）；难以确定合适的存储规模（表长大小固定）；2.3线性表的链式表示和实现2.3.1单链表1单链表概念及术语○1单链表a.概念：表中所有结点通过指针的链接而组织成链表，每个结点只有一个指针域。b.线性表举例：(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)c.结点形式：next:指针域，指向后继结点；data：数据域，存储表中一个元素；单链表示例：P27○2单链表的逻辑表示箭头表示指针○3几个术语：a.空指针NULL：标志作用标志链表最后一个结点b.头指针H：指向链表第一个结点，标示链表数据结构c.头结点：单链表第一个结点之前的结点d.头结点作用：使空表和非空表的处理一致；使得链表对第一个位置上元素的操作与其他位置上元素的操作一致○4单链表结点定义：用C语言结构指针：○5a.头结点/表结点/首结点/尾结点b.引用：设p指向单链表a第i个结点：第i个结点指针域：p第i个结点数据域：p-data=ai第i+1个结点指针域：p-next第i+1个结点数据域p-next-data=a1i○6单链表操作：a.结点读取操作功能：查找链表中第i个元素，找到返回结点值步骤：初始化指针p=L-next,j=1;顺时针查找，直到p指向e或p为空；返回结果算法分析：等概率情况下，平均时间复杂度为O（n）算法：b.结点插入操作功能：在单链表第i个位置前，插入元素x;步骤：数据结构找插入位置，while(p&&ji-1)生成新的结点：s-data=e链入结点：修改指针：s-next=p-nextp-next=s算法分析：等概率情况下，平均时间复杂度为O(n)算法：c.结点删除操作功能：删除链表中第i结点步骤：找到第i个结点：while(p-next&&ji-1),p=p-next摘除：q=p-next,p-next=q-next释放结点：e=q-data,free(q)算法分析：等概率情况下，平均时间复杂度为O（n）算法：数据结构d.创建链表方法：一：从表头到表尾顺序建立：（在表尾插入）二：从表尾到表头逆向建立；（在表头插入）步骤：建立空单链表：L-next=NULL;输入新结点：scanf(“%d”,&x);插入结点：p-next=L-next;L-next=p算法分析：等概率情况下，平均时间复杂度为O(n)算法：e.链表合并操作含义：把两个有序表合并成一个链表：步骤：建立3个指针pa,pb,pc，分别指向La,Lb,Lc；取La,Lb表中元素，比较后放入Lc中；La,Lb表之一为空，插入剩余结点到Lc中；算法分析：等概率情况下，平均时间复杂度为O(n)算法：数据结构2.3.2循环链表1定义：另一种链式存储结构；单链表尾结点p指针域为空，即p-next=NULL;循环单链表，尾指针p不为空，而是指向头结点，即p-next=L;2循环链表示意图：p35,2.123循环链表操作：与单链表操作基本一致：算法中循环条件：判断头指针和尾指针是否相等；循环链表：p-next=L;单链表：p-next=NULL4优点从任一结点出发都可以找到表中的结点2.3.3双向链表1单链表缺点：单向性（查找前驱困难，后继容易）定义：双向循环链表结点有俩个指针域，一个指向直接后继，一个指向直接前驱；结点形式：prior:指针域，指向前驱结点；next:指针域，指向后继结点；data:数据域，存储表中元素2双向链表类型定义：3双向链表结构特性：对称结构，d为DuLinklist型指针变量d-next-prior=d=d-prior-next4双向链表的基本操作：求表长、读结点、查找与单链表相同；数据结构插入、删除与单链表不同5结点插入操作：链入结点：新结点s，插入当前结点p前；注意：操作顺序不唯一，但○1必须在○4的前面：○1.s-prior=p-prior○2p-prior-next=s○3s-next=p○4p-prior=s6结点删除操作：摘除结点：删除当前结点p：○1p-prior-next=p-next○2p-next-prior=p-prior2.3.4顺序表与链表比较1空间性能比较：顺序实现：优点：空间利用率高缺点：需事先估计容量连接实现：优点：链表占空间可随时改变缺点：空间利用率低2时间性能比较：当需要随机存取时，易采用顺序实现当经常需要插入和删除时，易采用链接实现