实验

1.array

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<string.h>
using namespace std;

#define MAX 100
struct Array
{
    int *head;//头结点
    int len;//长度
    int num;//有效位数
};
void Creatarray(struct Array &A,int length)
{
    A.head=(int *)malloc(sizeof(int)*length);
    if(A.head==NULL)
    {
        cout<<"wrong!";
        exit(-1);
    }
    A.num=0;
    A.len=length;
}
int seek(struct Array &A,int x)
{
    for(int i=0;i<A.num;i++)
    {
        if(A.head[i]==x)
        {
            cout<<x<<"is in the "<<i;
            return i;
        }
    }
    cout<<"not in the array";
    return 0;
}
void Initarray(struct Array &A,int x)
{
    if(A.num<A.len)
    {
        A.head[A.num]=x;
    A.num++;
    }
    else
        cout<<"can't initarray";
}
void Delearray(struct Array &A,int pos)
{
    if(A.num==0)
        cout<<"it is empty";
    else
    {
        for(int i=pos;i<A.num;i++)
    {
        A.head[i]=A.head[i+1];
    }
    A.num--;
    }

}
void Showarray(struct Array A)
{
    cout<<"\n";
    if(A.num==0)
        cout<<"it is empty";
    else
        for(int i=0;i<A.num;i++)
        cout<<A.head[i]<<"  ";

}
void Isempty(struct Array A)
{
    if(A.num==0)
        cout<<"it is empty";
    else
        cout<<"it is not empty";
}
void Isfull(struct Array A)
{
    if(A.len==A.num)
        cout<<"it is full";
    else
        cout<<"it is not full";
}
bool compare(struct Array A,struct Array B)
{
    for(int i=0;i<min(A.num,B.num);i++)
    {
        if(A.head[i]==B.head[i])
            continue;
        else
            {
                cout<<"A and B is not equal;";
                return false;
            }
    }
    cout<<"A and B is equal;";
    return true;
}

void Union(struct Array A,struct Array B,struct Array &C)
{

    for(int i=0;i<A.num;i++)
    Initarray(C,A.head[i]);
    for(int j=0;j<B.num;j++)
    {
        int flag=0;
        int b=B.head[j];
        for(int i=0;i<C.num;i++)
        {
            if(b!=C.head[i])
                continue;
            else
                {
                    flag=1;
                    break;
                }
        }
            if(flag==0)
                Initarray(C,b);
            else
                continue;
    }
}
void Mix(struct Array A,struct Array B)
{
    for(int i=0;i<A.num;i++)
    {
        for(int j=0;j<B.num;j++)
        {
            if(A.head[i]==B.head[j])
                cout<<A.head[i]<<"  ";
            else
                continue;
        }
    }
}
int main()
{
    Array A;
    Creatarray(A,10);
    Array B;
    Creatarray(B,10);
    cout<<"how many numbers in A:";
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"input the number:";
        int a;
        cin>>a;
        Initarray(A,a);
    }
    Showarray(A);
    cout<<"\n";
    cout<<"how many number in B:";
    int m;
    cin>>m;
    for(int j=0;j<m;j++)
    {
        cout<<"input the number:";
        int b;
        cin>>b;
        Initarray(B,b);
    }
    Showarray(B);
    cout<<"\n";
    cout<<"compare A and B:"<<endl;
    compare(A,B);
    cout<<"\n";
    cout<<"A and B union:";
    Array C;
    Creatarray(C,20);
    Union(A,B,C);
    Showarray(C);
    cout<<"\n";
    cout<<"A and B mix:"<<endl;
    Mix(A,B);
    return 0;
}

2.sqlist

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

struct Lnode
{
    char data;
    struct Lnode *next;
};

struct Linklist
{
    Lnode *head;
    int num;//元素个数
};

void Creatlist(struct Linklist &L)
{
    L.head=NULL;
    L.num=0;
}

void Insertlist(struct Linklist &L,char x)
{
    Lnode *node=new Lnode;
    node->data=x;
    node->next=L.head;
    L.head=node;
    L.num++;
}

