22计算机408考研—数据结构—线性表、栈、队列、数组

2022计算机考研408—数据结构—线性表、栈、队列、数组
手把手教学考研大纲范围内的线性表、栈、队列、数组
22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，
如有什么建议或者不足欢迎大佬评论区或者私信指出

Talk is cheap. Show me the code.
理论到处都有，代码加例题自己练习才能真的学会

顺序表
链表
双向循环链表后面附：顺序表链表区别
栈
栈实现括号问题
循环链栈表
递归斐波那契
递归汉诺塔
循环队列
链队（链式队列）

顺序表

官方含义：一段地址连续的存储单元依次存储线性表的数据元素。
其实就相当于数组，`把顺序表当数组看`最简单了

  // 顺序表#include <iostream>
#include "string.h"
#define MAXSIZE 1001using namespace std;typedef struct {    //定义学生结构体，包含学号和姓名char ID[20];char name[50];
} Student;typedef struct {    //定义线性表，和长度属性Student *elem;int length;
} StuList;bool ListInit(StuList &L) { //初始化线性表L.elem = new Student[MAXSIZE];  //给数组分配空间长度if (!L.elem) {  //如果没分配成功，就返回失败return false;}L.length = 0;   //初始化线性表后长度为0return true;
}//插入的时候需要注意把这一位后面的，每个都后移一位，然后把数据放到空出来的那位
bool ListInsert(StuList &L, int i, Student stu) {   //把Student类型插入到序列为i的位置if (i < 0 || i > L.length + 1) {    //判断插入位置是否正确return false;}if (L.length == MAXSIZE) {  //如果插入位置到达最大值，无法插入return false;}for (int j = L.length - 1; j >= i - 1; j--) {   //把i以后元素都向后移动一位，L.elem[j + 1] = L.elem[j];}L.elem[i - 1] = stu;    //把将要插入的放到指定位置++L.length;             //线性表长度+1return true;
}
//也是和插入的时候一样，把i后面的都向前移动一位
bool ListDelete(StuList &L, int i) {    //删除序列为i的元素if (i < 1 || i > L.length) {return false;}for (int j = i; j < L.length; j++) {    //把序列i以后的元素全部前移一位，盖住了序列为i的那位L.elem[j - 1] = L.elem[j];}--L.length;     //线性表长度-1return true;
}bool ListGetStu(StuList &L, int i, Student &s) {    //返回序列为i的元素if (i < 1 || i > L.length) {return false;}s = L.elem[i - 1];return true;
}int ListGetIndex(StuList &L, Student s) {   //找到与s相等的元素的下标for (int i = 0; i < L.length; i++) {if (strcmp(L.elem[i].ID , s.ID) && strcmp(L.elem[i].name , s.name)) {return i + 1;}}return 0;
}void ListMerge(StuList &A, StuList B) { //把B表中A表没有的元素插入到A表后面int a = A.length, b = B.length;for (int i = 0; i < B.length; i++) {if (!ListGetIndex(A, B.elem[i])) {  //A表中是否存在B.elem[i]ListInsert(A, ++a,B.elem[i]);}}A.length = a;   //a代表新线性表的大小，初始为A线性表大小，后面每次插入到A线性表一个值，a++
}void ListaddAll (StuList &A, StuList B) {   //把B线性表插入到A线性表后面int a = A.length, b = B.length;for (int i = 0; i < B.length; i++) {ListInsert(A, ++a,B.elem[i]);}A.length = a;
}int main() {StuList demo;ListInit(demo);Student student = {"123", "张三"};Student student2 = {"456", "李三"};ListInsert(demo, 1, student);ListInsert(demo, 2, student2);cout << student2.ID << student2.name << "\n";ListGetStu(demo, 1, student2);cout << student2.ID << student2.name << "\n";cout << ListGetIndex(demo, student) << "\n";ListMerge(demo, demo);ListaddAll(demo, demo);cout << demo.length;return 0;
}

