#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
#include "test11_AdjM.h"
#include "test11_AdjL.h"
void testAdjM()
{
  int n,k1,k2;
  cout<<"输入待处理图的顶点数:";
  cin>>n;
  cout<<"输入图的有无向和有无权选择:";
  cin>>k1>>k2;
  adjmatrix ga;
  InitMatrix(ga,k2);
  cout<<"输入图的边集:";
  char *a=new char[100];
  cin>>a;
  CreateMatrix(ga,n,a,k1,k2);
  PrintMatrix(ga,n,k1,k2);
}
void testAdjL()
{
  int n,k1,k2;
  cout<<"输入待处理图的顶点数:";
  cin>>n;
  cout<<"输入图的有无向和有无权选择:";
  cin>>k1>>k2;
  adjlist GL;
  InitAdjoin(GL);
  cout<<"输入图的边集:";
  char *a=new char[100];
  cin>>a;
  CreateAdjoin(GL,n,a,k1,k2);
  PrintAdjoin(GL,n,k1,k2);
}
void main()
{
  char judge;
  cout<<"测试图的邻接矩阵?(Y/N)"<<endl;
  cin>>judge;
  if(judge=='Y')
    testAdjM();
  cout<<"测试图的邻接表?(Y/N)"<<endl;
  cin>>judge;
  if(judge=='Y')
    testAdjL();
}

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
typedef char ElemType;
struct BTreeNode{
  ElemType data;
  BTreeNode* left;
  BTreeNode* right;
};
#include "test9_stack.h"
#include "test10.h"
void main()
{
  BTreeNode* bt;
  InitBTree(bt);
  char b[50];
  cout<<"输入二叉树用广义表表示的字符串:"<<endl;
  cin.getline(b,sizeof(b));
  CreateBTree(bt,b);
  PrintBTree(bt);
  cout<<endl;
  cout<<"前序：";
  PreOrder(bt);
  cout<<endl;
  cout<<"中序：";
  InOrder(bt);
  cout<<endl;
  cout<<"中序（非递归算法）:";
  InOrder_fdg(bt);
  cout<<endl;
  cout<<"后序：";
  PostOrder(bt);
  cout<<endl;
  cout<<"按层：";
  LevelOrder(bt);
  cout<<endl;
  ElemType x;
  cout<<"输入一个待查字符："<<endl;
  cin>>x;
  if(FindBTree(bt,x))
    cout<<"查找字符"<<x<<"成功!"<<endl;
  else
    cout<<"查找字符"<<x<<"失败!"<<endl;
  cout<<"深度：";
  cout<<DepthBTree(bt)<<endl;
  if(ChangeBTree(bt)){
    printf("将二叉树中的所有结点的左右子树进行交换后: \n");
    PrintBTree(bt);
    cout<<endl;
  }
  printf("二叉树中的结点总数: %d \n",CountBTree(bt));
  BTreeNode* newbt;
  newbt=CopyBTree(bt);
  printf("复制二叉树得新二叉树：\n");
  PrintBTree(newbt);
  ClearBTree(bt);
  ClearBTree(newbt);
}

struct Stack{
    ElemType  *stack ;    // 存栈元素
    int  top;                // 栈顶指示器
    int MaxSize;            // 栈的最大长度
};
void InitStack (Stack &S)    //构造一个空栈 S
{
  S.MaxSize=10;
  S.stack=new ElemType[S.MaxSize];
  if(!S.stack){
    cerr<<"fail"<<endl;
    exit(1);
  }
  S.top=-1;
}

int EmptyStack (Stack S)   //若栈S为空栈返回1，否则返回0
{
  return S.top==-1;
}

void Push(Stack &S, ElemType item)   //元素 item进栈
{
  if(S.top==S.MaxSize-1){
    int k=sizeof(ElemType);
    S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);
    S.MaxSize=2*S.MaxSize;
  }
  S.top++;
  S.stack[S.top]=item;
}

ElemType Pop(Stack &S)    //栈S的栈顶元素出栈并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  S.top--;
  return S.stack[S.top+1];
}

