devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

scau 数据结构上机试题

作者：空白诗007 | 2024-06-27 07:32:07

赞

踩

scau 数据结构上机试题

实验1

8576 顺序线性表的基本操作

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #define OK 1
  4. #define ERROR 0
  5. #define LIST_INIT_SIZE 100
  6. #define LISTINCREMENT 10
  7. #define ElemType int
  8.  
  9. typedef struct
  10. {
  11. 	int *elem;
  12. 	int length;
  13. 	int listsize;
  14. }SqList;
  15.  
  16. int InitList_Sq(SqList &L)
  17. {
  18. // 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
  19. // 请补全代码
  20.    L.elem=new ElemType[LIST_INIT_SIZE];
  21.    if(!L.elem) return 1;
  22.    L.length=0;
  23.    L.listsize=LIST_INIT_SIZE;
  24.    return 0;
  25.  
  26. }
  27.  
  28. int Load_Sq(SqList &L)
  29. {
  30. // 输出顺序表中的所有元素
  31. 	int i;
  32. 	if(L.length==0) printf("The List is empty!");  // 请填空
  33. 	else
  34. 	{
  35. 		printf("The List is: ");
  36. 		for(i=0;i<L.length;i++) printf("%d ",L.elem[i]);  // 请填空
  37. 	}
  38. 	printf("\n");
  39. 	return OK;
  40. }
  41.  
  42. int ListInsert_Sq(SqList &L,int i,int e)
  43. {
  44. // 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
  45. // i的合法值为1≤i≤L.length +1
  46. // 请补全代码
  47.     if(i<1||i>L.length+1)
  48.     return 1;
  49.     else
  50.     {
  51.         for(int j=L.length-1;j>=i-1;j--)
  52.         {
  53.             L.elem[j+1]=L.elem[j];
  54.         }
  55.         L.elem[i-1]=e;
  56.         ++L.length;
  57.         return 0;
  58.     }
  59.  
  60. }
  61.  
  62. int ListDelete_Sq(SqList &L,int i, int &e)
  63. {
  64. // 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
  65. // i的合法值为1≤i≤L.length
  66. // 请补全代码
  67.     if(i<1||i>L.length)
  68.      return 1;
  69.      else
  70.      {
  71.          e=L.elem[i-1];
  72.          for(int j=i-1;j<=L.length-1;j++)
  73.          {
  74.              L.elem[j]=L.elem[j+1];
  75.          }
  76.          L.length--;
  77.          return 0;
  78.      }
  79. }
  80.  
  81. int main()
  82. {
  83. 	SqList T;
  84. 	int a, i;
  85. 	ElemType e, x;
  86. 	if(!InitList_Sq(T))    // 判断顺序表是否创建成功
  87. 	{
  88. 		printf("A Sequence List Has Created.\n");
  89. 	}
  90. 	while(1)
  91. 	{
  92. 		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
  93. 		scanf("%d",&a);
  94. 		switch(a)
  95. 		{
  96. 			case 1: scanf("%d%d",&i,&x);
  97. 					if(ListInsert_Sq(T,i,x)) printf("Insert Error!\n"); // 执行插入函数，根据返回值判断i值是否合法
  98. 					else printf("The Element %d is Successfully Inserted!\n", x);
  99. 					break;
  100. 			case 2: scanf("%d",&i);
  101. 					if(ListDelete_Sq(T,i,e)) printf("Delete Error!\n"); // 执行删除函数，根据返回值判断i值是否合法
  102. 					else printf("The Element %d is Successfully Deleted!\n", e);
  103. 					break;
  104. 			case 3: Load_Sq(T);
  105. 					break;
  106. 			case 0: return 1;
  107. 		}
  108. 	}
  109. }

8577 合并顺序表

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <iostream>
  4. using namespace std;
  5. #define OK 1
  6. #define ERROR 0
  7. #define ElemType int
  8. #define LIST_INIT_SIZE 100
  9. typedef int Status;
  10.  
  11. typedef struct
  12. {
  13.     int *elem;
  14.     int length;
  15.     int listsize;
  16. }SqList;
  17.  
  18. Status InitList_Sq(SqList &L)
  19. {
  20.     L.elem=new ElemType[LIST_INIT_SIZE];
  21.     if(!L.elem) return ERROR;
  22.     L.length=0;
  23.     L.listsize=LIST_INIT_SIZE;
  24.     return OK;
  25. }
  26.  
  27. Status CreatList_Sq(SqList &L,int n)
  28. {
  29.     if(!InitList_Sq(L)) return ERROR;
  30.     for(int i=0;i<n;i++)
  31.     {
  32.         cin>>L.elem[i];
  33.         L.length++;
  34.     }
  35.     return OK;
  36. }
  37.  
  38. Status PrintList_Sq(SqList L)
  39. {
  40.     if(L.length==0)
  41.     cout<<'The List is empty!';
  42.     int i;
  43.     for(i=0;i<L.length;i++)
  44.     {
  45.         cout<<L.elem[i]<<' ';
  46.     }
  47.     cout<<endl;
  48.     return OK;
  49. }
  50.  
  51. Status MergeList_Sq(SqList LA,SqList LB,SqList &LC)
  52. {
  53.     int *pa,*pb,*pc,*pa_last,*pb_last;
  54.     LC.length=LA.length+LB.length;
  55.     LC.elem=new ElemType[LC.length];
  56.     pc=LC.elem;
  57.     pa=LA.elem;
  58.     pb=LB.elem;
  59.     pa_last=LA.elem+LA.length-1;
  60.     pb_last=LB.elem+LB.length-1;
  61.     while(pa<=pa_last&&pb<=pb_last)
  62.     {
  63.         if((*pa)<=(*pb))
  64.         *pc++=*pa++;
  65.         else
  66.         *pc++=*pb++;
  67.     }
  68.     while(pa<=pa_last) *pc++=*pa++;
  69.     while(pb<=pb_last) *pc++=*pb++;
  70. }
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77. int main()
  78. {
  79.     SqList A,B,C;
  80.     int n,m;
  81.     InitList_Sq(A);
  82.     InitList_Sq(B);
  83.     InitList_Sq(C);
  84.     cin>>n;
  85.     CreatList_Sq(A,n);
  86.     cin>>m;
  87.     CreatList_Sq(B,m);
  88.     cout<<"List A:";
  89.     PrintList_Sq(A);
  90.     cout<<"List B:";
  91.     PrintList_Sq(B);
  92.     MergeList_Sq(A,B,C);
  93.     cout<<"List C:";
  94.     PrintList_Sq(C);
  95.     return 0;
  96.  
  97. }

 8578 顺序表逆置

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<iostream>
  4. #define OK 1
  5. #define ERROR 0
  6. #define LIST_INIT_SIZE 100
  7. #define LISTINCREMENT 10
  8. #define ElemType int
  9.  
  10. using namespace std;
  11.  
  12. typedef int Status;
  13. typedef struct
  14. {
  15.     int *elem;
  16.     int length;
  17.     int listsize;
  18. }SqList;
  19.  
  20. Status InitList_Sq(SqList &L)
  21. {  // 算法2.3
  22.   // 构造一个空的线性表L。
  23.   L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
  24.   if (!L.elem) return OK;        // 存储分配失败
  25.   L.length = 0;                  // 空表长度为0
  26.   L.listsize = LIST_INIT_SIZE;   // 初始存储容量
  27.   return OK;
  28. } // InitList_Sq
  29.  
  30. Status ListInsert_Sq(SqList &L, int i, ElemType e)
  31. {  // 算法2.4
  32.   // 在顺序线性表L的第i个元素之前插入新的元素e，
  33.   // i的合法值为1≤i≤ListLength_Sq(L)+1
  34.   ElemType *p;
  35.   if (i < 1 || i > L.length+1) return ERROR;  // i值不合法
  36.   if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
  37.     ElemType *newbase = (ElemType *)realloc(L.elem,
  38.                   (L.listsize+LISTINCREMENT)*sizeof (ElemType));
  39.     if (!newbase) return ERROR;   // 存储分配失败
  40.     L.elem = newbase;             // 新基址
  41.     L.listsize += LISTINCREMENT;  // 增加存储容量
  42.   }
  43.   ElemType *q = &(L.elem[i-1]);   // q为插入位置
  44.   for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
  45.                                   // 插入位置及之后的元素右移
  46.   *q = e;       // 插入e
  47.   ++L.length;   // 表长增1
  48.   return OK;
  49. } // ListInsert_Sq
  50.  
  51. Status ListDelete_Sq(SqList &L, int i, ElemType &e)
  52. {  // 算法2.5
  53.   // 在顺序线性表L中删除第i个元素，并用e返回其值。
  54.   // i的合法值为1≤i≤ListLength_Sq(L)。
  55.   ElemType *p, *q;
  56.   if (i<1 || i>L.length) return ERROR;  // i值不合法
  57.   p = &(L.elem[i-1]);                   // p为被删除元素的位置
  58.   e = *p;                               // 被删除元素的值赋给e
  59.   q = L.elem+L.length-1;                // 表尾元素的位置
  60.   for (++p; p<=q; ++p) *(p-1) = *p;     // 被删除元素之后的元素左移
  61.   --L.length;                           // 表长减1
  62.   return OK;
  63. } // ListDelete_Sq
  64.  
  65. Status CreatList_Sq(SqList &L,int n)
  66. {
  67.      if(!InitList_Sq(L)) return ERROR;
  68.      for(int i=0;i<n;i++)
  69.      {
  70.  
  71.          cin>>L.elem[i];
  72.           L.length++;
  73.  
  74.      }
  75.      return OK;
  76. }
  77.  
  78. Status PrintList_Sq(SqList L)
  79. {
  80.     for(int i=0;i<L.length;i++)
  81.     {
  82.         cout<<L.elem[i]<<' ';
  83.     }
  84.     cout<<endl;
  85.     return OK;
  86. }
  87. Status DaozhiList_Sq(SqList &L)
  88. {
  89.     ElemType p;
  90.  
  91.     for(int n=0;n<L.length/2;n++)
  92.     {
  93.         p=L.elem[n];
  94.         L.elem[n]=L.elem[L.length-1-n];
  95.         L.elem[L.length-1-n]=p;
  96.  
  97.  
  98.     }
  99.     return OK;
  100. }
  101.  
  102. int main()
  103. {
  104.     ElemType n;
  105.     SqList T;
  106.     InitList_Sq(T);
  107.     cin>>n;
  108.     CreatList_Sq(T,n);
  109.     cout<<"The List is:";
  110.     PrintList_Sq(T);
  111.     DaozhiList_Sq(T);
  112.     cout<<"The turned List is:";
  113.     PrintList_Sq(T);
  114.     return 0;
  115. }

