首页 > 其他分享 >【NEFU】数据结构阶段二机试代码

【NEFU】数据结构阶段二机试代码

时间:2023-06-07 14:05:11浏览次数:33  
标签:include return int s1 二机试 ret NEFU 数据结构 root


个人拙见,难免有不足之处,望大佬们斧正

P1

#define MAXNODE  64
#include <stdio.h>
#include <stdlib.h>
typedef struct Node     //边的信息
{
    int adjvex;
    struct Node *next;
}ArcNode;
typedef struct VNode    //顶点的信息
{
    int data;
    ArcNode *firstarc;
}VexNode;
typedef struct         //图的结构定义   
{
    VexNode ver[MAXNODE];   //下标0不用
    int vexnum,arcnum;
}Graph;
int visited[MAXNODE]={0};    
//start
void CreatAdjList( Graph &G)
 {
    scanf("%d%d", &G.vexnum, &G.arcnum);
    for(int i=1;i<=G.vexnum;i++){
        //cin>>G.verlist[i].data;
        scanf("%d", &G.ver[i].data);
        G.ver[i].firstarc=NULL;
    }
    for(int i=1;i<=G.arcnum;i++){
        int x,y;
        //cin>>x>>y;
        scanf("%d%d", &x, &y);
        ArcNode * p1= new ArcNode;
        ArcNode * p2= new ArcNode;

        p1->adjvex=y;
        p1->next=G.ver[x].firstarc;
        G.ver[x].firstarc=p1;

        p2->adjvex=x;
        p2->next=G.ver[y].firstarc;
        G.ver[y].firstarc=p2;
    }
}
void DFS(Graph G, int v)
{
    //memset(visited, 0, sizeof(visited));
    Node *p=G.ver[v].firstarc;
    visited[v]=1;
    printf("%d ", v);
    while(p!=NULL)
    {
        if(!visited[p->adjvex])    DFS(G, p->adjvex);
        p=p->next;
    }
}
//end
int main()
{
    Graph G;
    CreatAdjList(G);//创建图
    DFS(G,1); //从第一个顶点进行深度遍历
    return 0;
}

P2

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>

using namespace std;

const int MAX_SUM=110;

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

void CreateBTree(BinTree &T)
{
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else
    {

        T=new BinNode;
        T->data=ch;
        CreateBTree(T->left);
        CreateBTree(T->right);
    }
}

/*int levelOrder(BinTree root)
 {
     int ret=0;
     if (!root) {
            return ret; }
     queue <BinTree> q;
     q.push(root);
     while (!q.empty())
        {
            int currentLevelSize = q.size();
            //ret.push_back(vector <int> ());
            //ret++;
            for (int i = 1; i <= currentLevelSize; ++i)
                {
                    BinTree node = q.front();
                    q.pop();
                    ret++;
                    if (node->left)
                        q.push(node->left);
                    if (node->right)
                        q.push(node->right);
                }
            }
    return ret;
}*/

 vector<vector<int> > levelOrder(BinTree root)
 {
     vector <vector <int> > ret;
     if (!root) {
            return ret; }
     queue <BinTree> q;
     q.push(root);
     while (!q.empty())
        {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i)
                {
                    BinTree node = q.front();
                q.pop();
                ret.back().push_back(node->data);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
                }
            }
    return ret;
}

/*int maxDepthRecursion(BinTree root)
{
    int HL, HR, MaxH;
    if (root)
        {
            HL = maxDepth(root->left);
            HR = maxDepth(root->right);
            MaxH = (HL > HR) ? HL : HR;
            return MaxH + 1;
        }
        else return 0;
}*/

int getDepth(BinTree T)
{
    int LD=0,RD=0;
    if(T==NULL) return 0;
    else
    {
        LD=getDepth(T->left);
        RD=getDepth(T->right);
        if(LD>RD)   return LD+1;
        else
            return RD+1;
    }
}

