[NEFU 数据结构]阶段二复习

阶段二只考编程题目，所以进行常见带代码整理
考串到图的遍历，由于是写代码，所以我尽量精简一些
由于个人习惯，可能C和C++代码会混合起来，所以编写的时候，请写.cpp文件，并使用C++的编译方式。

因为这个玩意写的比较早后面老师又更新了范围之类的，所以你们挑着看吧，就代码模块而言这篇文档应该足够了。
如果按老师说的加难度，那我觉得应该是算法和思维方面加难度吧。

另外STL很爽，可以学一下。但是考试尽量别用吧，下面代码为了简化可能直接使用STL，你们可以自己手打栈和队列

如何编写和编译运行C++文件

机房主要是codeblock和dev c++，所以我以这两个举例

明天去机房更新（如果我空的话）

codeblock

dev c++

栈

顺序存储栈

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=105;
typedef struct {
    int data[MAXSIZE];
    int top;
}SeqStack;

void Init(SeqStack &S){S.top=-1;}
bool Empty(SeqStack S){return S.top==-1;}
void Push(SeqStack &S,int x){S.data[++S.top]=x;}
int Pop(SeqStack &S){return S.data[S.top--];}
int Top(SeqStack S){return S.data[S.top];}

int main(){
    SeqStack S;
    Init(S);
    Push(S,1);Push(S,2);
    cout<<"栈顶："<<Top(S)<<endl;
    cout<<"栈顶出队:"<<Pop(S)<<endl;
    Pop(S);
    if(Empty(S))printf("Stack Empty\n");
    else printf("Stack not Empty\n");
    return 0;
}

链栈

#include<bits/stdc++.h>
using namespace std;

typedef struct StackNode{
    int data;
    struct StackNode *next;
}StackNode,*LinkStack;

void Init(LinkStack &top){top=NULL;}
bool Empty(LinkStack top){return top==NULL;}
int Top(LinkStack top){return top->data;}
void Push(LinkStack &top,int x){
    StackNode *s;
    s=(StackNode*)malloc(sizeof(StackNode));
    s->data=x;s->next=top;
    top=s;
}
int Pop(LinkStack &top){
    int ret=top->data;
    StackNode *p=top;
    top=top->next;free(p);
    return ret;
}

int main(){
    int x;
    LinkStack Stk;
    Init(Stk);
    Push(Stk,1);Push(Stk,2);
    cout<<"栈顶："<<Top(Stk)<<endl;
    cout<<"栈顶出队:"<<Pop(Stk)<<endl;
    Pop(Stk);
    if(Empty(Stk))printf("Stack Empty\n");
    else printf("Stack not Empty\n");
    return 0;
}

队列

顺序存储循环队列

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=105;
typedef struct{
    int data[MAXSIZE];
    int front,rear;
}SeQueue;
void Init(SeQueue &Q){Q.front=Q.rear=0;}
int Head(SeQueue Q){return Q.data[Q.front];}
bool Empty(SeQueue Q){return Q.front==Q.rear;}
void Push(SeQueue &Q,int x){
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXSIZE;
}
int Pop(SeQueue &Q){
    int ret=Q.data[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;
    return ret;
}

int main(){
    SeQueue Q;
    Init(Q);
    Push(Q,1);Push(Q,2);
    cout<<Head(Q)<<endl;
    if(Empty(Q))printf("Queue Empty!\n");
    else printf("Queue not Empty!\n");
    Pop(Q);
    cout<<Head(Q)<<endl;
    return 0;
}

链队

#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    int data;
    struct Node *next;
}LQNode,*LinkQNode;
typedef struct{
    LQNode *front,*rear;
}LQueue,*LinkQueue;

