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

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

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

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

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

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

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

codeblock

dev c++

栈

顺序存储栈

#includeusing 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;}

链栈

#includeusing 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;}

队列

顺序存储循环队列

#includeusing 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;}

链队

#includeusing 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//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//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(
            
                     

                 

                                                                                                                    
                         混合云
                                             
                         超融合服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               第二阶段协商成功
                                                                                                           java第二阶段测试
                                                                                                           第二阶段协商未成功
                                                                                                           数据仓库复习
                                                         
                 
               
              
             
               

                   
 文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
                 
                   
转载请注明本文地址：https://www.ucloud.cn/yun/124056.html
               
                      
               

                 
                                  
上一篇：Redis五种数据结构及常用操作指令、Redis在JAVA中如何封装使用
  
                                                
                                       
下一篇：【数据结构】八大排序(超详解+附动图+源码)