数据结构word笔记

1、张东1145105494简介：1、算法+数据结构=程序2、数据结构3、数据、数据元素（基本单位）、数据项（最小单位）4、数据结构在计算机中的映像是存储结构；数据元素在计算机中的映像是结点；数据项在计算机中的映像是数据域；逻辑结构在计算机中的映像是关系。5、四种存储方式6、抽象数据类型1）按不同特性分类l 原子类型l 固定聚合类型l 可变聚合类型2）基本操作l init 构造l destroy 销毁l get 返回l put 改变l isasc 升序l isdesc 降序l Max 最大l min 最小7、时间复杂度技巧1）对于循环程序（for），最大执行次数即为for的乘积。简言之，程序有多少

2、for出现，就是n的多少次方2）对于顺序结构，可用“求和取最大值“法则3）对于循环程序（while），一般结果是O(logMN) 4）若是一般的赋值语句，时间复杂度必为O(1)5）对于选择结构的程序，一般时间复杂度为O(1)加：自加自减+ x=2；y=x+;y=+x; 第二章 线性表1、表长相当于元素个数2、线性表一般下标是1n，故当n=0时，表示线性表为空表3、list 表示线性表 elem 元素 length 表示求长度（线性表） locate 定位（位置） insert 插入（元素之前） delete 删除 void 空类型（写程序必写）顺序结构（链表相反）优势：随机存取劣势：在做插入或

3、删除时需要移动大量的元素malloc 分配一个连续空间realloc 将已分配的空间进行重新分配顺序表插入时所需移动的元素次数期望值是n/2删除时所需移动的元素次数期望值是（n-1）/2删除：模板语句：q=&(L.elemi-1) 表示顺序表中插入元素或者删除元素的地址加：逻辑运算符：！非 &与（一假即假） |或（一真即真）逻辑值：真（1） 假（0）比较运算符： = = = !=若在if或者while后面的括号中出现逻辑表达式或者比较表达式，那么结果只能为真或假。模板语句：if(iL.length) return ERROR;表示在顺序表中，删除元素，若输入的删除地址不符合题意，则返回错误。2

4、、链式结构1）结点=数据域（元素）+指针域（指向后继结点） 单链表2）一般在第一个元素之前，会创建一个头结点（头指针），用head表示。指向第一个元素head-NULL 表示空表head-next=NULLclear 重置create 创建模板语句p=L-next 表示单链表中、头结点为L指向下一个结点N=（linklist）malloc(sizeof(LNode)表示在单链表中生成新结点技巧：做单链表的插入操作1）判断单链表的存在与否2）找到插入位置 p=p-next j+3）生成新结点 malloc4）赋值 p-data=e(插入的元素)5）插入元素 单链表删除操作1）2）同插入3）删除结

5、点模板输出逆序顺序 for(i=0;i0;i-)循环链表1、判断单链表的最后一个结点，表示方式是指针域为空；判断循环链表的最后结点，表示方式是指针域指向第一个结点2、不需要头结点3、循环链表为空，表达方式为 L-next=L双向链表1、插入2、删除3、三部分：data next priorlinklist表示链式结构的线性表第三章 栈和队列1、操作受限的线性表栈1、先进后出 后进先出2、表头-栈底 表尾-栈顶3、必须要有栈顶指针 top系列：12345进栈出栈：12345 54321 34521 24351 412354、 stack 栈 push 进栈 pop 出栈 empty 判断是否为空

6、5、当top=0/-1时，表示为空栈 top=base(指向栈底指针) top-base=0 stacksize=N 表示栈中元素个数模板语句1）S.top=S.base 设置栈顶栈底指针2）S.Stacksize= STACK_INIT_SIZE6、入栈（插入）：栈满（s.top-s.base=s.stacksize）;s.top+;*s.top=e出栈（删除）：栈空（s.top=s.base）;s.top-;e=*s.top7、加：双栈共享一个空间栈：1,2空间：Am1）栈底在空间两端2）栈空：top1=0 top2=m-13）栈满：top1+1=top2 中缀后缀（前缀）1）将每一步运算

7、加括号2）将每一括号内的运算符放在所在的括号后（前）3）将括号全部去除4）必须保证一个括号内只有一个运算符加： 顺序结构、选择结构、循环结构选择结构：ifelse if(x=0) y=1; else y=2;递归调用1、每次运行都是相似的操作2、每一项的值都由前一项的值决定3、必须要有一个基础值队列1、先进先出2、在队尾处进行插入、在队头处进行删除3、基本操作1）Queue2）clear 清空3）gethead 取队头元素4）Enqueue 入队 Dequeue出队5）queuetraverse 遍历队列（查询队列中每一个元素）模板：Q.front-next=NULL 表示初始化队列Q.fro

8、nt=Q.rear 表示队列为空e=Q.front-next-data 表示队头元素 若将队列放入数组base中：1、入队：baserear=e;rear+;2、出队1）e=basefront;2）front=front+1;注意：入队相当于尾指针自加1，出队相当于头指针自加1。循环队列1、队空：Q.front=Q.rear2、入队：baserear=e;rear=(rear+1)%M;M:循环队列元素个数3、出队：e=basefront;front=(front+1)%M;4、队满front=(rear+1)%M队空：front=rear求循环队列的元素个数（长度）(Q.rear-Q.fro

9、nt+MAXQSIZE)%MAXQSIZE 第四章 串1、空串 空格串“” “ ”2、字符位置：所在字符串的位置 子串位置：子串第一个字符在主串中的位置3、串相等1）长度相等2）元素相同l 非平凡子串即非空非主串的子串l 任意串为本身子串、空串为任意串子串l 一个串的子串个数为n*(n+1)/2+1（空串）l 一个串的真子串个数为n*(n+1)/2-1（本身）加：ASCII码0 -48 09（48-57）A-65 AZ（65-90）a-97 az （97-122）concat 串的连接compare 串的比较（ASCII）substring 求子串（表示从左边第N个字符开始截取M个字符）ind

10、ex 求子串的位置（POS表示从左边第pos个字符开始检索）顺序：1、定长1）0号单元存放的是串的长度2、堆分配1)实际串长和数组长度相等加：数据类型1）整型 int int a; a=1; a=123; 2）浮点型 float float a; a=1.23）字符型 char char ch; ch=i; ch=1;模式匹配1）若主串长度n，模式串长度为m，则时间复杂度为O(m*n)2）模板语句：if(si=tj) +i; +jelse i=i-j+2; j=1if(jt0) return i-t0;else return 0; S: abbcbacbabc 11T:abc 3男朋友：9KM

