Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1425072
  • 博文数量: 842
  • 博客积分: 12411
  • 博客等级: 上将
  • 技术积分: 5772
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-14 14:43
文章分类

全部博文(842)

文章存档

2013年(157)

2012年(685)

分类: C/C++

2012-05-29 18:00:36



1.已知n个人(以编号1,2,3,...,n分别表示)围坐在一张圆桌周围,从编号为k的人开始报数,数到m的那个人出列,他的下一个人又从k开始报数,数到m的那个人出列,依次重复下去,直到圆桌的人全部出列。试用C++编写实现。
 
解析:本题就是约瑟夫环问题的实际场景,要通过输入n、m、k三个正整数,求出列的序列。这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素:
    p->link=head;
    解决问题的核心步骤如下:
    (1)建立一个具有n个链节点、无头节点的循环链表。
    (2)确定第一个报数人的位置。
    (3)不断的从链表中删除链节点,直到链表为空。

  1. #include<iostream>
  2. using namespace std;

  3. typedef struct LNode
  4. {
  5.     int data;
  6.     struct LNode *link;
  7. }LNode,*LinkList;

  8. //n为总人数,k为第一个开始报数的人,m为出列者喊到的数
  9. void JOSEPHUS(int n,int k,int m)
  10. {
  11.     //p为当前节点,r为辅助节点,指向p的前驱节点,list为头节点
  12.     LinkList p,r,list,curr;
  13.     //简历循环链表
  14.     p=(LinkList)malloc(sizeof(LNode));
  15.     p->data=1;
  16.     p->link=p;
  17.     curr=p;
  18.     for(int i=2;i<=n;i++)
  19.     {
  20.         LinkList t=(LinkList)malloc(sizeof(LNode));
  21.         t->data=i;
  22.         t->link=curr->link;
  23.         curr->link=t;
  24.         curr=t;
  25.     }
  26.     //把当前指针移动到第一个报数的人
  27.     r=curr;
  28.     while(k--)
  29.         r=p,p=p->link;
  30.     while(n--)
  31.     {
  32.         for(int s=m-1;s--;r=p,p=p->link);
  33.         r->link=p->link;
  34.         printf("%d->",p->data);
  35.         free(p);
  36.         p=r->link;
  37.     }
  38. }

2.编程实现队列的入队/出队操作。

  1. #include<iostream>
  2. using namespace std;

  3. typedef struct student
  4. {
  5.     int data;
  6.     struct student *next;
  7. }node;

  8. typedef struct linkqueue
  9. {
  10.     node *first,*rear;
  11. }queue;

  12. //队列的入队
  13. queue *insert(queue *HQ,int x)
  14. {
  15.     node *s;
  16.     s=(node *)malloc(sizeof(node));
  17.     s->data=x;
  18.     s->next=NULL;
  19.     if(HQ->rear==NULL)
  20.     {
  21.         HQ->first=s;
  22.         HQ->rear=s;
  23.     }
  24.     else
  25.     {
  26.         HQ->rear->next=s;
  27.         HQ->rear=s;
  28.     }
  29.     return (HQ);
  30. }

  31. //队列的出队
  32. queue *remove(queue *HQ)
  33. {
  34.     node *p;
  35.     if(HQ->first==NULL)
  36.         printf("\n yichu");
  37.     else
  38.     {
  39.         p=HQ->first;
  40.         if(HQ->first==HQ->rear)
  41.         {
  42.             HQ->first=NULL;
  43.             HQ->rear=NULL;
  44.         }
  45.         else
  46.         {
  47.             HQ->first=HQ->first->next;
  48.             free(p);
  49.         }
  50.         return (HQ);
  51.     }
  52. }

3.用两个栈实现一个队列的功能,请用C++实现。
用两个栈实现一个队列的功能,请用C++实现。
解析:思路如下:
    假设两个栈A和B,且都为空。
    可以认为栈A提供入队列的功能,栈B提供出队列的功能。
    入队列:入栈A。
    出队列:
    (1)如果栈B不为空,直接弹出栈B的数据。
    (2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。

  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;

  4. template<class T>
  5. struct Queue
  6. {
  7.     void push(T &t)
  8.     {
  9.         s1.push(t);
  10.     }

  11.     T front()
  12.     {
  13.         if(s2.empty())
  14.         {
  15.             if(s1.size()==0)throw;
  16.             while(!s1.empty())
  17.             {
  18.                 s2.push(s1.top());
  19.                 s1.pop();
  20.             }
  21.         }
  22.         return s2.top();
  23.     }

  24.     void pop()
  25.     {
  26.         if(s2.empty())
  27.         {
  28.             while(!s1.empty())
  29.             {
  30.                 s2.push(s1.top());
  31.                 s1.pop();
  32.             }
  33.         }
  34.         if(!s2.empty())
  35.             s2.pop();
  36.     }

  37.     stack<T> s1;
  38.     stack<T> s2;
  39. }

4.请讲诉heap和stack的差别。

  1. (1)stack的空间由操作系统自动分配/释放,heap上的空间手动分配/释放。
  2. (2)stack空间有限,heap是很大的自由存储区。
  3. (3)C中的malloc函数分配内存空间即在堆上,C++中对应的是new操作符。
  4. (4)程序在编译期对变量和函数分配内存都在栈上进行,且程序运行过程中函数调用时参数的传递也在栈上进行。
阅读(1033) | 评论(0) | 转发(1) |
0

上一篇:单链表

下一篇:C++模板的使用及功能

给主人留下些什么吧!~~