void Init(LinkQueue &Q){
    LinkQNode p;
    Q=(LinkQueue)malloc(sizeof(LQueue));//申请头尾指针节点
    p=(LinkQNode)malloc(sizeof(LQNode));//申请链队头节点
    p->next=NULL;Q->front=Q->rear=p;
}
void Push(LinkQueue &Q,int x){
    LinkQNode p=(LinkQNode)malloc(sizeof(LQNode));
    p->data=x;p->next=NULL;
    Q->rear->next=p;Q->rear=p;
}
int Pop(LinkQueue &Q){
    int ret=0;
    LinkQNode p=Q->front->next;
    Q->front->next=p->next;ret=p->data;
    if(p==Q->rear)Q->rear=Q->front;//只有一个元素的话，出队后为空
    free(p);
    return ret;
}
int Head(LinkQueue Q){return Q->front->next->data;}
bool Empty(LinkQueue Q){return(Q->front==Q->rear);}

int main(){
    LinkQueue Q;
    Init(Q);
    Push(Q,1);Push(Q,2);
    cout<<Head(Q)<<endl;
    if(Empty(Q))printf("Queue Empty!\n");
    else printf("Queue not Empty!\n");
    Pop(Q);
    cout<<Head(Q)<<endl;
    return 0;
}

字符串

貌似没啥好写的，应该不会很难，感兴趣的话可以看看C++ STL的string.
如果搞你的话应该是不让你用string.h里的库函数的

树

创建树

typedef struct BinNode{
    char data;
    //可以多维护一些信息，深度啊，度数啊之类的，可以直接建树的时候维护掉
    struct BinNode *left;
    struct BinNode *right;
}BinNode,*BinTree;

void CreateBinTree(BinTree &T){
    char ch;cin>>ch;
    if(ch=='@')T=NULL;
    else{
        T=new BinNode;
        T->data=ch;
        CreateBinTree(T->left);
        CreateBinTree(T->right);
    }
}

遍历

递归遍历

void PreOrder(BinTree T){//先序遍历
    if(T){
        printf("%c",T->data);
        PreOrder(T->left);
        PreOrder(T->right);
    }
}

void InOrder(BinTree T){//中序遍历
    if(T){
        InOrder(T->left);
        printf("%c",T->data);
        InOrder(T->right);
    }
}

void BackOrder(BinTree T){//后序遍历
    if(T){
        BackOrder(T->left);
        BackOrder(T->right);
        printf("%c",T->data);
    }
}

非递归遍历

#include<stack>//STL栈，不用手写了

void PreOrder2(BinTree T){//非递归先序遍历
    if(T){
        stack<BinTree>stk;
        stk.push(T);
        BinTree cur = T;
        while(!stk.empty()){
            cur = stk.top();stk.pop();
            cout<<cur->data;
            if(cur->right!=NULL)stk.push(cur->right);//栈后进先出
            if(cur->left!=NULL)stk.push(cur->left);
        }
    }
}
void InOrder2(BinTree T){//非递归中序遍历
    if(T){
        stack<BinTree>stk;
        BinTree cur = T;
        while(!stk.empty()||cur!=NULL){
            if(cur!=NULL){
                stk.push(cur);
                cur = cur->left;
            }else{
                cur = stk.top();stk.pop();
                cout<<cur->data;
                cur = cur->right;
            }
        }
    }
}

void BackOrder2(BinTree T){//非递归后序遍历
    if(T){
        stack<BinTree>stk1;
        stack<BinTree>stk2;
        BinTree cur = T;
        stk1.push(cur);
        while(!stk1.empty()){
            cur = stk1.top();stk1.pop();
            stk2.push(cur);
            if(cur->left!=NULL)stk1.push(cur->left);
            if(cur->right!=NULL)stk1.push(cur->right);
        }
        while(!stk2.empty()){
            cur = stk2.top();stk2.pop();
            cout<<cur->data;
        }

    }
}

层序遍历

可以顺便统计不同度的结点个数

#include<queue>//STL队列 不用手写了

int deg0,deg1,deg2;
void BFS(BinTree T){//可以顺便统计不同度数的结点个数
    if(T){
        queue<BinTree>q;
        q.push(T);
        while(!q.empty()){
            BinTree head = q.front();q.pop();//获取队首后出队
            cout<<head->data;
            if(head->left==NULL&&head->right==NULL)deg0++;
            else if(head->left!=NULL&&head->right!=NULL)deg2++;
            else deg1++;
            if(head->left)q.push(head->left);
            if(head->right)q.push(head->right);
        }
    }
}

