算法与数据结构复习总结.doc

算法与数据结构复习总结.docCHI
数据结构：相互之间存在一种或多种特定关系的数据元素的集合Data_Structure= (D, S)
数据〉数据元素〉数据项例：班级通讯录〉个人记录〉姓名、年龄……
存储结构可分为4大类：顺序、链式、索引、散列
最常用的数据运算有5种：插入、删除、修改、查找、排序
ADT = (D, S, P)数据对象 D上的关系集 D上的操作集
算法有5个基本特性：有穷性、确定性、可行性、输入和输出
算法评价有4个指标：运行时间、占用空间、正确性和简单性
CH2线性表(info头结点*q后一位*p前一位coef 一元多项式系数expon指数link指针)
顺序表写入 a-z： V[0]= a ;V[i]=V[i-l]+l;
插入：for (j=n; j>=i; j—) a[ j+1 ] =a[ j];a[i] =x;n++:**f (n) =n - i+1
删除：for (j=i+l; j〈=n; j++)a[jT]=a[j] ;n—;**f(n) =n - i
插入、删除操作平均需要移动一半元素(n/2)插入、删除算法的平均时间复杂度为：0(n)
链表 p-〉data=i+ 'a' T; p-> next= (text*) malloc (m)；为后继结点开辟新空间；
〃最后一个元素单独处理p-〉next=NULL ;} 〃单链表尾结点的指针域要置空！；
链表插入(在 p 后插入 s)： s-〉next=p-〉next ;p-〉next=s ；
链表删除(前 q 后 q 删除 q)： q = p-〉next;p-〉next=q-〉next;free(q)；
链表查找时间复杂度为0(n),线性链表插入和删除耗时间复杂度为0(1)单链表中所耗时 间复杂度为0(n),空间复杂度为0(n)
**************—■元多 项式相 加I
CH3栈与队列(front队头rear队尾top栈顶(表尾 即an端)base栈底(表头al) data 队栈的值link队栈的后续指针*?栈顶*st栈将要入的位)
空队列：front=rear入队(尾部插入)：v[rear]=e;rear++;出队(头部删除)： x=v[front];front++;
假溢出：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组 中还有空位置；
循环队列队满特征为front=(rear+l)%N；《N：共N个单位》；元素个数(n+r-f) %n
出栈序列通用的判别原则：在可能的输出序列中，不存在这样的输入序列i, j, k,能 同时满足i<j<k (输出)和Pj〈Pk〈Pi (输入)
对于向上生成的栈入栈口诀：堆栈指针top先压后加(v[top++]=x)；出栈口诀：堆栈指 针top先减后弹(y=v[—top])
栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize; *************初始化空循环队列，入队出队，顺序入栈出栈，链式入栈出栈，四则运算
CH4串(pos第几个字符len子串长S [0]串长concat串连接SubString ()求s中pos起长 度为len的子串Index返回子串T在pos之后的位置)
空白串(空白字符)与空串子串位置(第一个字符的序号)串尾加'\0'不计入串长
存储密度(有效base/总)
BF算法最坏情况时间复杂度0 (n*m) 一般情况下0 (n+m)《n主串m子串》
KMP算法next[j]时间为0 (m), Index_KMP函数时间为0(n) ;KMP算法的总时间耗费为： 0 (n+m)
递推：由“小”到“大”递进； 递归：由“大”到"小”嵌套。
next [j]越大，相似部分越多，模式串向右滑动得越远，与主串进行比较的次数越少，时 间复杂度就越低。
*************串插入算法，堆分配存储，BF算法，KMP算法
CH5
数组(LOC位址*base元素基址dim维数*bound各维长度信息保存区基址^constants Ci的 保存区e元素值mu行数nu列数tu非零元素总个数)
任一元素的地址(三要素)：①开始结点的存放地址(即基地址)②维数和每维的上、下 界；③每个数组元素所占用的单元数
行优先存储地址公式：L0C(aij)=L0C(acl, c2)数组基址+[(i-cl)《aij之前的行数》 *(d2-c2+l)总列数+j-c2本行前元素个数)]*L单个元素长度
列优先存储的通式为：L0C(aij)=L0C(acl, c2) +: (j-c2)*(dl-cl+1) +i-cl)]*L
顺序存储方式：低或高地址优先顺序《较长，难达到映射关系》 三