int main()
{
    BinTree T;
    CreateBTree(T);
    //cout<<getDepth(T)<<endl;
    //cout<<levelOrder(T)<<endl;
    vector<vector<int> > ret=levelOrder(T);
    cout<<ret.size()<<endl;
    return 0;
}

P3

第一版

写完被老师警告不能这么玩…

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
    string s1,s2;
    cin>>s1;
    s2=s1;
    reverse(s1.begin(), s1.end());

    if(s1==s2)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}

第二版

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
    char s1[100];
    int ans=1;
    cin>>s1;
    for(int i=0,j=strlen(s1)-1;i!=j;i++,j--)
    {
        if(s1[i]!=s1[j])
        {
            ans=0;
            break;
        }
    }
    if(ans) cout<<"YES"<<endl;
    else    cout<<"NO"<<endl;
    return 0;
}

P4

#include <iostream>
#include<cstdio>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0

typedef char TElemtype;
typedef char Status;

typedef struct BiTNode {
    TElemtype data;
    struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;

int ok=1;

void CreatTree(BiTree &T) {
    char ch;
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else {
        T=new BiTNode;
    T->data=ch;
    CreatTree(T->lchild);
    CreatTree(T->rchild);
    }
}

void judge(BiTree &T)
{
    if(T==NULL) return;
    else {
        if(ok==1) {
            if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild!=NULL))
            {
                printf("NO\n");
                ok=0;
                return;
            }
            else {
                judge(T->lchild);
                judge(T->rchild);
            }
        }
        else return;
    }
}
int main()
{
    BiTree T;
    CreatTree(T);
    judge(T);
    if(ok==1)
        printf("YES\n");
    return 0;
}

P5

#include <iostream>
using namespace std;
#define MVNum 100              	//最大顶点数
//- - - - -图的邻接矩阵存储表示- - - - -
typedef struct{
	int vexs[MVNum];            //顶点表   0不用
	int arcs[MVNum][MVNum];   	//邻接矩阵
	int vexnum,arcnum;        //图的当前点数和边数
}Graph;
//start
int in[MVNum], out[MVNum];
void CreateUDN(Graph &G)
{
    int i,j,k,w,c;
    cin >> G.vexnum >> G.arcnum;//n->vex   e->arc
    //读取各顶点
    for(i=0; i < G.vexnum; i++)
    {
        cin >> G.vexs[i];
    }
    //初始化各条边
    for(i=0; i < G.vexnum; i++)
    {
        for(j=0; j < G.vexnum; j++)
        {
            if(i==j)
            {
                G.arcs[i][j]=0;
            }
            else
            {
                G.arcs[i][j]=0x3f3f;
            }
        }
    }
    //读取各条边
    for(k=0; k < G.arcnum; k++)
    {
        cin>>i>>j;
        G.arcs[i][j]=1;
        /*if(c==0)
        {
            G.edges[j][i]=w;
        }*/
    }
}
 void td(Graph G)
 {
    for(int i=0;i<=G.vexnum;i++)
    {
        for(int j=0;j<=G.vexnum;j++)
        {
            if(G.arcs[i][j]==1)
            {
                in[j]++;
                out[i]++;
            }
        }
    }
    for(int i=0;i<G.vexnum;i++)
    {
        //cout<<g.vexs[i]<<" ";
        //printf("%d:%d %d", g.vexs[i], in[g.vexs[i]], out[g.vexs[i]])
        cout<<G.vexs[i]<<":"<<in[G.vexs[i]]<<" "<<out[G.vexs[i]]<<endl;
    }
 }

 void print(Graph g)
{
    int i;
    for(i=0;i<g.vexnum;i++)
    {
        //cout<<g.vexs[i]<<" ";
        //printf("%d:%d %d", g.vexs[i], in[g.vexs[i]], out[g.vexs[i]])
        cout<<g.vexs[i]<<":"<<in[g.vexs[i]]<<" "<<out[g.vexs[i]]<<endl;
    }
}
//end
int main()
{
	Graph G;
	CreateUDN(G);
	td(G);
	//print(G);
	return 0;
}