信息统计

这些玩意其实都可以直接在建树的时候就维护起来的，下面是建树后的一些递归算法。

int CountLeaf(BinTree T){//统计叶子结点个数
    int res=0;
    if(T==NULL)return 0;
    if(T->left==NULL)return 1+CountLeaf(T->right);
    else return CountLeaf(T->left)+CountLeaf(T->right);
}
int GetDepth(BinTree T){//统计树的深度
    int LeftDepth=0,RightDepth=0;
    if(T==NULL)return 0;
    else{
        LeftDepth=GetDepth(T->left);
        RightDepth=GetDepth(T->right);
        if(LeftDepth>RightDepth)return LeftDepth+1;
        else return RightDepth+1;
    }
} 
int dep[105];//dep表层数，记录第i层有多少个结点
int GetWidth(BinTree T){//统计二叉树的最大宽度
    if(T==NULL)return 0;

    //BFS层序遍历
    queue<BinTree>q;q.push(T);
    queue<int>depth;depth.push(1);

    while(!q.empty()){
        BinTree head=q.front();q.pop();
        int now_depth=depth.front();depth.pop();
        dep[now_depth]++;
        if(head->left){
            q.push(head->left);
            depth.push(now_depth+1);
        }
        if(head->right){
            q.push(head->right);
            depth.push(now_depth+1);
        }
    }
    int ret=0;
    for(int i=1;i<=105;i++)ret=max(ret,dep[i]);
    return ret;
}

其他

bool Compare(BinTree A,BinTree B){//判断两棵树是否相等
    if(A==NULL&&B==NULL)return true;
    else if(A==NULL||B==NULL)return false;
    if(A->data!=B->data)return false;
    bool left=Compare(A->left,B->left);
    bool right=Compare(A->right,B->right);
    return left&&right;
}

void SwapSon(BinTree T){//交换每个结点的左右孩子
    if(T==NULL)return;
    if(T->left==NULL&&T->right==NULL)return;//叶子结点不用换了
    BinTree tmp=T->left;
    T->left=T->right;
    T->right=tmp;
    SwapSon(T->left);
    SwapSon(T->right);
}


BinTree Find(BinTree T,char ch){
    if(T==NULL)return NULL;
    else if(T->data==ch)return T;
    else{
        BinTree p=Find(T->left,ch);
        if(p!=NULL)return p;
        else return Find(T->right,ch);
    }
}

找祖先

创建的时候加个father指针方便回溯

#include<iostream>
#include<cstdio>

using namespace std;

typedef struct BinNode{
    char data;
    struct BinNode *left;
    struct BinNode *right;
    struct BinNode *father;
}BinNode,*BinTree;

void CreateBinTree(BinTree &T,BinTree &fa){
    char ch;cin>>ch;
    if(ch=='*')T=NULL;
    else{
        T=new BinNode;
        T->data=ch;T->father=fa;
        CreateBinTree(T->left,T);
        CreateBinTree(T->right,T);
    }
}

BinTree Find(BinTree T,char ch){
    if(T==NULL)return NULL;
    else if(T->data==ch)return T;
    else{
        BinTree p=Find(T->left,ch);
        if(p!=NULL)return p;
        else return Find(T->right,ch);
    }
}

void Ancestors(BinTree T){
    if(T->father==NULL)printf("没有祖先结点");
    else{
        while(T->father){
            cout<<T->father->data<<" ";
            T=T->father;
        }
    }
}

int main(){
    BinTree T,fa=NULL;
    CreateBinTree(T,fa);
    char ch;cin>>ch;
    BinTree A=Find(T,ch);
    if(A==NULL)printf("%c不存在",ch);
    else Ancestors(A);
    return 0;
}

图

建图

typedef struct ArcNode{
    int adjvex;
    struct ArcNode * nextarc;
}ArcNode;

