新建 文本文档.txt

这是个数据结构的综和算法。包函了数据结构里所有的算法

我也来个数据结构综合
大家请给挑挑错误，找找不足吧，谢谢各位
#include<iostream.h>
#include<stdlib.h>
int whatdo1()//总菜单
{
 int n;
 cout<<"你想做什么？"<<endl;
 cout<<"创建链表   1"<<endl;
 cout<<"创建二叉树 2"<<endl;
 cout<<"图的遍历   3"<<endl;
 cout<<"数据查找   4"<<endl;
 cout<<"数据排序   5"<<endl;
 cout<<"退出       0"<<endl;
 cin>>n;
 return n;
}
int whatdo2()//链表输出插入删除
{
 int n;
 cout<<"链表输出、插入、删除"<<endl;
 cout<<"链表输出  1"<<endl;
 cout<<"链表插入  2"<<endl;
 cout<<"链表删除  3"<<endl;
 cin>>n;
 return n;
}
int whatdo3()//二叉树遍历
{
 int n;
 cout<<"二叉树排列顺序"<<endl;
 cout<<"先序          1"<<endl;
 cout<<"中序          2"<<endl;
 cout<<"后序          3"<<endl;
 cout<<"叶子及节点数  4"<<endl;
 cin>>n;
 return n;
}
int whatdo4()//排序
{
 int n;
 cout<<"数据排序!"<<endl;
 cout<<"快速排序  1"<<endl;
 cout<<"冒泡排序  2"<<endl;
 cout<<"选择排序  3"<<endl;
 cout<<"插入排序  4"<<endl;
 cout<<"堆排序    5"<<endl;
 cout<<"数组输出  6"<<endl;
 cin>>n;
 return n;
}
int whatdo5()
{
 int n;
 cout<<"选择查找方式"<<endl;
 cout<<"数组查找       1"<<endl;
 cout<<"二叉排序树查找 2"<<endl;
 cin>>n;
 return n;
}
int whatdo6()
{
 int n;
 cout<<"数组查找"<<endl;
 cout<<"顺序查找  1"<<endl;
 cout<<"二分查找  2"<<endl;
 cout<<"数组输出  3"<<endl;
 cin>>n;
 return n;
}
int whatdo7()
{
 int n;
 cout<<"深度优先遍历 1"<<endl;
 cout<<"广度优先遍历 2"<<endl;
 cin>>n;
 return n;
}

/*以下为链表*/
typedef struct node//定义链表
{
 int data;
 struct node * next;
}listnode;
typedef listnode * linklist;
int getch()//输入函数
{
 int a;
 cin>>a;
 return a;
}
void del(linklist head)  /*删除一个结点*/
{ 
 linklist p,q;
 int a;
 if(head->next==NULL)
  cout<<"链表为空!"<<endl;
 else {
   cout<<"输入删除数据:";
   cin>>a;
   p=q=head->next;
   if(a==0)cout<<"查无此节点!"<<endl;
   else{
    if(head->next==NULL)cout<<"数据表为空"<<endl;
    else if (head->next->data==a)
     {
     p=head->next;
     head->next=p->next;
     free(p);
     cout<<"删除完成!"<<endl;
     }
     else{ 
      while(p->next && p->next->data!=a)
          p=p->next;
      if(p->next==NULL)cout<<"查无此节点!"<<endl;
      else {  q=p->next;
           p->next=q->next;
        free(q);;
        cout<<"删除完成!"<<endl;
       }
      } 
    }
 }
}

void insertnode(linklist head)//插入
{
 linklist p,s;
 int i=2,m,n;
 cout<<"输入插入数据和位置:";
 cin>>n>>m;
 p=head;
 while(p->next!=NULL && p->data!=m)
  p=p->next;
 if(p->data==m)
  cout<<"链表中有此节点，数据重复，不能插入!!!"<<endl;
 else{
   p=head;
   s=(linklist)malloc(sizeof(node));
   s->data=m;
   while(i<n && p)
   {
    p=p->next;
    i++;
   }
   if(!p)
   {
    cout<<"无此节点!新节点插入链表尾!"<<endl;
    p=head;
    while(p->next!=NULL)
     p=p->next;
    p->next=s;
    cout<<"插入完成!"<<endl;
   }
   else
   {
    s->next=p->next;
    p->next=s;
    cout<<"插入完成!"<<endl;
   }
  }
}
void shownode(linklist head)//输出链表
{
 linklist p;
 if(head->next==NULL)
  cout<<"链表为空!"<<endl;
 else
 {
  p=head->next;
  while(p)
  {
   cout<<p->data<<" ";
   p=p->next;
  }
  cout<<endl;
 }
}
void crsc(int n,linklist head)//插入删除函数
{
 switch(n)
 {
  case 1:shownode(head);break;
  case 2:insertnode(head);
      break;
  case 3:del(head);
      break;
 }
}

