【数据结构】 链队列的基本操作 （C语言版）

发布时间：2024年01月24日

目录

一、链队列

1、链栈的定义：

2、链栈的优缺点：

二、链队列的基本操作算法（C语言）????

1、宏定义

??2、创建结构体

3、链栈的初始化?

4、链队列的入队?

5、链队列的出队

6、取链队列的对头元素

7、链队列的销毁

8、链队列的清空

9、判断链队列是否为空

10、求队列长度

?11、遍历队列元素

三、链队列的基本操作完整代码（C语言）

??四、运行结果

一、链队列

1、链栈的定义：

链队列是一种线性数据结构，采用链表来实现队列的操作。链队列具有队头指针和队尾指针，用于指示队列元素所在的位置。链队列只允许在队尾插入元素，在队头删除元素，符合先进先出（First In First Out，FIFO）的原则。

2、链栈的优缺点：

链队列的优点：

  1. 动态分配空间：链队列使用链表实现，可动态分配和释放空间。因此，不需要预先分配大量存储空间，可以根据实际需求进行空间分配。
  2. 无需移动元素：相比普通队列，链队列在删除元素时无需移动大量元素，只需修改指针即可。这使得链队列在处理大规模数据时具有更高的效率。
  3. 适合处理用户排队等待的情况：链队列适用于处理用户排队等待的情况，例如银行排队、网络请求等。通过链队列，可以快速地插入新用户和删除已处理的用户。

链队列的缺点：

  1. 需要额外的存储空间：为了实现链表结构，链队列需要额外的存储空间来维护指针和节点。这会增加存储空间的消耗。
  2. 插入和删除操作可能引起内存分配和释放：在链队列中插入和删除元素时，可能需要动态分配和释放内存。这会增加操作的时间复杂度，并可能引起内存碎片化问题。
  3. 无法充分利用连续空间的优势：链表结构使得链队列无法像数组一样充分利用连续空间的优势，这会影响空间利用率和访问速度。

二、链队列的基本操作算法（C语言）????

1、宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemtype;
typedef int Status;
??2、创建结构体
//创建结构体
typedef struct QNode {
    QElemtype data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;
3、链栈的初始化?
//链队列的初始化
Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q.front) {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}
4、链队列的入队?
//链队列的入队 
Status EnQueue(LinkQueue &Q, QElemtype e) {
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}
5、链队列的出队
//链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    delete p;
    return OK;

}
6、取链队列的对头元素
//取链列的对头元素 
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;

}
7、链队列的销毁
//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        delete (Q.front);
        Q.front = Q.rear;
    }
//    printf("销毁成功！");
    return OK;
}
8、链队列的清空
//清空
Status ClearQueue(LinkQueue &Q) {
    Q.rear = Q.front->next;
    while (Q.front->next) {
        Q.rear = Q.rear->next;
        delete (Q.front->next);
        Q.front->next = Q.rear;
    }
    Q.rear = Q.front;
//    printf("清空成功！");
    return OK;
}
9、判断链队列是否为空
//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
//        printf("队列为空！\n");
        return true;
    } else {
        return false;
    }
//    printf("该队列不为空！");
}
10、求队列长度
//求队列长度
Status QueueLength(LinkQueue Q) {
    int i = 0;
    while (Q.front != Q.rear) {
        i++;
        Q.front = Q.front->next;
    }
//    printf("该队列长度为：%d", i);
    return i;
}
?11、遍历队列元素
//遍历队列
Status QueueTraverse(LinkQueue Q) {
    QNode *p;
    if (Q.front == Q.rear) {
        return ERROR;
    }
    p = Q.front->next;//存储头元素
    printf("从队头依次读出该队列中的元素值为: ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

三、链队列的基本操作完整代码（C语言）

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemtype;
typedef int Status;

//创建结构体
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));
    if (!Q.front) {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}

//链队列的入队 
Status EnQueue(LinkQueue &Q, QElemtype e) {
    QueuePtr 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 DeQueue(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    delete p;
    return OK;

}

//取链列的对头元素 
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;

}


//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        delete (Q.front);
        Q.front = Q.rear;
    }
//    printf("销毁成功！");
    return OK;
}

//清空
Status ClearQueue(LinkQueue &Q) {
    Q.rear = Q.front->next;
    while (Q.front->next) {
        Q.rear = Q.rear->next;
        delete (Q.front->next);
        Q.front->next = Q.rear;
    }
    Q.rear = Q.front;
//    printf("清空成功！");
    return OK;
}


