小明总结 数据结构

数据结构复习一、选择题/填空题：以基本概念基本性质为主数据元素的逻辑结构、物理结构；⏹ 4. 逻辑结构⏹数据的逻辑结构是对数据元素之间的逻辑关系的一种抽象描述，它可以用一个数据元素的集合和定义在此集合上若干关系来表示。

例如线性结构、树结构和网状结构指的是数据的逻辑结构。

⏹ 5. 物理结构⏹物理结构: (或称映像)又称为存储结构，指在计算机上如何具体表示数据的各种逻辑结构，同一逻辑结构可有几种不同的物理结构表示。

通常分为两种结构⏹顺序存储结构: 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系（公式化描述）⏹链式存储结构: 借助指示元素存储地址的指针表示数据元素之间的逻辑关系（链式描述）算法的时间复杂度、空间复杂度的概念；⏹二、时间复杂度⏹狭义上讲，算法的效率指的是算法的执行时间随问题规模的增长而增长的趋势。

⏹假如随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记做T(n)=O(f(n)) … (1-1)称T(n)为算法的（渐进）时间复杂度⏹狭义上讲，算法的效率指的是算法执行的时间随问题规模的增长而增长的趋势。

⏹⏹空间复杂性(space complexity)是指运行一个程序所需要的内存大小。

⏹空间复杂性的组成：⏹指令空间(instruction space)是指用来存储经过编译之后的程序指令所需的空间。

⏹数据空间(data space)是指用来存储所有常量和所有变量值所需的空间。

数据空间由两部分组成：存储常量和简单变量、存储复合变量。

⏹环境栈空间(environment stack space)用来保存函数调用保存时恢复运行所需要信息的存储空间。

⏹如果输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时可以不加考虑；通常情况下，程序代码本身所占的空间对不同的算法也不会有数量及的差别，因此只需要分析除输入和程序以外的空间。

⏹类似于时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的度量。

⏹定义算法空间复杂度为⏹S(n) = O(g(n)) …(1-2)⏹表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。

⏹时间复杂度的简单计算（如i=1;While(i<=n) i=i*2;如fact(int n){ if (n<=1) return 1; else return(n*fact(n-1));} ）；线性表采用顺序存储结构时，任意元素a i的存储地址的计算；⏹假设线性表的每个存储单元需占用L个存储单元，并以所占的第一个单元的存储地址作为数据单元的存储地址，则下列关系成立：LOC(ai+1) = LOC(ai) + LLOC(ai) = LOC(a1) + (i-1)*L⏹其中LOC(a1) 是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基地址。

⏹由前面的公式可知：只要确定存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

栈的概念（栈顶、栈底）、性质（LIFO）；⏹栈（stack）是限定只能在一端进行插入和删除操作的线性表。

其中允许进行插入和删除的一端称为“栈顶（top）”，另一端称为“栈底（bottom）”。

数据元素个数为零的栈是“空栈”⏹栈是一种“先进后出（LIFO）”的线性表队列的概念（队头、队尾）、性质（FIFO）、循环队列的特点（队列为空、满的条件）；⏹队列与我们通常所将的排队很相似，它是限定在表的一端进行插入，而在表另一端进行删除的线性表。

其中，允许插入的一端称为队尾（rear），允许删除的一端称为队首(front)。

⏹队列是一种先进先出(First In First Out,缩写为FIFO)的线性表。

⏹当环状队列Q为空时：⏹Q.front=Q.rear⏹当环状队列Q为满时：⏹(Q.rear+1)%Q.queuesize=Q.front⏹队列为满时少用一个元素空间⏹后缀表达式计算（8 3 6 * + 2 3 5 * + 4 - /）；中缀、后缀表达式的相互转换（(8+3*6)/(2+3*5-4)）；树与二叉树的相关术语（根、兄弟、祖先、深度等）；⏹根结点（root node）一棵树中没有父结点的结点，称为根结点⏹叶（子）结点leaf node或终端结点terminal node一棵树中没有子结点的结点，称为叶（子）结点或终端结点⏹分支结点或非终端结点（nonterminal node）除了叶（子）结点以外的其他结点，称为分支结点或非终端结点⏹父结点（parent）和子结点（child）若结点x有一个以结点y为树根的子树, 则x为y的父结点（父亲），而y为x的子结点（孩子）。

⏹兄弟（sibling）同一个父结点之子结点，称为兄弟⏹层次（level）和深度（depth）层次为结点之特性值，将根结点之层次设为1，其子结点为2，依此类推。