在这里插入图片描述

链表

链表和顺序表其实是差不多的
顺序表在访问下一个的时候是用下标访问
链表访问下一个只能通过结构体中的指针

插入，删除的时候不需要改变其他元素，只需要修改指定元素前后元素的指针即可

//此链表的index为序列号从1开始    ！！！！不是下标
//此链表多处用到new ，建议大家删一个new调试一下，就能了解到new和不用new的区别了#include "iostream"
#include "vector"using namespace std;typedef struct LNode {  //LNode类型 包含一个int值和一个指针指向下一个地址int data;struct LNode *next;
} LNode, *LinkList;bool ListInit(LinkList &L, int val) {   //初始化链表，要给一个初始值当作链表头节点L = new LNode;L->next = NULL;L->data = val;return true;
}bool ListInsertE(LinkList &L, int val) {    //添加一个元素到链表尾端LNode *headL = new LNode;   //保存一下链表当前的位置headL = L;while (L->next) {   //循环到L最后面，然后把当前值给L的下一个L = L->next;}LNode *temp = new LNode;    //new一个结点，如果不new可能会使用上一个temp结点temp->data = val;temp->next = NULL;L->next = temp;L = headL;  //链表的头位置给L
}bool ListInsert(LinkList &L, int index, int val) {  //插入到链表的序列index（注意不是下标）位置LNode *headL = new LNode;   //保存头位置的上一个（headL的下一个是头位置）headL->next = L;            //这里不保存头位置，    防止添加第一个位置时，链表会添加到第二个位置int j = 0;while (headL && j < (index - 1)) {      //找到第index个位置j++;headL = headL->next;}if (!headL || index < 1) {return false;}LNode *temp = new LNode;    //new一个结点，（不new可能会用到上一个结点）temp->data = val;temp->next = headL->next;   //把headL的下一个结点给temp的下一个结点headL->next = temp;         //把temp给headL的下一个结点     现在temp的下一个就是原headL的下一个结点，相当于把temp插入到了里面L = headL->next;return true;
}bool ListDelete(LinkList &L, int index) {   //删除指定序列index的值LNode *headL = new LNode;LNode *tempL = new LNode;tempL->next = L;            //tempL的下一个是头节点（防止删除第一个结点出现问题）headL = tempL;              //保存头结点的上一个，就是tempLint j = 0;while (tempL && j < (index - 1)) {  //找到序列index的结点tempL = tempL->next;j++;}if (!tempL) {   //如果tempL为NULL，直接退出，没有要删除的结点return false;}tempL->next = tempL->next->next;    //tempL的下一个的下一个给下一个   相当于下一个会被直接盖住（删除了下一个   ）L = headL->next;    //把头结点给L
}bool ListGetElem(LinkList L, int index, int &val) {     //找到知道序列index的值，传送给valint j = 0;while (L && j < (index - 1)) {  //找到序列为index的值L = L->next;j++;}if (!L) {       //如果L为空，直接退出，没有此节点return false;}val = L->data;return true;
}int ListGetIndex(LinkList L, int val) {     //通过值找到指定序列下标int index = 1;while (L->data != val) {L = L->next;index++;}if (!L) {return 0;}return index;
}void ListCreateH(LinkList &L, vector<int> num) {    //前插法创建节点（num数组的值创建链表）L = new LNode;L->next = NULL;for (int i = 0; i < num.size(); i++) {LNode *p = new LNode;p->data = num[i];p->next = L->next;  //每次把L的下一个给p的下一个L->next = p;        //然后把p给L的下一个    p的下一个是原来L的下一个}L = L->next;    //L的下一个才是num数组创建的第一个值
}void ListCreateE(LinkList &L, vector<int> num) {    //前插法创建节点（num数组的值创建链表）L = new LNode;LNode *headL = new LNode;headL = L;L->next = NULL;for (int i = 0; i < num.size(); i++) {LNode *p = new LNode;p->data = num[i];p->next = NULL;L->next = p;    //当前指针p给L的下一个L = p;          //把p给L     p的上一个就是原L}L = headL->next;    //头结点的下一个才是num创建的第一个结点
}void ListPrint(LinkList L) {    //输出链表各个的值while (L) {cout << L->data << " ";L = L->next;}cout << "\n";
}
int main() {vector<int> num = {1,2,3,4,5};LinkList temp;
//    ListCreateE(temp, num);
//    ListPrint(temp);
//    ListCreateH(temp, num);
//    ListPrint(temp);ListInit(temp, 10);     //创建List链表ListInsertE(temp, 10);  //尾端插入值ListInsertE(temp, 10);ListPrint(temp);ListInsert(temp, 1, 20);    //插入一个值 到序列index位置ListPrint(temp);ListDelete(temp, 3);            //删除链表中序列index的值ListPrint(temp);int val;ListGetElem(temp, 3, val);      //通过序列index找到值，传给valcout << val << "\n";ListPrint(temp);cout << ListGetIndex(temp, 2) << "\n";  //通过值找到序列index}

在这里插入图片描述

双向循环链表

双向循环链表和单链表也是大致相同的
只是在修改结点的关系的时候需要修改每个结点的前后节点

//循环链表
#include "iostream"
#include "vector"using namespace std;typedef struct DuLNode {    //结点，每个结点有一个值，int data;               //每个结点包括两个指针，一个指向前一个结点，一个指向后一个结点struct DuLNode *prior;  //指定当前结点的前一个结点struct DuLNode *next;   //指定当前结点的后一个结点
} DuLNode, *DuLinkList;bool ListInitDul(DuLinkList &L, vector<int> data) { //初始化双指针循环链表DuLNode *headL = new DuLNode;   //记录一下头结点，初始化结束后，把头结点重新赋值给LDuLNode *node = new DuLNode;    //初始化的时候，把第一个值给node，依次向下连接node->data = data[0];L = node;headL = L;for (int i = 1; i < data.size(); i++) {DuLNode *temp = new DuLNode;temp->data = data[i];   //每次创建一个新的结点，当作node的下一个，绑定与node的关系node->next = temp;      //绑定temp变成node的下一个temp->prior = node;     //绑定node变成temp的上一个node = temp;    //绑定后，把当前点给node， 方便下次循环绑定下一个值}node->next = L; //node此时为最后一个值，，node的下一个绑定头结点（循环链表）L->prior = node;    //L的前一个为node，首结点的上一个就是当前链表的最后一个L = headL;  //把初始头结点给Lreturn true;
}bool ListGetDulElem(DuLinkList L, int index, DuLNode &node) {   //得到链表序列为index的值，传给nodeint j = 1;while (L && j < index) {    //找到序列为index的结点，L = L->next;            //前面有几个，就循环几次，每次都向下走一位j++;}if (!L) {   //如果L为空，直接跳过return false;}node = *L;  //如果不为空，把当前结点传给nodereturn true;
}bool ListInsertDul(DuLinkList &L, int index, int data) {    //在序列index位置插入结点DuLNode *node = new DuLNode;if (!ListGetDulElem(L, index, *node)) { //查找一下指定index位置，如果没有当前位置，返回falsereturn false;}//假设在a b的位置插入c（在a b中间插入c，b为node，c为newNode）//设置c的前一个为a      设置a的下一个为c    设置c的下一个为b    设置b的上一个为cDuLNode *newNode = new DuLNode;newNode->data = data;newNode->prior = node->prior;   //把node的前一个给newNode的前一个，node->prior->next = newNode;    //把newNode给node的前一个的后一个newNode->next = node;           //把node给newNode的下一个node->prior = newNode;          //把newNode给node的前一个if (index == 1) {   //如果是插入第一个的话，返回node的上一个L = node->prior;    //node此时为第二个，新插入的为第一个值，把第一个值给L}return true;
}bool ListDeleteDul(DuLinkList &L, int index) {  //删除序列为index的值DuLNode *headL = new DuLNode;headL = L;DuLNode *node = new DuLNode;if (!ListGetDulElem(L, index, *node)) { //找到序列index的结点，传给nodereturn false;}//删除node（node为序列index的结点）//假设a b c删除 b   （b为node）//设置a的下一个为c     设置c的上一个为anode->prior->next = node->next;node->next->prior = node->prior;return true;
}void ListPrintDul(DuLinkList L) {   //输出循环节点if (L == NULL) {return;}DuLNode *headL = new DuLNode;   //保存头结点，头结点用来判断是不是已经输出过了headL = L;do {                            //循环输出cout << L->data << " ";L = L->next;} while (L->next != headL->next);   //判断是不是和头结点的下一个相等，如果相等说明已经输出过了cout << "\n";                       //这里有个小bug，如果用L和headL直接比较，相同的结点会显示不同的地址，导致 一直在输出
}                                       //（在线等大佬解决，评论私信指出都可以）int main() {DuLinkList LinkList;vector<int> data = {1, 2, 3, 4, 5, 6};ListInitDul(LinkList, data);    //把vector传入循环链表ListInsertDul(LinkList, 1, -1);ListInsertDul(LinkList, 4, 8);ListInsertDul(LinkList, 7, 7);ListInsertDul(LinkList, 2, 4);ListPrintDul(LinkList);ListDeleteDul(LinkList, 2); //删除序列号为2的结点ListPrintDul(LinkList);DuLNode node;ListGetDulElem(LinkList, 2, node);  //得到序列号index的结点cout << node.data << "\n";return 0;
}