//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
//        printf("队列为空！\n");
        return true;
    } else {
        return false;
    }
//    printf("该队列不为空！");
}

//求队列长度
Status QueueLength(LinkQueue Q) {
    int i = 0;
    while (Q.front != Q.rear) {
        i++;
        Q.front = Q.front->next;
    }
//    printf("该队列长度为：%d", i);
    return i;
}


//遍历队列
Status QueueTraverse(LinkQueue Q) {
    QNode *p;
    if (Q.front == Q.rear) {
        return ERROR;
    }
    p = Q.front->next;//存储头元素
    printf("从队头依次读出该队列中的元素值为: ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}


//功能菜单列表
void show_help() {
    printf("******* 功能菜单列表 *******\n");
    printf("1----入队------------------\n");
    printf("2----求链队列长度----------\n");
    printf("3----出队------------------\n");
    printf("4----取队头元素-------------\n");
    printf("5----清空循环队列-----------\n");
    printf("6----销毁循环队列-----------\n");
    printf("7----判断循环队列是否为空-----\n");
    printf("8----批量插入元素------------\n");
    printf("9----显示队列元素------------\n");
    printf("10----退出------------------\n\n");
}


//主函数
int main() {
    LinkQueue LQ;
    Status reIn = InitQueue(LQ);
    if (reIn == OK) {
        printf("链队列初始时成功  \n");
    } else {
        printf("链队列初始时失败 \n");
    }

    while (1) {

        //功能菜单列表
        show_help();

        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d", &flag);

        switch (flag) {
            case 1: {//入队
                Status EnQueueindex;
                printf("请输入插入元素(请在英文状态下输入例如:1): \n");
                scanf("%d", &EnQueueindex);
                Status rEnQueue = EnQueue(LQ, EnQueueindex);
                if (rEnQueue == OK) {
                    printf("向链队列入队%d成功！\n", EnQueueindex);
                } else {
                    printf("向链队列入队失败！\n");
                }
            }
                break;
            case 2: {//求链队列的长度
                int length = QueueLength(LQ);
                printf("链队列的长度为:%d。 \n\n", length);
            }
                break;
            case 3: {//出队
                QElemtype DeElem;
                Status DeEn = DeQueue(LQ, DeElem);
                if (DeEn == OK) {
                    printf("从链队列中出队成功，出队的元素为 %d! \n", DeElem);
                } else {
                    printf("从链队列中出队失败！\n");
                }
            }
                break;
            case 4: {//求队头元素
                QElemtype getEl;
                Status reGet = GetQueueHead(LQ, getEl);
                if (reGet == OK) {
                    printf("从链队列中取对头元素成功，队头元素为:%d! \n", getEl);
                } else {
                    printf("从链队列中取对头元素成功 \n");
                }
            }
                break;
            case 5: { //清空
                Status rClearStack = ClearQueue(LQ);
                if (rClearStack == OK) {
                    printf("链队列清空成功！\n");
                } else {
                    printf("链队列清空失败！\n");
                }
            }
                break;
            case 6: {//销毁
                Status rDestroyStack = DestoryQueue(LQ);
                if (rDestroyStack == OK) {
                    printf("链队列销毁成功！\n");
                } else {
                    printf("链队列销毁失败！\n");
                }
            }
                break;
            case 7: {///判空
                Status ClearStatus = QueueEmpty(LQ);
                if (ClearStatus == true) {
                    printf("链队列为空！\n\n");
                } else {
                    printf("链队列不为空！\n\n");
                }
            }
                break;
            case 8: {//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                QElemtype array[on];
                for (int i = 1; i <= on; i++) {
                    printf("向链队列第%d个位置插入元素为:", i);
                    scanf("%d", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status InsertStatus = EnQueue(LQ, array[i]);
                    if (InsertStatus == OK) {
                        printf("向链队列第%d个位置插入元素%d成功！\n", i, array[i]);
                    } else {
                        printf("向链队列第%d个位置插入元素%d失败！\n", i, array[i]);
                    }
                }
            }
                break;
            case 9: {//输出链表元素
                QueueTraverse(LQ);
//                printf("\n");
            }
                break;
            case 10: {//退出程序
                return 0;
            }
                break;
            default: {
                printf("输入错误，无此功能，请检查输入:\n\n");
            }
        }
    }


    return 1;
}

??四、运行结果

文章来源:https://blog.csdn.net/weixin_56814370/article/details/135831656
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章