typedef struct VNode{
    int data;
    ArcNode *firstarc;
}VNode,AdjList[MAXN];

typedef struct{
    AdjList verlist;
    int vexnum,arcnum;
}Graph;

void CreateUDG(Graph &G){//无向图
    cin>>G.vexnum>>G.arcnum;
    for(int i=1;i<=G.vexnum;i++){
        cin>>G.verlist[i].data;
        G.verlist[i].firstarc=NULL;
    }
    for(int i=1;i<=G.arcnum;i++){
        int x,y;cin>>x>>y;

        ArcNode * p1= new ArcNode;
        ArcNode * p2= new ArcNode;

        p1->adjvex=y;
        p1->nextarc=G.verlist[x].firstarc;
        G.verlist[x].firstarc=p1;

        p2->adjvex=x;
        p2->nextarc=G.verlist[y].firstarc;
        G.verlist[y].firstarc=p2;
    }
}

void CreateDG(Graph &G){//有向图
    cin>>G.vexnum>>G.arcnum;
    for(int i=1;i<=G.vexnum;i++){
        cin>>G.verlist[i].data;
        G.verlist[i].firstarc=NULL;
    }
    for(int i=1;i<=G.arcnum;i++){
        int x,y;cin>>x>>y;

        ArcNode * p1= new ArcNode;

        p1->adjvex=y;
        p1->nextarc=G.verlist[x].firstarc;
        G.verlist[x].firstarc=p1;
    }
}

BFS

void BFS(Graph G){//无向图，有向图是特殊的无向图，也可以直接用
    queue<int>Q;
    bool vis[MAXN];
    memset(vis,0,sizeof(vis));
    cout<<"v1 ";
    Q.push(1);
    vis[1]=true;
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        ArcNode* p=G.verlist[u].firstarc;
        while(p!=NULL){
            if(!vis[p->adjvex]){
                cout<<"v"<<p->adjvex<<" ";
                vis[p->adjvex]=true;
                Q.push(p->adjvex);
            }
            p=p->nextarc;
        }
    }
}

DFS

递归版

bool vis[MAXN];
//如果你要看是否存在某一条路径
//dfs调用的u传入起点
//然后看vis[v]就可以知道是否存在u->v的一条路径了

void DFS(Graph G,int u){
    ArcNode* p=G.verlist[u].firstarc;
    vis[u]=true;
    cout<<"v"<<u<<" ";
    while(p!=NULL){
        if(!vis[p->adjvex]){
            DFS(G,p->adjvex);
        }
        p=p->nextarc;
    }
}

非递归版

bool vis[MAXN];

void DFS(Graph G,int u){
    stack<int>stk;
    stk.push(u);vis[u]=true;
    cout<<"v1 ";
    while(!stk.empty()){
        int tt=stk.top();
        ArcNode *p=G.verlist[tt].firstarc;
        while(p&&vis[p->adjvex]){
            p=p->nextarc;
        }
        while(p&&!vis[p->adjvex]){
            cout<<"v"<<p->adjvex<<" ";
            vis[p->adjvex]=true;
            stk.push(p->adjvex);
            p=G.verlist[p->adjvex].firstarc;
        }
        if(p==NULL)stk.pop();
    }
}

输出邻接表

void Print(Graph G){
    for(int i=1;i<=G.vexnum;i++){
        ArcNode* p=G.verlist[i].firstarc;
        cout<<i<<":";
        while(p!=NULL){
            cout<<p->adjvex;
            if(p->nextarc!=NULL)cout<<" ";
            p=p->nextarc;
        }
        cout<<endl;
    }
}

统计度数

也可以直接建图的时候统计

int in[MAXN],out[MAXN];
void GetInfo(Graph G){
    for(int i=1;i<=G.vexnum;i++){
        ArcNode* p=G.verlist[i].firstarc;
        while(p!=NULL){
            in[p->adjvex]++;
            out[i]++;
            p=p->nextarc;
        }
    }
}