linklist createlist( )//创建链表
{
 int ch;
 int n;
 char w='y'; 
 cout<<"链表元素为整型,输入0结束!"<<endl;
 linklist head=(linklist)malloc(sizeof(listnode));
 listnode *s,*r;
 r=head;

 while((ch=getch())!=0)
 {
  s=(listnode*)malloc(sizeof(listnode));
  s->data=ch;
  r->next=s; 
  r=s;
 }
 r->next=NULL;
 while(w=='y' || w=='Y')
 {
  n=whatdo2();
  crsc(n,head);
  cout<<"是否继续插入或删除(y/n):";
  cin>>w;
 }
 return head;
}
/*以下为二叉树*/


typedef struct list//定义二叉树
{
 int data;
 struct list * lchild; 
 struct list * rchild;
}tree;
typedef tree * tr;
int yz(tr p)
{
 int m=1,n=0;
 if(p->lchild==NULL&& p->rchild==NULL)
  return m;
 else m++;
 if(p->lchild==NULL)
  n=yz(p->rchild);
 if(p->rchild==NULL)
  m=yz(p->lchild);
 return m+n;
}
void xian(tr p)//先序
{
 if(p)
 {  
  cout<<p->data<<" ";
  xian(p->lchild);
  xian(p->rchild);
 }
}
int num(tr p)//计算节点个数
{
 static int m=0;
 if(p)
 {  
  m++;
  num(p->lchild);
  num(p->rchild);
 }
 return m;
}
void mid(tr p)//中序
{
 if(p)
 {
  mid(p->lchild);
  cout<<p->data<<" ";
  mid(p->rchild);
 }
}
void late(tr p)//后序
{
 if(p)
 {
  late(p->lchild);
  late(p->rchild);
  cout<<p->data<<" ";
 }
}
void shuenxu(int n,tr p)//选择二叉树遍历方式
{
 int m,k;
 switch(n)
  {
  case 1:xian(p);break;
  case 2:mid(p);break;
  case 3:late(p);break;
  case 4:m=yz(p);
      k=num(p);
      cout<<"叶子数为"<<m<<endl;
      cout<<"节点数为"<<k;
      break;
  }
 cout<<endl;
}
void a(tr p)//二叉树遍历
{
 int n;
 char w='y';
 while(w=='y' || w=='Y')
 {
  n=whatdo3();
  shuenxu(n,p);
  cout<<"是否继续查看其他顺序(y/n):";
  cin>>w;
 }
}
tr create()//创建二叉树
{
 tr p;
 char m;
 p=(tr)malloc(sizeof(tree));
 p->lchild=NULL;
 p->rchild=NULL;
 cout<<"输入节点内的数据:";
 cin>>p->data;
 cout<<"请问"<<p->data<<"节点是否有左子树(y/n)?";
 cin>>m;
 if(m=='y' || m=='Y')
  p->lchild=create();
 cout<<"请问"<<p->data<<"节点是否有右子树(y/n)?";
 cin>>m;
 if(m=='y' || m=='Y')
  p->rchild=create();
 return p;
}
/*以下为图*/
char geta()
{
 char m;
 cout<<"输入一个顶点:";
 cin>>m;
 return m;
}
void showa(int edges[][100],int n)
{
 int i,j;
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   cout<<edges[i][j]<<" ";
  cout<<endl;
 }
}
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[100];
void DFSM(char vexs[],int edges[100][100],int i,int n)
{
 int j;
 cout<<vexs[i];
 visited[i]=TRUE;
 for(j=0;j<n;j++)
  if(edges[i][j]==1 && !visited[j])
   DFSM(vexs,edges,j,n);
}

