当前位置： 首页 > news >正文

佛山网站建设及优化公司友情链接交换方式有哪些

news 2025/7/27 16:23:33
佛山网站建设及优化公司,友情链接交换方式有哪些,网站用哪些系统做的比较好用,做直播哪个网站好目录 一.循环队列简单介绍 二.用静态数组实现循环队列 1.数组循环队列结构设计 2.数组循环队列的堆区内存申请接口 3.数据出队和入队的接口实现 4.其他操作接口 5.数组循环队列的实现代码总览 三.静态单向循环链表实现循环队列 1.链表循环队列的结构设计 2.创建静…

 

目录

一.循环队列简单介绍

二.用静态数组实现循环队列

1.数组循环队列结构设计

2.数组循环队列的堆区内存申请接口 

3.数据出队和入队的接口实现

4.其他操作接口

5.数组循环队列的实现代码总览 

三.静态单向循环链表实现循环队列 

1.链表循环队列的结构设计

2.创建静态单向循环链表的接口

3.数据的出队和入队接口

4.其他队列操作接口

5.静态链表循环队列总体代码

问题来源:622. 设计循环队列 - 力扣（Leetcode）

一.循环队列简单介绍

  • 循环队列一般是一种静态的线性数据结构,其中的数据符合先进先出的原则.
  • 循环队列的容器首地址和容器尾地址通过特定操作(比如指针链接,数组下标取余等方式)相连通,从而实现了容器空间的重复利用(在一个非循环静态队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间)

 

二.用静态数组实现循环队列

维护队列的结构体:

typedef struct 
{int * arry;  //指向堆区数组的指针int head;    //队头指针int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)int capacity;//静态队列的容量
} MyCircularQueue;

1.数组循环队列结构设计

我们假定静态数组的容量为k(可存储k个数据)：

  • 根据队列的基本数据结构:有两个指针用于维护数组中的有效数据空间,分别为head指针和tail指针,head指针用于指向队头数据,tail用于指向队尾数据的下一个位置(即tail指针不指向有效数据)
  •  如图所示,head指针和tail指针之间就是有效数据的内存空间
  • 通过head指针和tail指针的关系来实现队列的判满(判断队列空间是否已被占满)与判空(判断队列是否为空队列)；为了达到这个目的,我们需要将静态数组的容量大小设置为k+1(即多设置一个元素空间) 
  1. 队列的判空条件: tail == head;
  2. 队列的判满条件: (tail+1)%(k+1) == head; 另外一种情形:
  • 由此我们可以先设计出队列的判满和判空接口： 
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空
{assert(obj);return (obj->tail == obj->head);
}bool myCircularQueueIsFull(MyCircularQueue* obj)  //判断队列是否为满
{assert(obj);return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}

2.数组循环队列的堆区内存申请接口 

  • 在堆区上创建MyCircularQueue结构体,同时为队列申请一个空间大小为(k+1)*sizeof(DataType)字节的数组： 
    MyCircularQueue* myCircularQueueCreate(int k)  //k个容量大小的循环队列的初始化接口
{MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));//开辟维护循环队列的结构体if(NULL == tem){perror("malloc failed");exit(-1);}tem->arry = NULL;tem->capacity = k;   //队列的数据容量为ktem->arry = (int*)malloc((k+1)*sizeof(int));//开辟堆区数组if(NULL == tem->arry){perror("malloc failed");exit(-1);}//将head,tail下标初始化为0tem->head = 0; tem->tail = 0;return tem;
}

3.数据出队和入队的接口实现

数据出队和入队的图解:

 

  •  根据图解我们可以设计出数据入队和出队的接口: 
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口
{assert(obj);if(myCircularQueueIsFull(obj)){return false;}//确保队列没满obj->arry[obj->tail]=value;obj->tail = (obj->tail + 1)%(obj->capacity +1);return true;
}
    bool myCircularQueueDeQueue(MyCircularQueue* obj)    //数据出队接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//确保队列不为空obj->head = (obj->head +1)%(obj->capacity +1);return true;
}

4.其他操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)   //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arry[obj->head];
}

 返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;//注意tail如果指向数组首地址,则尾数据位于数组最后一个位置return obj->arry[labelret];
}

