站点建设方案,北京旧房改造装修哪家好,北京 广告 手机网站,怎样用百度做网站优化队列可以理解为单链表的阉割版#xff0c;相比单链表而言#xff0c;队列只有在添加和删除元素上和单链表有区别 一.队列的链式实现#xff1a;
1.图解#xff1a; 2.代码#xff1a;
#includestdio.h
typedef struct LinkNode //链式队列结点
{int data;st…队列可以理解为单链表的阉割版相比单链表而言队列只有在添加和删除元素上和单链表有区别 一.队列的链式实现
1.图解 2.代码
#includestdio.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
int main()
{return 0;
} 二.初始化队列
1.带头结点
a.图解 b.代码
#includestdio.h
#includestdlib.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向头结点Q.front Q.rear (LinkNode *)malloc(sizeof(LinkNode));//malloc用于申请一个头结点 Q.front - nextNULL; //头指针下一个元素为NULL,因为一开始什么都没有
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontQ.rear ) //也可以这么判断:如果Q.front - nextNULL此时队列为空 {return true; //代表队列为空 }else{return false; //代表队列不为空 }
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。 return 0;
}
2.不带头结点
a.图解 b.代码
#includestdio.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(不带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向NULLQ.frontNULL;Q.rearNULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontNULL ) //只需要看头指针是否等于NULL即可,也可以看Q.rear是否为NULL,是的话队列为空 {return true; //代表队列为空,头指针为NULL,代表没有头指针,自然队列为空 }else{return false; //代表队列不为空 }
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。return 0;
} 三.入队操作
1.带头结点
a.图解 b.代码
#includestdio.h
#includestdlib.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向头结点Q.front Q.rear (LinkNode *)malloc(sizeof(LinkNode));//malloc用于申请一个头结点 Q.front - nextNULL; //头指针下一个元素为NULL,因为一开始什么都没有
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontQ.rear ) //也可以这么判断:如果Q.front - nextNULL此时队列为空 {return true; //代表队列为空 }else{return false; //代表队列不为空 }
}
//新元素入队(带头结点)
void EnQueue(LinkQueue Q,int x)//只是让x入队,不改变x的值,所以无需
{LinkNode *s (LinkNode *)malloc(sizeof(LinkNode)); //用malloc申请一个新结点用来存要入队的元素 s-data x; //把新插入的元素x放入新结点中 s-next NULL; //由于队列入队的操作是在表尾的位置进行,因此新插入的结点是队列的最后一个结点,后面就是NULL Q.rear-next s;/*由于一开始rear指针指向的是当前的表尾结点而新插入的新结点应该连到表尾结点之后所以要把rear指向的结点next指针域指向新结点s */Q.rear s; //修改表尾指针指向新添加的元素新添加的元素就是表尾元素
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。 return 0;
}
2.不带头结点
a.图解 b.代码
#includestdio.h
#includestdlib.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(不带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向NULLQ.frontNULL;Q.rearNULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontNULL ) //只需要看头指针是否等于NULL即可,也可以看Q.rear是否为NULL,是的话队列为空 {return true; //代表队列为空,头指针为NULL,代表没有头指针,自然队列为空 }else{return false; //代表队列不为空 }
}
//新元素入队(不带头结点)
void EnQueue(LinkQueue Q,int x)
{LinkNode *s (LinkNode *)malloc(sizeof(LinkNode));//用malloc申请一个新结点用来存要入队的元素 s-data x;//把新插入的元素x放入新结点中s-next NULL;//由于队列入队的操作是在表尾的位置进行,因此新插入的结点是队列的最后一个结点,后面就是NULL if( Q.frontNULL ) //在空队列中插入第一个元素,插入第一个元素时Q.front为NULL,因为刚开始front和rear都指向NULL { //如果队列为空,那么插入的元素就是队列第一个元素 //修改队头和队尾指针 Q.front s;Q.rear s;}else{Q.rear-next s;//新结点插入到rear结点之后 Q.rear s;//修改rear指针 }
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。return 0;
} 四.出队操作
1.带头结点
a.图解
不是最后一个元素出队 最后一个元素出队 b.代码
#includestdio.h
#includestdlib.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向头结点Q.front Q.rear (LinkNode *)malloc(sizeof(LinkNode));//malloc用于申请一个头结点 Q.front - nextNULL; //头指针下一个元素为NULL,因为一开始什么都没有
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontQ.rear ) //也可以这么判断:如果Q.front - nextNULL此时队列为空 {return true; //代表队列为空 }else{return false; //代表队列不为空 }
}
//队头元素出队(带头结点)
bool DeQueue(LinkQueue Q,int x) //最终x会变为要删除的元素,所以需要
{if( Q.frontQ.rear ){return false;//空队,就无法出队即删除元素 }//此时队列不为空//Q.front为头结点 LinkNode *p Q.front-next; //让p指针指向要删除的结点,对于带头结点的队列来说就是要删除头结点的后一个结点 x p-data; //用变量x返回队头元素即要删除的元素 Q.front-next p-next; //修改头结点的next指针if( Q.rearp ) //此次是最后一个结点出队,最终就是空队列即Q.rearQ.front {Q.rearQ.front; //修改rear指针 } free(p); //释放结点空间return true;
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。 return 0;
}
2.不带头结点
a.图解 b.代码
#includestdio.h
#includestdlib.h
typedef struct LinkNode //链式队列结点
{int data;struct LinkNode *next;
}LinkNode;
typedef struct //链式队列
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue;
//初始化队列(不带头结点)
void InitQueue(LinkQueue Q)
{//初始化时,front和rear都指向NULLQ.frontNULL;Q.rearNULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{if( Q.frontNULL ) //只需要看头指针是否等于NULL即可,也可以看Q.rear是否为NULL,是的话队列为空 {return true; //代表队列为空,头指针为NULL,代表没有头指针,自然队列为空 }else{return false; //代表队列不为空 }
}
//队头元素出队(不带头结点)
bool DeQueue(LinkQueue Q,int x)
{if( Q.frontNULL ){return false; //空队 }LinkNode *pQ.front; //p指向此次出队的结点即front指针指向的结点出队 x p-data; //用变量x返回队头元素 Q.front p-next; //由于没有头结点,所以每次有队头元素出队后都需要修改front指针的指向 if( Q.rearp ) //此次是最后一个结点出队,最终就是空队列 {Q.frontNULL; //front指向NULL Q.rearNULL; //rear指向NULL } free(p); //释放结点空间 return true;
}
int main()
{LinkQueue Q;//声明一个队列InitQueue(Q); //初始化队列//后续操作。。。return 0;
} 五.队列满的条件 六.统计队列的长度
思路
从队头结点开始依次往后遍历统计总共有多少个结点显然时间复杂度为O(n)。 七.总结
