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;
}
网友评论