8579 链式线性表的基本操作

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<iostream>
  4. #define ERROR 0
  5. #define OK 1
  6. #define ElemType int
  7. using namespace std;
  8.  
  9. typedef struct LNode
  10. {
  11.  int data;
  12.  struct LNode *next;
  13. }LNode,*LinkList;
  14.  
  15. int CreateLink_L(LinkList &L,int n){
  16. // 创建含有n个元素的单链表
  17.   LinkList p,q;
  18.   int i;
  19.   ElemType e;
  20.   L = new LNode;
  21.   L->next = NULL;              // 先建立一个带头结点的单链表
  22.   q = L;
  23.   for (i=0; i<n; i++) {
  24.     scanf("%d", &e);
  25.     p = new LNode;  // 生成新结点
  26.     p->data=e;
  27.     p->next=NULL;
  28.     q->next=p;
  29.     q=p;// 请补全代码
  30.  
  31.   }
  32.   return OK;
  33. }
  34.  
  35. int LoadLink_L(LinkList &L){
  36. // 单链表遍历
  37.  LinkList p = L->next;
  38.  if(!p)printf("The List is empty!"); // 请填空
  39.  else
  40.  {
  41. 	 printf("The LinkList is:");
  42. 	 while(p!=NULL)    // 请填空
  43. 	 {
  44. 		printf("%d ",p->data);
  45. 		p=p->next;    // 请填空
  46. 	 }
  47.  }
  48.  printf("\n");
  49.  return OK;
  50. }
  51.  
  52. int LinkInsert_L(LinkList &L,int i,ElemType e){
  53. // 算法2.9
  54. // 在带头结点的单链线性表L中第i个位置之前插入元素e
  55. // 请补全代码
  56.   LinkList p=L,s;
  57.   int j=0;
  58.   while(p&&j<i-1)
  59.   {
  60.       p=p->next;
  61.       j++;
  62.   }
  63.   if(!p||j>i-1) return ERROR;
  64.   s=new LNode;
  65.   s->data=e;
  66.   s->next=p->next;
  67.   p->next=s;
  68.   return OK;
  69. }
  70.  
  71. int LinkDelete_L(LinkList &L,int i, ElemType &e){
  72. // 算法2.10
  73. // 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
  74. // 请补全代码
  75.  
  76.    LinkList p=L,t;
  77.    int j=0;
  78.    while(p->next&&j<i-1)
  79.    {
  80.        p=p->next;
  81.        j++;
  82.    }
  83.    if(!p->next||j>i-1) return ERROR;
  84.    t=p->next;
  85.    e=t->data;
  86.    p->next=t->next;
  87.    delete t;
  88.    return OK;
  89.  
  90.  
  91. }
  92.  
  93. int main()
  94. {
  95.  LinkList T;
  96.  int a,n,i;
  97.  ElemType x, e;
  98.  printf("Please input the init size of the linklist:\n");
  99.  scanf("%d",&n);
  100.  printf("Please input the %d element of the linklist:\n", n);
  101.  if(CreateLink_L(T,n))     // 判断链表是否创建成功，请填空
  102.  {
  103. 	 printf("A Link List Has Created.\n");
  104. 	 LoadLink_L(T);
  105.  }
  106.  while(1)
  107. 	{
  108. 		printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
  109. 		scanf("%d",&a);
  110. 		switch(a)
  111. 		{
  112. 			case 1: scanf("%d%d",&i,&x);
  113. 				  if(!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); // 判断i值是否合法，请填空
  114. 				  else printf("The Element %d is Successfully Inserted!\n", x);
  115. 				  break;
  116. 			case 2: scanf("%d",&i);
  117. 				  if(!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); // 判断i值是否合法，请填空
  118. 				  else printf("The Element %d is Successfully Deleted!\n", e);
  119. 				  break;
  120. 			case 3: LoadLink_L(T);
  121. 				  break;
  122. 			case 0: return 1;
  123. 		}
  124. 	}
  125. }

8580 合并链表

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #define ERROR 0
  4. #define OK 1
  5. #define ElemType int
  6. #include<iostream>
  7. using namespace std;
  8. typedef int Status;
  9. typedef struct LNode
  10. {
  11.  int data;
  12.  struct LNode *next;
  13. }LNode,*LinkList;
  14.  
  15. Status CreatLinkList_L(LinkList &L,int n)
  16. {
  17.     LinkList p,q;
  18.     ElemType e;
  19.     L=new LNode;
  20.     L->next=NULL;
  21.     q=L;
  22.     while(n--)
  23.     {
  24.         cin>>e;
  25.         p=new LNode;
  26.         p->data=e;
  27.         p->next=NULL;
  28.         q->next=p;
  29.         q=p;
  30.     }
  31.     return OK;
  32. }
  33. Status ListInsert_L(LinkList &L, int i, ElemType e) {  // 算法2.9
  34.   // 在带头结点的单链线性表L的第i个元素之前插入元素e
  35.   LinkList p,s;
  36.   p = L;
  37.   int j = 0;
  38.   while (p && j < i-1) {  // 寻找第i-1个结点
  39.     p = p->next;
  40.     ++j;
  41.   }
  42.   if (!p || j > i-1) return ERROR;      // i小于1或者大于表长
  43.   s = (LinkList)malloc(sizeof(LNode));  // 生成新结点
  44.   s->data = e;  s->next = p->next;      // 插入L中
  45.   p->next = s;
  46.   return OK;
  47. } // LinstInsert_L
  48.  
  49. Status ListDelete_L(LinkList &L, int i, ElemType &e) {  // 算法2.10
  50.   // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
  51.   LinkList p,q;
  52.   p = L;
  53.   int j = 0;
  54.   while (p->next && j < i-1) {  // 寻找第i个结点，并令p指向其前趋
  55.     p = p->next;
  56.     ++j;
  57.   }
  58.   if (!(p->next) || j > i-1) return ERROR;  // 删除位置不合理
  59.   q = p->next;
  60.   p->next = q->next;           // 删除并释放结点
  61.   e = q->data;
  62.   free(q);
  63.   return OK;
  64. } // ListDelete_L
  65.  
  66. Status MergeList_L(LinkList LA,LinkList LB,LinkList &LC)
  67. {
  68.     LinkList la,lb,lc;
  69.     LC=new LNode;
  70.     la=LA->next;
  71.     lb=LB->next;
  72.     lc=LC=LA;
  73.     while(la&&lb)
  74.     {
  75.         if(la->data<lb->data)
  76.         {
  77.              lc->next=la;
  78.              lc=la;
  79.              la=la->next;
  80.         }
  81.         else
  82.         {
  83.             lc->next=lb;
  84.             lc=lb;
  85.              lb=lb->next;
  86.         }
  87.  
  88.     }
  89.     if(la&&!lb) {lc->next=la;}
  90.     if(!la&&lb) lc->next=lb;
  91.     return OK;
  92. }
  93.  
  94. Status PrintList_L(LinkList L)
  95. {
  96.     LinkList p=L;
  97.     if(p->next==NULL) return ERROR;
  98.     while(p->next)
  99.     {
  100.         p=p->next;
  101.         cout<<p->data<<' ';
  102.     }
  103.     cout<<endl;
  104.     return OK;
  105. }
  106. int main()
  107. {
  108.     int n;
  109.     LinkList A,B,C;
  110.     cin>>n;
  111.     CreatLinkList_L(A,n);
  112.     cin>>n;
  113.     CreatLinkList_L(B,n);
  114.     cout<<"List A:";
  115.     PrintList_L(A);
  116.     cout<<"List B:";
  117.     PrintList_L(B);
  118.     MergeList_L(A,B,C);
  119.     cout<<"List C:";
  120.     PrintList_L(C);
  121.     return 0;
  122. }