在这里插入图片描述

顺序表和链表的区别

顺序表	链表
插入删除效率低	插入删除效率高
存取元素效率高	存取元素效率高
顺序表在空间中是一块连续的地址	链表在空间中地址不连续

栈

和顺序表有点类似
他只能返回栈顶元素，添加栈顶元素

#include "iostream"using namespace std;
#define MAXSIZE 100     //设置栈的大小
typedef struct {        //栈结构体：栈顶指针，栈底指针，栈的容量int *base;int *top;int stacksize;
}SqStack;bool InitStack(SqStack &S) {    //初始化栈S.base = new int[MAXSIZE];  //创建MAXSIZE大小的空间if (!S.base) {  //如果没创建成功返回falsereturn false;}S.top = S.base; //当前栈没有内容，栈顶和栈底指向一个位置S.stacksize = MAXSIZE;  //栈的容量为MAXSIZEreturn true;
}bool Push(SqStack &S, int data) {   //把data入栈if (S.top - S.base == S.stacksize) {    //如果栈顶-栈底==栈的容量，证明栈满了，无法添加数据return false;}*S.top++ = data;    //top指针位置添加元素，top指向后一个位置return true;
}bool Pop(SqStack &S, int &data) {   //出栈，返回值给dataif (S.top == S.base) {      //如果栈顶和栈底指向同一个位置，说明栈内没元素return false;}data = *--S.top;        //top指针前移，把值给datareturn true;
}bool Peek(SqStack &S, int &data) {  //peek返回值给data，但栈内不删除if (S.top != S.base) {data = *(S.top - 1);    //返回top指针前一个位置的值给datareturn true;}return false;
}bool StackPrint(SqStack S) {    //输出栈内元素，这里传的不是地址，如果传地址用完还要把指针改到栈顶while (S.top != S.base) {   //只要栈顶和栈底不是同一个位置，证明栈内元素没有空cout << *--S.top << " ";}cout << "\n";
}int main() {SqStack stack;InitStack(stack);   //初始化Push(stack,10);Push(stack,30);Push(stack,20);Push(stack,50);StackPrint(stack);int val;Pop(stack, val);    //出栈cout << val << " \n";StackPrint(stack);Peek(stack, val);   //返回栈顶的值，不删除cout << val << " \n";StackPrint(stack);return 0;
}

