微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

【C++面试题解析】之循环链表、队列、栈和堆

2016-12-02 09:08 算法与数据结构

来自:it笨笨 - 博客园

链接:http://www.cnblogs.com/iuices/archive/2011/11/07/2240325.html(点击尾部阅读原文前往)


1、已知n个人(以编号1,2,3,...,n分别表示)围坐在一张圆桌周围,从编号为k的人开始报数,数到m的那个人出列,他的下一个人又从k开始报数,数到m的那个人出列,依次重复下去,直到圆桌的人全部出列。试用C++编写实现。


解析:本题就是约瑟夫环问题的实际场景,要通过输入n、m、k三个正整数,求出列的序列。这个问题采用的是典型的循环链表的数据结构,就是将一个链表的尾元素指针指向队首元素:

 

p->link=head;


解决问题的核心步骤如下:


(1)建立一个具有n个链节点、无头节点的循环链表。

 (2)确定第一个报数人的位置。

 (3)不断的从链表中删除链节点,直到链表为空。


 答案:

#include<iostream>   

using namespace std;   typedef struct LNode   {      int data;      struct LNode *link;   }LNode,*LinkList;   //n为总人数,k为第一个开始报数的人,m为出列者喊到的数  
void JOSEPHUS(int n,int k,int m)   {      //p为当前节点,r为辅助节点,指向p的前驱节点,list为头节点      LinkList p,r,list,curr;      //简历循环链表      p=(LinkList)malloc(sizeof(LNode));      p->data=1;      p->link=p;      curr=p;      for(int i=2;i<=n;i++)      {          LinkList t=(LinkList)malloc(sizeof(LNode));          t->data=i;          t->link=curr->link;          curr->link=t;          curr=t;      }      //把当前指针移动到第一个报数的人      r=curr;      while(k--)          r=p,p=p->link;      while(n--)      {          for(int s=m-1;s--;r=p,p=p->link);          r->link=p->link;          printf("%d->",p->data);          free(p);          p=r->link;      }   }

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


答案:

#include<iostream>   

using namespace std;   typedef struct student   {      int data;      struct student *next;   }node;   typedef struct linkqueue   {      node *first,*rear;   }queue;   //队列的入队   queue *insert(queue *HQ,int x)   {      node *s;      s=(node *)malloc(sizeof(node));      s->data=x;      s->next=NULL;      if(HQ->rear==NULL)      {          HQ->first=s;          HQ->rear=s;      }      else      {          HQ->rear->next=s;          HQ->rear=s;      }      return (HQ);   }   //队列的出队   queue *remove(queue *HQ)   {      node *p;      if(HQ->first==NULL)          printf("\n yichu");      else      {          p=HQ->first;          if(HQ->first==HQ->rear)          {              HQ->first=NULL;              HQ->rear=NULL;          }          else          {              HQ->first=HQ->first->next;              free(p);          }          return (HQ);      }   }

3、用两个栈实现一个队列的功能,请用C++实现。


解析:思路如下:


假设两个栈A和B,且都为空。


可以认为栈A提供入队列的功能,栈B提供出队列的功能。


入队列:入栈A。


出队列:


(1)如果栈B不为空,直接弹出栈B的数据。

(2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。

 

答案:

#include<iostream>   
#include<stack>  
using namespace std;   template<class T>   struct Queue   {      void push(T &t)      {          s1.push(t);      }      T front()      {          if(s2.empty())          {              if(s1.size()==0)throw;              while(!s1.empty())              {                  s2.push(s1.top());                  s1.pop();              }          }          return s2.top();      }      void pop()      {          if(s2.empty())          {              while(!s1.empty())              {                  s2.push(s1.top());                  s1.pop();              }          }          if(!s2.empty())              s2.pop();      }      stack<T> s1;      stack<T> s2;   }

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


解析:在进行C/C++编程时,需要程序员对内存的了解比较精准。经常需要操作的内存可分为以下几个类别:


(1)栈区(stack):由编译器自动分配和释放,存放函数的参数值、局部变量的值等。其操作方式类似于数据结构中的栈。


(2)堆区(heap):一般由程序员分配和释放,若程序员不释放,程序结束时可能由操作系统回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表


(3)全局区(静态区)(static):全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和静态变量在相邻的另一块区域。程序结束后由系统释放。


(4)文字常量区:常量字符串就是放在这里的,程序结束后由系统释放。

 

(5)程序代码区:存放函数体的二进制代码。


 答案:


(1)stack的空间由操作系统自动分配/释放,heap上的空间手动分配/释放。

(2)stack空间有限,heap是很大的自由存储区。

(3)C中的malloc函数分配内存空间即在堆上,C++中对应的是new操作符。

(4)程序在编译期对变量和函数分配内存都在栈上进行,且程序运行过程中函数调用时参数的传递也在栈上进行。

 

5、今天在csdn上看到一道面试题


给定方法签名:

MoveSubArrayToTheEnd(int[] array, int numberOfElements)

传入一个数组如 {1,2,3,4,5,6,7}  

 将数组前面 head的一个子集移到数组末尾end 
 如:input numberOfElements=3,则{1,2,3,4,5,6,7}=>{4,5,6,7,1,2,3}  
 input numberOfElements=5,则{1,2,3,4,5,6,7}=>{6,7,1,2,3,4,5}   
 请不要使用FCL提供的类库函数..



本文编号280,以后想阅读这篇文章直接输入280即可。

●输入m可以获取到文章目录。

相关推荐↓↓↓
 

C/C++编程

推荐15个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 25岁上下的你,现在混得怎么样?豆瓣6000 热帖,看完心里真的好难受! 初学者如何从零学习人工智能?看完你就懂了 张大胖学递归 轻松看懂机器学习十大常用算法 数据结构和算法(二):AVL自平衡二叉树
猜您喜欢 太阁x百日,感谢有你!"当程序员遇上XXX"五月线下活动疯狂来袭! 屌丝码农该怎么过周末 iOS10 \/ Swift3.0 \/ XCode 8 总结 Java知识图谱收集整理 一个变态程序员的窥私欲:智能语音录制程序——窃听神器(源码放送!)