19080 反转链表

  1.  
  2. #include <iostream>//C++
  3. using namespace std;
  4. struct LNode
  5. {
  6.     int data;
  7.     LNode * next;
  8. };
  9. void createList(LNode * &L,int n)
  10. {
  11.     //< 尾插法创建单链表
  12.     LNode *r, *p;
  13.     r=L=new LNode;//< 创建头结点
  14.     L->next=NULL;
  15.     for(int i=1; i<=n; i++)
  16.     {
  17.         p=new LNode;
  18.         cin>>p->data;
  19.         p->next=NULL;
  20.         r->next=p;
  21.         r=p;
  22.     }
  23. }
  24. void trv(LNode * L)
  25. {
  26.     //< 一个简单的链表遍历函数，供编程过程中测试使用
  27.     L=L->next;
  28.     while(L)
  29.     {
  30.         cout<<L->data<<' ';
  31.         L=L->next;
  32.     }
  33. }
  34. void reverseList(LNode * &L)
  35. {
  36.   LNode *pre=NULL,*cur=L->next,*nex=NULL;
  37.   while(cur)
  38.   {
  39.       nex=cur->next;
  40.       cur->next=pre;
  41.       pre=cur;
  42.       cur=nex;
  43.   }
  44.   L->next=pre;
  45. }
  46. int main()
  47. {
  48.     int n;
  49.     LNode *L;
  50.     cin>>n;
  51.     createList(L,n);
  52.     reverseList(L);
  53.     trv(L);
  54.     return 0;
  55. }

实验2

8583 顺序栈的基本操作

  1. #include<malloc.h>
  2. #include<stdio.h>
  3. #define OK 1
  4. #define ERROR 0
  5. #define STACK_INIT_SIZE 100 // 存储空间初始分配量
  6. #define STACKINCREMENT 10 // 存储空间分配增量
  7.  
  8. typedef int SElemType; // 定义栈元素类型
  9. typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
  10.  
  11. struct SqStack
  12. {
  13.      SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
  14.      SElemType *top; // 栈顶指针
  15.      int stacksize; // 当前已分配的存储空间，以元素为单位
  16. }; // 顺序栈
  17.  
  18. Status InitStack(SqStack &S)
  19. {
  20. // 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
  21. // 请补全代码
  22.   S.base=new SElemType[STACK_INIT_SIZE];
  23.   if(!S.base) return ERROR;
  24.   S.top=S.base;
  25.   S.stacksize=STACK_INIT_SIZE;
  26.   return OK;
  27. }
  28.  
  29. Status Push(SqStack &S,SElemType e)
  30. {
  31. // 在栈S中插入元素e为新的栈顶元素
  32. // 请补全代码
  33. if(S.top-S.base==STACK_INIT_SIZE) return ERROR;
  34. *S.top++=e;
  35. return OK;
  36.  
  37. }
  38.  
  39. Status Pop(SqStack &S,SElemType &e)
  40. {
  41. // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
  42. // 请补全代码
  43. if(!(S.top==S.base))
  44. {
  45.     e=*--S.top;
  46.     return OK;
  47. }
  48. else return ERROR;
  49.  
  50. }
  51.  
  52. Status GetTop(SqStack S,SElemType &e)
  53. {
  54. // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
  55. // 请补全代码
  56. if(S.top==S.base) return ERROR;
  57. e=*(S.top-1);
  58. return OK;
  59.  
  60. }
  61.  
  62. int StackLength(SqStack S)
  63. {
  64. // 返回栈S的元素个数
  65. // 请补全代码
  66.  return (S.top-S.base);
  67.  
  68. }
  69.  
  70. Status StackTraverse(SqStack S)
  71. {
  72. // 从栈顶到栈底依次输出栈中的每个元素
  73. 	SElemType *p  =  S.top;        //请填空
  74. 	if(S.top==S.base)printf("The Stack is Empty!"); //请填空
  75. 	else
  76. 	{
  77. 		printf("The Stack is: ");
  78. 		while(p!=S.base)            //请填空
  79. 		{
  80.             p--;//请填空
  81. 			printf("%d ", *p);
  82.  
  83. 		}
  84. 	}
  85. 	printf("\n");
  86. 	return OK;
  87. }
  88.  
  89. int main()
  90. {
  91.      int a;
  92.      SqStack S;
  93. SElemType x, e;
  94.      if(InitStack(S))    // 判断顺序表是否创建成功，请填空
  95. {
  96. 	printf("A Stack Has Created.\n");
  97. }
  98. while(1)
  99. 	{
  100.     printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease choose:\n");
  101. 	scanf("%d",&a);
  102. 		switch(a)
  103. 		{
  104. 			case 1: scanf("%d", &x);
  105. 		      if(!Push(S,x)) printf("Push Error!\n"); // 判断Push是否合法，请填空
  106. 		      else printf("The Element %d is Successfully Pushed!\n", x);
  107. 		      break;
  108. 		case 2: if(!Pop(S,e)) printf("Pop Error!\n"); // 判断Pop是否合法，请填空
  109. 			  else printf("The Element %d is Successfully Poped!\n", e);
  110. 		  	  break;
  111. 		case 3: if(!GetTop(S,e))printf("Get Top Error!\n"); // 判断Get Top是否合法，请填空
  112. 			  else printf("The Top Element is %d!\n", e);
  113. 		   	  break;
  114. 			case 4: printf("The Length of the Stack is %d!\n",StackLength(S)); //请填空
  115. 				  break;
  116. 			case 5: StackTraverse(S);  //请填空
  117. 				  break;
  118. 			case 0: return 1;
  119. 		}
  120. 	}
  121. }

8584 循环队列的基本操作

  1. #include<malloc.h>
  2. #include<stdio.h>
  3. #define OK 1
  4. #define ERROR 0
  5. typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
  6. typedef int QElemType;
  7. #define MAXQSIZE 100 // 最大队列长度(对于循环队列，最大队列长度要减1)
  8.  
  9. typedef struct
  10. {
  11.    QElemType *base; // 初始化的动态分配存储空间
  12.    int front; // 头指针,若队列不空,指向队列头元素
  13.    int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
  14.  }SqQueue;
  15.  
  16. Status InitQueue(SqQueue &Q)
  17. {
  18. // 构造一个空队列Q，该队列预定义大小为MAXQSIZE
  19. // 请补全代码
  20.  Q.base=new QElemType[MAXQSIZE];
  21.  if(!Q.base) return ERROR;
  22.  Q.front=Q.rear=0;
  23.  return OK;
  24.  
  25. }
  26.  
  27. Status EnQueue(SqQueue &Q,QElemType e)
  28. {
  29. // 插入元素e为Q的新的队尾元素
  30. // 请补全代码
  31. 	if((Q.rear+1)%MAXQSIZE==Q.front)
  32. 	return ERROR;
  33. 	Q.base[Q.rear]=e;
  34. 	Q.rear=(Q.rear+1)%MAXQSIZE;
  35. 	return OK;
  36. }
  37.  
  38. Status DeQueue(SqQueue &Q, QElemType &e)
  39. {
  40. // 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR
  41. // 请补全代码
  42. 	if(Q.front==Q.rear) return ERROR;
  43. 	e=Q.base[Q.front];
  44. 	Q.front=(Q.front+1)%MAXQSIZE;
  45. 	return OK;
  46.  
  47. }
  48.  
  49. Status GetHead(SqQueue Q, QElemType &e)
  50. {
  51. // 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR
  52. // 请补全代码
  53. if(Q.front==Q.rear) return ERROR;
  54. e=Q.base[Q.front];
  55. return OK;
  56.  
  57. }
  58.  
  59. int QueueLength(SqQueue Q)
  60. {
  61. // 返回Q的元素个数
  62. // 请补全代码
  63. return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
  64.  
  65. }
  66.  
  67. Status QueueTraverse(SqQueue Q)
  68. {
  69. // 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.
  70. 	int i;
  71. 	i=Q.front;
  72. 	if(Q.rear==Q.front)printf("The Queue is Empty!");  //请填空
  73. 	else{
  74. 		printf("The Queue is: ");
  75. 		while(i!=Q.rear)     //请填空
  76. 		{
  77. 			printf("%d ",Q.base[i] );   //请填空
  78. 			i = (i+1)%MAXQSIZE;   //请填空
  79. 		}
  80. 	}
  81. 	printf("\n");
  82. 	return OK;
  83. }
  84.  
  85. int main()
  86. {
  87. 	int a;
  88.   SqQueue S;
  89. 	QElemType x, e;
  90.   if(InitQueue(S))    // 判断顺序表是否创建成功，请填空
  91. 	{
  92. 		printf("A Queue Has Created.\n");
  93. 	}
  94. 	while(1)
  95. 	{
  96. 	printf("1:Enter \n2:Delete \n3:Get the Front \n4:Return the Length of the Queue\n5:Load the Queue\n0:Exit\nPlease choose:\n");
  97. 		scanf("%d",&a);
  98. 		switch(a)
  99. 		{
  100. 			case 1: scanf("%d", &x);
  101. 				  if(!EnQueue(S,x)) printf("Enter Error!\n"); // 判断入队是否合法，请填空
  102. 				  else printf("The Element %d is Successfully Entered!\n", x);
  103. 				  break;
  104. 			case 2: if(!DeQueue(S,e)) printf("Delete Error!\n"); // 判断出队是否合法，请填空
  105. 				  else printf("The Element %d is Successfully Deleted!\n", e);
  106. 				  break;
  107. 			case 3: if(!GetHead(S,e))printf("Get Head Error!\n"); // 判断Get Head是否合法，请填空
  108. 				  else printf("The Head of the Queue is %d!\n", e);
  109. 				  break;
  110. 			case 4: printf("The Length of the Queue is %d!\n",QueueLength(S));  //请填空
  111. 				  break;
  112. 			case 5: QueueTraverse(S); //请填空
  113. 				  break;
  114. 			case 0: return 1;
  115. 		}
  116. 	}
  117. }

