数据结构必背代码

1.二叉树的三种非递归

void PreorderWithOutRecursion(BiTree b){
   BiTNode* p;
   SqStack st;
    InitStack(st);
    p = b;
    while(!StackEmpty(st)||p!=NULL){
        while(p!=NULL){
            printf("%c",p->data);//先序打印
            Push(st,p);//打印之后进栈
            p = p->lchild;//左边孩子进栈进完
        }
        if(!StackEmpty(st)){
            Pop(st,p);//节点出栈
            p = p->rchild;//有右孩子就转向右孩子，等待下一步右孩子进栈然后再进右孩子的左孩子，没有p就是NULL，上面的循环会直接跳过，再次出栈，直到有右孩子再转向右孩子。
        }
    }
    printf("\n");

}
//PPT7.7:中序遍历非递归
void InOrderWithoutRecursion(BiTree b){
    BiTNode * p;
    SqStack st;
    InitStack(st);
    p = b;
    while(!StackEmpty(st)||p!=NULL){
        while(p!=NULL) {
            Push(st, p);//只管左边孩子全部进栈。
            p = p->lchild;
        }
        if(!StackEmpty(st)){
            Pop(st,p);//出栈一次
            printf("%c",p->data);//延后打印
            p = p->rchild;//搜索右孩子，如果没有右孩子p会为NULL，不会进入上一个循环，从而再次出栈，再次打印。直到有右孩子才转向右孩子。
        }

    }
    printf("\n");
}
////PPT7.7 后序遍历非递归
//在该节点的右孩子被处理之后，该节点则立即可以被访问。使用一个r指针来指向刚刚访问过的节点

void PostOrder1(BiTNode *b){    //后序非递归遍历算法
    BiTNode *p = b;
    BiTNode *r;
    bool flag;
    SqStack st;
    InitStack(st);
    do{
        while(p!=NULL){
            Push(st,p);
            p = p->rchild;
        }
        r = NULL;
        flag = true;
        while(!StackEmpty(st)&& flag){
            GetTop(st,p);//不着急访问，看这个节点的值。
            if(p->rchild == r){//没有右孩子||p的右孩子已经访问过
                printf("%c",p->data);//访问打印节点
                Pop(st,p);//节点出栈。
                r = p;//r指向刚刚访问过的节点。
            }else{
                p = p->rchild;//有右孩子就去处理右孩子。
                flag = false;//表示当前处理是右孩子，右孩子还没有被处理，所以不能从这里开始继续打印。（不是栈顶节点）
            }
        }
    } while (!StackEmpty(st));
    printf("\n");
}

2.图的深度优先，广度优先遍历

typedef struct Vertex{
    int edge;
}Vertex;
typedef struct ANode
{     int adjvex;            //该边的终点编号
    struct ANode *nextarc;    //指向下一条边的指针
    InfoType info;        //该边的权值等信息
}  ArcNode;

typedef struct Vnode
{    Vertex data;            //顶点信息
    ArcNode *firstarc;        //指向第一条边
}  VNode;

typedef struct
{     VNode adjlist[MAXV] ;    //邻接表
    int n,e;            //图中顶点数n和边数e
} AdjGraph;

void DFS(AdjGraph *G，int v)  
{      ArcNode *p; int w;        //顶点*p，定义一个w用来存序号。
       visited[v]=1;         //置已访问标记
       printf("%d  "，v);         //输出被访问顶点的编号
       p=G->adjlist[v].firstarc;         //p指向顶点v的第一条边的边头结点
       while (p!=NULL) 
       {      w=p->adjvex;        //w存了p的边的序号。每一步走到nextarc其实就已经跳换到列指定位置上面去了。
    if (visited[w]==0) 
           DFS(G，w);       //若w顶点未访问，递归访问它
    p=p->nextarc; 　    //p指向顶点v的下一条边的边头结点，就是切换到下一列上面去了。
      }
}

 void BFS(AdjGraph *G，int v)
{        int w， i;
         ArcNode *p;
         SqQueue *qu;        //定义环形队列指针
         InitQueue(qu);        //初始化队列
         int visited[MAXV];                //定义顶点访问标记数组
         for (i=0;i<G->n;i++) 
      visited[i]=0;          //访问标记数组初始化
         printf("%2d"，v);         //输出被访问顶点的编号
         visited[v]=1;                  //置已访问标记
         enQueue(qu，v);
    while (!QueueEmpty(qu))           //队不空循环
       {    deQueue(qu，w);            //出队一个顶点w
    p=G->adjlist[w].firstarc;     //指向w的第一个邻接点
    while (p!=NULL)        //查找w的所有邻接点
    {     if (visited[p->adjvex]==0)     //若当前邻接点未被访问
           {    printf("%2d"，p->adjvex);  //访问该邻接点
        visited[p->adjvex]=1;    //置已访问标记
        enQueue(qu，p->adjvex);    //该顶点进队
                      }
                      p=p->nextarc;                  //找下一个邻接点
    }
       }
       printf("\n");
}
    

3.二分搜索

typedef struct List{
    int data[maxsize];
    int  n1;
}List;
int binarySearch(List L,int k){
    int low =0,high = L.n1-1;
    while(low<high){
        int mid = (low+high)>>1;
        if(L.data[mid] == k) return mid+1;
        else if(L.data[mid]>k) high = mid-1;
        else low = mid+1;
    }
    return -1;
}