在这里插入图片描述

栈实现括号问题

给定一个字符串，里边可能包含( ) 这一种种括号，请编写程序检查该字符串的括号是否成对出现。

#include "iostream"
#include "stack"using namespace std;int main() {stack<char> s;  //栈存左括号，当前括号为左括号就压栈，如果遇到右括号就弹出一个左括号string str;cin >> str;     //输入字符串for (int i = 0; i < str.size(); i++) {if (str[i] == '(') {    //遇到左括号就压栈s.push('(');} else {    //遇到右括号就出栈，就是一个左括号配对一个右括号if (s.size() == 0) {    //如果此时没有左括号，在弹出说明左括号不足，无法匹配括号cout << "无法匹配————右括号多了";return 0;}s.pop();}}if (s.size() != 0) {    //如果循环完成后，栈内还有左括号，证明左括号多了，无法完成匹配cout << "无法匹配————左括号多了";} else {cout << "可以匹配";}return 0;
}

循环链栈表

栈的链表
栈和链栈的区别就是顺序表和单链表的区别
入栈和出栈只需要改变指定结点的关系
因为栈是单方向的，所以只需要改变单方向结点的关系

#include "iostream"using namespace std;typedef struct StackNode{   //链栈结构体：一个数据，一个指向下一位的指针int data;struct StackNode *next;
}StackNode, *LinkStack;bool InitStackNode(LinkStack &L) {  //初始化链栈，直接给链表NULL就可以L = NULL;return true;
}//此压栈方法和单链表的前插法有点类似（如果用后插法，无法访问到上一个结点）
bool Push(LinkStack &L, int data) { //压入data数据进入链栈StackNode *temp = new StackNode;temp->data = data;      //给temp数据temp->next = L;         //temp的下一个指向LL = temp;               //temp给L
}bool Pop(LinkStack &L, int &data) { //出栈（把数据传给data）if (L == NULL) {return false;}data = L->data;     //传给data，L指向下一个L = L->next;return true;
}bool Peek(LinkStack &L, int &data) {    //返回栈顶元素（给data）if (L != NULL) {data = L->data;return true;}return false;
}void linkStackPrint(LinkStack L) {  //输出链栈while (L) {cout << L->data << " ";L = L->next;}cout << "\n";
}int main() {LinkStack stack;InitStackNode(stack);   //初始化链栈，插入数据Push(stack,12);Push(stack,56);Push(stack,15);Push(stack,43);linkStackPrint(stack);int val;Pop(stack, val);    //栈顶结点出栈cout << val << "\n";linkStackPrint(stack);Peek(stack, val);   //返回栈顶元素（不删除栈顶元素）cout << val << "\n";linkStackPrint(stack);Push(stack,15); //入栈linkStackPrint(stack);
}

