网站外链建设的八大基本准则,威海百度网站建设,成都学校网站制作,微网站模板在线今天学习的是线性表里面的栈和队列
链表的相关知识可以查看http://t.csdnimg.cn/NX464
顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ
目录
栈
栈的定义
栈的特点
顺序栈
结构体
顺序栈的相关操作案例
链式栈
结构体
链式栈的相关操作案例
总结
队列
队列…今天学习的是线性表里面的栈和队列
链表的相关知识可以查看http://t.csdnimg.cn/NX464
顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ
目录
栈
栈的定义
栈的特点
顺序栈
结构体
顺序栈的相关操作案例
链式栈
结构体
链式栈的相关操作案例
总结
队列
队列的定义
队列的特点
顺序队列(又称为循环队列)
结构体
顺序队列的相关操作案例
链式队列
结构体
链式队列的相关操作案例
栈
栈的定义 只能在一端进行插入和删除操作的线性表又称为堆栈进行插入和删除操作的一端称为栈顶另一端称为栈底。
栈的特点
先进后出 FILO first in last out LIFO
顺序栈 1.逻辑结构线性结构 2.存储结构顺序存储 3.操作入栈、出栈 结构体 typedef struct seqstack { int *data; // 指向栈的存储位置 int maxlen; // 保存栈的最大长度 int top; // 称为栈针用的时候心里面可以将按照顺序表里的last来使用 top 始终代表当前栈内最后一个有效元素的下标 } seqstack_t; 顺序栈的相关操作案例
头文件seqstack.h:
#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_
#include stdio.h
#include stdlib.h
typedef struct seqstack
{int *data; // 指向栈的存储位置int maxlen; // 保存栈的最大长度int top; // 称为栈针用的时候心里面可以将按照顺序表里的last来使用// top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;
// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len); // len代表的是创建栈的时候的最大长度
// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p);
// 3.入栈
int PushStack(seqstack_t *p, int data); // data代表入栈的数据
// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p);
// 5.出栈
int PopSeqStack(seqstack_t *p);
// 6. 清空栈
void ClearSeqStack(seqstack_t *p);
// 7. 获取栈顶数据(注意不是出栈操作如果出栈相当于删除了栈顶数据只是将栈顶的数据获取到不需要移动栈针)
int GetTopSeqStack(seqstack_t *p);
// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p);
#endif顺序栈函数seqstack.c:
#include seqstack.h// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len) // len代表的是创建栈的时候的最大长度
{// 1.开辟一个结构体类型大小的空间seqstack_t *p (seqstack_t *)malloc(sizeof(seqstack_t));if (p NULL){perror(CreateEpSeqStack函数创建结构体失败);return NULL;}// 2.初始化p-top -1;p-maxlen len;p-data (int *)malloc(len * sizeof(int));if (p-data NULL){perror(CreateEpSeqStack函数创建数据空间失败);free(p);p NULL;return NULL;}return p;
}// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p)
{return p-top p-maxlen - 1;
}// 3.入栈
int PushStack(seqstack_t *p, int data) // data代表入栈的数据
{// 1.容错判断(判满)if (IsFullSeqStack(p)){perror(PushStack函数出错\n);return -1;}// 2.移动指针p-top;// 3.入栈p-data[p-top] data;return 0;
}// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p)
{return p-top -1;
}// 5.出栈
int PopSeqStack(seqstack_t *p)
{// 1.容错判断(判空)if (IsEpSeqStack(p)){perror(PopSeqStack函数出错\n);return -1;}// 2.移动指针p-top--;// 3.出栈数据return p-data[p-top 1];
}// 6. 清空栈
void ClearSeqStack(seqstack_t *p)
{p-top -1;
}// 7. 获取栈顶数据(注意不是出栈操作如果出栈相当于删除了栈顶数据只是将栈顶的数据获取到不需要移动栈针)
int GetTopSeqStack(seqstack_t *p)
{while (!IsEpSeqStack(p)){return p-data[p-top];}return -1;
}// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p)
{return p-top 1;
}主函数main.c:
#include seqstack.hint main(int argc, char const *argv[])
{int data;seqstack_t *p CreateEpSeqStack(5);PushStack(p, 1);PushStack(p, 2);PushStack(p, 3);printf(目前栈里的数据为\n);for (int i 0; i LengthSeqStack(p); i){printf(%d , GetTopSeqStack(p));}printf(\n);printf(请输入你要插入的数据\n);scanf(%d, data);PushStack(p, data);printf(出栈操作\n);while (!IsEpSeqStack(p)){printf(出栈的数据为%d , PopSeqStack(p));}printf(\n);free(p-data);p-data NULL;free(p);p NULL;return 0;
}链式栈 1.逻辑结构线性结构 2.存储结构链式存储 3.操作入栈、出栈 结构体 typedef struct linkstack { datatype data; // 数据域 struct linkstack *next; // 指针域 } linkstack_t; 链式栈的相关操作案例
头文件linkstack.h:
#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include stdio.h
#include stdlib.h
// 入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{datatype data; // 数据域struct linkstack *next; // 指针域
} linkstack_t;// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop);
// 2.入栈 data是入栈的数据
// 参数上之所以采用二级指针因为我们要随着入栈添加新的节点作为头top需要永远指向当前链表的头
// 那么修改main函数中的top我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data);
// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top);
// 4.出栈
datatype PopLinkStack(linkstack_t **ptop);
// 5.清空栈
void ClearLinkStack(linkstack_t **ptop); // 用二级指针是因为清空后需要将main函数中的top变为NULL
// 6.求栈的长度
int LengthLinkStack(linkstack_t *top); // 用一级指针是因为我只是求长度不需要修改main函数中top指针的指向
// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top所以用一级指针
datatype GetTopLinkStack(linkstack_t *top);
#endif链式栈函数linkstack.c:
#include linkstack.h// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop)
{*ptop NULL;
}// 2.入栈
// data是入栈的数据
// 参数上之所以采用二级指针因为我们要随着入栈添加新的节点作为头top需要永远指向当前链表的头那么修改main函数中的top我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data)
{// 1.创建一个新节点并初始化linkstack_t *pnew (linkstack_t *)malloc(sizeof(linkstack_t));if (pnew NULL){perror(PushLinkStack函数出错\n);return -1;}pnew-data data;pnew-next NULL;// 2.将新节点插到无头单向链表中pnew-next *ptop;// 3.移动栈针栈针永远指向无头单向链表的第一个节点*ptop pnew;return 0;
}// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{return top NULL;
}// 4.出栈 *ptop--top
datatype PopLinkStack(linkstack_t **ptop)
{// 1.容错判断(判空)if (IsEpLinkStack(*ptop)){perror(PopLinkStack函数出错\n);return -1;}// 2.定义pdel指向被删除节点linkstack_t *pdel *ptop;// 3.定义一个变量temp保存出栈数据datatype temp pdel-data; // datatype temp (*ptop)-data;// 4.移动指针*ptop pdel-next; // *ptop (*ptop)-next;// 5.释放被删除节点free(pdel);pdel NULL;return temp;
}// 5.清空栈
void ClearLinkStack(linkstack_t **ptop) // 用二级指针是因为清空后需要将main函数中的top变为NULL
{while (!(IsEpLinkStack(*ptop))){PopLinkStack(ptop);}
}// 6.求栈的长度
int LengthLinkStack(linkstack_t *top) // 用一级指针是因为只是求长度不需要修改main函数中top指针的指向
{int len 0;while (top ! NULL){top top-next;len;}return len;
}// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{if (IsEpLinkStack(top)){perror(GetTopLinkStack函数出错\n);return -1;}return top-data;
}
主函数main.c:
#include linkstack.hint main(int argc, char const *argv[])
{linkstack_t *p NULL;for (int i 1; i 5; i){PushLinkStack(p, i);}printf(栈的长度为%d\n, LengthLinkStack(p));while (!(IsEpLinkStack(p))){printf(%d , PopLinkStack(p));}printf(\n);ClearLinkStack(p);return 0;
}总结
顺序栈和链式栈的区别 (1)存储结构不同顺序栈相当于数组连续的链式栈 链表非连续的 (2)顺序栈的长度受限制而链栈不会 队列
顺序队列(循环队列) 和 链式队列
队列的定义
只允许在两端进行插入和删除操作的线性表在队尾插入在队头删除 插入的一端被称为队尾删除的一端被称为队头。
在队列操作过程中为了提高效率以调整指针代替队列元素的移动并将数组作为循环队列的操作空间。
队列的特点 先进先出 FIFO first in first out 后进后出 LILO last 顺序队列(又称为循环队列) 1.逻辑结构: 线性结构 2.存储结构顺序存储结构 3.操作入列出列 结构体 #define N 5 typedef int datatype; typedef struct { datatype data[N]; int rear; //存数据端 rear 后面 int front; //取数据端 front 前面 }sequeue_t;//sequence 顺序 queue队列 注意
循环队列中假设数组的元素个数为N那么循环队列中存储最多的数据个数为N-1个
原因舍去数组上的一个存储位置,用于判断队列是否为满
顺序队列的相关操作案例
头文件sequeue.h:
#ifndef _SEQUEUE_H_
#define _SEQUEUE_H_
#include stdio.h
#include stdlib.h
#define N 5
typedef int datatype;
typedef struct
{datatype data[N]; // 循环队列的数组int rear; // 存数据端 rear 后面int front; // 取数据端 front 前面
} sequeue_t;
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue();
// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data);
// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p);
// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p);
// 5.出列
datatype OutSequeue(sequeue_t *p);
// 6.求队列的长度
int LengthSequeue(sequeue_t *p);
// 7.清空队列函数
void ClearSequeue(sequeue_t *p);
#endif
顺序队列函数sequeue.c:
#include sequeue.h
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue()
{// 1.开辟一个结构体大小的空间sequeue_t *p (sequeue_t *)malloc(sizeof(sequeue_t));if (p NULL){perror(CreateEmptySequeue函数报错\n);return NULL;}// 2.初始化p-rear p-front 0;return p;
}// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data)
{// 1.判满if (IsFullSequeue(p)){perror(InSequeue函数出错\n);return -1;}// 2.将数据入列p-data[p-rear] data;p-rear (p-rear 1) % N;return 0;
}// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p)
{return (p-rear 1) % N p-front;
}// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p)
{return p-rear p-front;
}// 5.出列
datatype OutSequeue(sequeue_t *p)
{// 1.判空if (IsEmptySequeue(p)){perror(OutSequeue函数出错\n);return -1;}// 2.出列// 取出数据datatype temp p-data[p-front];// 移动头指针p-front (p-front 1) % N;return temp;
}
// 6.求队列的长度
int LengthSequeue(sequeue_t *p)
{// // 1.方法一// if (p-rear p-front)// {// return p-rear - p-front;// }// else// {// return p-rear - p-front N;// }// 2.方法二return (p-rear - p-front N) % N;
}
// 7.清空队列函数
void ClearSequeue(sequeue_t *p)
{p-front p-rear;
}
主函数main.c:
#include sequeue.hint main(int argc, char const *argv[])
{sequeue_t *p CreateEmptySequeue();for (int i 0; i 4; i){InSequeue(p, i);}printf(顺序队列的长度为%d\n, LengthSequeue(p));OutSequeue(p);OutSequeue(p);OutSequeue(p);InSequeue(p, 10);printf(顺序队列的长度为%d\n, LengthSequeue(p));while (!IsEmptySequeue(p)){printf(%d , OutSequeue(p));}printf(\n);printf(清空顺序队列\n);ClearSequeue(p);free(p);p NULL;return 0;
}链式队列 1.逻辑结构: 线性结构 2.存储结构链式存储 3.操作入列 、出列 结构体 typedef struct node { datatype data;//数据域 struct node *next;//指针域 }linkqueue_node_t,*linkqueue_list_t; typedef struct//将队列头指针和尾指针封装到一个结构体里 { linkqueue_list_t front;//相当于队列的头指针 linkqueue_list_t rear;//相当于队列的尾指针 //有了链表的头指针和尾指针那么我们就可以操作这个链表 }linkqueue_t; 链式队列的相关操作案例
头文件linkqueue.h:
#ifndef _LINKQUEUE_H_
#define _LINKQUEUQ_H_#include stdio.h
#include stdlib.h
typedef int datatype;
typedef struct node
{datatype data; // 数据域struct node *next; // 指针域
} linkqueue_node_t, *linkqueue_list_t;// linkqueue_list_t p linkqueue_node_t *
typedef struct // 将队列头指针和尾指针封装到一个结构体里
{linkqueue_list_t front; // 相当于队列的头指针linkqueue_list_t rear; // 相当于队列的尾指针// 有了链表的头指针和尾指针那么我们就可以操作这个链表
} linkqueue_t;
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue();
// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data);
// 3.出列
datatype OutLinkQueue(linkqueue_t *p);
// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p);
// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p);
// 6.清空队列
void ClearLinkQueue(linkqueue_t *p);
#endif
链式队列函数linkqueue.c:
#include linkqueue.h
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue()
{// 1.创建存放头尾指针的空间linkqueue_t *p (linkqueue_t *)malloc(sizeof(linkqueue_t));if (p NULL){perror(CreateEmptyLinkQueue函数创建存放头尾指针的空间出错\n);return NULL;}// 2.初始化p-front p-rear (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (p-front NULL){perror(CreateEmptyLinkQueue函数创建链表结构体的空间出错\n);return NULL;}p-front-next NULL;return p;
}// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data)
{// 1.开辟一个节点并初始化存放数据linkqueue_list_t pnew (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (pnew NULL){perror(InLinkQueue函数出错\n);return -1;}pnew-next NULL;pnew-data data;// 2.数据入队p-rear-next pnew;// 3.移动尾指针p-rear pnew;return 0;
}// 3.出列
datatype OutLinkQueue(linkqueue_t *p)
{// 1.判空if (IsEmptyLinkQueue(p)){perror(OutLinkQueue函数出错\n);return -1;}// 2.出列数据// (1)定义pdel指向头节点linkqueue_list_t pdel p-front;// (2)移动头指针p-front p-front-next;// (3)释放头节点free(pdel);pdel NULL;// (4)出队数据return p-front-data;
}// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p)
{return p-rear p-front;
}// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p)
{int len 0;linkqueue_list_t q p-front;while (q-next! NULL){q q-next;len;}return len;
}// 6.清空队列
void ClearLinkQueue(linkqueue_t *p)
{while (!IsEmptyLinkQueue(p)){OutLinkQueue(p);}
}主函数main.c
#include linkqueue.hint main(int argc, char const *argv[])
{linkqueue_t *p CreateEmptyLinkQueue();InLinkQueue(p, 1);InLinkQueue(p, 2);InLinkQueue(p, 3);printf(链式队列的长度为%d\n, LengthLinkQueue(p));printf(%d , OutLinkQueue(p));printf(%d , OutLinkQueue(p));printf(%d , OutLinkQueue(p));printf(\n);printf(清空链式队列\n);ClearLinkQueue(p);free(p-front);p-front NULL;free(p);p NULL;return 0;
}
