数据结构复习

数据结构复习第一章绪论1.1.1数据是一种描述，C语言中，常用数据类型有int、float、double、char等，当我们描述一样物体时，物体具有各种属性（学生有姓名、年龄、性别），所以有了结构体（struct）。在实际写代码时候，通常用typedef来优化代码typedefstruct{longnumber;charname[10];charsex[3];intage;}StudentType;//typedef记得在后面加分号，#define是没有分号的1.1.2数据的逻辑结构可以分成：集合结构、线性结构、树型结构、图型结构1.1.3数据的存储结构可以分成：顺序存储结构、链式存储结构数据结构讨论的就是：表、堆栈、队列、串、数组、树、二叉树、图1.3算法是描述求解问题方法的操作步骤集合算法的基本特性：输入性、输出性、有穷性、确定性、可执行性算法都应满足五个目标：正确性、可读性、健壮性、高时间效率、高空间效率其中，由于现代存储设备的水平提高了，因此更多考虑的是时间效率，也就是时间复杂度算法的时间复杂度由嵌套最深层语句的频度决定–对于循环程序，一般看有几重循环时间复杂度的数量级递增顺序：简单的求时间复杂度的例题可以看书本P9，下面给多几个例题：(1)i=1;k=0;while(in){k=k+10*i;i++;}解答：基本语句执行了n-1次，故时间复杂度为O(n)(2)x=n;while(x=(y+1)*(y+1))y++;解答：设y的初值为0，则第k次循环完后，y的值为k于是循环的退出条件变为：(k+1)*(k+1)n，也就是k√-1，由于k为正整数，所以k为√下取整，这样时间复杂度为O(√)(3)x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;解答：这个程序总共循环运行了1000次，但是都与n无关，故时间复杂度O(1)扩展：测试一段代码运行的时间的方法P13#includetime.hdoublet;time_tstart,end;time(&start);………………;time(&end);t=difftime(end,start);//书本上给的这个函数精度并不够，所以需要更高精度的函数可以选择使用clock，具体可以百度一下数据结构复习第二章线性表线性表的特点是可以在任意位置插入和删除线性表分为：顺序存储结构（顺序表）、链式存储结构（链表）线性表的操作：初始化、求个数、插入、删除、获取、销毁等，具体代码请同学们自行查阅书本，或者是看附件中的源码，建议还是自己抄(qiao)一遍，好记性不如烂笔头（烂键盘？）2.2顺序表动态数组头文件：#includestdlib.h函数有：malloc(总长度);calloc(个数,长度);free(一个指针(地址));int*p;p=(int*)malloc(sizeof(int));free(p);malloc和calloc有什么不同？当内存只剩下很小的零碎空间时，calloc优于malloc顺序表中方法的时间复杂度：插入、删除：O(n)，其他与n无关的操作：O(1)顺序表的优点：算法简单，内存单元利用率高；可以随机存取表中任一元素，方便快捷顺序表的缺点：需要预先确定数据元素的最大个数；在插入或删除某一元素时，需要移动大量元素2.2链表指针是链表的核心，一个节点的结构体中有数据域和指针域、数据域用于存放数据，指针域存放指向下一个的指针，重点要掌握单链表的各种操作以及实现方法。关于初始化函数为什么要用**head（指针的指针）Initiate(SLNode**head);{*head=(SLNode*)malloc(sizeof(SLNode));(*head)-next=NULL;}我们注意到，因为next是一个SLNode*类型假如函数用的是*head，那么在主函数中创建SLNode*head这个head本身就是一个地址，相当于门牌号，不是实际的房子既然没有房子，也就没有里面的元素（next以及data）而如果我们使用指针的指针，那么首先*head是一个在主函数定义好的实体（虽然这一个门牌号指向的房子不知道是哪一间，但这个门牌号却实际存在）**head指向是一个实体，所以就可以给他赋值&head（指针的指针）=======head（指针）========？？？(地址指向实体，指向明确)(这个对象实际存在)(但指向不明)顺序表中方法的时间复杂度：插入、删除：O(n)，撤销单链表：O(n)，其他与n无关的操作：O(1)链表的优点：不需要预先确定数据元素的最大个数链表的缺点：因为每个节点都有个指针域，空间效率不高；算法复杂循环单链表P361.在初始化时，(*head)-next=NULL;改成(*head)-next=*head;2.在其他函数中，循环判断条件p-next!=NULL和p-next-next!=NULL中的NULL改成head。双向链表增加了一个指向前驱节点的指针域双向链表的插入和删除设p是指向10的节点，q是指向15的节点，步骤：先处理好新建的节点：q-next=p-next;q-piror=p;再处理后面的：p-next-piror=q;再处理本身：p-next=q;删除节点的方式数据结构复习第三章堆栈和队列我们在学习完第二章后，堆栈是十分好理解的，它们就是特殊的线性表而已堆栈是先进后出，就像是放书本进箱子，拿书本出来的操作，栈是仅在表尾进行插入、删除操作的线性表。强调：插入和删除都只能在表的一端（栈顶）进行！插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。typedefstruct{DataTypestack[MaxSize];inttop;//栈顶指示器，也可以用于表示栈内元素的个数}SeqStack;//顺序表栈typedefstauctsnode{DataTypedata;structsnode*next;}LSNode;//链表的一个节点问：为什么要设计堆栈？它有什么独特用途？1.调用函数或子程序非它莫属；2.递归运算的有力工具；3.用于保护现场和恢复现场；4.简化了程序设计的问题。不管是链表还是顺序表，它们所有操作（插入删除这些）的时间复杂度都是O(1)例题：三个数据a、b、c，将它们存入栈中取出，可以有多少种不同的取出排列？（这个会考）1.a入栈，出栈。b入栈，出栈。c入栈，出栈。结果是abc2.a入栈，b入栈，出栈,a出栈,c入栈，出栈。结果是bac3.a入栈，b入栈,出栈,c入栈，出栈,a出栈。结果是bca4.a入栈，出栈,b入栈,c入栈，出栈,b出栈。结果是acb5.a入栈，b入栈，c入栈，c出栈,b出栈,a出栈,。结果是cba队列是先进先出，就像是平时排队打饭，只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。强调：仅在表尾（队尾）进行插入操作，仅在表头（队头）进行删除操作在队尾插入元素称为入队；在队首删除元素称为出队。为什么要设计队列？它有什么独特用途？1.离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）；2.操作系统中的作业调度（一个CPU执行多个作业）；3.简化程序设计。顺序表队列的存储结构typedefstruct{DataTypequeue[MaxSize];intrear;//队尾指示器intfront;//队头指示器}SeqQueue;顺序表队列存在假溢出现象，所以顺序队列用的是循环顺序表假溢出：顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。循环顺序表把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxSize-1后，再前进一个位置就自动到０。实现：利用“模”运算入队：rear=(rear+1)%N;data[rear]=x;出队：front=(front+1)%N;x=data[front];注意！！顺序循环队列的队空和队满判断问题新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案3：使用一个计数器记录队列中元素个数（即队列长度）判队满：count0&&rear==front或者count==N判队空：count==0链式队列的存储结构链式队列的队头指针指在队列的当前队头结点位置，队尾指针指在队列的当前队尾结点位置。下图是一个不带头结点的链式队列的结构：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;//每一个节点为了方便参数调用，通常把链式队列的队头指针front和队尾指针rear也定义为结构体类型，如下：typedefstruct{LQNode*front;LQNode*rear;}Lqueue;//相当于指示器实验：利用栈和队列来判断是否回文小结线性表、栈、队的异同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：（1）运算规则不同：•线性表为随机存取；•栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；•队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。（2）用途不同：线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、操作系统作业调度和简化设计等。数据结构复习第四章串串，也就是平时我们理解的字符串，对串进行操作的时候，要加上头文件#includestring.h，常用函数有：串长度：intstrlen(char*s);串比较：intstrcmp(char*str1,char*str2);串拷贝：char*strcpy(char*str1,char*str2);串连接：char*strcat(char*str1,char*str2);子串查找：char*strstr(char*s1,char*s2);顺序存储结构：typedefstruct{charstr[MaxSize];intlength;}String;链式存储结构typedefstruct{char*str;intmaxLength;intlength;}Dstring;本章重点：串的模式匹配算法设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。BF算法（这个一定要会）算法思想：子串与主串从头到尾逐个匹配，只要有一个不满足，就把子串后挪一位，循环BF算法时间复杂度：情况最好O(m);情况最坏O(nm)，其中n为主串长，m为子串长KMP算法算法思想是通过研究主串，发现主串存在某种规律，可以让匹配次数变少，这种规律就是next数组，里面存放的数字都是每一次主串不匹配发生时，下一次从主串的哪一个位置开始找起，而不是像BF那样，每次都从错误的下一个找起KMP算法时间复杂度：O(n+m)，其中n为主串长，m为子串长next[]如何求？主串：ababacdaenext[]-100123001第1个默认为-1第2个默认为0第3个前面是ab，无真子串，所以是0第4个前面是aba，真子串a，所以是1，也就是长度第5个前面是abab，真子串ab，所以是2第6个前面是ababa，真子串aba，所以是3第7个前面是ababac，无真子串，所以是0第8个前面是ababacd，无真子串，所以是0第9个前面是ababaca，真子串a，所以是1数据结构复习第五章数组数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一