在这里插入图片描述

递归斐波那契

递归，其实就是自己不断的调用自己，每次改变参数

第五项的斐波那契就是第四项+第三项
初始值，第一项，第二项的值为1
第三项的值就是前两个相加
第n项就是（n-1）+（n-2） 不断的调用自己
当找到第1项和第2项的时候直接返回1，我们默认第一项和第二项为1 上面的默认值，我们也称为递归的出口

**递归还有很多变种，（DFS,BFS）在后面的博客中会一一细说的**

#include "iostream"using namespace std;int f(int n) {if (n == 1 || n == 2) {return 1;}return f(n - 1) + f(n - 2);
}int main() {cout << f(5);
}

递归汉诺塔

在这里插入图片描述

/*根据汉诺塔的规则：一次只能移动一个托盘，而且必须保证小托盘在大托盘上面，完成A的托盘移动到C设 1号 为最小的托盘，用递归思路把这个问题分开，如果想把 n 号托盘移动，需要把 n 号上面的托盘都移动了然后我们转去移动 n-1 号托盘，一直找到最上面的托盘当移动 1 号托盘的时候，直接移动到C即可为什么移动n-1号托盘的时候是传入的Hanoi(n - 1, A, C, B)Hanoi（n, A, B, C） 是把 n 号托盘从A->C如果 1号 直接移动到C那么 2号 的时候就要先移动到B，中转一下，(1号 在C，把 1号 移动到B，空出C来给3号)3号 移动的时候移动到C，（然后再慢慢把B上的转到C上面（！！！并不是一步从B转到C），把B空出来给下一个托盘）……一直重复如此不难发现，1->C,2-B,3->C,4->B……这就是为什么每次都要C和B换位置的原因，n号移动到B，n-1号就要移动到C！！！所有的A B C都不是固定的ABC  都和这种类似，临时的ABC（这么做其实就是确保递归时每次都是从当时方法的目的是A->C 而不是一直要自己变动A->B,A->C  把参数改了，方法不变，就达到一直变动的目的了）当我们 n-1号 托盘移动完成后（同时意味着 1到（n-1） 都移动完成了），我们就可以把 n号 托盘从A直接转到C上n号移动以后，把1到（n-1）号托盘从B移动到C，重复上面的操作如果还是不好理解，多看一看动图理解，或者调试调试代码理解，只看不做很难理解Talk is Cheap, Show me the Code.
*/