ElemType Peek(Stack S)   //取栈S的当前栈顶元素并返回
{
  if(S.top==-1){
    cerr<<"Stack is empty!"<<endl;
    exit(1);
  }
  return S.stack[S.top];
}

void ClearStack (Stack &S)   //清除栈s，使成为空栈
{
  if(S.stack){
    delete []S.stack;
    S.stack=0;
  }
  S.top=-1;
  S.MaxSize=0;
}

struct LNode{
  ElemType data;
  LNode* next;
};
struct LinkQueue{
  LNode* front;
  LNode* rear;
};

void InitQueue(LinkQueue &HQ)
{
  HQ.front=HQ.rear=NULL;
}

bool EmptyQueue (LinkQueue &HQ)
{
  return HQ.front==NULL;
}

void EnQueue (LinkQueue &HQ, ElemType item)
{
  LNode* newptr=new LNode;
  newptr->data=item;
  newptr->next=NULL;
  if(HQ.rear==NULL)
    HQ.front=HQ.rear=newptr;
  else
    HQ.rear=HQ.rear->next=newptr;
}

ElemType OutQueue (LinkQueue &HQ)
{
  if(HQ.front==NULL){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  ElemType temp=HQ.front->data;
  LNode* p=HQ.front;
  HQ.front=p->next;
  if(HQ.front==NULL)
    HQ.rear=NULL;
  delete p;
  return temp;
}

ElemType PeekQueue (LinkQueue &HQ)
{
  if(HQ.front==NULL){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  return HQ.front->data;
}

void ClearQueue (LinkQueue &HQ)
{
  LNode* p=HQ.front;
  while(p!=NULL){
    HQ.front=HQ.front->next;
    delete p;
    p=HQ.front;
  }
  HQ.rear=NULL;
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef struct{
  int num;  //汽车牌照号码
  int time;   //进入停车场的时刻
} ElemType;  //栈与队列中元素的数据类型
#include"test9_stack.h"
#include"test9_queue.h"
void main()
{
  ElemType  x, y;
  char flag;
  int n,fee;
  Stack parking,temp;
  LinkQueue path;
  InitStack(parking);
  InitStack(temp);
  InitQueue(path);
  cout<<"请输入停车场的停车位个数：";
  cin>>n;
  cout<<"请输入每小时的停车费用（元/小时）：";
  cin>>fee;
  cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
  cin>>flag>>x.num>>x.time;
  while (flag!='E'){
    if (flag=='A'){ //进栈或进队列，并输出汽车的停车位置
      if(parking.top==n-1){
        EnQueue(path,x);
        cout<<"停车场车位已满，该车已停入过道"<<endl;
      }
      else{
        Push(parking,x);
        cout<<"该车停在"<<parking.top<<"号停车位"<<endl;
      }
    }
    else if (flag=='D'){
      y=Pop(parking);//出栈，并输出在车场内停留的时间和应交纳的费用
      while(y.num!=x.num){
        Push(temp,y);
        y=Pop(parking);
      }
      cout<<"该车在停车场内停留了"<<x.time-y.time<<"小时，需付费："<<fee*(x.time-y.time)<<"元"<<endl;
      while(!EmptyStack(temp))
        Push(parking,Pop(temp));
      if(!EmptyQueue(path)){  //若队列非空，则队头元素出队列（便道）并入栈（停车场）
        Push(parking,OutQueue(path));
        cout<<parking.top<<"号车位有空，过道中的第一辆车已停入该车位"<<endl;
      }
    }
    else     //打印出错信息，提示重新输入
      cout<<"输入错误，请重试！"<<endl;
    cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
    cin>>flag>>x.num>>x.time;
  }
  ClearStack(parking);
  ClearStack(temp);
  ClearQueue(path);
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef struct{
  int num;  //汽车牌照号码
  int time;   //进入停车场的时刻
} ElemType;  //栈与队列中元素的数据类型
#include"test9_stack.h"
#include"test9_queue.h"
void main()
{
  ElemType  x, y;
  char flag;
  int n,fee;
  Stack parking,temp;
  LinkQueue path,temp_Q;
  InitStack(parking);
  InitStack(temp);
  InitQueue(path);
  InitQueue(temp_Q);
  cout<<"请输入停车场的停车位个数：";
  cin>>n;
  cout<<"请输入停车场内每小时的停车费用（元/小时），过道内的停车费用为半价，费用不分开计算，以出来时所处位置为准：";
  cin>>fee;
  cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
  cin>>flag>>x.num>>x.time;
  while (flag!='E'){
    if (flag=='A'){ //进栈或进队列，并输出汽车的停车位置
      if(parking.top==n-1){
        EnQueue(path,x);
        cout<<"停车场车位已满，该车已停入过道"<<endl;
      }
      else{
        Push(parking,x);
        cout<<"该车停在"<<parking.top<<"号停车位"<<endl;
      }
    }
    else if (flag=='D'){//出栈，并输出在车场内停留的时间和应交纳的费用
      while(!EmptyStack(parking)){
        y=Pop(parking);
        Push(temp,y);
        if(x.num==y.num){
          cout<<"该车在停车场内停留了"<<x.time-y.time<<"小时，需付费："<<fee*(x.time-y.time)<<"元"<<endl;
              Pop(temp);
              while(!EmptyStack(temp))
            Push(parking,Pop(temp));
          if(!EmptyQueue(path)){  //若队列非空，则队头元素出队列（便道）并入栈（停车场）
            Push(parking,OutQueue(path));
            cout<<parking.top<<"号车位有空，过道中的第一辆车已停入该车位"<<endl;
          }          
          break;
        }
      }
      if(temp.top==n-1){ //在停车场内找不到该车，进入过道内查找
          while(!EmptyStack(temp))
          Push(parking,Pop(temp));
        if(!EmptyQueue(path)){
          while(!EmptyQueue(path)){
            y=OutQueue(path);
            if(x.num==y.num){
              cout<<"该车在过道内停留了"<<x.time-y.time<<"小时，需付费："<<0.5*fee*(x.time-y.time)<<"元"<<endl;
              continue;
            }
            EnQueue(temp_Q,y);
          }
          while(!EmptyQueue(temp_Q))
            EnQueue(path,OutQueue(temp_Q));
        }
      }
    }
    else     //打印出错信息，提示重新输入
      cout<<"输入错误，请重试！"<<endl;
    cout<<"请输入车辆情况(A: 到达  D: 离开  E: 结束) ，车牌号码，时间"<<endl;
    cin>>flag>>x.num>>x.time;
  }
  ClearStack(parking);
  ClearStack(temp);
  ClearQueue(path);
  ClearQueue(temp_Q);
}

struct LNode
{  // 定义单链表节点类型
    ElemType data;       // 存放结点中的数据信息
    LNode *next;            // 指示下一个结点地址的指针
};

void InitList (LNode* &H)      //初始化单链表
{
  H=(LNode *)malloc(sizeof(LNode));
  if(!H)
    exit(0);       // 存储分配失败，退出系统
    H->next=NULL;     // 指针域为空
}

void ClearList(LNode* &H)    //清除单链表
{
  LNode *cp;
  LNode *np;
  cp=H;
  while(cp!=NULL){
    np=cp->next;
    delete cp;
    cp=np;
  }
  H=NULL;
}

int LengthList (LNode* H)   //求单链表长度
{
  int i=0;
  H=H->next;
  while(H!=NULL){
    i++;
    H=H->next;
  }
  return i;
}

bool EmptyList (LNode* H)      //判断单链表是否为空表
{
  return H->next==NULL;
}

ElemType GetList (LNode* H, int pos)  //取单链表第 pos 位置上的元素  
{
  if(pos<1){
    cerr<<"pos is out range!"<<endl;
    exit(1);
  }
  int i=0;
  H=H->next;
  while(H!=NULL){
    i++;
    if(i==pos)
      break;
    H=H->next;
  }
  if(H!=NULL)
    return H->data;
  else
  {
    cerr<<"pos is out range!"<<endl;
    exit(1);
  }
}

void TraverseList(LNode* H)    //遍历单链表
{
  H=H->next;
  while(H!=NULL){
    cout<<H->data<<" ";
    H=H->next;
  }
  cout<<endl;
}

bool InsertList ( LNode* &H, ElemType item, int pos) //向单链表插入一个元素
{
  if(pos<-1){
    cout<<"pos is illegal!"<<endl;
    return false;
  }
  LNode* newptr;
  newptr=new LNode;
  newptr->data=item;
  LNode* cp=H;
  if(pos==0){
    while(cp!=NULL){
      if(item<cp->data)
        break;
      else
        cp=cp->next;
    }
  }
  else if(pos==-1)
    while(cp!=NULL)
      cp=cp->next;
  else{
    int i=0;
    while(cp!=NULL){
      i++;
      if(i==pos)
        break;
      else
        cp=cp->next;
    }
  }
  newptr->next=cp->next;
  cp->next=newptr;
  return true;
}

bool DeleteList ( LNode* &H, ElemType& item, int pos)   //从单链表中删除一个元素
{
  if(H==NULL){
    cerr<<"H is Null, fail to delete!"<<endl;
    return false;
  }
  if(pos<-1){
    cout<<"pos is illegal!"<<endl;
    return false;
  }
  LNode* cp=H;
  LNode* s=NULL;
  if(pos==0){
    while(cp!=NULL){
      if(item==cp->next->data)
        break;
      else
        cp=cp->next;
    }
    if(cp==NULL){
      cerr<<"error"<<endl;
      return false;
    }
  }
  else{
    int i=0;
    while(cp!=NULL){
      i++;
      if(i==pos)
        break;
      else
        cp=cp->next;
    }
    if(cp==NULL){
      cout<<"pos is illegal!"<<endl;
      return false;
    }
  }
  s=cp->next;
  cp->next=cp->next->next;
  delete s;
  return true;
}

void MergeList(LNode* &La, LNode* &Lb, LNode* &Lc)
{
  LNode* pa=La;
  LNode* pb=Lb;
  LNode* ptr;  //移动指针
  Lc=pa;  //将La的表头作为Lc的表头
  pa=pa->next;
  ptr=pb;
  pb=pb->next;
  delete ptr;  //清空Lb表头
  ptr=Lc;
  while (pa!=NULL && pb!=NULL){
    if (pa->data<=pb->data){
      ptr->next=pa;
      pa=pa->next;
      ptr=ptr->next;
    }
    else{
      ptr->next=pb;
      pb=pb->next;
      ptr=ptr->next;
    }
  }
  ptr->next=(pa==NULL)?pb:pa; //当比较结束后，将La或Lb中剩下的节点接在Lc后面
}

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
#include"LinkList.h"
void main(void)
{
  int i=1,x;
  LNode* list;
  LNode* La;
  LNode* Lb;
  LNode* Lc;
  InitList(list);  //建立链表表头
  scanf("%d", &x);
  while(x!=-1)
  {  
    if(InsertList(list,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  if(EmptyList(list)!=0) //测试EmptyList函数
    printf("The list is NULL.\n");  
  else
  {
    printf("The length of the list is %d \n",LengthList(list)); //测试LengthList函数
    printf("Traverse the List:\n");
    TraverseList(list); //输出链表
    printf("The top 5 is :\n");
    for(i=1;i<=5;i++)
      printf("%d ",GetList(list,i));  //测试GetList函数，输出前5个节点的值
    printf("\n");
    printf("enter the position you want to insert:\n");  //以下开始测试DeleteList函数
    printf("0: delete the element you want.\n");  //输入0删除具体元素值所在节点
    printf("others >-1: delete the element in that position.\n"); //输入其它（大于-1）按序号删除节点
    scanf("%d",&i);
    if(i==0){
      scanf("%d",&x);
      if(DeleteList(list,x,i)!=0){  //测试删除具体元素值所在节点
        printf("After Detete the element :");
      TraverseList(list);
      }
    }
    else{
      if(DeleteList(list,i,i)!=0){  //删除第i个节点
        printf("After Detete the element in position %d :",i);
      TraverseList(list);
      }
    }
    ClearList(list);  //删除链表
  }
  InitList(La);
  printf("input elements for La: \n");
  i=1;
  scanf("%d", &x);
  while(x!=-1)
  {  
    if(InsertList(La,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  InitList(Lb);
  printf("input elements for Lb: \n");
  scanf("%d", &x);
  i=1;
  while(x!=-1)
  {  
    if(InsertList(Lb,x,i)==false){ //加入链表各个节点
      printf("错误!\n");
      return;
    }
    i++;
    scanf("%d", &x);
  }
  InitList(Lc);
  printf("after MergeList: \n");
  MergeList(La,Lb,Lc);
  TraverseList(Lc);
}

struct Queue{
  ElemType *queue;
  int front,rear,len;
  int MaxSize;
};

void InitQueue(Queue &Q)
{
  Q.MaxSize=10;
  Q.len=0;
  Q.queue=new ElemType[Q.MaxSize];
  Q.front=Q.rear=0;
}

int EmptyQueue (Queue Q)
{
  return Q.front==Q.rear;
}

void EnQueue (Queue &Q, ElemType item)
{
  if((Q.rear+1)%Q.MaxSize==Q.front){
    int k=sizeof(ElemType);
    Q.queue=(ElemType*)realloc(Q.queue,2*Q.MaxSize*k);
    if(Q.rear!=Q.MaxSize-1){
      for(int i=0;i<=Q.rear;i++)
        Q.queue[i+Q.MaxSize]=Q.queue[i];
      Q.rear+=Q.MaxSize;
    }
    Q.MaxSize=2*Q.MaxSize;
  }
  Q.rear=(Q.rear+1)%Q.MaxSize;
  Q.queue[Q.rear]=item;
  Q.len++;
}

ElemType OutQueue (Queue &Q)
{
  if(Q.front==Q.rear){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  Q.front=(Q.front+1)%Q.MaxSize;
  Q.len--;
  return Q.queue[Q.front];
}

ElemType PeekQueue (Queue &Q)
{
  if(Q.front==Q.rear){
    cerr<<"queue is empty!"<<endl;
    exit(1);
  }
  return Q.queue[(Q.front+1)%Q.MaxSize];
}

void ClearQueue (Queue &Q)
{
  if(Q.queue!=NULL)
    delete []Q.queue;
  Q.front=Q.rear=0;
  Q.queue=NULL;
  Q.MaxSize=0;
}

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
  char name[10];  
  char sex;
}dancer;
typedef dancer ElemType;
#include"test8.h"
void partner()
{
  Queue QM,QF;
  dancer t;
  char ch,oldch;
  int i;
  InitQueue(QM);
  InitQueue(QF);
  oldch=' ';
  printf("请输入跳舞者的姓名和性别（以# #结束）：\n");
  while((ch=getchar())!='#'||oldch!='#'){
    i=0;
    while(ch!='\n'){
      if(ch!=' ')
        t.name[i++]=ch;
      else{
        ch=getchar();
        t.sex=ch;
      }
      ch=getchar();
    }
    t.name[i]='\0';
    oldch='#';
    if(t.sex=='M')
      EnQueue(QM,t);
    else if(t.sex=='F')
      EnQueue(QF,t);    
  }
  printf("配对的舞伴是：\n");
  while(!EmptyQueue(QF)&&!EmptyQueue(QM)){
    t=OutQueue(QF);
    printf("%s  ",t.name);
    t=OutQueue(QM);
    printf("%s\n",t.name);
  }
  if(QM.len>QF.len){
    printf("男队还有人等待下一轮舞曲。\n");
    t=OutQueue(QM);
    printf("%s  将是下一轮得到舞伴的第一人。\n",t.name);
  }
  else if(QM.len<QF.len){
    printf("女队还有人等待下一轮舞曲。\n");
    t=OutQueue(QF);
    printf("%s 将是下一轮得到舞伴的第一人。\n",t.name);
  }
  ClearQueue(QM);
  ClearQueue(QF);
}
void main()
{
  partner();
}