数据结构与算法第一章绪论1数据结构的分类：⑴线性结构。其中每个结点最多只有一个前驱和后继的结构。线性表（单链表、循环链表、双向链表）、栈、队列等都是线性表的结构。“一对一”⑵树形结构。其中每个结点最多只有一个前驱，但可以有多个后继的结构。二叉树、树、森林都是树形结构。“一对多”⑶复杂结构。其中结点的前驱和后继点个数都不做限制的结构。有向图、无向图都是复杂结构。“多对多”2存储的各种表示：顺序表示、连接表示、散列旗袍、索引表示3文件的处理，在文件上的操作的种类：⑴检索⑵插入⑶删除⑷修改⑸排序4算法的性质：有穷性、确定性、可行性练习题：1计算下列程序片段的时间代价inti=1;while(i<=n){printf(“i=%d\n”.i);i=i+1;}2计算下列程序片段的时间代价inti=1;while(i<=n){intj=1;while(j<=n){intk=1;while(k<=n){printf(“i=%d,j=%d,k=%d\n”,i,j,k);k=k+1;}j=j+1;}i=i+1;}第二章线性表1顺序表：⑴插入for(q=palist->n-1;q>=p;q--)palist->element[q+1]=palist->element[q]⑵删除for(q=p;q
n-1;n-1;q++)Palist->element[q]=palist->element[q+1];2单链表：⑴插入intinsertPost_link(LinkListllist,PNodep,DataTypex)⑵删除intdeleteV_link(LinkListllist,DataTypex)3循环双链表⑴插入p->llink->rlimk=p->rlink;p->rlink->->llink=p->llink;⑵删除q=(PDoubleNode)malloc(sizeof(structDoubleNode));4采用顺序存储方式表示矩阵一般有行优先顺序和列优先顺序。按行优先顺序存储，其地址计算公式为：loc(aij)=loc(a00)+i×n+j按列优先顺序存储，其地址计算公式为：loc(aij)=loc(a00)+i×m+j5深度：一个广义表的深度，就是指广义表中所含括号的层数。练习题：1某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为100+4×11=1442线性表的链式存储结构主要有、、三种形式。3线性表的顺序存储时通过来反映元素之间的逻辑关系，而链式存储结构是通过反映元素之间的逻辑关系。4在一个链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行As->link=p;p->link=sBs->link=p->link;p->link=sCs->link=p->link;p=sDp->link=s;s->link=p第三章字符串一个串中包括的字符的个数称为这个串的长度。长度为零的串称为空串。第四章栈与队列1栈⑴栈是一种特殊的线性表，它所有的插入和删除操作都限制在表的同一端进行。表中允许进行插入、删除操作的一端叫做栈顶，另一端则叫做栈底。⑵栈的插入操作通常称为进栈或入栈(push)，栈的删除操作通常称为退栈或出栈（pull）。⑶顺序栈进栈的代码：voidpush_seq(PSeqStackpastack,DataTypex)出栈的代码：voidpop_seq(PSeqStackpastack)⑷链式栈进栈的代码：voidpush_link(PLinkStackplstack,DataTypex)出栈的代码：voidpop_link(PLinkStackplstack)⑸栈空的条件plstack!=NULLPlstack->top=NULL栈满的条件5队列队列也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的一端称为对头，允许进行插入的一端叫做队尾。队列的插入操作通常称为入队，队列的删除操作通常称为出队。⑴顺序队列顺序队列的入队voidenQueue_seq(PSeqQueuepaqu,DataTypex)顺序队列的出队voidenQueue_seq(PSeqQueuepaqu)⑵环形队列判满条件(paqu-r+1)%MAXNUM=pauqu⑶链式队列链式队列的入队voidenQueue_link(PSeqQueueplqu,DataTypex)链式队列的出队voidenQueue_link(PSeqQueueplqu)练习题：若按从左到右的顺序依次读入已知序列{a,b,c,d,e,f,g}中的元素，然后结合栈的操作，能得到下列序列中的哪些序列（每个元素进栈一次，哪些序列可能为出栈的次序）？A{d,e,c,f,b,g,a}B{f,e,g,d,a,c,b}C{e,f,d,g,b,c,a}D{c,d,b,e,f,a,g}第五章二叉树与树1结点的层数：规定根的层数为0，其余结点的层数等于其父结点的层数加12结点的度数：结点的非空子树（即后缀）个数叫做结点的度数3一般二叉树的性质：性质一：在非空二叉树的i层上，至多有2i个结点（i≥0）性质二：高度为k的二叉树中最多有2k+1-1个结点（k≥0）性质五：对于具有n个结点的...