**递归中所有的A B C都不是固定的ABC**

#include "iostream"using namespace std;int step = 1;
void Hanoi(int n, char A, char B, char C) { //将编号为n的托盘从A移动到C，B当作中间托盘if (n == 1) {cout << "步数:" << step++ << " 托盘:" << n << "  " << A << "->" << C << "\n";} else {Hanoi(n - 1, A, C, B);  //把（1-（n-1）号托盘）A->B C做中转结点cout << "步数:" << step++  << " 托盘:" << n << "  " << A << "->" << C << "\n";Hanoi(n - 1, B, A, C);  //把（1-（n-1）号托盘）B->C A做中转结点}
}
int main() {Hanoi(3,'A','B','C');return 0;
}

在这里插入图片描述

循环队列

循环队列，有点类似双指针数组
左指针存数据后，左指针左移，如果是左端的话，左移到右端
右指针存数据后，右指针右移，如果是右端的话，右移到左端

#include "iostream"using namespace std;#define MAXSIZE 10
typedef struct{ //队列结构体：数据，头指针，尾指针int *num;int front;int rear;
}SqQueue;bool InitQueue(SqQueue &S) {    //初始化队列S.num = new int[MAXSIZE];S.front = S.rear = 0;   //头指针和尾指针在一块（初始没有数据）return true;
}int QueueLength(SqQueue S) {    //返回长度（尾结点-头结点）return (S.rear - S.front + MAXSIZE) % MAXSIZE;//加上MAXSIZE防止出现负数，有可能出现头结点比尾结点大的情况
}bool QueueInsertHead(SqQueue &S, int data) {    //队列头结点插入if ((S.front - 1 + MAXSIZE) % MAXSIZE == S.rear) {  //判断一下是不是满了return false;}S.num[S.front] = data;  //插到头结点//因为他是队列，如果头指针在下标0的地方，那么前移就移动到末尾了S.front = (S.front - 1 + MAXSIZE) % MAXSIZE;    //头指针前移，防止指针-1小于0，return true;
}bool QueueInsertEn(SqQueue &S, int data) {  //队列尾结点插入if ((S.rear + 1) % MAXSIZE == S.front) {    //看是不是满的，尾结点+1可能超过末端，超过末端就从起始端开始算return false;}S.rear = (S.rear + 1) % MAXSIZE;    //后移一位S.num[S.rear] = data;   //存放数据return true;
}bool QueueDeleteHead(SqQueue &S, int &data) {   //删除头结点，传给dataif (S.front == S.rear) {    //如果是空的没办法传return false;}S.front = (S.front + 1) % MAXSIZE;  //头结点后移一位data = S.num[S.front];  //把值传给datareturn true;
}bool QueueDeleteEn(SqQueue &S, int &data) { //删除尾结点，传给dataif (S.front == S.rear) {    //判断是否为空return false;}data = S.num[S.rear];   //把值传给dataS.rear = (S.rear - 1 + MAXSIZE) % MAXSIZE;  //尾指针前移return true;
}bool QueueGetHead(SqQueue &S,int &data) {   //得到头结点if (S.front == S.rear) {return false;}data = S.num[(S.front + 1) % MAXSIZE];return true;
}bool QueueGetEnd(SqQueue &S, int &data) {   //得到尾结点if (S.front == S.rear) {return false;}data = S.num[S.rear];return true;
}bool QueuePrint(SqQueue S) {    //输出队列while (S.front != S.rear) {S.front = (S.front + 1) % MAXSIZE;cout << S.num[S.front] << " ";int temp = S.num[S.front];}cout << "\n";
}int main() {SqQueue queue;InitQueue(queue);QueueInsertHead(queue, 10);QueueInsertEn(queue, 40);QueueInsertHead(queue, 20);QueueInsertEn(queue, 30);QueuePrint(queue);int data;QueueDeleteEn(queue, data);cout << "删除尾结点:" << data << "\n";QueueDeleteHead(queue, data);cout << "删除头结点:" << data << "\n";QueueGetHead(queue, data);cout << "得到头结点:" << data << "\n";QueueGetEnd(queue, data);cout << "得到尾结点:" << data << "\n";cout << "得到长度:" << QueueLength(queue) << "\n";QueuePrint(queue);
}