void DFST(char vexs[],int edges[100][100],int n)
{
 int i;
 for(i=0;i<n;i++)
  visited[i]=FALSE;
 for(i=0;i<n;i++)
  if(!visited[i])
   DFSM(vexs,edges,i,n);
 cout<<endl;
}
void createmgragh()
{
 int edges[100][100]={0};
 char vexs[100],l='y';
 int e,n,i,j,k,p;
 cout<<"输入顶点数:";
 cin>>n;
 cout<<"输入边数:";
 cin>>e;
 for(i=0;i<n;i++)
  vexs[i]=geta();
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   edges[i][j]=0;
 for(k=0;k<e;k++)
 {
  cout<<"输入边号i、j:";
  cin>>i>>j;
  edges[i-1][j-1]=1;
  edges[j-1][i-1]=1;
 }
 cout<<"领接锯阵为:"<<endl;
 showa(edges,n);
 while(l=='y' || l=='Y')
 {
  p=whatdo7();
  switch(p)
  {
  case 1:DFST(vexs,edges,n);
  //case 2:bfst();
  }
  cout<<"是否继续其他遍历(y/n):";
  cin>>l;
 }
}

/*以下为查找*/


void show(int c[],int high)
{
 int i;
 for(i=0;i<high;i++)
  cout<<c[i]<<" ";
 cout<<endl;
}
int sort(int a[],int n,int k)//顺序查找
{
 int i,m=-1;
 for(i=0;i<n;i++)
  if(a[i]==k)
   m=i;
 return m;
}
int cz(int a[],int m,int n,int k)//折半查找
{
 int mid,p=-1;
 if(m<=n)
 { 
  mid=(m+n)/2;
  if(a[mid]==k)
   p=mid;
  if(a[mid]>k)
   p=cz(a,m,mid-1,k);
  if(a[mid]<k)
   p=cz(a,mid+1,n,k);
  }        
 return p;
}
//定义二叉排序树
void in(tr *t,int k)
{
 tree *f,*p,*q=*t;
 p=(tr)malloc(sizeof(tree));
 p->data=k;
 p->lchild=p->rchild=NULL;
 if(*t==NULL)
  *t=p;
 else
 {
  while(q)
  {
   if(q->data==k)
    cout<<"树中有此数据,无须插入!"<<endl;
   else
   {
    f=q;
    q=(k<q->data)?q->lchild:q->rchild;
   }
  }
   if(k<f->data)
    f->lchild=p;
   else f->rchild=p;
 }
}
tr chzh(tr t,int k)//二叉排序树查找
{
 if(t==NULL || k==t->data)
  return t;
 if(k<t->data)
  return chzh(t->lchild,k);
 else
  return chzh(t->rchild,k);
}
void ecs(tr t)//查找函数
{
 char w='y';
 tr p;
 int k;
 xian(t);
 while(w=='y' || w=='Y')
 {
  cout<<"输入查找数据:";
  cin>>k;
  p=chzh(t,k);
  if(p==NULL)
   cout<<"无此数据!!!"<<endl;
  else cout<<p->data<<endl;
  cout<<"是否继续查找(y/n):";
  cin>>w;
 }
}
tr createtree()//创建二叉排序树
{
 tr t=NULL;
 int k;
 cout<<"输入二叉树的数据,输入0结束!"<<endl;
 cin>>k;
 while(k!=0)
 {
  in(&t,k);
  cin>>k;
 }
 return t;
}
void sxcz(int k,int a[],int n,int m)//向量查找函数
{
 int x,p;
 switch(k)
 {
 case 1:cout<<"输入查找数据:";
     cin>>x;
     p=sort(a,m,x);
     if(p==-1)
      cout<<"无此数据!!!"<<endl;
     else cout<<"查找数据在数组的第"<<p+1<<"位上!"<<endl;
     break;
 case 2:cout<<"输入查找数据:";
     cin>>x;
     p=cz(a,n,m,x);
     if(p==-1)
    cout<<"无此数据!!!"<<endl;
     else cout<<"查找数据在数组的第"<<p+1<<"位上!"<<endl;
     break;
 case 3:show(a,m);break;
 }
}
//以下为排序
//void in(int a[],int n)//直接插入排序
void insertsort(int a[],int m)
{
 int i,j,x;
 for(i=1;i<m;i++)
  if(a[i]<a[i-1])
  {
   x=a[i];
   j=i-1;
   do
   {
    a[j+1]=a[j];
    j--;
   }while(x<a[j]);
   a[j+1]=x;
  }
 show(a,m);
}
void bubblesort(int a[],int n)//冒泡排序
{
 int i,j,x;
 for(i=0;i<n;i++)
  for(j=n-2;j>=i;j--)
   if(a[j+1]<a[j])
   {
    x=a[j+1];
    a[j+1]=a[j];
    a[j]=x;
   }
 show(a,n);
}
int partition(int a[],int i,int j)//快速排序
{
 int pivot=a[i];
 while(i<j)
 {
  while(i<j && a[j]>=pivot)
   j--;
  if(i<j)
   a[i++]=a[j];
  while(i<j && a[i]<=pivot)
   i++;
  if(i<j)
   a[j--]=a[i];
 }
 a[i]=pivot;
 return i;
}
void quicksort(int a[],int m,int n)//快速排序
{
 int pivotpos;
 if(m<n)
 {
  pivotpos=partition(a,m,n);
  quicksort(a,m,pivotpos-1);
  quicksort(a,pivotpos+1,n);
 }
}
void selectsort(int a[],int n)//选择排序
{
 int i,j,k,x;
 for(i=0;i<n;i++)
 {
  k=i;
  for(j=i+1;j<n;j++)
   if(a[j]<a[k])
    k=j;
  if(k!=i)
  {
   x=a[i];
   a[i]=a[k];
   a[k]=x;
  }
 }
 show(a,n);
}
void heapify(int a[],int low,int high)//堆的筛选
{
 int large;
 int temp=a[low];
 for(large=2*low;large<=high;large=large*2)
 {
  if(large<high && a[large]<a[large+1])
   large++;
  if(temp>=a[large])
   break;
  a[low]=a[large];
  low=large;
 }
 a[low]=temp;
}
void buildheap(int a[],int n)//堆的建立
{
 int i;
 for(i=n/2-1;i>=0;i--)
  heapify(a,i,n);
}
void heapsort(int a[],int n)//堆排序
{
 int i,x;
 buildheap(a,n);
 for(i=n-1;i>0;i--)
 {
  x=a[0];
  a[0]=a[i];
  a[i]=x;
  heapify(a,0,i-1);
 }
 show(a,n);
}
void czpx(int n,int c[],int low,int high)//排序函数
{
 switch(n)
 {
 case 1:quicksort(c,low,high);
     show(c,high);
     break;
 case 2:bubblesort(c,high);
     break;
 case 3:selectsort(c,high);break;
 case 4:insertsort(c,high);break;
 case 5:heapsort(c,high);break;
 case 6:cout<<"数组输出"<<endl;
     show(c,high);
     break;
 }
}
void shuzu(int p)//创建数组
{
 int a[100];
 char w='y';
 int m=0,x,n,low=0,k;
 cout<<"输入数组数据,输入0结束!"<<endl;
 cin>>x;
 while(x!=0)
 {
  a[m]=x;
  cin>>x;
  m++;
 }
 k=p;
 if(k==2)
 {
   while(w=='y' || w=='Y')
  {
   n=whatdo4();
   czpx(n,a,low,m);
   cout<<"是否继续其他的排序(y/n):";
   cin>>w;
  }
 }
 if(k==1)
 {
   while(w=='y' || w=='Y')
  {
   n=whatdo6();
   sxcz(n,a,low,m);
   cout<<"是否继续其他的查找(y/n):";
   cin>>w;
  }
 }
}
void cz()
{
 int n,m=1;
 tr p;
 n=whatdo5();
 switch(n)
 {
 case 1:shuzu(m);break;
 case 2:p=createtree();
     ecs(p);
     break;
 }
}
/*领接锯阵*/

/*主函数*/

void main()
{
cout<<"*******************************************************************************"<<endl;
cout<<"*                        欢迎使用数据结构综合应用系统                         *"<<endl;
cout<<"*                                                                             *"<<endl;
cout<<"*                               WELCOME USE                                   *"<<endl;
cout<<"*******************************************************************************"<<endl;

 int n,m=2;
 linklist head;
 tr p;
 n=whatdo1();
 while(n!=0)
 {
  switch(n)
  {
  case 1:head=createlist();break;
  case 2:p=create();a(p);break;
  case 3:createmgragh();break;
  case 4:cz();break; 
  case 5:shuzu(m);break;
  }
  n=whatdo1();
 }
}