408数据结构备考代码整理和算法思想归纳

一 线性表

（1）顺序表

1 顺序表的定义

typedef struct{
   
    int length;//记录当前长度
    int array[MAX];//表示最大长度为MAX
}

2插入操作：先判断插入的位序合不合法以及存储空间有没有满。而后插入的位序的后面的所有数相后
移动一位，而后插入，length++；
3删除操作：把删除的对应位序之后的所有元素向前移动一位，length--；
4把顺序表逆置的算法：设置双指针i和j，一个指向头部一个指向尾部，每次都把i和j所对应的元素进行对换，而后i++，j--直到i>=j为止
5 删除线性表当中所有值为x的元素的方法：
①扫描线性表以后得到所有“值为x”的元素的位序
②另外开辟一个数组，把“不是①的位序”的元素复制到辅助数组上面去。
6把一个数组中存放的两个线性表（a1，a2，a3…am,b1,b2…bn）进行互换变成（b1,b2…bn,a1，a2，a3…am）的方法：先把整个线性表逆置，而后分别对两个子表进行逆值

（2）链表

1 一些常见的代码

1定义某个单链表节点
typedef struct Node{
   
   int value;
   struct Node*next;//指向下一个节点
}Lnode，*Linklist;

2申请一个Node空间:L=(Linklist)malloc(sizeof(Lnode));（注意前面的（Linklist）
 malloc函数的意思就是申请一个大小为参数所指的大小的内存区域并将地址返回，而且返回地址要强制转换
3为链表内某个节点赋值：L——>value=1;访问结构体内的某个元素也是这样
4删除某个节点并回收空间:free(q)

2头插法（不断在头结点进行后插）构建的单链表顺序是反的；
尾插法（不断在为尾结点进行后插）构建的单链表顺序值正的
3递归算法的步骤演示:设置递归算法不断删除单链表L中所有值为x的节点：

  void delete (Linklist &L,ElemType x)   &是引用的意思，表示可以被修改
  {
   
          Lnode *p;
          if(L==NULL) return;//递归出口是当前L已经是NULL，任何递归都要有出口
          else if(L——>data==x）
          {
   
              p=L;
              L=L——>next;
              free(p);//让L指向下一个节点并删除当前节点
              delete(L,x);
          }
          else delete(L——>next,x);
  }

4链表的逆置：
（1）再次利用头插法构建单链表
（2）设置3个指针pre，p，q（pre指向p的前一个节点，q指向p的后一个节点），而后依次进行如下操作

             pre=q;  q=r;  r=r——>next; (所有指针往后移动一格）
             q——>next=pre;//修改链条
             //这个操作的前提是pre和pre前面的的操作已经调整完毕

5让单链表有序的方法：头插法+直接插入排序的思想
6合并两个有序单链表的方法：设Linklist1指向链表A，Linklist2指向链表B
①对比Linklist1和Linklist2的元素哪一个符合，把它选出来
②选的是Linklist1的话就把Linklist1向前移动一个元素
7判断两个链表的公共节点：
①统计出两个链表的长度差k，把长度较长的那个线性表向前移动k个位置
②两个链表同时移动，如果二个链表的“尾结点”都不同，说明根本就么有公共节点；
如果有的话，顺便查一下“第一个相同的节点”，这是公共节点的第一个节点
8 判断单链表有环的方法：快慢指针法+龟兔赛跑判环法

二 树

1 二叉树的二叉链表存储结构

typedef struct Treenode {
   
    Elemtype x;
    struct Treenode*left,right;
}Binode,*Bitree;

2 二叉树的三种遍历
以先序遍历为例子

递归形式:
void Preorder(Bitree T){
   
    if(T!=NULL)
    {
   
       visit(T);
       Preorder(T——>left);
       Preorder(T——>right);
    }
}
非递归形式:
(1)从根节点开始，一路向着“左”走，不断把节点入栈，直到找到最左的节点 
(2)找到“最左的节点”之后对栈顶元素进行出栈，而后访问“出栈后的栈顶元素”的右子树，
   对右子树也来一遍这样的操作,如果没有右子树的话就直接跳过
(3)先序遍历：入栈的同时访问元素
   中序遍历：栈顶元素出栈的时候访问
   后序遍历：
  

3层次遍历：借助队列实现

借助C++容器queue
void Levelorder(Bitree root)
{
   
   queue <Treenode> Q;
   Q.push<root>
   while(Q.length!=0)//只要队列内部还有元素就不能停止
   {
   
      Treenode node=Q.front();//访问第一个队头元素，pop只会出队并不会返回
      Q.pop();//出队
      if(node——>left!=NULL) Q.push(node——>left);
      if(node——>right!=NULL) Q.push(node——>right);//如果左右节点不为空，就让左右节点入队列
   }
}

4 求二叉树高度的办法：
①递归的方法：具体的递归函数是int high=max（left，right）+1
②非递归的方法：level记录层数，采用层次遍历的算法，并且在根节点入队列的时候要初始化两个值：一个是当前层次的“最右节点”now，一个是“下一层的最右节点”next“，
PS:next=now——>left；或者next=now——>right
并且不断更新，并且每次层序便利出队的时候都和“now比较一下，如果相等的话level++

5 判断一个二叉树是否为完全二叉树：层次遍历+入队列的时候把空节点一块入队列+判断队头元素是否为空节点，不是的话照常，是的话判断空节点后面还有没有非空节点，如果空节点后面还有非空节点的话说明该树不是完全二叉树

6把二叉树左右节点交换的算法：递归算法，具体步骤如下所示：
（1）先对根节点的左子树进行左右节点交换
（2）而后对根节点的右子树进行左右节点交换
（3）最后交换左右子树
代码如下所示：

void swap(Treenode* T)
{
   
      if(T!=NULL)
      {
   
         swap(T——>left);
         swap(T——>right);
         Treenode *link=T——>left;
         T——>left=T——>right;
         T——>right=link;
      }
      
}

7删除以p为根节点的二叉树：使用递归算法，先删除左右子树，而后删除节点p

void delete(Treenode* T)
{
   
      if(T!=NULL)
      {
   
         delete(T——>left);
         delete(T——>right);
         free(T);
      }
      
}

8 使用非递归后序遍历的时候，当要访问x元素的时候，栈里面所有的元素都是x的祖先
9 层次遍历可以确定某个节点的高度：根节点是0，根节点的子节点是1…高度为x的子节点高度位x+1。具体处理方法是：访问队头元素Q的时候把它的在孩子节点的值存起来（存到自己定义的某个结构体或者哈希表上去，后面要用就自己取出来就行）

三 图

（1）判断是否为树：如果一次DFS可以把所有的点和边都遍历那就是树
（2）广度优先遍历：层次遍历+用一个数组标记该节点是否已经被访问
（3）DFS：递归法和非递归法（借助栈来实现）

（4）迪杰斯特拉算法
??迪杰斯特拉算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。Dijkstra算法可以理解为是一种贪心算法。
??算法流程如下：
???????????? ( 1 ) 算法术语： P n , S n , W n , d i s t [ N ] ???????????????????????? P n : 已标记的点集合 ???????????????????????? S n : 未标记的点集合 ???????????????????????? W n : 已标记的边集 ???????????????????????? d i s t [ i ] ： P n 与 W n 组成图中源点 a m 到 a i 最短路的距离 , i ≠ 1 ???????????? (