11、P：3Q:模式串p=abaabcac,next函数值序列为？t=abcaabbcabcaabdabnext01112231123456712第五章 数组 广义表1、二维数组2、元素个数：行*列3、已知首地址a0和每个数组元素所占用的空间l，求任意数组元素的地址aiai=a0+(i)*l 下标从0开始ai=a0+(i-1)*l 下标从1开始4、二维数组1）以行为先序输入线性表aij=a00+(i*n+j)*L2）以列为先序输入线性表aij=a00+(j*m+i)*L注：二维数组为m*n,首元素为a00Q：数组A，每个元素长度3B,行i下标18，列j下标110。首地址SA开始存储，数组按行（列）存

12、放，元素a85的起始地址？解：按行：a85=a00+(8-1)*10+5-1)*3=SA+222按列：a85=a00+(5-1)*8+8-1)*3=SA+117Q:二维数组M的元素占用4B，行下标i(0-4),列下标j(0-5),M按行存储M35的起始地址和M按列存储？的起始地址相同。M24 M34 M35 M44解：按行M35=a00+(3*6+5)*4=a00+92按列 M34=a00+(4*5+3)*42）三维l 以行为主序，则行下标变化最慢，纵下标变化最快l 以纵为主序，则行下标变化最快，纵下标变化最慢l 列的变化速度介于行纵之间矩阵的压缩存储1、特殊矩阵1）对称矩阵aij=aji压缩

13、方法：为每一对对称元分配一个存储空间存储：n(n+1)/2个存储空间aij：k=i(i-1)/2+j-1 （i=j） k=j(j-1)/2+i-1 (ilchild); /递归遍历左子树 PreOrderTraverse(T-rchild); /递归遍历右子树表示先序！中序：InOrderTraverse(T-lchild); /递归遍历左子树printf(“%c”,data); /访问根结点 InOrderTraverse(T-rchild); /递归遍历右子树后序：PostOrderTraverse(T-lchild); /递归遍历左子树PostOrderTraverse(T-rchild

14、); /递归遍历右子树printf(“%c”,data); /访问根结点五、表达式用二叉树表示1、中缀表达式用二叉树的中序遍历表示l 运算符在分支结点上l 操作数在叶子结点上2、前缀表达式可以用二叉树的先序表示；后缀表达式可以用二叉树的后序表示；六、用字符串表示二叉树1、先根再左再右2、必须将左子树全部结点进行完毕后再去访问右子树模板：表示统计二叉树中叶子节点个数：if(!T-lchild)& (!T-rchild)count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); 表示求二叉树的深度depth