8585 栈的应用——进制转换

  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<malloc.h>
  5. #define OK 1
  6. #define ERROR 0
  7. #define StackInitSize 100
  8. typedef int Status;
  9. typedef int SElemType;
  10.  
  11. using namespace std;
  12. struct SqStack
  13. {
  14.     SElemType *base;
  15.     SElemType *top;
  16.     int stacksize;
  17. };
  18.  
  19. Status CreateStack_S(SqStack &S)
  20. {
  21.     S.base=new SElemType[StackInitSize];
  22.     if(!S.base) return ERROR;
  23.     S.top=S.base;
  24.     S.stacksize=StackInitSize;
  25.     return OK;
  26. }
  27.  
  28. Status PoPStack_S(SqStack &S,SElemType x)
  29. {
  30.     if(S.top-S.base==StackInitSize) return ERROR;
  31.     *S.top++=x;
  32.     return OK;
  33. }
  34.  
  35. Status PushStack_S(SqStack &S,SElemType e)
  36. {
  37.     if(S.top==S.base) return ERROR;
  38.     e=*--S.top;
  39.     return OK;
  40. }
  41.  
  42. Status StackTraverse(SqStack S)
  43. {
  44. // 从栈顶到栈底依次输出栈中的每个元素
  45. 	SElemType *p  =  S.top;        //请填空
  46. 	if(S.top==S.base)return ERROR;
  47.  
  48. 		while(p!=S.base)            //请填空
  49. 		{
  50.             p--;//请填空
  51. 			printf("%d", *p);
  52.  
  53. 		}
  54.  
  55. 	return OK;
  56. }
  57. void Transnum8(SqStack &S,int n)
  58. {
  59.     int a,b;
  60.     while(n)
  61.     {
  62.         a=n%8;
  63.         PoPStack_S(S,a);
  64.         n=n/8;
  65.     }
  66.     StackTraverse(S);
  67. }
  68. int main()
  69. {
  70.     SqStack S;
  71.     SElemType x,e;
  72.     CreateStack_S(S);
  73.     int n;
  74.     cin>>n;
  75.     Transnum8(S,n);
  76.     return 0;
  77. }

8586 括号匹配检验

  1. typedef char SElemType;
  2. #include"malloc.h"
  3. #include"stdio.h"
  4. #include"math.h"
  5. #include"stdlib.h" // exit()
  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0
  10. typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
  11. #define STACK_INIT_SIZE 10 // 存储空间初始分配量
  12. #define STACKINCREMENT 2 // 存储空间分配增量
  13. struct SqStack
  14. {
  15.  SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
  16.  SElemType *top; // 栈顶指针
  17.  int stacksize; // 当前已分配的存储空间，以元素为单位
  18.  }; // 顺序栈
  19. Status InitStack(SqStack &S)
  20. {
  21.     S.base=new SElemType[STACK_INIT_SIZE];
  22.     if(!S.base) return ERROR;
  23.     S.top=S.base;
  24.     S.stacksize=STACK_INIT_SIZE;
  25.     return OK;
  26.  }
  27.  
  28. Status StackEmpty(SqStack S)
  29. {
  30.     if(S.top==S.base)
  31.      return OK;
  32.      else
  33.      return 0;
  34.  }
  35. Status Push(SqStack &S,SElemType &e)
  36. {
  37.     if(S.top==S.base) return ERROR;
  38.     e=*--S.top;
  39.     return OK;
  40.  }
  41.  Status Pop(SqStack &S,SElemType e)
  42. {
  43.     if(S.top-S.base==S.stacksize) return ERROR;
  44.     *S.top++=e;
  45.     return OK;
  46.  }
  47. void check()
  48.  { // 对于输入的任意一个字符串，检验括号是否配对
  49.    SqStack s;
  50.    SElemType ch[80],*p,e;
  51.    if(InitStack(s)) // 初始化栈成功
  52.    {
  53.     //printf("请输入表达式\n");
  54.      gets(ch);
  55.      p=ch;
  56.      while(*p) // 没到串尾
  57.      {
  58.  
  59.        switch(*p)
  60.        {
  61.          case '(':
  62.          case '[':Pop(s,*p++);
  63.                   break; // 左括号入栈，且p++
  64.          case ')':
  65.          case ']':if(!StackEmpty(s)) // 栈不空
  66.                   {
  67.                    Push(s,e); // 弹出栈顶元素
  68.                     if(*p==')'&&e!='('||*p==']'&&e!='[')
  69.  
  70.                                                 // 弹出的栈顶元素与*p不配对
  71.                    {
  72.                       printf("isn't matched pairs\n");
  73.                       exit(ERROR);
  74.                     }
  75.                     else
  76.                     {
  77.                      p++;
  78.                       break; // 跳出switch语句
  79.                     }
  80.                   }
  81.                   else // 栈空
  82.                   {
  83.                     printf("lack of left parenthesis\n");
  84.                     exit(ERROR);
  85.                   }
  86.          default: p++; // 其它字符不处理，指针向后移
  87.        }
  88.      }
  89.      if(StackEmpty(s)) // 字符串结束时栈空
  90.        printf("matching\n");
  91.      else
  92.        printf("lack of right parenthesis\n");
  93.    }
  94.  }
  95. int main()
  96.  {
  97.    check();
  98.  }

8587 行编辑程序

  1. typedef char SElemType;
  2. #include"malloc.h"
  3. #include"stdio.h"
  4. #include"math.h"
  5. #include"stdlib.h" // exit()
  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0
  10. typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
  11. #define STACK_INIT_SIZE 100 // 存储空间初始分配量
  12.  #define STACKINCREMENT 2 // 存储空间分配增量
  13. struct SqStack
  14. {
  15.  SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
  16.  SElemType *top; // 栈顶指针
  17.  int stacksize; // 当前已分配的存储空间，以元素为单位
  18. }; // 顺序栈
  19.  
  20. Status InitStack(SqStack &S)
  21. { // 构造一个空栈S
  22.   S.base=new SElemType[STACK_INIT_SIZE];
  23.   if(!S.base) return ERROR;
  24.   S.top=S.base;
  25.   S.stacksize=STACK_INIT_SIZE;
  26.   return OK;
  27.  }
  28. Status StackEmpty(SqStack S)
  29.  { // 若栈S为空栈，则返回TRUE，否则返回FALSE
  30.    if(S.top==S.base) return TRUE;
  31.    else return FALSE;
  32.  }
  33. Status ClearStack(SqStack &S)
  34.  { // 把S置为空栈
  35.    S.top=S.base;
  36.    return OK;
  37.  }
  38. Status DestroyStack(SqStack &S)
  39.  { // 销毁栈S，S不再存在
  40.    free(S.base);
  41.    S.base=NULL;
  42.    S.top=NULL;
  43.    S.stacksize=0;
  44.    return OK;
  45.  }
  46. Status Push(SqStack &S,SElemType e)
  47.  { // 插入元素e为新的栈顶元素
  48.      if(S.top-S.base==S.stacksize) return ERROR;
  49.      *S.top++=e;
  50.      return OK;
  51.  
  52.  }
  53.  Status Pop(SqStack &S,SElemType &e)
  54.  { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
  55.    if(S.top!=S.base)
  56.    {
  57.        e=*--S.top;
  58.       return OK;
  59.    }
  60.    else return ERROR;
  61.  
  62.  }
  63. Status StackTraverse(SqStack S,Status(*visit)(SElemType))
  64.  { // 从栈底到栈顶依次对栈中每个元素调用函数visit()。
  65.    // 一旦visit()失败，则操作失败
  66.    while(S.top>S.base)
  67.      visit(*S.base++);
  68.    printf("\n");
  69.    return OK;
  70.  }
  71. Status visit(SElemType c)
  72.  {
  73.    printf("%c",c);
  74.    return OK;
  75.  }
  76.  void LineEdit()
  77.  { // 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2
  78.    SqStack s;
  79.    char ch,c;
  80.    int n,i;
  81.    InitStack(s);
  82.    scanf("%d",&n);
  83.    ch=getchar();
  84.    for(i=1;i<=n;i++)
  85.    { ch=getchar();
  86.      while(ch!='\n')
  87.     {
  88.        switch(ch)
  89.        {
  90.          case '#':Pop(s,c);
  91.                   break; // 仅当栈非空时退栈
  92.          case '@':ClearStack(s);
  93.                   break; // 重置s为空栈
  94.          default :Push(s,ch); // 有效字符进栈
  95.        }
  96.        ch=getchar(); // 从终端接收下一个字符
  97.      }
  98.      StackTraverse(s,visit); // 将从栈底到栈顶的栈内字符输出
  99.     ClearStack(s); // 重置s为空栈
  100.     }
  101.    DestroyStack(s);
  102.  }
  103.  int main()
  104.  {
  105.      LineEdit();
  106.      return 0;
  107.  }

