搜索
《数据结构与算法》复习第1部分：1.概念：数据结构，存储结构，逻辑结构注：磁盘文件管理系统是树状结构。1.1基本概念（1）数据：指所有能够输入到计算机中并被计算机程序处理的符号的总称（图像声音都可以通过编码归于数据的范围），范围大（2）数据项：数据的不可分割的最小单元（3）数据元素：是数据的基本单位，有若干数据项组成，通常作为一个整体考虑（4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例子：表A科目分数是否及格数学99是语文89是表B姓名性别身高小花女100小草男120其中，A表为成绩表，B表为学生信息表，这两张表就是数据；单独的一张表就称为数据对象，即A和B表都是一个数据对象；每张表中的每一行就称为数据元素；姓名，性别，身高，科目，分数就称为数据项1.2数据结构定义：相互之间存在一种或多种特定关系的数据元素的集合，这种关系包括三方面的内容，即数据逻辑结构，数据存储结构，数据的操作。数据结构数据逻辑结构集合线性结构树形结构图形结构数据存储结构顺序存储把逻辑上相邻的元素存放在物理位置上相邻的单元链式存储使用指针把有关联的元素链接起来，不用物理地址相连数据的操作读取、修改、插入、删除等数据数据对象数据元素数据项2.数据元素是组成数据的基本单位3.算法，算法分析，算法特性，时间复杂度3.1算法：描述求解问题方法操作步骤的集合。（不是所有的程序都是算法，要满足五个特性）3.2时间复杂度3.2.1定义：在算法分析中，一般用算法中的语句的执行次数来度量算法的时间效率，时间效率也就是时间复杂度。3.2.2计算方法：对于问题规模为n的某个函数f(n)，算法时间复杂度记为T(n)，存在一个正常数c，使cf(n)T(n)恒成立，则T(n)=Of(n)，称Of(n)为时间复杂度。时间复杂度的大O表示法：保留最高次数项，令最高次数项的系数为1。例如O(8)-O(1)，O(2n^3+2n^2)-O(n^3)，O(n*log2n)第2部分1.线性表的概念，特点，存储结构1.1．1线性表的概念：线性表是最简单，最常见，最基本的一种线性结构（数据的逻辑结构的一种），元素之间为线性关系，即除了第一个和最后一个元素之外，所有的元素都有前驱和后继元素，同一个线性表中的数据类型相同。当数据元素为0时，可以是空表，但是没有空图的说法。1.1.2线性表的特点：插入删除算法的时间复杂度为O(n)，不适合多次插入或删除1.2.1线性表的存储方式：（1）顺序存储（又称顺序表）物理地址相连a0A1A2A3A4A5A6A7A8A9（2）链式存储（又称链式表）1.2.2链式表的特点：可动态分配空间，插入删除算法的时间复杂度为O(1)单链表在特定节点插入和删除元素之前需要遍历链表，所以算法的时间复有穷性确定性有输入有输出可行性算法的基本特性正确性健壮性可读性高时间效率（主）高空间效率（次重）好算法的指标数据域指针域杂度为O(n)，对于单链表的求表长，取元素，插入删除，释放掉几个操作的平均时间复杂度都是O(n)，但是链表只需比较元素不用移动元素，所以时间效率上优于顺序表2.顺序存储时插入、删除（移动元素的个数）（1）定义顺序表的数据类型：typedefstruct{Intlist[maxsize];Intsize}（2）初始化voidlistinitial(sequence*L){L-size=0;}（3）插入元素：在i位置前插入一个新的元素，原顺序表中i位置之后的元素都要移动，并修改L-size+1；Intinsert(sequence*L,inti,intx){intj;if(L-size)=mavsize{printf(“线性表已满”)}elseif(i0||iL-size){printf(“参数不合法”)}else{for(j=L-size;ji;i++)//j指向顺序表最后一个元素size-1的后面{L-list[j]=list[j-1];}//先逐个移动元素L-list[i]=x;//再插入新的元素L-size++;//使得线性表的总长度+1}}插入算法的时间效率：平均移动元素的次数看做n/2（即移动一半元素），时间复杂度为O(n)（4）删除元素:删除i位置上的元素，将i后面的元素依次往前移，再令L-size-1,intinsert(sequence*L,inti,intx){intj;if(L-size)=0{printf(“线性表为空，无法删除”)}elseif(i0||iL-size){printf(“参数不合法”)}else{*x=L-list[i];for(j=i+1;jL-size-1;i++)//j指向要删除的元素的后一位{L-list[j-1]=list[j];}//再将i后面的元素逐个前移L-size--;}}删除算法的时间效率：任意删除一个元素平均需要移动的次数看做n/2（即移动一半元素）时间复杂度为O(n)（5）取元素*x=L-list[i];3.链式存储的插入，删除的语句如何写，如何判空。（1）定义链式表：typedefstructNode{intdata;//这样定义就是定义了一个数组相当于intdata[]structNode*next;}Lnode,*LinkList;//Lnode等价于structnode定义了一个新的数据类型//Lnode*L等价于LinkListL定义一个指向节点的指针变量（2）插入元素Lnode*q=(Lnode*)malloc(sizeof(Lnode));//分配一个新的节点空间q-data=ele;//是该结点的数据域赋值为eleq-next=temp-next;//把插入的节点的指针域指向下一个节点的data域temp-next=q;//然后让要插入的节点的前一个节点的指针域指向该插入节点的数据域，两者的顺序不能乱，否则的话就丢失了插入节点的后一个节点的指针，找不到他了（3）删除元素Lnode*del=temp-next;//单独设置一个指针指向被删除结点以防丢失temp-next=temp-next-next;//删除del的方法就是更改del-1的指针域,让他指向del+1的数据域，一步成功free(del);//释放删除的节点del的空间（4）单链表判空1、不带头结点的单链表first为空的判定条件：first=NULL；2、带头结点的单链表first为空的判定条件：first-=NULL；4.顺序存储与链式存储的优缺点。顺序表的存储优点是：方法简单，容易实现；不用为表示节点间的逻辑关系而额外增加储存开销；具有按元素序号随机访问的特点顺序表的存储缺点是：对于n较大的顺序表，插入和删除元素需要移动的次数较大，效率低；需要预先分配足够大的空间，可能会导致大量闲置空间或者出现数据溢出；链式表的优缺点与顺序表相反。在选择存储方式时，若n较大，多进行插入删除操作，建议用链式存储，若按序号访问元素时，建议按顺序表存储（时间效率为O(1)）例题：第3部分1.字符串的基本操作，什么叫模式匹配、1.1串的定义：字符串（也就是串）是0个或多个字符序列组成的有限序列。串就是数据元素为单个字符的特殊线性表。“qhjkdcbjsb”（隐含结束符\0）就是一个字符串，引号起界定作用，“”表示空串，串长为0“”空格串不是空串，串长为空格数1.2串的存储类型：顺序存储：定长顺序存储结构、堆分配存储结构（动态分配连续内存）链式存储1.3串的模式匹配：就是指定一个主串S和子串T，求T在S中第一次出现的位置。（1）朴素模式匹配（BP算法）核心思想：主串S和子串T，S[1]和T[1]比较，S[2]与T[2]比较，直到S[n]与T[n]都是相等的为止，若S[i]与T[i]不相等，则子串向右移动一个（一个字符）继续比较时间复杂度：主串S长度为n，子串T长度为m，最多进行m(m-n+1)次，最坏的时间复杂度为O(mn)效率不高（2）KMP算法核心思想：尽量利用已经得到的“部分匹配”的结果信息，不要让i回溯，加快子串右滑的速度，问题由子串决定而不是主串决定的next数组：是一个智能数组，指导子串下一步改用几号元素去匹配，next数组的next[1]和next[2]永远为0和1，其余next[n]看n位的前后缀的相同数目实例：（1）现有子串i=“ABABAAABA”,求其next数组i9ababaaabaj0123456789next011234223Next数组中对应i数组的值前缀后缀Next[]的值Next[j1]000Next[j2]AA1Next[j3]AB1Next[j4]AA2Next[j5]ABAB3Next[j6]ABAABA4Next[j7]AA2Next[j8]AA2Next[j9]ABAB3（2）实例，不详细解释主串是S=“bbsbbcdfbb”子串是“bbsbbs”,求next数组T6bbsbbsJ0123456next012123主串是S=“sssssvsd”,子串是T=“ssssb”求next数组S5ssssBl012345Next01234Next数组中对应i数组的值前缀后缀Next[]的值Next[j1]000Next[j2]ss1Next[j3]ss2Next[j4]ssss3Next[j5]ssssss4KMP算法的时间复杂度：O(m+n)第4部分1.栈的基本概念与特点栈和队列也是线性表，只是操作受限制的线性表，他们线性表的区别在于线性表可以在在任意位置插入或删除元素，而栈只能在栈顶操作，队列只能在队尾操作。1.1栈的特点：后进先出（LIFO）可看做装电池，只能对栈顶进行操作1.2存储方式：顺序存储和链式存储有n个元素的栈的顺序存储栈的链式存储2.栈的两种存储结构的基本操作，如何入栈，出栈，判空？操作栈存储方式类型顺序栈链式栈定义数据类型Typedefstruct{Intstack[maxsize];Inttop;}sequencestack;Typedefstructsnode{Intdata;Intsnode*next;}singlelinkednode;初始化S-top=0;取栈顶*d=S.stack[S.top-1];Singlelinkednode*p=head-next;*d=p-data;入栈S-stack[S-top]=x;S-top++;移动top指针Singlelinkednode*p；p-data=x;p-next=head-next；//先执行head-next=p;//后执行出栈S-top--;直接移动top指针，不用删除原栈顶head-next=head-next-next;free(p);//需要释放出栈的元素判空if(S-top==0)printf(“stackisempty”);If(head-next==null)Printf(“stackisempty”);例题：3.栈的应用举例（进制转换，递归，迷宫，表达式求值等）栈的应用内容进制转换算法原理：辗转相除法算法公式：N=(Ndiv2)*2+Nmod2递归迷宫表达式求值例1：A+(B-C/D)*E（也称为中缀表达式）前缀表达式为：+A*-B/CDE即运算符在数值前面后缀表达式为：ABCD/-E*+运算符在数值后面例2：[(a+b)+c*(d+e)+f]*(g+h)前缀表达式为：*++ab*+cdeg+gh后缀表达式为：ab+cde+*+f+gh+*例题：4.队列的基本概念与特点4.1队列的特点：先进先出（FIFO）可看做排队买冰淇淋，只能对队头和队尾进行操作4.2存储方式：顺序存储和链式存储（注意front和rear的位置）队列的顺序存储队列的链式存储4.3假溢出问题队列中因为多次出队入队而导致的存储空间不足的问题——解决办法：循环队列front+1==[front+1]%maxsize;5.队列的两种存储结构的基本操作，队空，队满，环形队列，假溢出？队列的操作循环队列链式队列定义数据类型Type