标签:include,return,int,s1,二机试,ret,NEFU,数据结构,root
From: https://blog.51cto.com/u_15567308/6431263

相关文章

  • 【数据结构】图的基本操作
    #include<iostream>#include<cstdio>#include<stack>#include<queue>#include<cstring>constintMAX_SUM=110;usingnamespacestd;typedefstructArcNode{intadj;structArcNode*nextarc;}ArcNode;typedefstruct......
  • NEFU高级程序设计-期末复习习题组
    1.用链表实现单词序列倒序输出题目用链表实现单词序列倒序输出。与以往不同,请考虑采用一种完全的动态分配方式!为降低难度,“仁慈”的我已经给出了输出和释放的代码,你只要写出创建链表的creat函数定义就可以了。比如输入为:abcbcdcde则输出为:cdebcdabc见题干!你只能在代码输入......
  • 初级数据结构--栈在表达式求值的应用
    表达式一般有三部分组成:操作数、运算符、界限符我们常见的表达式一般都属于中缀表达式,比如:2*2/(1+1)-4/2+1后缀表达式中缀表达式便于人的理解,但不便于计算机的处理。于是便有了后缀表达式,也成逆波兰表达式。比如上面表达式手动转为后缀表达式为22*11+/42/-1+(提一下不常......
  • 每日记录(数据结构 第 三 章 栈与队列 二 )
    队列队列是一种先进先出(FIFO)(FIFO)(FIFO)的线性表.在表一端插入,在另一端删除。0.队列的基本概念定义只能在表的一端(队尾)进行插入,在另一端(队头)进行删除运算的线性表逻辑结构与线性表相同,仍为一对一关系存储结构用顺序队列或链队存储均可运算规则先进先出(FIFO)实现方式......
  • 每日记录(数据结构 第 三 章 栈与队列 )
     一、栈栈(stack)(lastinfirstout)(stack)(last\infirst\out)(stack)(lastinfirstout)后进先出 栈的基本概念定义只能在表的一端(栈顶)进行插入和删除运算的线性表逻辑结构与线性表相同,仍为一对一关系存储结构用顺序栈或链栈存储均可,但以顺序栈更......
  • 数据结构与算法分析(Java语言描述)(14)—— 索引堆
    packagecom.dataStructure.heap;importjava.util.Arrays;publicclassIndexMaxHeap{//最大索引堆中的数据privateInteger[]data;//最大索引堆中的索引privateint[]indexes;privateintcount;privateintcapacity;//构造函数,......
  • 数据结构与算法分析(Java语言描述)(13)—— 原地堆排序
    packagecom.algorithm.sort;publicclassHeapSortInPlace{privateHeapSortInPlace(){}publicstaticvoidsort(Integer[]arr){intn=arr.length;//注意:我们堆的索引是从0开始的//从(最后一个元素的索引-1)/2开始......
  • 数据结构与算法分析(Java语言描述)(27)—— 深度优先遍历与连通分量
    packagecom.dataStructure.graph;//求无权图的联通分量publicclassComponents{privateGraphgraph;//存放输入的数组privateboolean[]visited;//存放节点被访问状态privateintcomponentCount;//连通分量的数量privateint[]mark;//......
  • 数据结构与算法分析(Java语言描述)(10)—— (三向切分)快速排序
    QuickSortThreeWays.javapackagecom.algorithm.sort;publicclassQuickSortThreeWays{privateQuickSortThreeWays(){}publicstaticvoidsort(Integer[]arr){intn=arr.length;sort(arr,0,n-1);}publicstatic......
  • 数据结构与算法分析(Java语言描述)(9)—— (双轴)快速排序
    QuickSortTwoWays.javapackagecom.algorithm.sort;publicclassQuickSortTwoWays{privateQuickSortTwoWays(){}publicstaticvoidsort(Integer[]arr){intn=arr.length;sort(arr,0,n-1);}//递归使用快速排序,对arr......