2.1.1 引, 多项式表示
P1,P2,P3 可以取出系数 和项数这样表示:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| (9,12) | (15,8) | (3,2) | ||||
| (26,19) | (-4,8) | (-13,6) | (82,0) | |||
| (26,19) | (9,12) | (11,8) | (-13,6) | (3,2) | (82,0) |
链表结构存储非零项
| coef(指数) | expon(系数) | link(指针) |
|---|
typedef struct PolyNode *Polynomial;
struct PolyNode{
int coef ;
int expon;
Polynomial link;
}
注意: 链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。
`数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构`。
2.1.2线性表及其顺序存储
线性表(Linear List)
(1) 什么是线性表?
`将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表)`。
`要求数据类型必须一致`
也就是说，线性表存储的数据，要么全不都是整形，要么全部都是字符串。一半
是整形，另一半是字符串的一组数据无法使用线性表存储。
(2)下面是两种线性表:
两种线性存储结构
- 如图 3a) 所示，将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称
[顺序表]）； - 如图 3b) 所示，数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构 (简称
[链表])；
连续内存空间 - 申请连续内存空间,只使用一个头指针存放
有待解决的坑:
1.代码重构: 重复代码块的问题;
2.申请空间head 指向malloc申请的空间时, head[i] i可以比 malloc 申请的空间
大; 因为是 CS:IP 查找的;
3.简单结构体 (如下的) length 与 size 完全无关, 与 head 也无关, 建立联系与限
制;目前想到的解决办法是 每个节点都加限制(联系) 或者使用之后的数据结构进行处理;希望
在未来能找到一种简单的方式进行限制;
typedef struct Table {
int * head ; //指针
int length ;
int size ;
}Table ;
2.1.3顺序存储的线性表.cpp
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-19 13:49:14
* @LastEditors: Mailor
* @LastEditTime: 2020-12-22 14:06:36
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>
#define MAX_SIZE 100
typedef bool boolean ;
typedef int elementType; //只是起别名
// typedef struct LNode *List ;
typedef struct LNode{
elementType Data[MAX_SIZE];
int Last;
int ListSize ;
} LNode , *List;
//PtrL是一个指针,这个指针指向这个结构体 L
//访问下标为 i 的元素: L.Data[i] 或者 PtrL->Data[i];
//线性表的长度: L.Last+1 或者 Ptr->Last+1 ;
List makeEmpty(); //初始化线性表
boolean insert(elementType X, int index, List L);
boolean deleteByIndex(int index, List L);
boolean update(elementType X, int index, List L);
int find(elementType X, List L);
int * findAll(elementType X, List L);
void display(List L);
// int findPtrL(elementType X, List PtrL);
//------init------
List makeEmpty(){
List L = (List)malloc(sizeof(struct LNode));
L->Last = -1 ;
// 元素1-n ;长度;
L->ListSize = MAX_SIZE;
return L;
}
//-------增删改查------
boolean insert(elementType X, List L){
insert(X,0,L);
// if(L->Last+1>=MAX_SIZE){
// printf("\n 数据库满了...");
// return false;
// }
// for(int i=L->Last;i>=0;i--){
// L->Data[i+1] = L->Data[i];
// }
// L->Data[0] = X ;
return true;
}
boolean insert(elementType X, int index, List L){
//插入 数组满了 不让插入
if(L->Last+1 >= MAX_SIZE){
printf("\nSORRY, 插入的数据库满了...");
return false;
}
if(index<0||index>L->Last+1){
printf("\n插入位置不合法...");
return false ;
}
for(int i=L->Last;i>=index;i--){
L->Data[i+1]=L->Data[i];
}
L->Last++;
L->Data[index]=X;
return true ;
}
boolean update(elementType X ,int index, List L){
if(index<0||index>L->Last){
printf("\n修改位置不合法...");
return false ;
}
L->Data[index]=X ;
return true;
}
boolean deleteByIndex(int index, List L){
if(index<0||index>L->Last){
printf("删除位置不合法...");
return false ;
}
for(int i=index;i<L->Last-1;i++){
L->Data[i]=L->Data[i+1];
}
L->Last -- ;
return true ;
}
//查 返回第一个找到的第一个 index 不是全部查找
int findOne(elementType X, List L){
for (int i=0;i<L->Last;i++){
if(L->Data[i]==X){
return i;
}
}
printf("没找到...");
return -1;
}
//需要设计一个动态数组
//查 返回所有找到的 index 全部查找返回
int * findAll(elementType X, List L){
if(L->Last<0){
printf("\n 数据链表不合法");
return NULL ;
}
int countX=0;//这一步很重要;
for(int i=0;i<L->Last+1;i++){
if(L->Data[i]==X){
countX++;
}
}
display(L);
printf("\nL.Last+1= %d",L->Last+1);
printf("\nX=%d",X);
printf("\ncountX=%d",countX);
//解决返回指针不知道长度问题
//第一个数据存放长度
int * indexArray=(int *)malloc((countX+1) * sizeof(int));
indexArray[0] = countX ;
int j=1;
for(int i=0;i<L->Last+1;i++){
if((j-1)==countX){
break;
}
if(L->Data[i]==X){
indexArray[j]=i;
j++;
}
}
display(L);
return indexArray ;
}
void display(List L){
printf("数据内容为: ");
for(int i=0;i<L->Last+1;i++){
printf("%d\t", L->Data[i]);
}
printf("\n");
}
int main(){
List L1 = makeEmpty();
insert(1,L1);
insert(2,L1);
insert(12,L1);
insert(4,L1);
insert(4,4,L1);
insert(2,L1);
insert(2,L1);
insert(2,L1);
display(L1);
printf("\n查找值为12的下标是：%d\n",findOne(12,L1));
display(L1);
int * p = findAll(2,L1);
//返回的指针不知道长度,不是数组
printf("\n满足条件的个数是:%d",p[0] );
printf("\n查找满足条件的下标为: ");
for(int i=1;i<p[0]+1;i++){
printf("%4d", p[i]);
}
printf("\n");
display(L1);
deleteByIndex(4,L1);
display(L1);
update(100,1,L1);
display(L1);
return 0;
}
2.1.4链表存储的线性表.cpp
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-19 13:49:14
* @LastEditors: Mailor
* @LastEditTime: 2020-12-22 16:55:59
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>
#define MAX_SIZE 100
typedef bool boolean ;
typedef int ElementType; //只是起别名
typedef struct LNode *List ;
typedef struct LNode{
ElementType Data;
List Next;
int length;
} LNode ;
//PtrL是一个指针,这个指针指向这个结构体 L
//访问下标为 i 的元素: L.Data[i] 或者 PtrL->Data[i];
//线性表的长度: L.Last+1 或者 Ptr->Last+1 ;
List initList();
int lengthOfList(List L);
List selectBySingleId(int id,List L);
List selectBySingleElement(ElementType element, List L);
int selectByElementToFirstId(ElementType element, List L);
List insertSingleElement(ElementType element,List L);
List insertSingleElementById(ElementType element, int id, List L);
List updateBySingleId(ElementType element,int id, List L);
List deleteBySingleId(int id,List L);
boolean display(List L);
List initList(){
List L = (List)malloc(sizeof(struct LNode));
L->length = 0;
L = NULL;
return L ;
}
int LengthOfList(List L){
int length = 0;
while(L){
L = L->Next;
length++;
}
return length;
}
List selectBySingleId(int id,List L){
int i= 1;
while(L && i<id){
L=L->Next;
i++;
}
if(i==id){
return L;
}else{
return NULL;
}
}
List selectBySingleElement(ElementType element,List L){
int length = LengthOfList(L);
int i=0;
while(L &&(L->Data!=element )){
L=L->Next ;
i++;
}
if(L->Data == element){
return L;
}else
{
return NULL;
}
}
int selectByElementToFirstId(ElementType element, List L){
int length = LengthOfList(L);
int i=1;
if(L==NULL){return -1;}
while(L->Data!=element){
L=L->Next ;
if(L==NULL){return -1;}
i++;
}
if(L->Data == element){
return i;
}else
{
return 0;
}
}
List insertSingleElementById(ElementType element, int id, List L){
List s;
if(id==1){
s = (List)malloc(sizeof(struct LNode));
s->Data = element;
s->Next = L;
return s;//返回头结点
}
int length = LengthOfList(L);
if(id>length+1){
printf("id越界;\n");
return L;
}
List p = selectBySingleId(id-1,L);
if(p!=NULL){
s = (List)malloc(sizeof(struct LNode));
s->Data = element;
s->Next = p->Next;
p->Next = s ;
return L;
}else{
printf("\n插入下表越界,id>链表长度+1\n");
return NULL ;
}
}
List insertSingleElement(ElementType element,List L){
return insertSingleElementById(element,1,L);
}
List updateBySingleId(ElementType element,int id,List L){
selectBySingleId(id,L)->Data = element;
return L;
}
List deleteBySingleId(int id,List L){
if(L==NULL){
printf("链表为空,无法继续删除;");
return NULL;
}
if(id==1){
List freeList = L;
L = L->Next;
free(freeList);
return L;
}
List tmp = selectBySingleId(id-1,L);
if(tmp==NULL){
printf("第%d 个节点不存在;",id-1);
return NULL;
}else if( tmp->Next == NULL){
printf("第%d个节点不存在;",id);
return NULL;
}
List freeList = tmp->Next;
tmp->Next =freeList->Next;
free(freeList);
return L;
}
boolean display(List L){
if(L==NULL){
printf("NULL\n");
return true;
}
printf("链表的数据为: ");
while(L!=NULL){
printf("%d\t",L->Data);
L = L->Next ;
}
printf("\n");
return true;
}
int main(){
List list = initList();
display(list);
list = insertSingleElement(20,list);
list = insertSingleElement(10,list);
list = insertSingleElement(11,list);
list = insertSingleElementById(166,6,list);
list = insertSingleElementById(66,2,list);
list = insertSingleElementById(166,5,list);
display(list);
printf("List 长度 = %d\n",LengthOfList(list));
printf("id= 2 的 List 元素数据为 = %d\n",selectBySingleId(2,list)->Data);
printf("查找元素为 20 在 list 中 id = %d\n", selectByElementToFirstId(20,list));
printf("查找元素为 22 在 list 中 id = %d\n", selectByElementToFirstId(22,list));
list = deleteBySingleId(1,list);
display(list);
return 0;
}
输出为:
NULL
id越界;
链表的数据为: 11 66 10 20 166
List 长度 = 5
id= 2 的 List 元素数据为 = 66
查找元素为 20 在 list 中 id = 4
查找元素为 22 在 list 中 id = -1
链表的数据为: 66 10 20 166
2.1.6 广义表和多重链表
typedef int ElementType;
typedef struct GNode *GList;
struct GNode{
int Tag;//标志域, 0 标示单元素, 1 表示广义表
union{
ElementType Data;
GList SubList;
} URegion;
GList Next; //执行后继节点
};
2.2 栈
定义：一种可以实现先进后出的存储结构，类似于箱子。
分类：
静态栈：以数组为基本内核;顺序存储;
动态栈：以链表为基本内核;链式存储;
动态栈的算法：
就是把链表的一些功能给砍掉，例如不允许在头部插入，不允许删除中间的元素等等。
出栈
压栈（入栈）
动态栈.jpg
栈的应用：
- 函数调用就是考栈的思路实现的。
f调用g，g调用k；
执行的时候，先执行k，再g再f - 中断
- 表达式求值 （两个栈可以编写计算器）
- 内存分配
- 缓冲处理
- 迷宫
2.2静态栈.cpp
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-22 21:11:44
* @LastEditors: Mailor
* @LastEditTime: 2020-12-22 21:59:01
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define MAX_SIZE 100
typedef bool boolean;
typedef int ElementType;
typedef struct StackNodeImplementByArray *Stack;
struct StackNodeImplementByArray{
ElementType Data[MAX_SIZE];
int Top;
} StackNodeImplementByArray;
Stack initStack();
boolean isFull(Stack stack);
boolean isEmpty(Stack stack);
ElementType pop(Stack stack);
void push(Stack stack , ElementType element);
Stack initStack(){
Stack stack ;
stack = (Stack)malloc(sizeof(struct StackNodeImplementByArray));
stack->Top = -1;
return stack;
}
boolean isFull(Stack stack){
return (stack->Top == MAX_SIZE-1);
}
boolean isEmpty(Stack stack){
return (stack->Top == -1);
}
void push(Stack stack, ElementType element){
if(stack->Top >=MAX_SIZE-1){
printf("\n栈满了;");
}
stack->Data[++stack->Top]=element;
}
ElementType pop(Stack stack){
if(isEmpty(stack)){
printf("\n栈空;");
return 0;//因为 element 是 int 如果是 String 返回 null
}
return stack->Data[stack->Top--];
}
boolean displayStackFromTopToButtom(Stack stack){
if(isEmpty(stack)){
printf("\n栈空");
return true;
}
printf("\n栈中元素显示出来-从栈顶到栈底: ");
for(int i=stack->Top;i>-1;i--){
printf("%d\t",stack->Data[i]);
}
return true;
}
int main(){
Stack stack = initStack();
push(stack,12);
push(stack,10);
displayStackFromTopToButtom(stack);
push(stack,10);
push(stack,1);
displayStackFromTopToButtom(stack);
pop(stack);
displayStackFromTopToButtom(stack);
return 0;
}
输出:
栈中元素显示出来-从栈顶到栈底: 10 12
栈中元素显示出来-从栈顶到栈底: 1 10 10 12
栈中元素显示出来-从栈顶到栈底: 10 10 12
2.2动态栈.cpp 可以利用栈顶节点存放栈长度
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-22 21:56:47
* @LastEditors: Mailor
* @LastEditTime: 2020-12-22 23:19:40
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
typedef bool boolean;
typedef int ElementType;
typedef struct StackNodeImplementByLinkedList *Stack;
struct StackNodeImplementByLinkedList{
ElementType Data;
Stack Next;
};
Stack initStack();
// boolean isFull(Stack stack);//动态链表除非 内存不够,不存在栈满
boolean isEmpty(Stack stack);
boolean push(Stack stack, ElementType element);
ElementType pop(Stack stack);
Stack initStack(){
Stack stack;
stack = (Stack)malloc(sizeof(struct StackNodeImplementByLinkedList));
stack->Next = NULL;
return stack;
}
boolean isEmpty(Stack stack){
return (stack->Next == NULL);
}
boolean push(Stack stack, ElementType element){
//申请一个节点 tmp 把 tmp的下一个节点设置为 stack
//再把 tmp 赋值给 stack 完成 stack 的更新
Stack tmp = (Stack)malloc(sizeof(struct StackNodeImplementByLinkedList));
tmp->Data = element;
tmp->Next = stack->Next;
stack->Next = tmp;
stack->Data++;
return true;
}
ElementType pop(Stack stack){
if(isEmpty(stack)){
printf("\n 栈空;");
return 0;
}
Stack tmp = stack->Next;
int element = tmp->Data;
stack->Next = stack->Next->Next;
free(tmp);
stack->Data--;
return element;
}
boolean displayStackFromTopToButtom(Stack stack){
if(isEmpty(stack)){
printf("\n 栈空;");
return true;
}
printf("\n栈的长度是: %d",stack->Data);
printf("\n 栈中的数据是: ");
Stack tmp = stack->Next;
while(tmp){
printf("%d\t",tmp->Data);
tmp = tmp->Next;
}
return true;
}
int main(){
Stack stack = initStack();
push(stack,12);
push(stack,10);
displayStackFromTopToButtom(stack);
push(stack,10);
push(stack,1);
displayStackFromTopToButtom(stack);
pop(stack);
displayStackFromTopToButtom(stack);
return 0;
}
输出为:
栈的长度是: 2
栈中的数据是: 10 12
栈的长度是: 4
栈中的数据是: 1 10 10 12
栈的长度是: 3
栈中的数据是: 10 10 12
2.3 队列
定义：一种够可以实现“先进先出”的数据结构
分类：
链式队列
静态队列
静态队列通常都必须是循环队列
静态队列需要搞清楚的几个点：
为什么必须是循环队列
如果按照普通的数组去形成队列的话，那删除元素后，front的位置就会往上移动，队列的前面就会空出来位置，这些位置就浪费了。如果添加元素，那rear也会往上移动。这样的结果就是，无论是入队还是出队，两个都往上移，空间就越来越少，操作不方便。
所以，关键是需要，在添加元素的时候，如果rear已经到顶部，rear可以从上面跳到下面接上去。循环队列需要几个参数来确定
两个，front和rear，front（前台）掌管出对，rear掌管入对，在不同场合中：
1). 队列初始化：两者都为零
2). 队列非空：
front代表的是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个位置
3). 队列空：front和rear的值相等，但不一定为零循环队列各个参数的含义
-
入队列，出队列算法
入队列：
1.把新增元素添加到当前r的位置
2.r = (r+1)%maxlen
出队列：
f = (f+1)%maxlen
-
如何判断空、满
空：front与rear的值相等，就一定为空
满：这个有点难判断，因为满的时候，似乎f也跟r相同了。
这个时候有两种办法处理：一种是添加一个参数，记录元素个数。第二种就是，不让队列的所有位置都可以放值，而是始终空出一个位置，让r的永远是一个空位置。这样，满的状态就是r==(f-1)%maxlen或者f==(r+1)%maxlen。
队列的应用：
所有和时间有关的操作都有队列的影子。
2.3静态队列_使用移动数组数据实现的非循环队列.cpp
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-23 00:01:48
* @LastEditors: Mailor
* @LastEditTime: 2020-12-23 00:35:47
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define MAX_SIZE 100
typedef bool boolean;
typedef int ElementType;
typedef struct QueueImplementByArray *Queue;
struct QueueImplementByArray{
ElementType Data[MAX_SIZE];
int length;
};
Queue initQueue();
boolean pushToQueue(Queue queue,ElementType element);
ElementType popFromQueue(Queue queue);
boolean isFull(Queue queue);
boolean isEmpty(Queue queue);
boolean displayAll(Queue queue);
Queue initQueue(){
Queue queue = (Queue)malloc(sizeof(struct QueueImplementByArray));
queue->length = 0;
return queue;
}
boolean isEmpty(Queue queue){
return queue->length == 0;
}
boolean isFull(Queue queue){
return queue->length==MAX_SIZE;
}
boolean pushToQueue(Queue queue, ElementType element){
queue->Data[queue->length]=element;
queue->length++;
return true;
}
ElementType popFromQueue(Queue queue){
if(queue->length == 0){
printf("\n 队列为空;");
return 0;
}
for(int i=1;i<queue->length;i++){
queue->Data[i-1]= queue->Data[i];
}
queue->Data[queue->length-1]=0;
queue->length--;
return queue->Data[0];
}
boolean displayAll(Queue queue){
if(queue->length==0){
printf("\n 队列为空;");
return true;
}
printf("\n队列先进先出,全部出队列的结果为: ");
for(int i=queue->length-1;i>-1;i--){
printf("%d\t",queue->Data[i]);
}
return true;
}
int main(){
Queue q = initQueue();
pushToQueue(q,2);
pushToQueue(q,54);
displayAll(q);
pushToQueue(q,100);
pushToQueue(q,100);
pushToQueue(q,12);
displayAll(q);
popFromQueue(q);
printf("\n 进行一次出队列操作,结果为: ");
displayAll(q);
}
输出:
队列先进先出,全部出队列的结果为: 54 2
队列先进先出,全部出队列的结果为: 12 100 100 54 2
进行一次出队列操作,结果为:
队列先进先出,全部出队列的结果为: 12 100 100 54
2.3静态队列_循环队列.cpp
这里我设置的循环队列初始 front 和 rear 都为 0 ;其实只要他们相等,指向同一个位置队列就为空;
设置 data[front]存放队列数据个数;
来一个数据rear+1;用 rear 一个个存放数据;
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-23 00:01:48
* @LastEditors: Mailor
* @LastEditTime: 2020-12-23 13:34:59
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define MAX_SIZE 7
typedef bool boolean;
typedef int ElementType;
typedef struct QueueImplementByArray *Queue;
struct QueueImplementByArray{
ElementType Data[MAX_SIZE];
int front;
int rear;
};
Queue initQueue();
boolean pushToQueue(Queue queue,ElementType element);
ElementType popFromQueue(Queue queue);
boolean isFull(Queue queue);
boolean isEmpty(Queue queue);
boolean displayAll(Queue queue);
Queue initQueue(){
Queue queue = (Queue)malloc(sizeof(struct QueueImplementByArray));
queue->front= 0;
queue->rear = 0;
return queue;
}
boolean isEmpty(Queue queue){
return (queue->rear == queue->front);
}
boolean isFull(Queue queue){
return ((queue->rear+1) % MAX_SIZE == queue->front);
}
boolean pushToQueue(Queue queue, ElementType element){
if(isFull(queue)){
printf("\n 队列满了,不能插入;");
return true;
}
queue->rear = (queue->rear+1)%MAX_SIZE;
queue->Data[queue->rear]=element;
queue->Data[queue->front]++;
return true;
}
ElementType popFromQueue(Queue queue){
if(isEmpty(queue)){
printf("\n 队列为空;");
return 0;
}
// for(int i=1;i<queue->rear;i++){
// queue->Data[i-1]= queue->Data[i];
// }
// queue->Data[queue->rear-1]=0;
// queue->rear--;
int popElement = queue->Data[((queue->front+1)%MAX_SIZE)];
queue->Data[((queue->front+1)%MAX_SIZE)] = queue->Data[queue->front];
queue->Data[queue->front] = 0;
queue->front = (queue->front+1) % MAX_SIZE ;
queue->Data[queue->front]--;
return popElement;
}
boolean displayAll(Queue queue){
if(queue->front == queue->rear){
printf("\n 队列为空;");
return true;
}
printf("\n队列先进先出,全部出队列的结果为: ");
printf("\n---队列长度为: %d",queue->Data[queue->front]);
printf("\n---队列数据为: ");
if(queue->front<queue->rear){
for(int i=queue->rear;i>queue->front;i--){
printf("%d\t",queue->Data[i]);
}
return true;
}
if(queue->front>queue->rear){
for(int i=queue->rear;i>-1;i--){
printf("%d\t",queue->Data[i]);
}
for(int i=MAX_SIZE-1;i>queue->front;i--){
printf("%d\t",queue->Data[i]);
}
return true;
}
return false;
}
int main(){
Queue q = initQueue();
pushToQueue(q,2);
pushToQueue(q,54);
displayAll(q);
pushToQueue(q,100);
pushToQueue(q,100);
pushToQueue(q,12);
displayAll(q);
popFromQueue(q);
printf("\n 进行一次出队列操作,结果为: ");
displayAll(q);
pushToQueue(q,1);
popFromQueue(q);
pushToQueue(q,1);
popFromQueue(q);
pushToQueue(q,1);
popFromQueue(q);
pushToQueue(q,1);
popFromQueue(q);
printf("\n在进行4 次进出循环队列后打印: ");
displayAll(q)
}
输出:
队列先进先出,全部出队列的结果为:
---队列长度为: 2
---队列数据为: 54 2
队列先进先出,全部出队列的结果为:
---队列长度为: 5
---队列数据为: 12 100 100 54 2
进行一次出队列操作,结果为:
队列先进先出,全部出队列的结果为:
---队列长度为: 4
---队列数据为: 12 100 100 54
在进行4 次进出循环队列后打印:
队列先进先出,全部出队列的结果为:
---队列长度为: 4
---队列数据为: 1 1 1 1
[Done] exited with code=0 in 0.513 seconds
2.3动态队列.cpp
/*
* @Descripttion:
* @version: v_1.0.0
* @Author: Mailor
* @Email: xiaolele19980118@163.com
* @Date: 2020-12-23 00:39:52
* @LastEditors: Mailor
* @LastEditTime: 2020-12-23 15:55:48
*/
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
typedef bool boolean;
typedef int ElementType;
typedef struct QueueImplementByLinkedList *Queue;
struct Node{
ElementType Data;
Node *Next;
} Node;
struct QueueImplementByLinkedList{
ElementType Data;
struct Node *front;
struct Node *rear;
};
//单指针我没有解决出队列问题,因为链表无法拐头;
//解决设置两个节点,一个节点存放头;一个存放尾巴
boolean isEmpty(Queue queue);
ElementType popFromQueue(Queue queue);
boolean pushToQueue(Queue queue, ElementType element);
Queue initQueue();
Queue initQueue(){
Queue q;
q = (Queue)malloc(sizeof(struct QueueImplementByLinkedList));
q->front = NULL;
q->rear = NULL;
return q;
}
boolean isEmpty(Queue queue){
return (queue->rear==NULL);
}
boolean pushToQueue(Queue queue, ElementType element){
if(isEmpty(queue)){
queue->front = (struct Node *)malloc(sizeof(struct Node));
queue->rear = (struct Node *)malloc(sizeof(struct Node));
queue->front->Next = queue->rear;
queue->rear->Data = element;
queue->rear->Next = NULL ;
queue->front->Data ++ ;
return true;
}
struct Node *tmp;
tmp = (struct Node *)malloc(sizeof(struct Node));
tmp->Data = element;
queue->rear->Next = tmp;
queue->rear = tmp;
queue->rear->Next = NULL;
queue->front->Data++;
return true;
}
ElementType popFromQueue(Queue queue){
if(isEmpty(queue)){
printf("\n队列为空;");
return 0;
}
struct Node * firstNode= queue->front;
int popElement = firstNode->Next->Data;
if(firstNode->Next==queue->rear){
queue->front = queue->rear = NULL;
queue->front->Data--;
return popElement;
}
queue->front = queue->front->Next;
queue->front->Data = firstNode->Data;
queue->front->Data -- ;
free(firstNode);
return popElement;
}
boolean displayAll(Queue queue){
if(isEmpty(queue)){
printf("\n队列为空;");
return true;
}
printf("\n队列中打印出来");
printf("\n---队列数据个数: %d",queue->front->Data);
printf("\n---队列数据: ");
struct Node * tmp = queue->front->Next;
int * a =new int[queue->front->Data];
int i=0;
while(tmp!=NULL){
a[i++] = tmp->Data;
tmp = tmp->Next;
}
for(int i=queue->front->Data-1;i>-1;i--){
printf("%d\t",a[i]);
}
return true;
}
int main(){
printf("\n-------动态队列-------");
Queue q = initQueue();
pushToQueue(q,2);
pushToQueue(q,54);
displayAll(q);
pushToQueue(q,100);
pushToQueue(q,100);
pushToQueue(q,12);
displayAll(q);
int pop1 = popFromQueue(q);
printf("\n\n进行一次出队列操作,出队列数据为: %d",pop1);
displayAll(q);
pushToQueue(q,1);
popFromQueue(q);
pushToQueue(q,2);
popFromQueue(q);
pushToQueue(q,3);
popFromQueue(q);
pushToQueue(q,4);
popFromQueue(q);
printf("\n在进行 4 次出队列后打印: ");
displayAll(q);
return 0 ;
}
输出:
-------动态队列-------
队列中打印出来
---队列数据个数: 2
---队列数据: 54 2
队列中打印出来
---队列数据个数: 5
---队列数据: 12 100 100 54 2
进行一次出队列操作,出队列数据为: 2
队列中打印出来
---队列数据个数: 4
---队列数据: 12 100 100 54
在进行 4 次出队列后打印:
队列中打印出来
---队列数据个数: 4
---队列数据: 4 3 2 1
