算法与数据结构复习总结

《算法与数据结构复习总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CH11，数据结构：相互之间存在一种或多种特定关系的数据元素的集合Data_Structure=（D,S）2，数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……3，存储结构可分为4大类：顺序、链式、索引、散列4，最常用的数据运算有5种：插入、删除、修改、查找、排序5，ADT=（D，S，P）数据对象D上的关系集D上的操作集6，算法有5个基本特性：有穷性、确定性、可行性、输入和输出7，算法评价有4个指标：运行时间、占用空间、正确性和简单性CH2线性表（info头结点*q后一位*p前一位coef一元多项式系数expon指数

2、link指针）1,顺序表写入a-z：V[0]='a';V[i]=V[i-1]+1;2，插入:for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;**f(n)=n–i+13,删除：for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;**f(n)=n–i4，插入、删除操作平均需要移动一半元素(n/2)插入、删除算法的平均时间复杂度为：O(n)5，链表p->data=i+‘a’-1;p->next=（text*）malloc（m）；为后继结点开辟新空间；//最后一个元素单独处理p->nex

3、t=NULL;}//单链表尾结点的指针域要置空！；6，链表插入（在p后插入s）：s->next=p->next;p->next=s；7，链表删除（前q后q删除q）：q=p->next;p->next=q->next;free(q)；8，链表查找时间复杂度为O(n)，线性链表插入和删除耗时间复杂度为O(1)单链表中所耗时间复杂度为O(n)，空间复杂度为O(n)**************一元多项式相加CH3栈与队列（front队头rear队尾top栈顶（表尾即an端）base栈底（表头a1）data队栈的值link队栈的后续指针*

4、p栈顶*st栈将要入的位）1，空队列：front=rear入队(尾部插入)：v[rear]=e;rear++;出队(头部删除)：x=v[front];front++;2，假溢出：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置；3，循环队列队满特征为front=(rear+1)%N；《N：共N个单位》；元素个数（n+r-f）%n4，出栈序列通用的判别原则：在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足i

5、top先压后加（v[top++]=x）；出栈口诀：堆栈指针top先减后弹（y=v[--top])6，栈不存在的条件：base=NULL;栈为空的条件：base=top;栈满的条件：top-base=stacksize;*************初始化空循环队列，入队出队，顺序入栈出栈，链式入栈出栈，四则运算CH4串（pos第几个字符len子串长S[0]串长concat串连接SubString（）求s中pos起长度为len的子串Index返回子串T在pos之后的位置）1，空白串（空白字符）与空串子串位置（第一个字符的序号）串尾加‘

6、’不计入串长2，存储密度（有效base/总）3，BF算法最坏情况时间复杂度O（n*m）一般情况下O（n+m）《n主串m子串》4，KMP算法next[j]时间为O（m），Index_KMP函数时间为O(n);KMP算法的总时间耗费为：O(n+m)5，递推：由“小”到“大”递进；递归：由“大”到“小”嵌套。6，next[j]越大，相似部分越多，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。*************串插入算法，堆分配存储，BF算法，KMP算法CH5数组（LOC位址*base元素基址dim维数*

7、bound各维长度信息保存区基址*constantsCi的保存区e元素值mu行数nu列数tu非零元素总个数）1，任一元素的地址（三要素）：①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数2，行优先存储地址公式：LOC(aij)=LOC(ac1，c2)数组基址+[(i-c1)《aij之前的行数》*(d2-c2+1)总列数+j-c2本行前元素个数)]*L单个元素长度3，列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L4，顺序存储方式

8、：低或高地址优先顺序《较长，难达到映射关系》三元组存储（i,j,aij）5，带辅助向量的三元组：增加NUM（i）每行非零元素个数和POS（i）每行第一个非0元素在三元组的行号规律：POS(1)＝1，POS(i)＝POS(i-1)+NUM(i-1)6，十字链表：加