C++面试笔记--循环链表,队列,栈,堆
之前已经学会了单链表的建立删除插入转置以及一些普通操作,双链表和单链表差不多,就是多了一个前驱指针,在许多操作中很方便,但是加了一个指针开销应该会大一些,总体上影响不大,这里开始讨论循环链表以及其他的一些数据结构。
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=;
p->link=p;
curr=p;
for(int i=;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-;s--;r=p,p=p->link);
r->link=p->link;
printf("%d->",p->data);
free(p);
p=r->link;
}
}
2、编程实现队列的入队/出队操作。
答案:
#include<iostream>
#include<string>
using namespace std; const int MaxQueueSize=;
class Queue{
private:
int front; //指向头结点
int rear; //指向最后一个元素的下一结点
//int *base;//用于动态分配内存,pBase保存数组的首地址
int queues[MaxQueueSize];
public:
Queue();
~Queue();
bool isEmpty();
bool isFull();
void enQueue(const int &item);
int outQueue(void);
};
Queue::Queue(){
front=;
rear=;
}
Queue::~Queue(){
front=;
rear=;
}
void Queue::enQueue(const int &item){
if(!isFull()){
queues[rear]=item;
rear++;
}
else
cout<<"队列已满!!"<<endl;
}
int Queue::outQueue(void){
if(!isEmpty()){
int value=queues[front];
return value;
front++;
}
else
cout<<"队列已空!!"<<endl;
}
bool Queue::isEmpty(){
if(rear==front)
return true;
else
return false;
}
bool Queue::isFull(){
return rear > MaxQueueSize?true:false;
}
3、用两个栈实现一个队列的功能,请用C++实现。
解析:思路如下:
假设两个栈A和B,且都为空。
可以认为栈A提供入队列的功能,栈B提供出队列的功能。
入队列:入栈A。
出队列:
(1)如果栈B不为空,直接弹出栈B的数据。
(2)如果栈B为空,则依次弹出栈A的数据,放入栈B中,再弹出栈B的数据。
答案:
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<stack>
using namespace std;
/*
思路:1.从头到尾遍历一遍链表,利用for循环进行遍历把遍历的数据存入到栈中
2.利用栈的数据结构进行输出,递归的输出
*/
typedef struct ListNode{//链表的结构
int m_nKey;
ListNode *m_pNext;
}node; //利用栈进行输出
int printlianbiao(ListNode *pHead){//
std::stack<ListNode*> nodes;//构造一个储存泛型的栈,存储的是链表数据
ListNode* pNode=pHead;
while(pNode!=NULL){
nodes.push(pNode);//进栈
pNode=pNode->m_pNext;//一个节点的后继
}
//从栈中输出这些数据
while(!nodes.empty()){
pNode=nodes.top();//头指针指向栈顶
cout<<pNode->m_nKey<<endl;;//输出栈顶的值
nodes.pop();//出站
}
}
//利用递归进行输出
/* 1.递归的输出链表中的数
2.递归的先输出前面的数
*/
int printdigui(ListNode *pHead){
if(pHead!=NULL){
if(pHead->m_pNext!=NULL){
printdigui(pHead->m_pNext);
}
cout<<pHead->m_nKey<<endl;
}
}
node *creat(){//创建链表
node *head,*p,*s;
head=(node *)malloc(sizeof(node));//申请动态内存
p=head;
int x,cycle=;
while(cycle){
// cout<<"请输入数据"<<endl;
cin>>x;
if(x!=-){
s=(node *)malloc(sizeof(node));//为S申请动态内存
s->m_nKey=x;
p->m_pNext=s;//头指针指向第一个刚刚输入的数据
p=s;//头指针移动一位
}
else
cycle=;
}
head=head->m_pNext;//头指针指向下一位
p->m_pNext=NULL;
return head;
}
int main(){
node *pHead=creat();
cout<<"利用栈进行输出"<<endl;
printlianbiao(pHead);
cout<<"利用递归进行输出"<<endl;
printdigui(pHead); }
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)程序在编译期对变量和函数分配内存都在栈上进行,且程序运行过程中函数调用时参数的传递也在栈上进行。
最新文章
- mongodb基础篇
- stm32 hid 键盘描述
- angular-ui-bootstrap-modal必须要说的几个点(转)
- iOS设置cell选中时文字颜色的变化
- [转]LocalDB数据库修改排序规则,修复汉字变问号
- Android中的接口回调技术
- python实现简单登陆代码
- CSS3-margin,padding,border
- IE条件注释
- 输入adb shell 时 提示error: more than one device and emulator
- 采用thinkphp框架实现添加管理员功能
- js中跨域请求原理及2种常见解决方案
- 实现BUG自动检测 - ASP.NET Core依赖注入
- OpenCV成长之路:图像直方图的应用
- shell多进程脚本
- Swift中switch强大的模式匹配
- angular 引入编辑器以及控制器的学习和理解。。。
- splash
- tomcat ---->; 源码关联/编译/....
- linux source命令的用法