15、Left = Depth( T-lchild );depthRight=Depth( T-rchild );depthval=1+(depthLeftdepthRight? depthLeft : depthRight);结论：1、由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 结论1技巧：1）先序的第一个结点定是根结点2）根结点（子树）在中序的位置两侧正是其左右子树的结点3）后序的最后一个结点定是根结点结论2：若某一节点有左孩子，那么该结点在中序遍历二叉树所形成的序列中，其前驱是左孩子的最右子孙Q: 中序

16、： d g b a e c h f后序: g d b e h f c a 线索化二叉树：1）0表示有孩子、1表示没有孩子2）若是0，则画出其孩子结点、若是1，则画出其某种遍历后的前驱后继结点3）孩子结点用实线表示、前驱后继结点用虚线表示树的存储结构1）孩子兄弟表示法树有两个指针、一个指向第一个孩子、另一个指向下一个兄弟2）森林（若干棵树）二叉树l 所有相邻兄弟结点之间加一条线l 对于所有非终端（叶子）结点，只保留其到最左边孩子的连线，删去与其他结点之间原来的连线（断绝关系）l 最后以根为轴心，将整棵树（森林）顺时针旋转45度2）二叉树森林（树）l 将左子树上的右结点（本来是兄弟结点）分别和祖先

17、（包括双亲）结点相连l 删除所有原二叉树上的双亲结点到右结点的连线l 整个森林逆时针旋转45度树的遍历1）先根：根结点（孩子结点）2）后根：结点根3）层次：从上至下、从左往后森林的遍历1）先序：依次从左至右对森林中的每一棵树进行先根遍历。2）中序：依次从左至右对森林中的每一棵树进行后根遍历。树森林二叉树先根先序先序后根中序中序赫夫曼树1、术语1）带权路径长度：叶子结点到根的路径长度与叶子结点上权的乘积2) 树的带权路径长度：树中所有叶子结点的带权路径长度之和3）赫夫曼树：带权路径长度最小的树核心思想：l 必须保证累加的两个权值是所有权值（已知的、用户创建的）中最小的特点: 无度为1的结点，为什

18、么？若有n个权值，则形成的赫夫曼树中有2n-1个结点 Huffman树的高度 h 与结点数 m 之间的关系:若Huffman树的高度为 h ( h 0 )，则 二叉树中最多有 2h-1 个结满二叉树最少有2h-1个结点除根以外每层2个节点赫夫曼编码1）左分支 为0 右分支为12）尽量让出现次数多的字符靠近根结点 赫夫曼编码1）字符相当于叶子结点2）概率（频率、次数）相当于叶子结点的权值3）左分支为0、右分支为1*赫夫曼编码最好将权值小的放在左侧第七章 图1、术语1）G=（V,E） 多对多2）无向图、有向图3）有向图（弧）、无向图（边（a,b）、顶点4）完全图：任意两个点都有一条边相连无向完全图

19、：n个顶点，则有n(n-1)/2条边有向完全图：n个顶点，则有n(n-1)条边5）子图、6）若无（有）向图的边（弧）上有权值，则称为无（有）向网7）邻接点、度（关联的边的个数）、出度、入度、路径、路径长度、简单路径、简单回路8）连通图（无）、强连通图（有）、强连通分量、连通分量2、存储1）邻接矩阵l 对角线均为0l 属于对称矩阵（无向图）l 有向图：不一定是对称l 无向图：顶点i 的度第 i 行 (列) 中1 的个数；l 特别：完全图的邻接矩阵中，对角元素为0，其余1。l 有向图：第i行表示出度、第i列表示入度。2、邻接表1）无向图：l TD(Vi)=单链表中链接的结点个数2）有向图l 单链表

20、链接的结点个数是顶点的出度l 逆邻接表邻接矩阵和邻接表1、联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2、区别：邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3、用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图Q：对于一个具有n个顶点的无向图、采用邻接矩阵表示，则该矩阵大小 对于具有n个顶点和e条边的无向图、采用邻接表表示，表头向量大小 n 所有邻接表中结点总数 2e 图的遍历1、深度（DFS）：仿树的先序1）至左向右访问2）尽可能在一条路径中访问更多的顶点技巧1：将每一个顶点当成根结点，然后旋转成类似于树的图形状，再从左向右遍

