step3 . day4 数据结构之线性表 栈和队
補充一下：循環(huán)鏈表初學可能不好理解，除了多畫圖以外，把循環(huán)鏈表想象成無限的單向（或者雙向）鏈表，每一個元素都是中間元素，就更好理解了。
1.棧和隊是線性表的兩種特殊管理邏輯，兩者都是線性表
2.棧的原則是先入后出FILO(first in last out)，類似桶裝餅干，最后裝入的先被取出用掉，只能在棧頂進行壓棧和彈棧操作
3.隊的原則是先入先出FIFO(first in first out)，類似水管，流出的水是先進入的水，只能在隊尾插入，隊首刪除操作。
?
①棧的順序存儲結構實現(xiàn)，和順序鏈表一樣，只是需要遵從棧的規(guī)則
②棧的鏈表結構實現(xiàn)
#include<stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct stack{
datatype data;
struct stack * next; //棧頂?shù)奈恢?br />}linkstack;
//1. 創(chuàng)建一個空棧
linkstack *linkstack_create()
{
linkstack *s = NULL;
s = (linkstack *)malloc(sizeof(linkstack));
s->next = NULL;
return s;
}
//2. 入棧操作 壓棧
void linkstack_push(linkstack *s,int value)
{
linkstack * temp = linkstack_create();
temp->data = value;
while(s->next != NULL){ s = s->next;}
temp->next = s->next;
s->next = temp;
}
//判斷棧為空
int linkstack_is_empty(linkstack *s)
{
return s->next == NULL ? 1 : 0;
}
//4.出棧 彈棧
int linkstack_pop(linkstack *s)
{
if(linkstack_is_empty(s) == 1)
{
printf("stack is empty.\n");
return -1;
}
int value;
linkstack * temp;
while(s->next->next != NULL){ s = s->next;}
value = s->next->data;
temp = s->next;
s->next = NULL;
free(temp);
temp = NULL;
return value;
}
//打印棧里面的所有值
int linkstack_show(linkstack *s)
{
if(linkstack_is_empty(s) == 1)
{
printf("stack is empty.\n");
return -1;
}
while(s->next !=NULL){
printf("%d ",s->next->data);
s = s->next;
}
printf("\n");
return 0;
}
int main(int argc, const char *argv[])
{
linkstack *s = NULL;
s = linkstack_create();
linkstack_push(s,1);
linkstack_push(s,2);
linkstack_push(s,3);
linkstack_push(s,4);
linkstack_push(s,5);
linkstack_push(s,6);
linkstack_show(s);
printf("%d \n",linkstack_pop(s));
linkstack_show(s);
return 0;
}
③隊的順序存儲實現(xiàn)，需要掌握的隊首和隊尾值之間的相互取余關系，實現(xiàn)循環(huán)隊列
#include <stdio.h>
#include <stdlib.h>
#define N 32
typedef struct queue{
int date[N];
int front;
int rear;
}sequeue;
sequeue * sequeue_creat(){
sequeue * q = NULL;
q = (sequeue*)malloc(sizeof(sequeue));
q->front = 0;
q->rear = 0;
return q;
}
int sequeue_is_full(sequeue *q){
return (q->rear + 1) % N == q->front ? 1 : 0;
}
int sequeue_is_empty(sequeue *q){
return q->rear == q->front ? 1 : 0;
}
int sequeue_input(sequeue *q,int value){
if(sequeue_is_full(q)){
printf("sequeue_is_full\n");
return -1;
}
q->date[q->rear] = value;
q->rear = (q->rear + 1) % N;
return 0;
}
int sequeue_output(sequeue * q){
if(sequeue_is_empty(q)){
printf("sequeue_is_empty\n");
return -1;
}
int value;
value = q->date[q->front];
q->front = (q->front+1) % N;
return value;
}
void sequeue_show(sequeue* q){
int i = 0;
for(i = q->front;i != q->rear;i = ((i+1) % N)){
printf("%d ",q->date[i]);
}
printf("\n");
}
?
int main(int argc, const char *argv[])
{
sequeue *q =NULL;
q = sequeue_creat();
sequeue_input(q,1);
sequeue_input(q,2);
sequeue_input(q,3);
sequeue_input(q,4);
sequeue_input(q,5);
sequeue_input(q,6);
sequeue_show(q);
printf("%d\n",sequeue_output(q));
sequeue_show(q);
return 0;
}
③隊的鏈表存儲形式實現(xiàn)，和單向鏈表類似，注意保持front和priv指針
#include <stdio.h>
#include <stdlib.h>
//隊成員結構體
typedef struct linkqueue{
int date;
struct linkqueue * next;
}linkqueue;
//隊首尾指針結構體
typedef struct lnqueue{
struct linkqueue * front;
struct linkqueue * priv;
}lnqueue;
//節(jié)點創(chuàng)建函數(shù)
linkqueue * linkqueue_creat(){
linkqueue * head = NULL;
head = (linkqueue*)malloc(sizeof(linkqueue));
head->next = NULL;
return head;
}
//隊頭及隊指針創(chuàng)建
lnqueue * lnqueue_creat(){
linkqueue * head =NULL;
head = linkqueue_creat();
lnqueue* ln = NULL;
ln = (lnqueue *)malloc(sizeof(lnqueue));
ln->front = head;
ln->priv = head;
}
//進隊 尾插
void lnqueue_input(lnqueue * ln,int value){
linkqueue * temp =NULL;
temp = linkqueue_creat();
temp->date = value;
temp->next = ln->priv->next;
ln->priv->next = temp;
ln->priv = temp;
}
//判斷是否位空隊
int lnqueue_is_empty(lnqueue *ln){
return ln->front == ln->priv ? 1 : 0;
}
//遍歷
int lnqueue_show(lnqueue * ln){
if(lnqueue_is_empty(ln)){
printf("lnqueue_is_empty\n");
return -1;
}
linkqueue *temp = ln->front;
while(temp->next != NULL){
printf("%d ",temp->next->date);
temp = temp->next;
}
printf("\n");
return 0;
}
//出隊 頭刪
int lnqueue_output(lnqueue * ln){
if(lnqueue_is_empty(ln)){
printf("lnqueue_is_empty\n");
return -1;
}
linkqueue * temp =NULL;
int value;
temp = ln->front->next;
value = temp->date;
ln->front->next = temp->next;
if(ln->priv == temp){
ln->priv = ln->front;
}
free(temp);
temp = NULL;
return value;
}
?
int main(int argc, const char *argv[])
{
lnqueue * ln = NULL;
ln = lnqueue_creat();
lnqueue_input(ln,1);
lnqueue_input(ln,2);
lnqueue_input(ln,3);
lnqueue_input(ln,3);
lnqueue_input(ln,3);
lnqueue_input(ln,6);
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
printf("%d\n",lnqueue_output(ln));
lnqueue_show(ln);
return 0;
}
?
轉載于:https://www.cnblogs.com/huiji12321/p/11233942.html
總結
以上是生活随笔為你收集整理的step3 . day4 数据结构之线性表 栈和队的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： step3 . day3 数据结构之线性
- 下一篇： 信息发布webpart——网页编辑器应用