18938 汉诺塔问题

  1. //汉诺塔问题，打印的是整个的移动过程
  2. #include <stdio.h>
  3.  
  4.  
  5. void hanoi(int n, char A, char B, char C)//n个圈圈在柱子A上，借助柱子B，移动到柱子C上
  6. {
  7. 	if (n == 1)//如果A柱子上只有一个圈圈，直接移动到B上
  8. 		printf("%c->%d->%c\n", A,n, B);
  9. 	else
  10. 	{
  11. 		hanoi(n - 1, A, C, B);//将A柱子上的n-1个圈圈，借助柱子B，移动到柱子C上
  12. 		printf("%c->%d->%c\n", A, n,B);//将A柱子上的最后一个圈圈移动到柱子B上
  13. 		hanoi(n - 1, C, B, A);//将C柱子上的n-1个圈圈，借助柱子A，移动到柱子B上
  14. 	}
  15. }
  16.  
  17. int main()
  18. {
  19. 	int n;
  20. 	char a, b, c;
  21. 	
  22. 	
  23. 	scanf("%d %c %c %c",&n,&a,&b,&c);
  24. 	if (n >= 20||n<=0) {
  25. 		return 0;
  26. 	}
  27. 	hanoi(n, a, b, c);
  28. 	return 0;
  29. }

18937 阿克曼(Ackmann)函数

  1. #include<iostream>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int akm(int m,int n){
  7. 	if(m==0){
  8. 		return n+1;
  9. 	}else if(m>0&&n==0){
  10. 		return akm(m-1,1);
  11. 	}else if(m>0&&n>0){
  12. 		return akm(m-1,akm(m,n-1));
  13. 	}
  14. }
  15.  
  16. int main(){
  17. 	int n,m;
  18. 	cin>>m>>n;
  19. 	cout<<akm(m,n);
  20. 	return 0;
  21. }

实验3

8591 计算next值

  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "iostream"
  4. #define  MAXSTRLEN  255                   // 用户可在255以内定义最大串长
  5. typedef unsigned char SString[MAXSTRLEN+1];	// 0号单元存放串的长度
  6.  
  7. void get_next(SString T,int next[]){
  8. // 算法4.7
  9. // 求模式串T的next函数值并存入数组next
  10.    // 请补全代码
  11.    int i=1;
  12.    next[1]=0;
  13.    int j=0;
  14.    while(i<=T[0])
  15.    {
  16.       if(j==0||T[i]==T[j])
  17.       {
  18.           ++i;++j;
  19.           next[i]=j;
  20.       }
  21.       else j=next[j];
  22.    }
  23. }
  24. int main(){
  25. int next[MAXSTRLEN];
  26. SString S;
  27. int n,i,j;
  28. char ch;
  29. scanf("%d",&n);    // 指定要验证NEXT值的字符串个数
  30. ch=getchar();
  31. for(i=1;i<=n;i++)
  32. {
  33. ch=getchar();
  34. for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++)    // 录入字符串
  35. {
  36. S[j]=ch;
  37. ch=getchar();
  38. }
  39. S[0]=j-1;    // S[0]用于存储字符串中字符个数
  40. get_next(S,next);
  41. printf("NEXT J is:");
  42. for(j=1;j<=S[0];j++)
  43. printf("%d",next[j]);
  44. printf("\n");
  45. }
  46.  
  47. return 0;
  48. }

8592 KMP算法

  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "iostream"
  4. #define TRUE  1
  5. #define FALSE  0
  6. #define OK  1
  7. #define ERROR  0
  8. #define INFEASLBLE  -1
  9. #define OVERFLOW  -2
  10. #define MAXSTRLEN  255 	//用户可在255以内定义最大串长
  11. typedef unsigned char SString[MAXSTRLEN+1];	//0号单元存放串的长度
  12.  
  13. void get_next(SString T,int next[]){
  14. // 算法4.7
  15. // 求模式串T的next函数值并存入数组next
  16.    // 请补全代码
  17.    int i=1,j=0;
  18.    next[1]=0;
  19.    while(i<=T[0])
  20.    {
  21.        if(j==0||T[i]==T[j])
  22.        {
  23.            ++i;++j;
  24.            next[i]=j;
  25.        }
  26.        else
  27.        j=next[j];
  28.    }
  29.  
  30. }
  31.  
  32. int Index_KMP(SString S,SString T,int pos,int next[]){
  33. // 算法4.6
  34. // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
  35. // KMP算法。请补全代码
  36.    int i=pos;
  37.    int j=1;
  38.    while(i<=S[0]&&j<=T[0])
  39.    {
  40.        if(j==0||S[i]==T[j])
  41.        {
  42.            ++j;
  43.            ++i;
  44.        }
  45.        else
  46.         j=next[j];
  47.    }
  48.    if(j>T[0]) return i-T[0];
  49.    else return 0;
  50.  
  51. }
  52. int  main()
  53. {
  54. SString T,S;
  55.  int i,j,n;
  56.  char ch;
  57.  int pos;
  58.  int next[MAXSTRLEN];
  59.  scanf("%d",&n); // 指定n对需进行模式匹配的字符串
  60.  ch=getchar();
  61.  for(j=1;j<=n;j++)
  62. {
  63.   ch=getchar();
  64.   for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入主串
  65.   {
  66. S[i]=ch;
  67.   ch=getchar();
  68. }
  69. S[0]=i-1;    // S[0]用于存储主串中字符个数
  70. ch=getchar();
  71. for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++)    // 录入模式串
  72. {
  73.   T[i]=ch;
  74.   ch=getchar();
  75. }
  76. T[0]=i-1;    // T[0]用于存储模式串中字符个数
  77.  get_next(T,next);
  78.  pos=Index_KMP(S,T,1,next);    // 请填空
  79.  
  80. printf("%d\n",pos);
  81. }
  82.     }

18769 不完整的排序

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>
  4. #include<iostream>
  5. using namespace std;
  6.  
  7. int b[100005];
  8.  
  9. int main()
  10. {
  11.     int n;
  12.     scanf("%d",&n);
  13.     for(int i=0;i<n;i++)
  14.     {
  15.         int m;
  16.         scanf("%d",&m);
  17.         int* a=new int[m];
  18.         for(int j=0;j<m;j++)
  19.         {
  20.             cin>>a[j];
  21.         }
  22.         int *p,*q;
  23.         p=a;
  24.         q=p+m-1;
  25.         while(p<q)
  26.         {
  27.            while(*p<0&&p<q) p++;
  28.            while(*q>0&&p<q) q--;
  29.            int temp=*p;
  30.            *p=*q;
  31.            *q=temp;
  32.  
  33.         }
  34.         for(int t=0;t<m;t++)
  35.         {
  36.             printf("%d ",a[t]);
  37.         }
  38.         printf("\n");
  39.  
  40.     }
  41.     return 0;
  42. }

实验4