21、历!2、广度（BFS）：仿树的层次遍历总结：1）若题目只给图、则深度遍历不唯一。2）若题目给出邻接表或邻接矩阵，则遍历唯一3）若唯一时可用技巧1来解答，注意顶点顺序最小生成树：1、目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树（保证不会出现环路且每个顶点都被访问）2、Prime算法: 归并顶点，与边数无关，适于稠密网Kruskal算法：归并边，适于稀疏网拓扑排序AOV网(Activity On Vertices)用顶点表示活动的网络AOE网(Activity On Edges)用边表示活动的网络拓扑排序算法的思想重复选择没有直接前驱的顶点拓扑排序不唯一关键路径：（最长）l el(i

22、)=ee(i)的活动称为关键活动，关键路径上的所有活动都是关键活动最短路径l 注：最短路径与最小生成树不同，路径上不一定包含n个顶点）l 求源点到各个顶点的最短路径值第九章 查找一、术语1、静态查找表：查询、检索 动态查找表：插入、删除、查询、检索2、关键字（标识）二、静态查找表1、顺序、有序、索引（块）2、顺序查找表1）查找成功：平均查找长度（n+1）/22）查找不成功：n+13）查找概率相等时，ASL相同；查找概率不等时，如果从前向后查找，则按查找概率由小到大排列的顺序表其ASL要比无排列的顺序表ASL小。 2、有序查找1）折半查找方式2）若k=Rmid.key，查找成功若kRmid.ke

23、y，则low=mid+1说明：k为待查找的值；high为指向高位的指针；low为指向低位的指针；Rmid.key表示具体被比较的值。mid为指向中间元素的指针。加：1）if(条件表达式：TF) 语句1； 语句2；若表达式为真，则输出语句1；若表达式为假，则输出语句2；2）else 否则if（表达式） 语句1； else 语句2；3）if(表达式1) 语句1；else if（表达式2）语句2； else 语句3；3）判定树:根结点是mid指向的元素；大于其放入右子树、小于其放入左子树，以此类推。Q:长度为12的有序表，折半方式查找。各概率相等。求平均比较次数？1 2 3 4 5 6 7 8 9

24、10 11 12Q:对有18个元素的有序表做折半查找，查找下标为3的元素需要比较多少次？4特例：若两元素左右关系，则查找左边元素满足low=high-1；查找右边元素满足low=high。3、索引查找1）块与块之间是有序、但块内是无序。即第n块的最大值小于第n+1块最小值。2）步骤：待查找的值和至少两块最大值进行比较，确定具体的块的位置；在块内进行顺序查找。二、动态查找表1、二叉排序树1）若用中序形式遍历则可得递增序列（有序）2）已知无序序列，求二叉排序树Q:15、10、6、19、17、3、7 二叉排序树任意结点均小于其右子树、大于其左子树。T3）不同插入次序的序列生成不同形态的二叉排序树3、

25、删除1）分为三种情况：叶子、左右各一、左右都有2）若仅有左（右）子树，则结点被删除后。其左（右）子树作为根结点3）若左右皆有。则以直接前驱结点代替，继而删除原前驱结点4）平均查找长度和二叉树的形态有关，即，最好：log2n（形态匀称，与二分查找的判定树相似）最坏: （n+1)/2（单支树）三、平衡二叉树1）l 左、右子树是平衡二叉树；l 所有结点的左、右子树深度之差的绝对值 1（-1、0、1）l 左右+ 左有序（折半）线性链地址第十章 排序一、概念1、内部排序 外部排序2、插入排序：即边插入边排序，保证子序列中随时都是排好序的1）直接插入：l 每一步确定一个关键字的位置l 第一步一般就是第一个

26、关键字l 每一步被排序的关键字尽量用中括号表示l 比较次数：比较次数l 移动次数：移动次数重点：l 时间复杂度为 o(n2)l 空间复杂度为 o(1)l 是一种稳定的排序方法2）折半插入排序l 有序序列l 每趟比较次数小于直接插入排序l 当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差l 趋近于有序序列、则折半插入比较次数要比直接插入比较次数多；移动次数均相同。l 时间复杂度为 o(n2)l 空间复杂度为 o(1)l 是一种稳定的排序方法3）希尔排序l d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。l 时间复杂度是n和d的函数：o

27、(n1.3)l 空间复杂度为 o(1)l 是一种不稳定的排序方法2、交换排序（快速排序）1）中心思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。2）比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上3）冒泡排序：基本思想：每趟不断将记录两两比较，并按“前小后大” 规则交换4）l 时间复杂度为 o(n2)l 空间复杂度为 o(1)l 是一种稳定的排序方法快速排序1、枢轴位置不唯一（第一个、最后一个）2、时间效率：O(nlog2n) 每趟确定的元素呈指数增加空间效率：O（log2n）递归要用到栈空间稳 定 性： 不稳定 可选任一元素为支点。Q:数列为50,26,38,80,70,90,8,30,40,201、 50 26 38 80 70 90 8 30 40 202、50 8 30 40 20 90 26 38 80 70Q：题型：判断某种排序？技巧：l 起泡：第一趟最后一个是最大值l 直接插入、折半：第一趟的前两个关键字的位置确定l 快速：第一趟确定中心数据左边是比