数据结构学习笔记..docx

算法的特性：有穷性、确定性、可行性、零个或多个输入、一个或多个输出算法的时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，则算法的时间复杂度为：T(n) = O(f(n))它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。算法的空间复杂度：作为算法所需存储空间的量度S(n) = O(f(n))一个上机执行的程序消耗的存储空间用在了两个地方：1 寄存程序本身执行所用的指令、常数、变量和输入数据 2 对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间线性表线性结构的特点：(1) 存在唯一一个被称为“第一个”的数据元素(2) 存在唯一一个被称为“最后一个”的数据元素(3) 除第一个之外，集合中每个数据元素均只有一个前驱(4) 除最后一个之外，集合中每个元素均只有一个后继(a1,…ai-1, ai, ai+1, …, an)线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据结构。是一种随机存取的存储结构。LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L线性表的链式表示：线性链表：节点包括数据域和指针域。n个节点链接成一个链表即为线性表的链式存储结构。只包含一个指针域的链表称为线性链表或单链表。假设L是LinkList型变量，则L为单链表的头指针，它指向单链表的第一个节点有时在单链表第一个节点之前附设一个头结点单链表是非随机存储的存储结构，取得第i个数据元素必须从头指针出发寻找。练习：判断一个单向链表中是否存在环的最佳方法是（）A、两重遍历?B、快慢指针? C、路径记录 D、哈希表辅助静态链表：借助一维数组来描述线性链表。可以用在没有指针概念的高级语言中。定义中用cur代替指针的概念假设S为SlinkList型的变量，则S[0].cur指示第一个节点在数组中的位置，若设I = S[0].cur，则S[i].data为存储在线性表中的第一个数据元素，S[i].cur指示第二个节点在数组中的位置。循环链表：特点是表中最后一个节点的指针域指向头结点。双向链表：特点，有两个指针域，一个指向直接后继，另一个指向直接前驱。栈定义：是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。是一种后进先出的线性表顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈顶指针top=0表示空栈。顺序栈的定义：其中，stacksize为栈容量；base=top时表示空栈；非空栈的栈顶指针始终在栈顶元素的下一个位置链栈：实现起来比顺序栈简单队列队列是一种先进先出的线性表。和线性表类似，队列也可以有两种存储结构。链队列：用链表表示的队列称为链队列。队列为空的判断条件是：Q.front=Q.rear,并都指向头结点。顺序队列：队列的顺序存储结构，用一组地址连续的存储单元依次存放队头到队尾的元素；附设两个指针front和rear分别指示队列头元素和队尾元素。初始化空队列时，front=rear=0；当插入新元素时队尾指针加1，当删除队头元素时，头指针增1.循环队列：当队列空或满时，都有front=rear，只根据此条件不能确定是空队列和满队列。可以少用一个存储位置，以队头元素在队尾元素的下一位置表示队满，队头元素等于队尾元素表示队空。串串：也叫字符串，是由零个或多个字符组成的有限序列，记为s=’a1a2…an’字符串的最小操作子集：串赋值、串比较、串连接、求串长、求子串。串的定长顺序存储：用一组地址连续的存储单元存储串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述：串的堆分配存储:仍然以一组地址连续的存储单元存放串值字符序列，但是他们的存储空间是程序执行过程中动态分配的。在C语言中，存在一种称之为“堆”的自由存储区，并由动态分配函数malloc()和free()来管理。串的块链存储表示：1 采用链式方式存储串值；2 存在一个节点大小的问题：如下图下图为串的块链存储表示数据结构：串的模式匹配算法：KMP算法实现的index函数：略，以后补充。数组和广义表数组的顺序存储：由于二维数组可看成一维数组的数组，在存储时存在两种存储方法：即以列序为主序和以行序为主序，C语言中用的是行序为主序，即存储顺序为[a00,a01…a0n,a10,a11…a1n,…am0,am1,…amn]二维数组中元素aij存储位置的计算(以行序为主序)：假设每个数据元素占L个存储空间，则二维数组A中任意一元素aij的存储位置为LOC(i,j)=LOC(0,0)+(b2*i+j)*L推广到n维：LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(b2*…*bn*j1+b3*…*