求各位帮忙写一个数据结构用C语言实现的程序 - C语言论坛

得分:20

你的意图我看不明白。不过你看了我写的，你应该会写出自己想要的程序。
队列
队列（Queue）也是一种运算受限的线性表。它只允许在表的一端进行插入，这端称之为队尾（Rear）；而在另一端进行删除，这端称之为队头（Front ）。当表中没有元素时称为空队列。插入运算称入队，删除运算称出队。队列的修改是按先进先出的原则进行的，故队列又称为先进先出(First In First Out)的线性表,简称FIFO表。
队列的基本运算也有六种：
置空队，构造一个空队列Q。InitQueue(Q)
判队空，队空返真值，否则返假值。QueueEmpty(Q)
判队满，满则返真值，否则返假值。只适用于队列的顺序存储结构。QueueFull(Q)
入队，若队列Q非满，则将元素x插入Q的队尾。EnQueue(Q,x)
出队，若队列Q非空，则删去Q的队头元素，并返回该元素。DeQueue(Q)
返回队头元素，若队列Q非空，则返回队头元素，但不改变队列状态。QueueFront(Q)
顺序队列
队列的顺序存储结构称为顺序队列，顺序队列也是运算受限的顺序表。
顺序队列也必须用一个向量空间来存放当前队列中的元素。因为出队入队操作使队头队尾位置发生变化，所以要设头指针front指向队头，尾指针rear指向队尾的下一个位置。队列初始化时这两个指针均应置0，入队时将元素插入rear所指位置，rear加1；出队时将front所指位置上的元素删除，front加1。这样下去这两个指针都可能指向向量的最后一个元素空间以下而产生“假上溢”现象。
为充分利用向量空间，克服“假上溢”现象，将向量空间想像为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue）。除一些简单应用外，真正实用的顺序队列是循环队列。
在循环队列中进行出队入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向上界时，其加1操作的结果是指向向量的下界0。即：
if (i+1==QueueSize)//i表示front或rear
    i=0;
else
    i++;
利用“模运算”可将上述操作简化：i=(i+1)%QueueSize;
队空队满时头尾指针均相等，无法通过front==rear来判别队列是空是满。解决此问题至少有三，这里我们只谈其中的一种方法：使用一个计数器记录队列中元素的总数。
循环队列的类型定义
#define QueueSize 100
typedef char DataType;
typedef Struct
{
    int front;      //头指针，队非空时指向队头元素
    int rear;       //尾指针，队非空时指向队尾元素的下一位置
    int count;    // 计数器，记录队中元素总数
    DataType data[QueueSize];
} CirQueue;
置空队
void InitQueue(CirQueue *Q){Q->front= Q->rear=0; Q->count=0;}
判队空
int QueueEmpty(CirQueue *Q){return Q->count==0;}
判队满
int QueueFull(CirQueue *Q){return Q->count== QueueSize;}
入队
void EnQueue(CirQueue *Q,DataType x)
{
    if (QueueFull(Q))Error(“Queue overflow”);
    Q->count++;
    Q->data[Q->rear]=x;
    Q->rear=( Q->rear+1) %QueueSize; //循环意义下将尾指针加1
}
出队
DataType DeQueue(CirQueue *Q)
{
    DataType x;
    if (QueueEmpty(Q)Error(“Queue underflow”);
    Q->count--;
    x=Q->data[Q->front];
    Q->front=( Q->front+1)%QueueSize; //循环意义下将头指针加1
    return x;
}
取队头元素
DataType QueueFront(CirQueue *Q)
{
    if (QueueEmpty(Q)) Error(“Queue is empty”);
    return Q->data[Q->front];
}
链队列
队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。跟顺序队列类似，链队列也必须用一个头指针和一个尾指针惟一地确定。头指针指向队头结点，而尾指针不向顺序队列中的那样指向队尾元素的下一个位置，而是指向队尾结点。
链队列的类型定义
typedef struct queuenode
{//链队列中的结点类型
    DataType data;
    struct queuenode *next;
}QueueNode;
typedef struct
{
    QueueNode *front;//队头指针
    QueueNode *rear;//队尾指针
}LinkQueue;
和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，但这里我们只讨论不加头结点的情况。
下面是链队列上实现的基本运算，和链栈类似，无须考虑判队满的运算及上溢。
置空队
void InitQueue(LinkQueue *Q){Q->front=Q->rear=NULL;}
判队空
int QueueEmpty(LinkQueue *Q)
{
    return Q->front==NULL&&Q->rear==NULL;
    //实际上只须判队头指针是否为空即可
}
入队：将元素x插入链队列尾部
void EnQueue(LinkQueue *Q,DataType x)
{
    QueueNode *p=( QueueNode *)malloc(sizeof(QueueNode));
    p->data=x;p->next=NULL;
    if(QueueEmpty(Q))
        Q->front=p;
    else
        Q->rear->next=p;
    Q->rear=p;
}
出队
DataType DeQueue(LinkQueue *Q)
{
    if (QueueEmpty(Q))Error(“Queue underflow”);
    QueueNode *p= Q->front;
    if (Q->rear== Q->front) //有且仅有一个结点时
        Q->rear=NULL;
    Q->front= Q->front->next;
    DataType x=p->data;
    free(p);
    return x;
}
取队头元素
DataType QueueFront(LinkQueue *Q)
{
    if (QueueEmpty(Q))Error(“Queue is empty.”);
    return Q->front->data;
}

我学编程，总爱用自己的语言将所学的东西描述下来，渐渐的，一篇篇的文章，看起来像一个个杰作。