队列的链式存储结构(C语言实现)
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERR 2 #define TRUE 1 #define FALSE 0 typedef int status; //定义函数返回的状态,OK & ERR typedef char datatype; //定义队列中每个元素的数据类型,这里暂定为字符型 typedef struct LinkQueue_anon{ datatype data; //数据区 struct LinkQueue_anon * next; //指针区 } LinkQueue; typedef struct { LinkQueue * front, * rear; /* 创建队列的游标,保存着队列的头尾指针所指向的结点 front指向队列的第一个结点(队头),rear指向队列的最后一个结点(队尾) 规定: 当front=rear=NULL时,表示队列为空 当front=rear!=NULL时,表示队列只有一个元素 */ }LinkQueueCursor; /* 函数原型,队列的基本操作,与栈相同 */ LinkQueueCursor *createLinkQueue(datatype first_node_value); status isEmpty(LinkQueueCursor *L); void clear(LinkQueueCursor *L); datatype getTop(LinkQueueCursor *L); int getLength(LinkQueueCursor *L); status push(LinkQueueCursor *L, datatype node_to_push); datatype pop(LinkQueueCursor *L); void showQueue(LinkQueueCursor *L); int main(){ /* 测试 */ LinkQueueCursor * mycursor; mycursor=createLinkQueue(‘1‘); //创建一个游标,同时入队一个元素,其值为‘1‘ printf("isEmpty = %d\n",isEmpty(mycursor)); printf("Length = %d\n",getLength(mycursor)); push(mycursor,‘a‘); push(mycursor,‘b‘); push(mycursor,‘c‘); push(mycursor,‘d‘); printf("isEmpty = %d\n",isEmpty(mycursor)); printf("Length = %d\n",getLength(mycursor)); showQueue(mycursor); putchar(‘\n‘); printf("pop = %c\n",pop(mycursor)); printf("pop = %c\n",pop(mycursor)); printf("getTop = %c\n",getTop(mycursor)); printf("isEmpty = %d\n",isEmpty(mycursor)); printf("Length = %d\n",getLength(mycursor)); showQueue(mycursor); putchar(‘\n‘); clear(mycursor); printf("isEmpty = %d\n",isEmpty(mycursor)); printf("Length = %d\n",getLength(mycursor)); return 0; } LinkQueueCursor *createLinkQueue(datatype first_node_value){ LinkQueueCursor *tmp_cur; LinkQueue *tmp; tmp_cur=malloc(sizeof(LinkQueueCursor)); //void*类型指针能自动转为其他类型的指针 tmp=malloc(sizeof(LinkQueue)); tmp_cur->front=tmp_cur->rear=tmp; //初始化游标 tmp->data=first_node_value; //初始化数据区 tmp->next=NULL; //初始化指针区 return tmp_cur; } status isEmpty(LinkQueueCursor *L){ if (L->front==L->rear && L->front==NULL) return TRUE; else return FALSE; } void clear(LinkQueueCursor *L){ LinkQueue * p,* q; if (isEmpty(L)) return; //空队列,不需要clear,所以直接返回 if (L->front==L->rear && L->front!=NULL){ //只有一个元素的队列,front和rear都指向这个元素 free(L->front); L->front=L->rear=NULL; //把队列设为空 return; } /* 当队列的元素大于1时 */ p=L->front; //p指向当前要被删除的结点 while (p){ //当p不为NULL继续循环 q=p->next; //q指向p的下一个结点 free(p); p=q; //交换 } L->front=L->rear=NULL; //把队列设为空 } datatype getTop(LinkQueueCursor *L){ return L->front->data; //直接返回队头的数据即可 } int getLength(LinkQueueCursor *L){ int i=0; LinkQueue * p; if (isEmpty(L)) return 0; //空队列,返回0 if (L->front==L->rear && L->front!=NULL) return 1; //规定:front=rear,说明队列只有一个元素 /* 队列的长度大于1时 */ p=L->front; while (p!=L->rear){ //还没到rear(队尾)则继续循环 i++; p=p->next; } return i+1; /* 上面的【队列的长度大于1时】还能用下面的等价代码代替 p=L->front; while (p){ //p不为NULL则继续循环,因为rear(队尾)结点的next(指针区)一定是NULL i++; p=p->next; } return i; */ } status push(LinkQueueCursor *L, datatype node_to_push){ //node_to_insert表示想要在队尾处入队的元素 LinkQueue * s=malloc(sizeof(LinkQueue)); s->data=node_to_push; //初始化新入队的元素 s->next=NULL; if (isEmpty(L)==TRUE){ //插入到空队列 L->front=L->rear=s; //入队,当队列只有一个元素时,规定front和rear都指向这个元素 }else{ //插入到已存在元素的队列 L->rear->next=s; //入队,将新元素附在rear指向的结点的后面 L->rear=s; //rear后移,即将它指向新元素 } return OK; } datatype pop(LinkQueueCursor *L){ //出队,即将队头删除 datatype v; LinkQueue * s; if (isEmpty(L)) return (datatype)ERR; //空队列 if (L->front==L->rear && L->front!=NULL){ //队列只有一个元素 v=L->front->data; //把这个元素的值赋值给临时变量 free(L->front); //删除这个元素 L->front=L->rear=NULL; //把队列设置为空 }else{ v=L->front->data; //将要删除的元素的值先赋值给临时变量 s=L->front; //将要删除的元素先赋值给临时变量 L->front=L->front->next; //将游标所保存的front后移到下个结点(元素) free(s); //删除原来的头结点(元素) } return v; //返回出队结点(元素)的值 } void showQueue(LinkQueueCursor *L){ int i; int total=getLength(L); LinkQueue * p; p=L->front; for (i=0; i<total; i++){ printf("%c\t",p->data); p=p->next; } } /* 队列的定义:只允许在一端进行插入,另一端进行删除的线性表,也是一种操作受限的线性表 一般,把允许插入的一端叫做队尾,允许删除的一端叫做队头 不含任何元素的队列就是空队 所以,队列又称先进先出(First in First out)的线性表 队列的链式存储其实就是线性表中的单链表,只不过它只能尾进头出 */ /* 环境: Code::Blocks with GCC 5.1 */
运行截图:
相关推荐
lpkwxl 2020-06-17
chensen 2020-11-14
拉斯厄尔高福 2020-11-04
杜倩 2020-10-29
拉斯厄尔高福 2020-10-19
嵌入式资讯精选 2020-10-15
zhaochen00 2020-10-13
penkgao 2020-10-13
yiyilanmei 2020-10-05
wanshiyingg 2020-09-29
Mars的自语 2020-09-27
shenwenjie 2020-09-24
一个逗逗 2020-09-22
flycony 2020-09-13
zhaochen00 2020-08-20
Biao 2020-08-20
qingsongzdq 2020-08-19