8606 二叉树的构建及遍历操作

  1. #include "stdio.h"
  2. #include "malloc.h"
  3. #include <iostream>
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK  1
  7. #define ERROR  0
  8. #define INFEASIBLE -1
  9. #define OVERFLOW -2
  10. typedef int  Status;
  11. using namespace std;
  12.  
  13. typedef char  ElemType;
  14. typedef struct BiTNode{
  15.   ElemType data;
  16.   struct BiTNode *lchild,*rchild;//左右孩子指针
  17. } BiTNode,*BiTree;
  18.  
  19. Status CreateBiTree(BiTree &T) {  // 算法6.4
  20.   // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  21.   // 构造二叉链表表示的二叉树T。
  22.   char ch;
  23.   scanf("%c",&ch);
  24.   if (ch=='#') T = NULL;
  25.   else {
  26.     if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
  27.     T->data=ch; // 生成根结点
  28.      CreateBiTree(T->lchild);   // 构造左子树
  29.     CreateBiTree((T->rchild));  // 构造右子树
  30.   }
  31.   return OK;
  32. } // CreateBiTree
  33.  
  34.  
  35.  
  36.  
  37.  
  38. Status PreOrderTraverse( BiTree T) {
  39.    // 前序遍历二叉树T的递归算法
  40.    //补全代码,可用多个语句
  41.    if(T)
  42.    {
  43.        cout<<T->data;
  44.   PreOrderTraverse(T->lchild);
  45.   PreOrderTraverse(T->rchild);
  46.    }
  47.  
  48. } // PreOrderTraverse
  49.  
  50.  
  51. Status InOrderTraverse( BiTree T) {
  52.      // 中序遍历二叉树T的递归算法
  53.     //补全代码,可用多个语句
  54.     if(T)
  55.     {
  56.       InOrderTraverse(T->lchild);
  57.       cout<<T->data;
  58.       InOrderTraverse(T->rchild);
  59.     }
  60.  
  61.  
  62. } // InOrderTraverse
  63.  
  64. Status PostOrderTraverse( BiTree T) {
  65.      // 后序遍历二叉树T的递归算法
  66.      //补全代码,可用多个语句
  67.      if(T)
  68.      {
  69.          PostOrderTraverse(T->lchild);
  70.          PostOrderTraverse(T->rchild);
  71.         cout<<T->data;
  72.      }
  73.  
  74. } // PostOrderTraverse
  75.  
  76.  
  77.  
  78. int main()   //主函数
  79. {
  80.     BiTree T;
  81.     CreateBiTree(T);
  82.     PreOrderTraverse(T);
  83.     cout<<endl;
  84.     InOrderTraverse(T);
  85.     cout<<endl;
  86.     PostOrderTraverse(T);
  87.     cout<<endl;
  88.     return 0;
  89.                 //补充代码
  90.  }//main
  91.

17121 求二叉树各种节点数

  1.  
  2. #include "stdio.h"
  3. #include "malloc.h"
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK  1
  7. #define ERROR  0
  8. #define INFEASIBLE -1
  9. #define OVERFLOW -2
  10. #include <iostream>
  11. using namespace std;
  12. typedef int  Status;
  13.  
  14. typedef char  ElemType;
  15. typedef struct BiTNode{
  16.   ElemType data;
  17.   struct BiTNode *lchild,*rchild;//左右孩子指针
  18. } BiTNode,*BiTree;
  19.  
  20. Status CreateBiTree(BiTree &T,int &count0,int &count1,int &count2) {  // 算法6.4
  21.   // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
  22.   // 构造二叉链表表示的二叉树T。
  23.  
  24.   char ch;
  25.   scanf("%c",&ch);
  26.   if (ch=='#') T = NULL;
  27.   else {
  28.     if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
  29.     T->data=ch; // 生成根结点
  30.      CreateBiTree(T->lchild,count0,count1,count2);   // 构造左子树
  31.     CreateBiTree(T->rchild,count0,count1,count2);  // 构造右子树
  32.     if(!T->lchild&&!T->rchild) count0++;
  33.     else if((T->lchild&&!T->rchild)||(!T->lchild&&T->rchild)) count1++;
  34.     else if(T->lchild&&T->rchild) count2++;
  35.  
  36.   }
  37.   return OK;
  38. } // CreateBiTree
  39.  
  40. int main()   //主函数
  41. {
  42.            BiTree T;
  43.            int count0=0,count1=0,count2=0;
  44.            CreateBiTree(T,count0,count1,count2);
  45.            cout<<count2<<endl;
  46.            cout<<count1<<endl;
  47.            cout<<count0<<endl;//补充代码
  48.            return 0;
  49.  }//main

