Review of the base algorithm, nndl and advanced network for doc examination.

Mar 2, 2023 00:00 · 332 words · 2 minute read exam algorithm

内存数据组织

数组(连续存储方式下的一维、二维、三维数组地址计算)

一般来说，内存中数据的组织格式包括按行存取以及按列存取，其地址起始位置包含0或者1，此类题目需要具体问题具体分析。

顺序表(查找算法、插入算法和删除算法;性能评估)

顺序表查找较为简单，一般为从第一个遍历到最后一个即可完成，插入算法以及删除算法同理，对于python等语言，对于顺序表的实现不对用户所展示，而对于类似C这种高级语言，程序员需要对其进行定义。

顺序表的特点： ①、随机访问，既可以在O(1)时间内找到第i个元素。 ②、存储密度高，每个节点只存储数据元素。 ③、扩展容量不方便（即便采用动态分配的方式实现，扩展长度的时间复杂度也比较高）。 ④、插入、删除操作不方便，需要移动大量元素。

静态存储实现方式：

#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int length;
}SqList;

如果不进行初始化，将会出现默认数据【即脏数据】

动态分配存储实现方式：

#define MaxSize 10
typedef struct{
  ElemType *data;
  int MaxSize;
  int length;
}SqList;

// For C++
L.data = new ElemType[MaxSize]
  
// For C
L.data = (ElemType *)malloc(sizeof(ElemType)*MaxSize)

当顺序表存满时可以采用malloc或者new继续申请内存，同时增加MaxSize数量。

对于插入算法，当遍历到该点时将后续点进行后移操作，删除需要将后面的进行前移。

查找的时间复杂度平均为 $O(n)$ 。

栈（顺序栈、多栈共享一段连续存储空间）

顺序栈，意为顺序表实现的栈结构，即只需要从0地址开始存取。

#include <stdio.h>
//元素elem进栈
int push(int* a, int top, int elem) {
    a[++top] = elem;
    return top;
}

//数据元素出栈
int pop(int* a, int top) {
    if (top == -1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n", a[top]);
    top--;
    return top;
}

但是需要判断插入与删除时是否越界。

多栈共享一段连续存储空间，需要保存每一个栈顶以及栈底，防止数组越界。

栈（链式栈;进栈算法、出栈算法、取栈顶算法和栈空栈满判定)

对于链式栈，在存储时加入指针指向下一个元素，对于该种算法，只需要保留栈顶元素，即可寻到整个链式栈。对于进栈算法，只需要在保留元素的基础上将地址保存在当前元素的指针种，理论上，该栈可以动态分配内存。

struct SNode
{
    int element;
    SNode * next;
}

class Stack
{
	  SNode headNode;
    int size;
}

bool push(int e)
{
  SNode* new_node = new SNode(e,0);

  new_node->next = headNode.next; 
  headNode.next = new_node;

  size++;

  return true;       
}


bool pop()
{
  SNode* del_node = headNode.next;   //取出待删结点（也就是链表的首结点）

  if(del_node == 0) return false;    //栈为空

  headNode.next = del_node->next;
  delete del_node;
  size--;

  return true;
}

队列(循环队列进队算法、出队算法、取队头算法和队空队满判定)

队列是插入位置和删除位置受限制的线性表，它只能在一端进行插入元素，另一端进行元素删除操作，其只允许插入的一端称为队尾，只允许删除的一端称为队首。

由于队列中的元素在插入与删除时，两端的都要变化，所以需要两个指针，一个是front指向队首元素，另一个是rear指向队尾的下一个地址。有的课本上是front指针指向前一个地址，rear指向队尾元素,这都是为了算法的方便而设定的。

队列的两个特点：先进先出和有序性。

队列有两种存储表示：可用链表和顺序表来存储队列。

队列按存储结构分为两种：顺序队列（循环队列）和链式队列。

int InsertQueue(sqQueue &qu,int x)
{
  if((qu.rear+1)%maxSize==qu.front)
  	return 0;
  qu.rear=(qu.rear+1)%maxSieze;
  qu.data[qu.rear]=x;
  return 1;
}

int deleteQueue(sqQueue &qu,int &x)
{
  if(qu.front==qu.rear)
  	return 0;
  x=qu.data[qu.front]; //先保存队头元素
  qu.front=(qu.front+1)%maxSize;
  return 1;
}