void Seeklist(Linklist L,char x)
{
    if(L.num==0)
        cout<<"it is empty";
    else
    {
        Lnode *p=L.head;
        for(int i=0;i<L.num;i++)
        if(p->data==x)
            cout<<x<<"is in the"<<i;
        else
        {
             p=p->next;
        }

    }
}
void Delelist(Linklist &L,int pos)
{
    if(pos==0)
        L.head=L.head->next;
    else
    {
        Lnode *p,*q;
        p=L.head;
        for(int i=0;i<pos-1;i++)
           p=p->next;
           q=p->next;
           p->next=q->next;
           L.num--;
    }
}

void Showlist(struct Linklist L)
{
    Lnode *p;
    p=L.head;
    for(int i=0;i<L.num;i++)
        {
            cout<<i<<"->"<<p->data<<endl;
            p=p->next;
        }
}

void Isempty(struct Linklist L)
{
    if(L.num==0)
        cout<<"it is empty";
    else
        cout<<"it is not empty";
}


int main()
{
    Linklist L;
    Creatlist(L);
    cout<<"**************************************"<<endl;
    cout<<"    +   ->  Insert"<<endl;
    cout<<"    -   ->  Delelist"<<endl;
    cout<<"    C   ->  seek"<<endl;
    cout<<"    S   ->  showlist"<<endl;
    cout<<"    E   ->  isempty"<<endl;

    char str[20];
    cin>>str;
    int s=strlen(str);
    for(int i=0;i<s;i++)
    {
        switch(str[i])
            {
            case '+':{Insertlist(L,str[i+1]);i=i+1;break;}
            case '-':{Delelist(L,(int)(str[i+1]-'0'));i=i+1;break;}
            case 'C':{Seeklist(L,str[i+1]);i=i+1;break;}
            case 'S':{Showlist(L);break;}
            case 'E':{Isempty(L);break;}
            }
    }
    return 0;
}

3.stack

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>

using namespace std;
struct Stack
{
    int *elem;
    int top;
    int stacksize;
};

void Initstack(struct Stack &S,int maxsize)
{
    S.elem=new int[maxsize];
    S.top=-1;
    S.stacksize=maxsize;
}

void Push(struct Stack &S,int e)
{
    S.elem[++S.top]=e;
}

void Pop(struct Stack &S,int &e)
{
    if(S.top==-1)
        cout<<"it is empty";
    else
    {
        e=S.elem[S.top--];
    }
}

void Showstack(struct Stack S)
{
    if(S.top==-1)
        cout<<"it is empty";
    else
    {
        while(S.top!=-1)
        {
            cout<<S.elem[S.top--]<<"  ";
        }
    }
}

struct Queuenode
{
    int data;
    struct Queuenode* next;
};
struct Queue
{
    struct Queuenode*front;
    struct Queuenode*rear;
    int num;
};

void Initqueue(struct Queue &Q)
{
    Q.front=Q.rear=new Queuenode;
    Q.front->next=NULL;
    Q.num=0;
}

void Enqueue(struct Queue &Q,int x)
{
    Queuenode *p=new Queuenode;
    p->data=x;
    Q.rear->next=p;
    Q.rear=p;
}

void Dequeue(struct Queue &Q,int &e)
{
    if(Q.front==Q.rear)
        cout<<"it is empty";
    else{
        Queuenode *p;
        p=Q.front->next;
        e=p->data;
        Q.front->next=p->next;
        if(Q.rear==p)
            Q.rear=Q.front;
        delete(p);
    }
}

void Showqueue(struct Queue Q)
{
    if(Q.front==Q.rear)
        cout<<"it is empty";
    else
    {
        Queuenode *p=Q.front->next;
        while(p!=Q.rear)
        {
            cout<<p->data<<"  ";
            p=p->next;
        }
        cout<<Q.rear->data;
    }
}