在这里插入图片描述

链队（链式队列）

每个结点有一个指向下一位的指针
相对双向循环链表简单

#include "iostream"using namespace std;typedef struct QNode {  //结点结构体：值，下一位的指针int data;struct QNode *next;
} QNode, *QueuePtr;typedef struct {    //队列包含一个头指针，一个尾指针QueuePtr front;QueuePtr rear;
} LinkQueue;bool InitQueue(LinkQueue &Q) {  //初始化队列Q.front = Q.rear = new QNode;   //创建头尾结点Q.front->next = NULL;           //头结点的下一个为空Q.front->data = Q.rear->data = NULL;    //初始时，头尾结点值为NULLreturn true;
}bool LinkQueueInsertEnd(LinkQueue &Q, int data) {   //添加元素到队尾if (Q.front == Q.rear && Q.front->data == NULL) {   //如果是第一次进来Q.rear->data = data;    //赋初值return true;}Q.rear->next= new QNode;Q.rear->next->data = data;  //给尾结点的下一个赋值Q.rear = Q.rear->next;      //尾结点指向尾结点的下一个Q.rear->next = NULL;        //尾结点的下一个为空return true;
}bool LinkQueueDeleteHead(LinkQueue &Q, int &data) { //删除头结点if (Q.front == Q.rear) {return false;}QNode *temp = new QNode;data = Q.front->data;   //保存头结点的值Q.front = Q.front->next;    //头指针指向下一位
}bool LinkQueueGetHead(LinkQueue &Q, int &data) {    //得到头结点if (Q.front != Q.rear) {    //队列不为空就返回data = Q.front->data;return true;}return false;
}void LinkQueuePrint(LinkQueue Q) {  //输出队列的值while (Q.front != Q.rear->next) {cout << Q.front->data << " ";Q.front = Q.front->next;}cout << "\n";
}int main() {LinkQueue linkQueue;InitQueue(linkQueue);LinkQueueInsertEnd(linkQueue, 10);LinkQueueInsertEnd(linkQueue, 20);LinkQueueInsertEnd(linkQueue, 30);LinkQueueInsertEnd(linkQueue, 40);LinkQueuePrint(linkQueue);int val;LinkQueueDeleteHead(linkQueue, val);cout << "删除的头结点值为:" << val << "\n";LinkQueueGetHead(linkQueue, val);cout << "得到的头结点值为:" << val << "\n";return 0;
}