队列的销毁接口:

void myCircularQueueFree(MyCircularQueue* obj)     //销毁队列的接口
{assert(obj);free(obj->arry);obj->arry = NULL;free(obj);obj = NULL;
}

5.数组循环队列的实现代码总览 

 数组循环队列总体代码:

typedef struct 
{int * arry;  //指向堆区数组的指针int head;    //队头指针int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)int capacity;//静态队列容量
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明MyCircularQueue* myCircularQueueCreate(int k)          //循环队列初始化接口
{MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));//开辟维护循环队列的结构体if(NULL == tem){perror("malloc failed");exit(-1);}tem->arry = NULL;tem->capacity = k;   //队列的数据容量为ktem->arry = (int*)malloc((k+1)*sizeof(int));//开辟堆区数组if(NULL == tem->arry){perror("malloc failed");exit(-1);}tem->head = 0;tem->tail = 0;return tem;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口
{assert(obj);if(myCircularQueueIsFull(obj)){return false;}//确保队列没满obj->arry[obj->tail]=value;obj->tail = (obj->tail + 1)%(obj->capacity +1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)           //数据出队接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}//确保队列不为空obj->head = (obj->head +1)%(obj->capacity +1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)               //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arry[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj)                 //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;//注意tail如果指向数组首地址,则尾数据位于数组最后一个位置return obj->arry[labelret];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)              //判断队列是否为空
{assert(obj);return (obj->tail == obj->head);
}bool myCircularQueueIsFull(MyCircularQueue* obj)               //判断队列是否为满
{assert(obj);return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}void myCircularQueueFree(MyCircularQueue* obj)                 //销毁队列的接口
{assert(obj);free(obj->arry);obj->arry = NULL;free(obj);obj = NULL;
}

力扣题解测试:

三.静态单向循环链表实现循环队列 

链表节点结构体定义:

typedef struct listnode
{int data;struct listnode * next;
}ListNode;

维护链表循环队列的结构体:

typedef struct 
{int capacity;     //记录队列容量大小ListNode * head;  //指向队头节点ListNode * tail;  //指向队尾节点
} MyCircularQueue;

1.链表循环队列的结构设计

静态单向循环链表的容量大小为k:

  • 与数组循环队列类似,我们同样需要开辟一个节点个数为k+1的静态循环链表
  • 链表循环队列的总体结构图示:另外一种队列判满的情形:
  1.  链表循环队列的判满条件(判断队列空间是否被占满的关系式):tail->next == head;
  2.  链表循环队列的判空条件(判断队列是否为空队列的关系式): tail == head;

链表循环队列的判满和判空的接口:

bool myCircularQueueIsEmpty(MyCircularQueue* obj)    //判断队列是否为空
{assert(obj);return(obj->head == obj->tail);
}bool myCircularQueueIsFull(MyCircularQueue* obj)     //判断队列是否为满
{assert(obj);return (obj->tail->next == obj->head);
}

2.创建静态单向循环链表的接口

实现一个接口,创建一个维护链表循环队列的结构体同时创建容量大小为k+1的静态单向循环链表:

MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{int NodeNum =k+1;                          //创建k+1个链表节点MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object);                            //申请维护循环队列的结构体object->capacity = k;ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum == k+1){   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode = tem;object->tail = object->head=tem;    //让tail和head指向同一个初始节点}else{ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode->next = tem;                //链接链表节点preNode = tem;}NodeNum--;}preNode->next = object->head;               //将表尾与表头相接return object;
}

3.数据的出队和入队接口

数据出入队图解:

根据图解实现数据出入队接口:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//数据入队接口(从队尾入队)
{assert(obj);if(!obj || myCircularQueueIsFull(obj))  //确定队列没满{return false;}           obj->tail->data = value;                //数据入队obj->tail = obj->tail->next;return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)  //数据出队接口
{assert(obj);if(!obj || myCircularQueueIsEmpty(obj)){return false;}//数据出队obj->head = obj->head->next;return true;
}

4.其他队列操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->head->data; //返回队头元素
}

返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}ListNode * tem = obj->head;while(tem->next != obj->tail)               //寻找队尾元素{tem=tem->next;}return tem->data;  //返回队尾元素
}