C++ STL相关应用

头文件与命名空间

万能头文件

#include<bits/stdc++.h>

如果万能头没法编译通过又不想设置编译参数，那么根据需求使用下面这些头文件（和C语言头文件不冲突的）

#include<cstdio>//使用c语言 printf scanf
#include<iostream>//使用c++ cin cout操作
#include<cstring>//使用c语言字符串相关函数,memcpy
#include<string> //使用C++ string
#include<stack>//使用STL的栈
#include<queue>//使用STL的队列
#include<vector>//使用vector
#include<algorithm>//使用sort等直接算法
#include<set>//使用STL set
#include<map>//使用STL map

命名空间

using namespace std;

头文件下面一行加收这句话，保证你正常使用的，不然的话写起来比较麻烦

使用STL stack

.empty()判栈空，空返回true否则false
.push(x)x入栈
.size()获取栈元素数量
.pop()栈顶元素出栈
.top()获取栈顶元素

#include<bits/stdc++.h>
using namespace std;

int main(){
	stack<int>stk_int;//创建一个存放int类型的栈

	//.empty()判栈空，如果为空返回true,否则false
    if(stk_int.empty())printf("栈空\n");
	
    //.size()得到栈的大小
    printf("栈的大小%d\n",stk_int.size());
    
    //把1入栈
    stk_int.push(1);
    stk_int.push(2);

    //获取栈顶
    //cout 输出，endl换行。不会的花用printf代替就行
    cout<<stk_int.top()<<endl;

    //栈顶出栈
    stk_int.pop();

    printf("现在栈的大小%d\n",stk_int.size());

    //获取新的栈顶
    cout<<stk_int.top()<<endl;
	return 0;
}

使用STL queue

.push(x)x入队
.empty()判队空
.pop()队首出队
.front()获取队首
.size()获取队内元素数量

#include<bits/stdc++.h>
using namespace std;

int main(){
	queue<int>queue_int;//创建一个存放int类型的

	//.empty()判队列空，如果为空返回true,否则false
    if(queue_int.empty())printf("队列空\n");
	
    //.size()得到队列的大小
    printf("队列的大小%d\n",queue_int.size());
    
    //入队
    for(int i=1;i<=10;i++){
        queue_int.push(i);
    }
    

    //获取队首
    //cout 输出，endl换行。不会的花用printf代替就行
     cout<<"队首元素为"<<queue_int.front()<<endl;

    //队首出队
    queue_int.pop();

    printf("现在队列的大小%d\n",queue_int.size());

    //获取新的队首
    cout<<"队首元素为"<<queue_int.front()<<endl;

    //手动清空队列，栈也可以这么弄
    while(!queue_int.empty()){
        printf("当前队首元素为%d\n",queue_int.front());
        printf("出队\n");
        queue_int.pop();
    }
    if(queue_int.empty())printf("队列已经被清空了");
	return 0;
}

使用STL sort

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N]={1,4,5,2,5,6,8};
int b[N]={1,4,5,2,5,6,8};
int c[N];
bool cmp1(int a,int b){return a>b;}
bool cmp2(int a,int b){return a<b;}
int main(){
    for(int i=0;i<7;i++)printf("%d ",a[i]);puts("");
    for(int i=0;i<7;i++)printf("%d ",b[i]);puts("");
    
    sort(a,a+7);
    for(int i=0;i<7;i++)printf("%d ",a[i]);puts("");

    sort(b,b+7,greater<int>());
    for(int i=0;i<7;i++)printf("%d ",b[i]);puts("");

    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    sort(c+1,c+1+n,cmp1);//根据cmp1从大到小排，注意sort前两个参数分别+1和+n因为我们要排序的数据是1～n不是0～n-1
    for(int i=1;i<=n;i++)cout<<c[i]<<" ";
    cout<<endl;
    sort(c+1,c+1+n,cmp2);//根据cmp2从小到大排
    for(int i=1;i<=n;i++)cout<<c[i]<<" ";
    cout<<endl;
    return 0;
}