递归(递归算法设计与实现;渐进时间复杂性评估)

法则1—FOR循环：
一次for循环的运行时间至多是该for循环内语句(包括测试)的运行时间乘以迭代的次数。
法则2—嵌套的FOR循环：
从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。

作为一个例子，下列程序片段为O(N3):

for(i=0; i<N; i++)
   for(j=0; j<N; j++)
     k++;

法则3—顺序语句：
将各个语句的运行时间求和即可(这意味着，其中的最大值就是所得的运行时间)。

作为一个例子，下面的程序片段先用去O(N) ，再花费O(N2) ，总的开销也是O(N2) 。

for( i=0; i<N; i++ )
   A[ i ] = 0;
for(i=0; i<N; i++)
   for(j=0; j<n; j++)
      A[ i ] += A[j] + i + j;

法则4—IF/ELSE语句：
一个if/else语句的运行时间从不超过判断再加上S1和S2中运行时间长着的总的运行时间。

if( Condition)
   S1
else
   S2

法则5—递归：
一般转换求解递推公式的范围。

其他法则是显然的，但是，分析的基本策略是从内部(或最深层部分)向外展开的。如果只有函数调用，那么这些调用首先要分析。如果有递归过程，那么存在几种选择。若递归实际上只是被薄棉纱遮住的for循环，则分析通常是很简单的。例如，下面的函数实际上就是一个简单的for循环，从而其他运行时间为O(N) 。

long int
Factorial( int N )
{
   if(N == 1)
     return 1;
   else
     return N * Factorial(N-1);
}

这个例子中对递归的使用实际上并不好。当递归被正常使用时，将其转换成一个简单的循环结构是相当困难的。在这种情况下，分析将涉及求求解一个递推关系。为了观察到这种可能发生的情形，考虑下列例子，实际上它对递归使用的效率低得令人惊讶。

long int
Fib( int N )
{
   if( N <= 1 )
      return 1;
   else
      return Fib(N-1) + Fib(N-2);
}

初看起来这个程序似乎对递归使用非常聪明。可是，如果将程序编码并且赋予N大约30的值并运行，那么这个程序让人感到效率低得吓人。分析十分简单，令T(N) 为函数Fib(N) 的运行时间。如果N=0 或N=1 ，则运行时间是某个常数值，即第4行上做做判断以及返回所用时间。因为常数不重要，所以我们可以说T(0)=T(1)=1 。对于N的其他值的运行时间则相对基准情形的运行时间来度量。若N>2 ，则就执行该函数的时间是第4行上的常数工作加上第7行上的工作。第7行由于一次加法和两次函数调用是Fib(N−1) ，从而按照T的定义，它需要T(N−1) 个时间单元。类似的论证指出，第二次函数调用需要T(N−2) 个时间单元。此时总的时间需求为T(N−1)+T(N−2)+2 ，其中“2”指的是第4行上的工作加上第7行上的加法。于是对于N⩾2

有下列关于Fib(N) 的运行时间公式：

T(N)=T(N−1)+T(N−2)+2

由于Fib(N)=Fib(N−1)+Fib(N−2) ，因此由归纳算法容易证明T(N)⩾Fib(N) 。利用已知结论，对于斐波那契数列有结论，对于N⩾4 有Fib(N)⩾(3/2)N ，可见，这个程序的运行时间以指数的速度增长。

非递归(递归算法到非递归算法的变换;渐进时间复杂性评估)

树(二叉树性质、二叉树遍历算法、二叉树计数求解;堆、调整算法、插入算法和删除算法)、

图( 图邻接矩阵、邻接表存储; 图深度优先搜索遍历算法、广度优先搜索遍历算法; 最小生成树构建、基于克鲁斯卡尔算法的构建实现、基于普利姆算法的构建实现; 迪克斯特拉单源非负最短路径求解算法; 拓扑排序算法; 关键路径求解)、

搜索结构( 无序表和有序表顺序搜索算法; 折半搜索递归和非递归算法; 搜索性能评估; 二叉搜索树构建算法、插入算法和删除算法; AVL 树四种平衡化旋转方式、AVL 树构建)、

内排序( 直接插入排序算法; 冒泡排序算法; 直接选择排序算法; 快速排序算法; 归并排序算法; 基数排序算法; 各类内排序方法性能比较与分析)等结构的有关性质及相关算法