队列销毁接口:

队列销毁过程图解:

void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{assert(obj);//利用头指针来完成链表节点的释放ListNode * endpoint = obj->head;           //记录一个节点释放的终点obj->head = obj->head->next;while(obj->head!=endpoint){ListNode * tem = obj->head->next;free(obj->head);obj->head = tem;}free(endpoint);                            //释放掉终点节点free(obj);                                 //释放掉维护环形队列的结构体
}

5.静态链表循环队列总体代码

总体代码:

typedef struct listnode
{int data;struct listnode * next;
}ListNode;typedef struct 
{int capacity;ListNode * head;ListNode * tail;int taildata;   //单向链表找尾复杂度为O(N),因此我们用一个变量来记录队尾数据
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{int NodeNum =k+1;                          //创建k+1个链表节点MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));assert(object);                            //申请维护循环队列的结构体object->capacity = k;ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址while(NodeNum){if(NodeNum == k+1){   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode = tem;object->tail = object->head=tem;    //让tail和head指向同一个初始节点}else{ListNode * tem = (ListNode *)malloc(sizeof(ListNode));assert(tem);preNode->next = tem;                //链接链表节点preNode = tem;}NodeNum--;}preNode->next = object->head;               //将表尾与表头相接return object;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口(从队尾入队)
{assert(obj);if(!obj || myCircularQueueIsFull(obj))  //确定队列没满{return false;}           obj->tail->data = value;                //数据入队obj->tail = obj->tail->next;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)               //数据出队接口
{assert(obj);if(!obj || myCircularQueueIsEmpty(obj)){return false;}obj->head = obj->head->next;return true;
}int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}ListNode * tem = obj->head;while(tem->next != obj->tail)               //寻找队尾元素{tem=tem->next;}return tem->data;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)                  //判断队列是否为空
{assert(obj);return(obj->head == obj->tail);
}bool myCircularQueueIsFull(MyCircularQueue* obj)                    //判断队列是否为满
{assert(obj);return (obj->tail->next == obj->head);
}void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{assert(obj);//利用头指针来完成链表节点的释放ListNode * endpoint = obj->head;           //记录一个节点释放的终点obj->head = obj->head->next;while(obj->head!=endpoint){ListNode * tem = obj->head->next;free(obj->head);obj->head = tem;}free(endpoint);                            //释放掉终点节点free(obj);                                 //释放掉维护环形队列的结构体
}

leetcode题解测试:

 

 

 

http://www.yidumall.com/news/47655.html

相关文章：

  • 河南seo推广平台seo的方法有哪些
  • 相亲网站绑定微信怎么做怎样在百度上发表文章
  • 广州专业网站制作seo交互论坛
  • 注销网站和取消接入知了seo
  • 怎么做视频聊天网站seo入门基础知识
  • 虚拟商品购物网站源码营销软件培训
  • 昆明建设局网站号码自己有货源怎么找客户
  • 网站添加广告源码百度首页入口
  • 潍坊网站建设公司哪家好今日热点新闻事件及评论
  • 制作网站的流程全媒体广告代理加盟
  • 公司品牌网站建设价格低百度广告一级代理
  • 西宁网站制作哪家公司好seo优化范畴
  • 网站流量刷桂平seo关键词优化
  • 企业网站推广和营销网页推广区别线上广告宣传方式有哪些
  • 营销网站设计公司有哪些人工智能培训机构哪个好
  • 织梦做企业网站个人网站怎么制作
  • 日本做美食视频网站市场调研报告怎么写
  • 建立网站服务器长沙seo网站
  • 如何看网站排名本周新闻热点
  • 大学生创业做网站友情链接是什么
  • 网站营销体系的建设及运营情况腾讯控股第三季度营收1401亿
  • 模板做的网站不好优化百度seo按天计费
  • 快速做网站的方法seo优化报价公司
  • 无锡百度网站排名万网查询
  • 爱用建站正规吗靠谱的代写平台
  • 做编程网站新东方托福班价目表
  • 做旅游海报的软件或是网站营销型网站策划方案
  • 如何用另一个端口做网站线上推广软件
  • 物流网站建设重要性百度竞价课程
  • 怎么做好推广廊坊百度推广seo