一个链队列问题调试了很久。就是没有找到错。请教大家一下。
/*
1. 链队列的初始化
2. 链队列的销毁
3. 链队列的进队
4. 链队列的出队
*/
#include "stdio.h "
#include "malloc.h "
#include "conio.h "
#include "process.h "
#include "alloc.h "
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue *Q)/*链队列的初始化*/
{
Q-> front=Q-> rear=(QueuePtr)malloc(sizeof(QNode));/*??(QueuePtr)malloc(sizeof(QNode))*/
if(!Q-> front) exit(OVERFLOW);
return OK;
}
Status DestroyQueue(LinkQueue *Q)/*链队列的销毁*/
{
while(Q-> front)
{
Q-> rear=Q-> front-> next;
free(Q-> front);
Q-> rear=Q-> front;
return OK;
}
}
Status EnQueue(LinkQueue *Q,QElemType e)/*链队列的进队*/
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p-> data=e;
p-> next=NULL;
Q-> rear-> next=p;
Q-> rear=p;
return OK;
}
Status DelQueue(LinkQueue *Q,QElemType *e)/*链队列的出队*/
{
if(Q-> rear==Q-> front) return ERROR;
QueuePtr p;
/*tc2.0 说 你用了不合适的typedef 符号 错误停留在这个地方。就没有办法往下看了*/
p=Q-> front-> next;
*e=p-> data;
Q-> front-> next=p-> next;
free(p);
return OK;
}
void Queueprintf(LinkQueue *Q)
{
if(Q-> rear==Q-> front)
printf( "hello! your LinkQueue is empty!!! ");
else
{
QueuePtr p;
int i=1;
p=Q-> front;
printf( "output LinkQueue 's QElemtypes ");
p=p-> next;
while(p)
{
printf( " %d=%c\n ",i++,p-> data);
p=p-> next;
}
}
}
int main()
{
QElemType e;
LinkQueue Q;
InitQueue(&Q);
Queueprintf(*Q);
printf( " 1..now,LinkQueue initial is OK ***\n\n ");
printf( " 2..now,LinkQueue EnQueue five QElemtype..\n\n ");
e= 'A ';
EnQueue(&Q,e);
e= 'B ';
EnQueue(&Q,e);
e= 'C ';
EnQueue(&Q,e);
e= 'D ';
EnQueue(&Q,e);
Queueprintf(*Q);
printf( " 3..let 's DelQueue two QElemtype.\n\n ");
printf( " Del the frist QElemtype.\n ");
DelQueue(*Q,*e);
Queueprintf(*Q);
getchar();
printf( " Del the second QElemtype.\n ");
DelQueue(*Q,*e);
Queueprintf(*Q);
printf( " now Del operate have done\n\n ");
getch();
printf( " 4..we dislike it,so let 's DestroyQueue LinkQueue\n ");
DestroyQueue(*Q);
Queueprintf(*Q);
getchar();
printf( " ***demo end***\n ");
getchar();
}
--------------------------------------
请教大家一下 要如何改?我什么地方写错了,还有什么地方需要改进?
谢谢。
[解决办法]
Status DestroyQueue(LinkQueue *Q)/*链队列的销毁*/
{
while(Q-> front)
{
Q-> rear=Q-> front-> next;
free(Q-> front); <-------------
Q-> rear=Q-> front;
return OK;
}
}
箭头指的行执行后,Q-> front指向的内存已经被释放了,再把这个无效的地址给你的队列尾部是什么意思?
------解决方案--------------------
有空再帮你调试看看吧,看看这个:
#include "stdio.h "
#include "conio.h "
typedef struct gp
{
int num;
struct gp* next;
struct gp* prev;
} Group;
Group* pHead = 0;/*链表头*/
Group* pTail = 0;/*链表尾*/
int Size_Group = 0;/*链表节点数目*/
/*清空队列*/
int ClearGroup()
{
Group* nod = 0;
while(pHead)
{
nod = pHead;
pHead = pHead-> next;
free(nod);
}
pTail = 0;
Size_Group = 0;
return 0;
}
/*新队列*/
int NewGroup()
{
if(pHead)
{
ClearGroup();
}
pHead = pTail = 0;
Size_Group = 0;
}
/*入队*/
int InGroup(int i)
{
Group* nod = 0;
Size_Group++;
if(!pHead)
{
pHead = (Group*)malloc(sizeof(Group));
pHead-> num = i;
pHead-> next = 0;
pTail = pHead;
return 0;
}
nod = (Group*)malloc(sizeof(Group));
nod-> num = i;
pTail-> next = nod;
nod-> prev = pTail;
pTail = nod;
pTail-> next = 0;
return 0;
}
/*出队*/
int OutGroup()
{
Group* nod = 0;
int i;
if(pHead == 0 || Size_Group == 0)
return -1;
if(pHead == pTail || Size_Group == 1)
pTail = 0;
nod = pHead;
pHead = pHead-> next;
i = nod-> num;
free(nod);
Size_Group--;
return i;
}
/*输出队列*/
int DispGroup()
{
Group* nod1 = 0;
printf( "\n ");
printf( "S[%d]\t ", Size_Group);
printf( "H:%d\t ", pHead-> num);
printf( "T:%d\t\t ", pTail-> num);
if(pHead == 0 || Size_Group == 0)
return 0;
nod1 = pHead;
while(nod1)
{
printf( "%d| ", nod1-> num);
nod1 = nod1-> next;
}
printf( "\t ");
nod1 = pTail;
while(nod1 != pHead)
{
printf( "=%d ", nod1-> num);
nod1 = nod1-> prev;
}
printf( "=%d ", nod1-> num);
printf( "\n ");
return 0;
}
main()
{
int i;
NewGroup();
DispGroup();
for(i = 0; i < 2; ++i)
{
InGroup(i + 1);
DispGroup();
}
NewGroup();
DispGroup();
for(i = 0; i < 5; ++i)
{
InGroup(i + 1);
DispGroup();
}
for(i = 0; i < 5; ++i)
{
OutGroup();
DispGroup();
}
for(i = 0; i < 1; ++i)
{
InGroup(i + 1);
DispGroup();
}
ClearGroup();
DispGroup();
getch();
}
[解决办法]
C++ 版:
// queue.h
#ifndef Queue_
#define Queue_
#include <stdlib.h>
#include <iostream>
#include "xcept.h "
template <class T>
class Queue {
// FIFO objects
public:
Queue(int MaxQueueSize = 10);
~Queue() {delete [] queue;}
bool IsEmpty() const { return front == rear; }
bool IsFull() const { return (((rear + 1) % MaxSize == front) ? 1 : 0); }
T First() const; // return front element
T Last() const; // return last element
Queue <T> & Add(const T& x);
Queue <T> & Delete(T& x);
private:
int front; // one counterclockwise from first
int rear; // last element
int MaxSize; // size of array queue
T *queue; // element array
};
template <class T>
Queue <T> ::Queue(int MaxQueueSize)
{
// Create an empty queue whose capacity
// is MaxQueueSize.
MaxSize = MaxQueueSize + 1;
queue = new T[MaxSize];
front = rear = 0;
}
template <class T>
T Queue <T> ::First() const
{
// Return first element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return queue[(front + 1) % MaxSize];
}
template <class T>
T Queue <T> ::Last() const
{
// Return last element of queue. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return queue[rear];
}
template <class T>
Queue <T> & Queue <T> ::Add(const T& x)
{
// Add x to the rear of the queue. Throw
// NoMem exception if the queue is full.
if (IsFull()) throw NoMem();
rear = (rear + 1) % MaxSize;
queue[rear] = x;
return *this;
}
template <class T>
Queue <T> & Queue <T> ::Delete(T& x)
{
// Delete first element and put in x. Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
front = (front + 1) % MaxSize;
x = queue[front];
return *this;
}
#endif
===========================================
// xcept.h
#ifndef Xcept_
#define Xcept_
#include <new.h>
// bad initializers
class BadInitializers {
public:
BadInitializers() {}
};
// insufficient memory
class NoMem {
public:
NoMem() {}
};
// change new to throw NoMem instead of standard behavior
// Visual C++ requires following form of my_new_handler
int my_new_handler(size_t x)
{
throw NoMem();
// even though the following statement is unreachable,
// visual C++ will not compile successfully without it
return 0;
};
_PNH Old_Handler_ = _set_new_handler(my_new_handler);
// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
public:
OutOfBounds() {}
};
// use when operands should have matching size
class SizeMismatch {
public:
SizeMismatch() {}
};
// use when zero was expected
class MustBeZero {
public:
MustBeZero() {}
};
// use when zero was expected
class BadInput {
public:
BadInput() {}
};
#endif
[解决办法]
贴一个以前写的作参考
/*=============================================================
*********************使用链表形成的队列************************
=============================================================*/
#ifndef _LINKEDQUEUE_H
#define _LINKEDQUEUE_H
#include <exception>
template <class T>
class LinkedQueue;
//---------------------
template <typename T>
class Node
{
friend LinkedQueue <T> ; //使用前LinkedQueue必须先声明
private:
T data;
Node <T> *link;
};
//---------------------
template <class T>
class LinkedQueue
{
// FIFO对象
public:
LinkedQueue() {front = rear = 0;} // 构造函数
~LinkedQueue(); // 析构函数
bool IsEmpty() const
{return ((front) ? false : true);}
bool IsFull() const;
T First() const; // 返回第一个元素
T Last() const; // 返回最后一个元素
LinkedQueue <T> & Add(const T& x);
LinkedQueue <T> & Delete(T& x);
//自定义的异常处理类
public:
class NoMem:public std::exception
{
public:
virtual const char* what() const throw()
{
return "there is no memory! ";
}
};
class OutOfBounds:public std::exception
{
public:
virtual const char* what() const throw()
{
return "out of bound! ";
}
};
private:
Node <T> *front; // 指向第一个节点
Node <T> *rear; //指向最后一个节点
};
//-----------------------
template <class T>
LinkedQueue <T> :: ~LinkedQueue( )
{// 队列析构函数,删除所有节点
Node <T> *next;
while(front)
{
next=front-> link;
delete front;
front=next;
}
}
//------------------------
template <class T>
bool LinkedQueue <T> ::IsFull() const
{// 判断队列是否已满
Node <T> *p;
try
{
p=new Node <T> ;
delete p;
return false;
}
catch (NoMem)
{return true;}
}
//--------------------------
template <class T>
T LinkedQueue <T> ::First() const
{// 返回队列的第一个元素
// 如果队列为空,则引发异常OutOfBounds
if(IsEmpty())
throw OutOfBounds();
return front-> data;
}
//-------------------------
template <class T>
T LinkedQueue <T> ::Last() const
{// 返回队列的最后一个元素
// 如果队列为空,则引发异常OutOfBounds
if(IsEmpty())
throw OutOfBounds();
return rear-> data;
}
//-------------------------
template <class T>
LinkedQueue <T> & LinkedQueue <T> ::Add(const T& x)
{// 把x 添加到队列的尾部
// 不捕获可能由n e w引发的NoMem 异常
// 为新元素创建链表节点
Node <T> *p = new Node <T> ;
p-> data=x;
p-> link=0;
// 在队列尾部添加新节点
if(front)
rear-> link=p; //队列不为空
else
front=p; // 队列为空
rear=p;
return *this;
}
//-------------------------
template <class T>
LinkedQueue <T> & LinkedQueue <T> ::Delete(T& x)
{
// 删除第一个元素,并将其放入x
// 如果队列为空,则引发异常OutOfBounds
if(IsEmpty())
throw OutOfBounds();
//保存第一个节点中的元素
x=front-> data;
// 删除第一个节点
Node <T> *p=front;
front=front-> link;
delete p;
return *this;
}
//------------------------
#endif
[解决办法]
Q-> rear=Q-> front-> next;
free(Q-> front);
Q-> rear=Q-> front;
---------
Q-> rear=Q-> front-> next;
Q-> rear=Q-> front;
free(Q-> front);
[解决办法]
问题是在Status DelQueue(LinkQueue *Q,QElemType *e)/*链队列的出队*/ 中的
1. QueuePtr p;
2.if(Q-> rear==Q-> front) return ERROR;
把他们的顺序调换一下竟然通不过编译.
大家是怎么想的?请教一下???
=============================
我记得tc2.0变量声明必须位于所有语句之前。在现在的gcc/cl.exe上应该可以
tc2.0版权是1987年我记得
:)