⏹深度（depth）或高度（height）叶子结点的最大层次数称为树的高度。

如图，叶子最大层次值为3，故树T的深度为3⏹祖先（ancestor）由某结点X到根结点之路径上的所有结点，均称为X之祖先⏹树林（forest）n>=0个树的集合称为树林若将一树的根结点移去，所剩这恰是一树林二叉树的性质及扩展应用（对500个元素利用折半查找法进行查找时，其最大比较次数，n 个结点的k叉树，可能达到的最大深度n、最小深度2，等）；二叉树的遍历；图与网的基本概念；⏹图由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V,E)。

图中的顶点即为数据结构中的数据元素，弧的集合E实际上是定义在顶点集合上的一个关系。

用有序对<v,w>表示从v到w的一条弧。

弧具有方向性，以带箭头的线段表示，通常称v为弧尾或始点，称w为弧头或终点，此时的图称为有向图。

若图中从v到w有一条弧，同时从w到v也有一条弧，则以无序对(v,w)代替这两个有序对<v,w>和<w,v>,表示v和w之间的一条边。

此时的图在顶点之间不再强调方向性的特征，称为无向图。

图的遍历；最小生成树、最短路径、关键路径的概念；⏹通常，对图进行遍历可有两种搜索路径：深度优先搜索和广度优先搜索。

⏹在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

⏹在有向网图中求顶点A到顶点B的所有路径中，边的权值之和最小的一条路径，这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点，最后一个顶点为终点。

在非网图中最短路径是指两点之间经过的边数最少的路径。

⏹在AOE网络中，一条路径上各弧权值之和称为该路径的带权路径长度。

由于AOE网络中某些活动可以并行进行，则完成整个工程的最短时间即为从源点到汇点最长的带权路径长度的值，称这样的路径为关键路径，关键路径上的弧称为关键活动。

⏹各种排序方法的比较（在待排序的元素序列基本有序的前提下，效率最高的排序方法，最不提倡使用的排序方法，排序方法中平均查找长度最小的方法，等）；各种查找方法的比较（如果要求一个线性表既能快速的查找，又能适应动态变化的要求，可以采用的查找方法，等）。

二、选择填空题以单链表的插入、删除操作为主：已知L是无表头结点的单链表，且P既不是首结点，也不是尾结点，请在下列语句中选择适当的语句序列填空。

①P->next = S;②P->next = P->next->next;③P->next = S->next;④S->next = P->next;⑤S->next = L;⑥S->next = NULL;⑦Q = P;⑧While ( P->next ! = Q ) P = P->next;⑨While ( P->next ! = NULL ) P = P->next;⑩P = P->next;⑾P = L;⑿L = S;⒀L = P;a、在P结点后插入S结点b、在P结点前插入S结点c、在表首插入S结点d、在表尾插入S结点已知L是带表头结点的非空单链表，且P既不是首结点，也不是尾结点，请在下列语句中选择适当的语句序列填空。

①P = P->next;②P->next = P;③P->next = P->next->next;④P = P->next->next;⑤While ( P ! = NULL ) P = P->next;⑥While ( Q->next ! = NULL ) {P = Q; Q = Q->next;}⑦While ( P->next ! = Q ) P = P->next;⑧While ( P->next->next ! = Q ) P = P->next;⑨While ( P->next->next ! = NULL ) P = P->next;⑩Q = P;⑾Q = P->next;⑿P = L;⒀L = L->next;⒁Free(Q);e、删除P结点的直接后继f、删除P结点的直接前趋g、删除P结点h、删除首结点i、删除尾结点三、补充算法/算法设计单链表的插入、删除算法；双链表的插入、删除算法；顺序栈的插入、删除算法；利用栈进行数制转换的算法；二叉树遍历的算法；折半查找的算法。

四、简答题1、说明程序段的输出结果：void main(){ Queue Q; InitQueue(Q);char x='e', y='c';Enqueue(Q,'h');Enqueue(Q,'r');Enqueue(Q,y);Qequeue(Q,x);Enqueue(Q,x);Dequeue(Q,x);Enqueue(Q,'a');while(!QueueEmpty(Q)){ Dequeue(Q,y);printf(y);}printf(x);}2、说明程序段的输出结果：a='THIS', f='A SAMPLE', c='GOOD', d='NE', b=' ',s=Concat(a,Concat(SubSrting(f,2,7),Concat(b,Substring(a,3,2)))),t=Replace(f,SubString(f,3,6),c),u=Concat(Substring(c,3,1),d),g='IS',v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),求出：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么。