int main()
{
    Stack S;
    Initstack(S,10);
    cout<<"****** stack******"<<endl;
    cout<<"how many numbers?";
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
         cout<<"input the number:";
         int d;
         cin>>d;
         Push(S,d);
    }
    cout<<"show the stack:"<<endl;
    Showstack(S);
    int e;
    Pop(S,e);
    cout<<"\n";
    cout<<"the top of stack:"<<e<<endl;
    cout<<"input the number enter stack:";
    int r;
    cin>>r;
    Push(S,r);
    Showstack(S);
    cout<<"\n";

    cout<<"******queue******"<<endl;
    Queue Q;
    Initqueue(Q);
    cout<<"how many numbers?";
    int k;
    cin>>k;
    for(int i=0;i<k;i++)
    {
        cout<<"input the number:";
        int a;
        cin>>a;
        Enqueue(Q,a);
    }
    cout<<"show the queue:"<<endl;
    Showqueue(Q);
    cout<<"\n";
    int f;
    Dequeue(Q,f);
    cout<<"the head of the queue:"<<f;
    cout<<"input the number enter queue:";
    int l;
    cin>>l;
    Enqueue(Q,l);
    Showqueue(Q);
    return 0;
}

4.tree

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;

typedef struct Treenode
{
    int data;
    struct Treenode*lchild;
    struct Treenode*rchild;
}*Tree,Treenode;

void Creattree(Tree &T)
{
    T=NULL;
}

bool Searchtree(Tree T,int x,Tree &p,Tree &q)
{
    p=T;
    while(p)
    {
        if(x==p->data)
        {
            return true;
          }
        else if(x<p->data)
        {
            q=p;
            p=p->lchild;
        }
        else
        {
            q=p;p=p->rchild;
        }
    }
    return false;
}

bool Insert(Tree &T,int x)
{
    Tree m,n;
  if(Searchtree(T,x,m,n))
    return false;
  else
  {
      Treenode *s=new Treenode;
      s->data=x;
      s->lchild=NULL;
      s->rchild=NULL;
      if(!T)T=s;
      else if(x<n->data)n->lchild=s;
      else n->rchild=s;
      return true;
  }
}

void Deletree(Tree &T,int x)
{
    Tree m,n;
    if(Searchtree(T,x,m,n))
    {
        if(m->data<n->data)
        {
            if(m->rchild==NULL)
        {
            n->lchild=m->lchild;
            delete(m);
        }
        else
        {
            n->lchild=m->rchild;
            delete(m);
        }
        }
        else
        {
            if(m->rchild==NULL)
        {
            n->rchild=m->lchild;
            delete(m);
        }
            else
        {
            n->rchild=m->rchild;
            delete(m);
        }
        }

    }
    else
        cout<<"can't find";
}
void Showtree1(Tree T)//中序遍历
{
    if(T){
    Showtree1(T->lchild);
    cout<<T->data<<"    ";
    Showtree1(T->rchild);
    }

}
void Showtree2(Tree T)//先序
{
    if(T)
    {
        cout<<T->data<<"    ";
        Showtree2(T->lchild);
        Showtree2(T->rchild);
    }
}
void Showtree3(Tree T)//后序
{
    if(T)
    {
        Showtree3(T->lchild);
        Showtree3(T->rchild);
        cout<<T->data<<"    ";
    }
}
int main()
{
    Tree T;
    Creattree(T);
    cout<<"how many numbers?";
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        cout<<"input the numbers：";
        int a;
        cin>>a;
        Insert(T,a);
    }
    cout<<"中序遍历："<<endl;
    Showtree1(T);
    cout<<"\n"<<"先序遍历："<<endl;
    Showtree2(T);
    cout<<"\n"<<"后序遍历："<<endl;
    Showtree3(T);
    cout<<"\n";
    cout<<"input the number you want to insert:";
    int q;
    cin>>q;
    Insert(T,q);
    cout<<"中序遍历："<<endl;
    Showtree1(T);
    cout<<"\n"<<"先序遍历："<<endl;
    Showtree2(T);
    cout<<"\n"<<"后序遍历："<<endl;
    Showtree3(T);
    cout<<"\n";
    cout<<"input the number you want to delete:";
    int z;
    cin>>z;
    Deletree(T,z);
    cout<<"中序遍历："<<endl;
    Showtree1(T);
    cout<<"\n"<<"先序遍历："<<endl;
    Showtree2(T);
    cout<<"\n"<<"后序遍历："<<endl;
    Showtree3(T);
    return 0;
}

