一个循环队列的问题（用C++描述）
各位朋友请帮忙一下
#include "conio.h"
#include "iostream.h"
#include "string.h"
#include "assert.h"
template<class type>class queuelink;
template<class type>class queuenode
{friend class queuelink<type>;
private:
type element;
queuenode<type> *next;
public:
queuenode(const type &data,queuenode<type>*p=NULL)
{element=data;next=p;}
~queuenode(){}
};
template<class type>class queuelink
{private:
queuenode<type>*rear,*front;
int size;
public:
queuelink(){front=rear=NULL;size=0;}
~queuelink(){}
queueempty(){return front==rear==NULL;}
void enqueue(const type& data);
type dequeue();
type getqueue();
void display();
void build(type a[],int n);
};
template<class type>void queuelink<type>::enqueue(const type& data)//入队
{if(front==NULL)
{front=rear=new queuenode<type>(data,front);
size++;
}
else
{rear=rear->next=new queuenode<type>(data,front);
size++;
}
}
template<class type>type queuelink<type>::dequeue()//出队
{assert(!queueempty());
queuenode<type> *p=front;
type retvalue=p->element;
front=front->next;
delete p;
rear->next=front;
size--;
return retvalue;
}
template<class type>type queuelink<type>::getqueue()//取队成员
{//assert(!queueempty());
type revalue=front->element;
front+=2;//这边为什么要加二而不是加一????????????
return revalue;
}
template<class type>void queuelink<type>::build(type a[],int n)
{
for(int i=0;i<n;i++)
enqueue(a[i]);
}
template<class type>void queuelink<type>::display()
{cout<<size<<endl;
for(int i=0;i<size;i++)
cout<<getqueue()<<" ";
getch();
cout<<endl;
}
void main()
{clrscr();
int b[]={1,2,3,4,5,6,7,8,9,10};
queuelink<int> obj2;
obj2.build(b,10);
obj2.display();
}
问题如下:
这是不是一个循环队列
如果不是要怎么改才能使它为循环队列（我自已认为不是循环队列）
还有上面的front如果加一的话为什么结果是1 9 2 9 3 9 4 9 5 9而不是
1 2 3 4 5 6 7 8 9 10（改为加二时的结果）
问题点数：100、回复次数：27Top
1 楼ttlb（__ttlb__ttlb__小鸟）回复于 2003-11-02 09:55:07 得分 5
upTop
2 楼leyt（思维机器）回复于 2003-11-02 11:31:06 得分 10
不是一个循环队列
front加1加2都是不对的。
因为你这是用的链表，不是数组，不能用指针加1的方法。
应该改为front=front->next;Top
3 楼leyt（思维机器）回复于 2003-11-02 11:47:39 得分 10
用链表实现循环队列不大合适，不如用数组。
如果想用的话，首先得指明MAXSIZE，这样才能循环使用结点。
出队列的结点别delete,用rear指向它，然后尾指针后移。
实现不难，但好像没什么意义。Top
4 楼carbon107（<软件开发思想.h>）回复于 2003-11-02 13:48:52 得分 5
离散数学图论的问题Top
5 楼chenzhichao2008（陈智超）回复于 2003-11-02 17:54:59 得分 0
leyt(汉克斯）
你好
你说的不要把出队的结点delete，我觉得不太合适吧
我的意思是要实现结点个数可变的（即出队就要size--而且把该结点删除）
Top
6 楼chenzhichao2008（陈智超）回复于 2003-11-02 17:56:41 得分 0
还有你能说一下这个程序不能实现循环的原因吗？
谢谢！！Top
7 楼hhlong（╰☆〖龙】╮）回复于 2003-11-02 18:10:07 得分 0
up!Top
8 楼453（修行者）回复于 2003-11-03 00:36:44 得分 5
那里的加2也许是指针指向的地址加2
如果那些数据连续存储也许会实现所要的功能
但即使那样也决不是一个好办法Top
9 楼leyt（思维机器）回复于 2003-11-03 14:21:54 得分 0
我觉得咱们首先得弄清楚什么是循环队列，我的理解是循环队列是用为了能用数组实现队列而采用的一种技巧，即把数组变成一个“环状的空间”，而不必在出队入队时移动元素，这就要求size是一个固定值。用链表实现队列时，当然没有必要把它变成循环的。Top
10 楼chenzhichao2008（陈智超）回复于 2003-11-03 17:41:47 得分 0
我并不在意它的必要性
而只在意于如何实现它
一道题总可以用不同的方法实现的
你能告诉我上面的程序为什么不是循环的吗（且不要说它是不是队列）Top
11 楼leyt（思维机器）回复于 2003-11-03 17:57:36 得分 5
如果把rear->next=front 就算是循环的话，那上面的应该说是循环。
Top
12 楼chenzhichao2008（陈智超）回复于 2003-11-03 18:42:44 得分 0
但是我在display中
改为
for(int i=0;i<size+100;i++)
为什么显示结果表明不是循环的(提示指针指向空)Top
13 楼mmlymlymly（mly）回复于 2003-11-03 19:42:51 得分 40
#include "conio.h"
#include "iostream.h"
#include "string.h"
#include "assert.h"
template<class type>class queuelink;
template<class type>class queuenode
{friend class queuelink<type>;
private:
type element;
queuenode<type> *next;
public:
queuenode(const type &data,queuenode<type>*p=NULL)
{element=data;next=p;}
~queuenode(){}
};
template<class type>class queuelink
{private:
queuenode<type>*rear,*front;
int size;
public:
queuelink(){front=rear=NULL;size=0;}
~queuelink(){}
void queueempty(){return front==rear==NULL;}//这里还贴错，昏
void enqueue(const type& data);
type dequeue();
type getqueue();
void display();
void build(type a[],int n);
};
template<class type>void queuelink<type>::enqueue(const type& data)//入队
{if(front==NULL)
{front=rear=new queuenode<type>(data,front);
front->next=rear; //不写的话就不是循环队列
size++;
}
else
{rear=rear->next=new queuenode<type>(data,front);
size++;
}
}
template<class type>type queuelink<type>::dequeue()//出队
{assert(!queueempty());
queuenode<type> *p=front;
type retvalue=p->element;
front=front->next;
delete p;
rear->next=front;
size--;
return retvalue;
}
template<class type>type queuelink<type>::getqueue()//取队成员
{//assert(!queueempty());
type revalue=front->element;
front=front->next;//取next，链表哪用加的
return revalue;
}
template<class type>void queuelink<type>::build(type a[],int n)
{
for(int i=0;i<n;i++)
enqueue(a[i]);
}
template<class type>void queuelink<type>::display()
{cout<<size<<endl;
for(int i=0;i<size;i++)
cout<<getqueue()<<" ";
getch();
cout<<endl;
}
void main()
{//clrscr();//这个函数懒得查了。：）
int b[]={1,2,3,4,5,6,7,8,9,10};
queuelink<int> obj2;
obj2.build(b,10);
obj2.display();
}Top
14 楼mmlymlymly（mly）回复于 2003-11-03 19:46:55 得分 0
这个类封得很不完整，有指针成员变量，建议一定要写copy construct,operator =和destruct。Top
15 楼chenzhichao2008（陈智超）回复于 2003-11-04 07:33:44 得分 0
楼上大哥
上面的题我调出来了
问题只在于front++的错误(唉!真是糊涂)(我只改动了front->next=front)
当然非常谢谢楼上几位大哥
你的意思是说
队列为空的话是front->next=rear=front是吗
但是书本上画的图不是front 和rear 指向同一结点吗
clrscr（）这是一个清屏函数而已
呀
这边的朋友真的很多都不错(挺热心的)
楼上两位兄弟（汉克斯和mmlymlymly(mly)）交个网友吧(我的QQ:190456674)
我现在刚在自学数据结构(以后可能有很多问题问的）
我现在不知道接下来该去看什么书了，迷或（能给我指一下路子吗？谢谢！）
当然我对C++还是很不了解(我看十天,只了解了那些基本的语法和结构)
难免会出错或考虑不周,还得向大家学习,学习
Top
16 楼chenzhichao2008（陈智超）回复于 2003-11-04 08:46:26 得分 0
template<class type>type queuelink<type>::getqueue()//取队成员
{//assert(!queueempty());
type revalue=front->element;
front=front->next;
return revalue;
}
输出结果是：1 2 3 4 5 6 7 8 9 10
改为：
template<class type>type queuelink<type>::getqueue()//取队成员
{//assert(!queueempty());
queuenode<type>*p=front;
type revalue=p->element;
p=p->next;
return revalue;
}
输出结果：1 1 1 1 1 1 1 1 1 1
奇怪了我只是改了这个怎么会结果不一样了（我觉得这两个的效果应该是一样的呀）
Top
17 楼chenzhichao2008（陈智超）回复于 2003-11-04 08:47:32 得分 0
上面的我是不想移动frontTop
18 楼mmlymlymly（mly）回复于 2003-11-04 09:03:25 得分 5
front没变，所以每次调用getqueue（）p的值都没变=head，就打出第一个节点。
解决方法 static queuenode<type>*p=front;
但是书本上画的图不是front 和rear 指向同一结点吗，头尾不相联何谓循环队列？Top
19 楼mmlymlymly（mly）回复于 2003-11-04 09:06:40 得分 10
给你贴个我以前写的循环队列，参考一下。
queue.h
//this is a circularly linked queue
#include <iostream>
using namespace std;
enum Error_code{success,overflow,underflow};
template<typename type>
struct Node
{
type entry;
Node * next;
Node();
Node(type,Node * add_on=NULL);
};
template<typename type>
inline Node<type>::Node()
{
next=NULL;
}
template<typename type>
inline Node<type>::Node(type item, Node * add_on)
{
entry=item;
next=add_on;
}
template<typename type>
class Queue
{
public:
Queue();
bool empty()const;
bool full()const;
int size()const;
void clear();
Error_code append(const type item);
Error_code serve();
Error_code retrieve(type& item)const;
Error_code serve_and_retrieve(type &item);
void prin()const;
~Queue();
Queue(const Queue &);
void operator = (const Queue &);
protected:
Node<type> * tail;
};
template<typename type>
inline Queue<type>::Queue()
{
tail=NULL;
}
template<typename type>
inline bool Queue<type>::empty() const
{
return (tail==NULL);
}
template<typename type>
inline bool Queue<type>::full()const
{
Node<type> *temp=new Node<type>;
if(temp==NULL) return true;
else
{
delete temp;
temp=NULL;
return false;
}
}
template<typename type>
inline int Queue<type>::size()const
{
Node<type> *temp=tail;
if(!tail) return 0;
int i=1;
while(temp->next!=tail)
{
i++;
temp=temp->next;
}
return i;
}
template<typename type>
inline void Queue<type>::clear ()
{
while(!empty())
serve();
}
template<typename type>
inline Error_code Queue<type>::append(const type item)
{
Node<type> * new_tail=new Node<type>(item);
if(!new_tail) return overflow;
if(!tail)
tail=new_tail;
else
new_tail->next=tail->next;
tail->next=new_tail;
tail=new_tail;
return success;
}
template<typename type>
inline Error_code Queue<type>::serve()
{
if(!tail) return underflow;
Node<type> * old_tail=tail->next;
if (tail->next==tail)
tail=NULL;
else
{
tail->next=old_tail->next;
delete old_tail;
}
return success;
}
template<typename type>
inline Error_code Queue<type>::serve_and_retrieve (type & item)
{
Error_code temp;
retrieve(item);
temp=serve();
return temp;
}
template<typename type>
inline void Queue<type>::prin() const
{
Node<type> * old_tail;
if(!tail) return;
old_tail=tail->next;
while(old_tail!=tail)
{
cout<<old_tail->entry<<endl;
old_tail=old_tail->next;
}
cout<<tail->entry<<endl;
}
template<typename type>
inline Error_code Queue<type>::retrieve (type& item) const
{
if(!tail) return underflow;
item=tail->next->entry;
return success;
}
template<typename type>
inline Queue<type>::Queue(const Queue<type> & original)
{
Node<type> *new_copy ,* original_node=original.tail;
if(!original_node) tail=NULL;
else
{
tail = new_copy =new Node<type>(original_node->entry);
while(original_node->next !=original.tail )
{
original_node=original_node->next ;
new_copy->next =new Node<type>(original_node->entry);
new_copy=new_copy->next ;
}
new_copy->next =tail;
}
}
template<typename type>
inline void Queue<type>::operator = (const Queue & original)
{
Node<type> *new_tail,*new_copy,*original_node=original.tail ;
if(!original_node) new_tail=NULL;
else
{
new_tail=new_copy =new Node<type>(original_node->entry);
while(original_node->next !=original.tail )
{
original_node=original_node->next ;
new_copy->next =new Node<type>(original_node->entry);
new_copy=new_copy->next ;
}
new_copy->next =new_tail;
}
while(!empty())
serve();
tail=new_tail;
}
template<typename type>
inline Queue<type>::~Queue ()
{
while(!empty())
serve();
}
Top
20 楼mmlymlymly（mly）回复于 2003-11-04 09:10:20 得分 5
看了你上面的一些问题，感觉的你的语言基础不很扎实，建议找本好的c++教材，像c++primer好好看看吧，多写多思考，实在想不通的来这问。这高手多，热心人也多：）Top
21 楼chenzhichao2008（陈智超）回复于 2003-11-04 09:42:09 得分 0
但是我有rear->next=front
并不是头尾不想连?Top
22 楼chenzhichao2008（陈智超）回复于 2003-11-04 09:45:38 得分 0
真谢谢你了
我可能过几天才会再来
交个朋友吧
我要回家了Top
23 楼chenzhichao2008（陈智超）回复于 2003-11-04 09:48:45 得分 0
我说的不想移动front
但是我并没有不移动p呀Top
24 楼mmlymlymly（mly）回复于 2003-11-04 11:58:14 得分 0
p是一个局部变量，他在函数结束后就释放了。
因此当你再次进入getqueue（）后p会重新初始化，除非申明为static。
你需要好好补补基础:)Top
25 楼mmlymlymly（mly）回复于 2003-11-04 12:01:09 得分 0
“但是我有rear->next=front
并不是头尾不想连?“
这是一头，从你的头front出发，能找到rear吗？Top
26 楼chenzhichao2008（陈智超）回复于 2003-11-08 17:19:25 得分 0
谢谢你的建议
我到今天才回来
好几天没上了
那天我问的:"我说的不想移动front
但是我并没有不移动p呀"
我知道我问错了
刚发完后原想改一下但是贴子不能连续发三个(也就没改了)
Top
27 楼chenzhichao2008（陈智超）回复于 2003-11-20 10:44:48 得分 0
我还有一个问题请问大家
下面是一个用三元组来表示稀疏矩阵
#include "conio.h"
#include "iostream.h"
template<class type> class sparse;
template<class type> class trituple
{friend class sparse<type>;
protected:
int row,col;
type value;
public:
trituple(int r,int c,type data):row(r),col(c),value(data){}
~trituple(){};
};
template<class type> class sparse
{protected:
int rows,cols,terms;
trituple<type> **arr;
public:
//sparse(&t);
sparse(int r,int c,int ter);
~sparse()
{for(int i=0;i<terms;i++)
delete arr[i];
}
sparse<type> transpose();
void build();
void display();
//sparse<type>add(sparse<type>b);
//sparse<type>multip(sparse<type>b);
};
template<class type>
sparse<type>::sparse(int r,int c,int ter)
{rows=r,cols=c,terms=ter;
arr=NULL;
// for(int i=0;i<terms;i++)
// arr[i]=new trituple<type>(0,0,type(0));
}
//template<class type>
//sparse<type>::sparse(&t)
// {}
template<class type>
void sparse<type>::build()
{int r,c;
type val;
for(int i=0;i<terms;i++)
{cout<<"please input row ,col and value"<<endl;
cin>>r>>c>>val;
if(r>rows||c>rows)
{cout<<"error,please input again"<<endl;i--;continue;}
arr[i]= new trituple<type>(r,c,val);
}
}
template<class type>
void sparse<type>::display()
{for(int i=0;i<terms;i++)
cout<<arr[i]->row<<"\t"<<arr[i]->col<<"\t"<<arr[i]->value<<endl;
getch();
}
template<class type>
sparse<type> sparse<type>::transpose()//矩阵转置
{
sparse<type>b(cols,rows,terms);
if(terms>0)
{b.rows=cols;
b.cols=rows;
b.terms=terms;
//如果在这边加一句b.display();//转置前
//则显示结果与转置前的obj.display()相同(这是不是证明对象obj 与 b同用一个空间
int j=0;
for(int k=0;k<cols;k++)
for(int i=0;i<terms;i++)
{
if(arr[i]->col==k)
{b.arr[i]->row=arr[i]->col;
b.arr[j]->col=arr[i]->row;
b.arr[j]->value=arr[i]->value;
j++;
}
}
}
cout<<"_________________________________"<<endl;
b.display();//转置后//
//问题一:这边的转置为什么不成功(我的观点是对象b与obj占用同一空间)
getch();
return b;
}
void main()
{int ro,co,ma;
clrscr();
cout<<"please input rows , cols,terms"<<endl;
cin>>ro>>co>>ma;
sparse<int> obj(ro,co,ma);
obj.build();
obj.display();//转置前
obj=obj.transpose();
obj.display();//转置后
}
问题一:这边的转置为什么不成功(我的观点是对象b与对象obj占用同一空间)
如果真的占用同一空间那该如何处理(是不是应该写一个拷贝构造函数的)
问题二:
转置后的b.display();与转置后的obj.display();为什么结果不同
问题三:
假设我们定义了
trituple<type> *arr;
然后要为arr申请空间
arr=new trituple<type>[terms]
这样为什么不行(我的观点:用new 时要调用构造函数)
是不是要改为:// for(int i=0;i<terms;i++)
// arr[i]=trituple<type>(0,0,type(0));
还有更好的修改方法吗?
谢谢!!!!!
Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