18924 二叉树的宽度

  1.  
  2.  
  3. #include<stdio.h>
  4. #include<math.h>
  5. #include<iostream>
  6. using namespace std;
  7. int level[55];
  8. struct tree
  9. {
  10.     int p;
  11.     int l;
  12.     int r;
  13. }tree[100];
  14.  
  15. void t(int p,int c)
  16. {
  17.     tree[c].p=p;
  18.     if(!tree[p].l)
  19.     tree[p].l=c;
  20.     else
  21.     tree[p].r=c;
  22. }
  23. void h(int root,int c)
  24. {
  25.     level[c]++;
  26.     if(tree[root].l)
  27.     h(tree[root].l,c+1);
  28.     if(tree[root].r)
  29.     h(tree[root].r,c+1);
  30. }
  31. int main()
  32. {
  33.     int n;
  34.     int x,y;
  35.     int ans=0,root=0;
  36.     cin>>n;
  37.     for(int i=1;i<n;i++)
  38.     {
  39.  
  40.         cin>>x>>y;
  41.         t(x,y);
  42.     }
  43.     for(int i=1;i<=n;i++)
  44.     {
  45.         if(tree[i].p==0)
  46.         {
  47.             root=i;
  48.             break;
  49.         }
  50.     }
  51.     h(root,1);
  52.     for(int i=1;i<=50;i++)
  53.     {
  54.         if(level[i]>ans)
  55.         ans=level[i];
  56.     }
  57.     cout<<ans;
  58.     return 0;

18724 二叉树的遍历运算

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. #define maxn 10000
  5. char pre[maxn],in[maxn],post[maxn];
  6. void Post(char pre[],char in[],int len,int root)
  7. {
  8.     if(len<=0) return;
  9.     int i=0;
  10.     while(in[i]!=pre[0]) i++;
  11.     Post(pre+1,in,i,root-(len-i-1)-1);
  12.     Post(pre+1+i,in+i+1,len-i-1,root-1);
  13.     post[root]=pre[0];
  14. }
  15. int main()
  16. {
  17.     cin>>pre>>in;
  18.     int len=strlen(in);
  19.     Post(pre,in,len,len-1);
  20.     cout<<post<<endl;
  21.     return 0;
  22. }

18923 二叉树的直径

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<iostream>
  4.  
  5. using namespace std;
  6. typedef int ElemType;
  7.  
  8. struct BiTNode
  9. {
  10.     ElemType data;
  11.     BiTNode *lchild,rchild;
  12. }BiTNode,*BiTree;
  13.  
  14. void insertData(BiTree &T,ElemType data)
  15. {
  16.     BiTree p=new BiTNode;
  17.     P->data=data;
  18.     p->lchild=NUll;
  19.     p->rchild=NUll;
  20.     if(T==NULL)
  21.     T=p;
  22.     else
  23.     {
  24.         if(T->lchild==NULL)
  25.     T->lchild=p;
  26.     else T->rchild=p;
  27.     }
  28. }
  29.  
  30. void PreOrderSearch(BiTree T,ElemType x,BiTree &result)
  31. {
  32.     if(T)
  33.     {
  34.         if(T->data==x) result=T;
  35.         PreOrderSearch(T->lchild,x,result);
  36.         PreOrderSearch(T->rchild,x,result);
  37.     }
  38. }
  39.  
  40. int maxcount=0;
  41. int maxDepth(BiTree &T)
  42. {
  43.     if(T==NULL)
  44.     return 0;
  45.     int leftdepth=maxDepth(T->lchild);
  46.     int rightdepth=maxDepth(T->rchild);
  47.     int count=leftdepth+rightdepth;
  48.     maxcount=count>maxcount?count:maxcount;
  49.     return leftdepth>rightdepth?leftdepth+1:rightdepth+1;
  50. }
  51.  
  52. int main()
  53. {
  54.     BiTree P=NULL;
  55.     int n;
  56.     cin>>n;
  57.     n--;
  58.     insertData(P,1);
  59.     while(n--)
  60.     {
  61.         ElemType x,y;
  62.         cin>>x>>y;
  63.         BiTree res=NULL;
  64.         PreOrderSearch(P,x,res);
  65.         insertData(res,y);
  66.     }
  67.     maxDepth(P);
  68.     cout>>maxcount;
  69.     return 0;
  70. }

实验5

8610 顺序查找

  1. #include"malloc.h" /* malloc()等
  2. #include"stdio.h"
  3. #include"stdlib.h"
  5. typedef int ElemType;
  6. typedef struct /*静态查找表的顺序存储结构 */
  7. {
  8. 	ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */
  9. 	int length; /* 表长度 */
  10. }SSTable;
  11.  
  12. void Creat_Seq(SSTable &ST,int n)
  13. { /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */
  14. 	int i,temp;
  15. 	ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */
  16. 	if(!(ST).elem)
  17. 	{
  18. 		printf("ERROR\n");
  19. 		exit(0);
  20. 	} /*内存分配失败结束程序*/
  21. 	for(i=1;i<=n;i++)
  22. 	{
  23. 		scanf("%d",&temp);
  24. 		*(ST.elem+i)=temp; /* 依次赋值给ST */
  25. 	}
  26. 	ST.length=n;
  27. }
  28.  
  29. int Search_Seq(SSTable &ST,ElemType key)
  30. { /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */
  31. /* 该元素在表中的位置，否则为0。算法9.1 */
  32.     int i=ST.length;
  33.     ST.elem[0]=key;
  34.     while(ST.elem[i]!=key)
  35.     {
  36.         i--;
  37.     }
  38.     return i;
  39. }
  40.  
  41. int main()
  42. {
  43. 	SSTable ST;
  44. 	int loc,key;
  45. 	int n;
  46. 	scanf("%d",&n);
  47. 	Creat_Seq(ST,n);
  48. 	//printf("Please input the key value：");
  49. 	scanf("%d",&key);
  50. 	loc = Search_Seq(ST,key);
  51. 	if(loc!=0)
  52. 		printf("The element position is %d.\n",loc);
  53. 	else
  54. 		printf("The element is not exist.\n");
  55. }

8621 二分查找

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int n,key,mid;
  5. int binary(int a[],int n)
  6. {
  7.     int low=0,high=n;
  8.     while(low<=high)
  9.     {
  10.         mid=(low+high)/2;
  11.         if(a[mid]==key)
  12.         return 1;
  13.         else if(key<a[mid])
  14.            high=mid-1;
  15.            else low=mid+1;
  16.     }
  17.     return 0;
  18. }
  19. int main()
  20. {
  21.     cin>>n;
  22.     int a[n+5];
  23.     for(int i=0;i<n;i++)
  24.         cin>>a[i];
  25.     cin>>key;
  26.     if(binary(a,n)) cout<<"The element position is "<<mid<<'.';
  27.     else cout<<"The element is not exist.";
  28. }

8622 哈希查找

  1. #include"malloc.h" /* malloc()等 */
  2. #include"stdlib.h" /* exit() */
  3. #include"stdio.h"
  4. #define EQ(a,b) ((a)==(b))
  5. #define SUCCESS 1
  6. #define UNSUCCESS 0
  7. #define NULLKEY -1 /*哈希表无元素时值为-1*/
  8. typedef int ElemType;
  9. int length;
  10. typedef struct
  11. {
  12.    ElemType *elem; /* 数据元素存储基址，动态分配数组 */
  13.    int count; /* 当前数据元素个数 */
  14. }HashTable;
  15.  
  16. void InitHashTable(HashTable *H)
  17.  { /* 操作结果: 构造一个长度为length的哈希表,length为全局变量 */
  18.    int i;
  19.    (*H).count=0; /* 当前元素个数为0 */
  20.    (*H).elem=(ElemType*)malloc(length*sizeof(ElemType));
  21.    if(!(*H).elem)
  22.      exit(0); /* 存储分配失败 */
  23.    for(i=0;i<length;i++)
  24.      (*H).elem[i]=NULLKEY; /* 未填记录的标志 */
  25. }
  26. unsigned Hash(ElemType K)
  27. { /* 一个简单的哈希函数*/
  28.  
  29.  
  30.  return 3*k%length;
  31.  
  32.  
  33.  
  34.  
  35.  
  36. }
  37. void collision(int *p) /*线性探测再散列 */
  38. { /* 开放定址法处理冲突 */
  39.  
  40.  
  41.  *p=(*p+1)%length;
  42.  
  43.  
  44.  
  45.  
  46. }
  47. int SearchHash(HashTable H,ElemType K,int *p,int *c)
  48. {  /* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
  49.    /* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
  50.    /* c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17 */
  51.    *p=Hash(K); /* 求得哈希地址 */
  52.    while(H.elem[*p]!=NULLKEY&&!EQ(K,H.elem[*p]))
  53.    { /* 该位置中填有记录,并且关键字不相等 */
  54.      (*c)++;
  55.      if(*c<length)
  56. 	   collision(p); /* 求得下一探查地址p */
  57.      else
  58.        break;
  59.    }
  60.    if EQ(K,H.elem[*p])
  61.      return SUCCESS; /* 查找成功，p返回待查数据元素位置 */
  62.    else
  63.      return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
  64. }
  65. int InsertHash(HashTable *H,ElemType e)
  66. { /* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回查找长度 */
  67.    int c,p;
  68.    c=0;
  69.    if(SearchHash(*H,e,&p,&c))   /* 表中已有与e有相同关键字的元素 */
  70.      printf("哈希表中已有元素%d。\n",e);
  71.    else{ /* 插入e */
  72.      (*H).elem[p]=e;
  73.      ++(*H).count;
  74.    }
  75.    return c+1; /*查找长度为冲突次数加1*/
  76. }
  77. void TraverseHash(HashTable H)
  78.  { /* 按哈希地址的顺序打印哈希表，无元素位置用X表示 */
  79.    int i;
  80.    printf("HashTable Address:0～%d\n",length-1);
  81.    for(i=0;i<length;i++)
  82.      if(H.elem[i]==NULLKEY) /* 有数据 */
  83.        printf("X ");
  84. 	 else
  85. 		 printf("%d ",H.elem[i]);
  86. 	 printf("\n");
  87. }
  88. main()
  89. {
  90. 	float i=0,j=0;
  91. 	ElemType e;
  92. 	HashTable H;
  93.          //printf("Input Table length:");
  94. 	scanf("%d",&length);
  95. 	InitHashTable(&H);
  96. 	//printf("Input key words sequence, -1 conclusion input：");
  97. 	scanf("%d",&e);
  98. 	while(e!=-1)
  99. 	{
  100. 		j ++;  /*j记录输入元素个数*/
  101. 		i = i + InsertHash(&H,e);  /*i记录查找长度的和*/
  102. 		scanf("%d",&e);
  103. 	}
  104. 	TraverseHash(H);
  105. 	printf("Average search length=%f\n",i/j);
  106. }

实验6

直接插入排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void InsertSort(int *a,int n)
  5. {
  6.     for(int i=2;i<=n;i++)
  7.     {
  8.         if(a[i]<a[i-1])
  9.         {
  10.             a[0]=a[i];
  11.             a[i]=a[i-1];
  12.             int j;
  13.             for(j=i-1;a[0]<a[j-1];j--)
  14.             {
  15.                 a[j]=a[j-1];
  16.             }
  17.             a[j]=a[0];
  18.             for(int k=1;k<=n;k++)
  19.     {
  20.         cout<<a[k]<<' ';
  21.     }
  22.     cout<<endl;
  23.         }
  24.  
  25.     }
  26.  
  27. }
  28.  
  29. int main()
  30. {
  31.     int a[1000];
  32.     int n;
  33.     cin>>n;
  34.     for(int i=1;i<=n;i++)
  35.     {
  36.         cin>>a[i];
  37.     }
  38.     InsertSort(a,n);
  39. }

折半插入排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void BinSort(int *a,int n)
  5. {
  6.         for(int i=2;i<=n;i++)
  7.         {
  8.             int low=1,high=i-1,mid;
  9.             a[0]=a[i];
  10.             while(low<=high)
  11.             {
  12.                 mid=(low+high)/2;
  13.             if(a[0]<a[mid]) high=mid-1;
  14.             else low=mid+1;
  15.             }
  16.             for(int j=i;j>high+1;j--) a[j]=a[j-1];
  17.             a[high+1]=a[0];
  18.             for(int k=1;k<=n;k++) cout<<a[k]<<' ';
  19.             cout<<endl;
  20.         }
  21.  
  22. }
  23. int main()
  24. {
  25.     int n,a[10000];
  26.     cin>>n;
  27.     for(int i=1;i<=n;i++)
  28.         cin>>a[i];
  29.     BinSort(a,n);
  30.     return 0;
  31.  
  32. }


shell排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void ShellSort(int a[],int n)
  5. {
  6.     int temp;
  7.     int d=n/2;
  8.     while(d)
  9.     {
  10.         for(int i=d;i<n;i++)
  11.         {
  12.             temp=a[i];
  13.             int j=i;
  14.             while(j>=d&&temp<a[j-d])
  15.             {
  16.                 a[j]=a[j-d];
  17.                 j-=d;
  18.             }
  19.             a[j]=temp;
  20.         }
  21.         d=d/2;
  22.         for(int k=0;k<n;k++)
  23.         cout<<a[k]<<' ';
  24.         cout<<endl;
  25.     }
  26.  
  27. }
  28. int main()
  29. {
  30.     int n,a[100000];
  31.     cin>>n;
  32.     for(int i=0;i<n;i++)
  33.      cin>>a[i];
  34.      ShellSort(a,n);
  35.  
  36. }

冒泡排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void BubbleSort(int *a,int n)
  5. {
  6.     int end=n-1;
  7.     bool flag=1;
  8.     while(end>0&&flag)
  9.     {
  10.         flag=false;
  11.         for(int i=1;i<=end;i++)
  12.         {
  13.             if(a[i]>a[i+1])
  14.             {
  15.                 int temp=a[i];
  16.                 a[i]=a[i+1];
  17.                 a[i+1]=temp;
  18.                 flag=true;
  19.             }
  20.         }
  21.         end--;
  22.         for(int k=1;k<=n;k++)
  23.         cout<<a[k]<<' ';
  24.         cout<<endl;
  25.     }
  26.  
  27. }
  28. int main()
  29. {
  30.     int n,a[10000];
  31.     cin>>n;
  32.     for(int i=1;i<=n;i++)
  33.       cin>>a[i];
  34.     BubbleSort(a,n);
  35.     return 0;
  36. }

快速排序

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int Part(int *a,int l,int r)
  5. {
  6.     a[0]=a[l];
  7.     int q=a[l];
  8.     while(l<r)
  9.     {
  10.         while(a[r]>=q&&l<r) r--;
  11.         a[l]=a[r];
  12.         while(a[l]<=q&&l<r) l++;
  13.         a[r]=a[l];
  14.     }
  15.     a[l]=a[0];
  16.     return l;
  17. }
  18. void QSort(int *a,int l,int r,int len)
  19. {
  20.     if(l<r)
  21.     {
  22.         int p=Part(a,l,r);
  23.         for(int k=1;k<=len;k++)
  24.         cout<<a[k]<<' ';
  25.         cout<<endl;
  26.         QSort(a,l,p-1,len);
  27.         QSort(a,p+1,r,len);
  28.  
  29.     }
  30.  
  31. }
  32.  
  33. int main()
  34. {
  35.     int n,a[10000];
  36.     cin>>n;
  37.     for(int i=1;i<=n;i++)
  38.       cin>>a[i];
  39.     QSort(a,1,n,n);
  40.     return 0;
  41. }

简单选排

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void Ssort(int *a,int len)
  5. {
  6.     for(int i=1;i<len;++i)
  7.     {
  8.         int k=i;
  9.         for(int j=i+1;j<=len;++j)
  10.          if(a[j]<a[k])
  11.          k=j;
  12.  
  13.          int tmp=a[k];
  14.          a[k]=a[i];
  15.          a[i]=tmp;
  16.  
  17.          for(int k=1;k<=len;++k)
  18.          cout<<a[k]<<' ';
  19.          cout<<endl;
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     int n,a[100000];
  26.     cin>>n;
  27.     for(int i=1;i<=n;i++)
  28.     cin>>a[i];
  29.     Ssort(a,n);
  30.     return 0;
  31.  
  32. }

堆排序

  1. #include<iostream>
  2.  
  3. using namespace std;
  4. void Adjust(int *a,int s,int len)
  5. {
  6.     int rc=a[s];
  7.  
  8.     for(int i=2*s;i<=len;i=i*2)
  9.     {
  10.         if(a[i]<a[i+1]&&i<len)
  11.         i++;
  12.         if(rc<a[i])
  13.         {
  14.             a[s]=a[i];
  15.             s=i;
  16.         }
  17.     }
  18.     a[s]=rc;
  19. }
  20.  
  21. void CreatHeap(int *a,int len)
  22. {
  23.     for(int i=len/2;i>0;i--)
  24.     {
  25.         Adjust(a,i,len);
  26.     }
  27. }
  28.  
  29. void StackSort(int *a,int len)
  30. {
  31.     CreatHeap(a,len);
  32.     for(int i=len;i>1;i--)
  33.     {
  34.         for(int k=1;k<=len;k++)
  35.         cout<<a[k]<<' ';
  36.         cout<<endl;
  37.  
  38.         int temp=a[1];
  39.         a[1]=a[i];
  40.         a[i]=temp;
  41.         Adjust(a,1,i-1);
  42.  
  43.     }
  44.  
  45. }
  46. int main()
  47. {
  48.     int n,a[100000];
  49.     cin>>n;
  50.     for(int i=1;i<=n;i++)
  51.     {
  52.         cin>>a[i];
  53.     }
  54.     StackSort(a,n);
  55.     for(int k=1;k<=n;k++)
  56.         cout<<a[k]<<' ';
  57.     return 0;
  58. }

归并

  1. #include<iostream>
  2. using namespace std;
  3. int n;
  4.  
  5. void Merge(int a[],int l,int m,int r)
  6. {
  7.     int *p=new int [r-l+10];
  8.     int i=l,j=m+1,k=0;
  9.     while(i<=m&&j<=r)
  10.     {
  11.         if(a[i]>=a[j]) p[k++]=a[j++];
  12.         else p[k++]=a[i++];
  13.     }
  14.     while(i<=m) p[k++]=a[i++];
  15.     while(j<=r) p[k++]=a[j++];
  16.     for(i=l,k=0;i<=r;i++,k++)
  17.     {
  18.         a[i]=p[k];
  19.     }
  20.     delete[]p;
  21. }
  22. void group_two(int a[],int gap)
  23. {
  24.     int i=1;
  25.     while(i+2*gap<n)
  26.     {
  27.         Merge(a,i,i+gap-1,i+2*gap-1);
  28.         i=i+2*gap;
  29.     }
  30.     if(i+gap-1<n) Merge(a,i,i+gap-1,n);
  31.  
  32. }
  33. void Msort(int a[])
  34. {
  35.     for(int gap=1;gap<n;gap*=2)
  36.     {
  37.         group_two(a,gap);
  38.         for(int k=1;k<=n;k++)
  39.         cout<<a[k]<<' ';
  40.         cout<<endl;
  41.     }
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47.     int a[10000];
  48.     cin>>n;
  49.     for(int i=1;i<=n;i++)
  50.     {
  51.         cin>>a[i];
  52.     }
  53.     Msort(a);
  54.     return 0;
  55. }*/

实验7

图的存储结构

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. #define num 100
  6. int arr[num][num];
  7. int main()
  8. {
  9.     int a,b;
  10.     cin>>a>>b;
  11.     for(int i=0;i<b;i++)
  12.     {
  13.         int v1,v2;
  14.         cin>>v1>>v2;
  15.         arr[v1][v2]=1;
  16.     }
  17.     for(int i=1;i<=a;i++)
  18.     {
  19.         for(int j=1;j<=a;j++)
  20.         {
  21.             cout<<arr[i][j]<<' ';
  22.  
  23.         }
  24.         cout<<endl;
  25.     }
  26.     return 0;
  27. }*/

图的深度/广度遍历

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. int book[10000]={0};
  7. vector<int>e[10000];
  8.  
  9. void dfs(int z)
  10. {
  11.     cout<<(char)(z+'a')<<" ";
  12.     int len=e[z].size();
  13.     for(int i=0;i<len;i++)
  14.     {
  15.         int y=e[z][i];
  16.         if(book[y]==0)
  17.         {
  18.             book[y]=1;
  19.             dfs(y);
  20.         }
  21.     }
  22.     return ;
  23. }
  24. void bfs(int z)
  25. {
  26.     queue<int>q;
  27.     q.push(z);
  28.     while(!q.empty())
  29.     {
  30.         int r=q.front();
  31.         q.pop();
  32.         cout<<(char)(r+'a')<<" ";
  33.         int len=e[r].size();
  34.         for(int i=0;i<len;i++)
  35.         {
  36.             int y=e[r][i];
  37.             if(book[y]==0)
  38.             {
  39.                 book[y]=1;
  40.                 q.push(y);
  41.             }
  42.         }
  43.     }
  44.     return;
  45.  
  46. }
  47. int main()
  48. {
  49.     int t;
  50.     cin>>t;
  51.     int n,m;
  52.     cin>>n>>m;
  53.     int temp;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         char x;
  57.         cin>>x;
  58.     }
  59.     for(int i=0;i<m;i++)
  60.     {
  61.         char x,y;
  62.         cin>>x>>y;
  63.         int a=(char)(x-'a');
  64.         int b=(char)(y-'a');
  65.  
  66.         if(i==0)
  67.         temp=a;
  68.         if(t<=1)
  69.         e[a].insert(e[a].begin(),b);
  70.         else
  71.         {
  72.             e[a].insert(e[a].begin(),b);
  73.             e[b].insert(e[b].begin(),a);
  74.         }
  75.     }
  76.     book[temp]=1;
  77.     //选择遍历
  78.     //dfs(temp);
  79.     bfs(temp);
  80. }

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号