5.graph

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>

using namespace std;

#define MAX 20
typedef struct ArcCell
{
    int adj;
}Adj[MAX][MAX],ArcCell;
struct Graph
{
    char vex[MAX];//顶点数组
    bool visited[MAX];//是否访问标志
    Adj arcs;//邻接矩阵
    int vexnum,arcnum;//顶点和边的数量
};

int Locate(char a[],char x)
{
    for(int i=0;;i++)
        if(x==a[i])
        return i;
    return -1;
}
void CreatGraph(Graph &g)
{
    cout<<"how many vex:";
    cin>>g.vexnum;
    cout<<"how many arc:";
    cin>>g.arcnum;
    for(int i=0;i<g.vexnum;i++)
    {
        cout<<"input the vex:";
        cin>>g.vex[i];
        g.visited[i]=false;
    }
    for(int i=0;i<g.vexnum;i++)
        for(int j=0;j<g.vexnum;j++)
        g.arcs[i][j].adj=0;
    for(int j=0;j<g.arcnum;j++)
    {
        cout<<"input the arc:";
        char v1,v2;
        cin>>v1>>v2;
        int m,n;
        m=Locate(g.vex,v1);
        n=Locate(g.vex,v2);
        int d;
        cout<<"input the info";
        cin>>d;
        g.arcs[m][n].adj=g.arcs[n][m].adj=d;
    }
}

void Initgraph(Graph &g)
{
    g.arcnum=g.vexnum=0;
}

void Showgraph(Graph g)
{
    for(int i=0;i<g.vexnum;i++)
    {
        for(int j=0;j<g.vexnum;j++)
        cout<<g.arcs[i][j].adj<<"  ";
        cout<<"\n";
    }
}

//深度优先遍历
void DFS(Graph &g,int v)
{
    g.visited[v]=true;
    cout<<"visit->"<<g.vex[v]<<"->";
    for(int i=0;i<g.vexnum;i++)
        if(g.arcs[v][i].adj!=0 && !g.visited[i])
        DFS(g,i);
}
void DFStraverse(Graph g)
{
    for(int v=0;v<g.vexnum;v++)
        if(!g.visited[v])
        DFS(g,v);
}

//广度优先遍历
struct Queuenode
{
    int data;
    struct Queuenode *next;
};
struct Queue
{
    Queuenode *front;
    Queuenode *rear;
    int num;
};
void Initqueue(struct Queue &Q,int n)
{
    Q.front=Q.rear=new Queuenode;
    Q.front->next=NULL;
    Q.num=0;
}
void Enqueue(struct Queue &Q,int x)
{
    Queuenode *p=new Queuenode;
    p->data=x;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    Q.num++;
}
bool Dequeue(struct Queue &Q,int &e)
{
    if(Q.front==Q.rear)
        return false;
    else
    {
        Queuenode *p=Q.front->next;
        e=p->data;
        Q.front->next=p->next;
        if(Q.rear==p)
            Q.rear=Q.front;
        delete(p);
        Q.num--;
        return true;
    }
}
void BFS(Graph &g)
{
    Queue Q;
    Initqueue(Q,g.vexnum);
    for(int i=0;i<g.vexnum;i++)
        if(!g.visited[i])
    {
        g.visited[i]=true;
        cout<<"visit->"<<g.vex[i]<<"->";
        Enqueue(Q,i);
        while(!Q.num){
                int e;
            Dequeue(Q,e);
        for(int j=0;j<g.vexnum;j++)
            if(!g.visited[j] && g.arcs[i][j].adj)
        {
            g.visited[j]=true;
            cout<<"visited->"<<g.vex[j]<<"->";
            Enqueue(Q,j);
        }
        }
    }
}
int main()
{
    Graph g;
    Initgraph(g);
    CreatGraph(g);
    Showgraph(g);
    cout<<"DFS:"<<endl;
    DFStraverse(g);
    cout<<"\n";
    cout<<"BFS:"<<endl;
    BFS(g);
    return 0;
}