网站建设营销公司,网站设计稿一般尺寸,wordpress怎么作模版,wordpress 图片模板修改数据结构
表
线性表
线性表是 具有相同数据类型的 n个数据元素 的有限序列#xff08;有次序#xff09;#xff0c;其中n为表长#xff0c;当n0时 线性表是一个空表。
若用L命名线性表#xff0c;则其一般表示为
L {a1,a2,…,ai,ai1,…,an}
几个概念#xff1a; …数据结构
表
线性表
线性表是 具有相同数据类型的 n个数据元素 的有限序列有次序其中n为表长当n0时 线性表是一个空表。
若用L命名线性表则其一般表示为
L {a1,a2,…,ai,ai1,…,an}
几个概念
ai是线性表中的“第i个”元素线性表中的位序。位序从1开始数组下标从0开始
a1是 表头元素an是表尾元素。
除了第一个元素外每个元素有且仅有一个直接前驱除最后一个元素外每个元素有且仅有一个直接后继。
什么时候要传入参数的引用“”–对参数的修改结果需要“带回来”
“”指向的是对象本身不占用对象的存储空间而指针本身是一个变量是需要分配存储空间的里面存储对象的地址通过对象地址就能访问操作对象。所以引用和指针都可以访问对象作用是类似的。
顺序表
顺序表–用顺序表存储的方式实现线性表顺序存储。
存储结构把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。
typedef struct{int num;//号数int people;//人数
} Customer;如何知道一个数据元素大小
sizeof(ElemType)顺序表的静态分配
流程
①在内存中分配 存储顺序表L各个数据元素 的连续存储空间。包括MaxSize*sizeofElemType和存储length的空间
②把各个数据元素的值设为默认值
③将Length的值设为0
#includestdio.h
#define MaxSize 10 //定义最大长度
typedef struct{ElemType data[MaxSize];//用静态的“数组”存放数据元素int length;//顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式//基本操作--初始化一个顺序表
void InitList(SqList L){for(int i0;iMaxSize;i)L.data[i]0;//将所有数据元素设置为默认初始值L.length0;//顺序表初始长度为0
}int main(){SqList L; //声明一个顺序表InitList(L);//初始化顺序表//....未完待续后续操作return 0;
}//不初始化数据元素内存不刷0
#includestdio.h
#define MaxSize 10 //定义最大长度
typedef struct{ElemType data[MaxSize];//用静态的“数组”存放数据元素int length;//顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式//基本操作--初始化一个顺序表
//没有设置数据元素的默认值内存中会有遗留的“脏数据”
void InitList(SqList L){L.length0;//顺序表初始长度为0
}int main(){SqList L; //声明一个顺序表InitList(L);//初始化顺序表//尝试“违规”打印出整个data数组for(int i 0;iL.length;i)printf(data[%d]%d\n,i,L.data[i]);return 0;
}顺序表的静态分配过程中如果“数组”存满了怎么办
可以放弃治疗顺序表的表长刚开始确定后就无法更改存储空间是静态的
顺序表的动态分配
key动态申请和释放内存空间
c —— malloc、free函数
#includestdlib.h//malloc、free函数的头文件
L.data (ElemType *) malloc(sizeof(ElemType)* InitSize);
//第一个(ElemType *)强制转换成所定义的数据类型所对应的指针
//malloc用于申请一整片连续的内存空间这整片连续的内存空间有一个起始的内存地址。
//malloc执行结束之后会返回一个指向这整片存储空间开始地址的指针c —— new、delete关键字
#includestdio.h
#includestdlib.h//malloc、free函数的头文件
#define MaxSize 10 //定义最大长度
typedef struct{ElemType *data;//指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SqList; //顺序表的类型定义动态分配方式//基本操作--初始化一个顺序表
//没有设置数据元素的默认值内存中会有遗留的“脏数据”
void InitList(SqList L){L.length0;//顺序表初始长度为0
}//增加动态数组的长度
void IncreaseSize(SeqList L, int len){int *p L.data;L.data (int *) malloc(sizeof(int)* InitSize); for(int i0; iL.length; i){L.data[i]p[i]; //将数据复制到新区域}L.MaxSizeL.MaxSizelen;//顺序表最大长度增加lenfree(p);//释放原来的内存空间
}int main(){SqList L; //声明一个顺序表InitList(L);//初始化顺序表//....往顺序表中随便插入几个元素....return 0;
}顺序表的特点
①随机访问即可以在O(1)时间内找到第i个元素。代码实现data[i-1];静态分配、动态分配都一样。
②存储密度高每个节点只存储数据元素。
③拓展容量不方便即便采用动态分配的方式实现拓展长度的时间复杂度也比较高
④插入、删除操作不方便需要移动大量元素。
顺序表的插入
ListInsert(L, i, e): 插入操作。在表L中的第i个位置上插入指定元素e。
void ListInsert(SqList L, int i, int e){for(int jL.length; ji; j--)//将第i个元素及之后的元素后移L.data[j]L.data[j-1];L.data[i-1]e;//在位置i处放入e数组是从0开始注意位序L.length; //长度加1
}好的算法应该具有“健壮性”。能处理异常情况并给使用者反馈。
#includestdio.h
#define MaxSize 10 //定义最大长度
typedef struct{ElemType data[MaxSize];//用静态的“数组”存放数据元素int length;//顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式bool ListInsert(SqList L, int i, int e){if(i1||iL.length1)//判断i的范围是否有效注意i从1开始算起其为位序return false;if(L.lengthMaxSize)//当前存储空间已满不能插入return false;for(int jL.length; ji; j--)//将第i个元素及之后的元素后移L.data[j]L.data[j-1];L.data[i-1]e;//在位置i处放入e数组是从0开始注意位序L.length; //长度加1return true;
}int main()
{SqList L; //声明一个顺序表InitList(L);//初始化顺序表//...此处省略一些代码插入几个元素ListInsert(L,3,3);return 0;
}顺序表的删除
ListDelete(L, i, e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。
#includestdio.h
#define MaxSize 10 //定义最大长度
typedef struct{ElemType data[MaxSize];//用静态的“数组”存放数据元素int length;//顺序表的当前长度
}SqList; //顺序表的类型定义静态分配方式bool ListDelete(SqList L, int i, int e){if(i1||iL.length) //判断i的范围是否有效return false;eL.data[i-1]; //将被删除的元素赋值给efor(int ji;jL.length;j)//将第i个位置后的元素前移L.data[j-1]L.data[j];L.length--; //线性表长度减1return true;
}int main()
{SqList L; //声明一个顺序表InitList(L);//初始化顺序表//...此处省略一些代码插入几个元素int e -1; //用变量“e“把删除的元素带回来if(ListInsert(L,3,e))printf(已删除第3个元素删除元素值为%d\n,e);elseprintf(位序i不合法删除失败\n);return 0;
}顺序表的查找
按位查找
//GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素值。
#includestdio.h
#define MaxSize 10 //定义最大长度
//typedef struct{
// ElemType data[MaxSize];//用静态的“数组”存放数据元素
// int length;//顺序表的当前长度
//}SqList; //顺序表的类型定义静态分配方式typedef struct{ElemType *data;//指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SqList; //顺序表的类型定义动态分配方式ElemType GetElem(SqList L, int i){return L.data[i-1];
}
按值查找
//LocateElem(L,e):按值查找操作。在表L中从第一个元素开始依次往后检索查找第一个元素值等于e的元素并返回其位序。
#includestdio.h
#define MaxSize 10 //定义最大长度
typedef struct{ElemType *data;//指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SqList; //顺序表的类型定义动态分配方式//在顺序表L中查找第一个元素值等于e的元素并返回其位序
int LocateElem(SeqList L, ElemType e){for(int i0; iL.length; i)if(L.data[i]e)return i1; //数组下标为i的元素值等于e返回其位序i1return 0;//退出循环说明查找失败
}基本数据类型int、char、double、float等可以直接用运算符”“比较。
结构类型的比较
typedef struct{int num;int people;
} Customer;
//注意c语言中结构体的比较不能直接用”“需要依次对比各个分量来判断两个结构体是否相等。
bool isCustomerEqual(Customer a, Customer b){if(a.num b.num a.people b.people)return true;elsereturn false;
}单链表
顺序表每个结点中只存放数据元素
优点可以随机存取存储密度高。
缺点要求大片连续空间改变容量不方便。
单链表每个结点除了存放数据元素外还要存放指向下一个结点的指针。
优点不要求大片连续空间改变容量方便。
缺点不可以随机存取要耗费一定空间存放指针。
struct LNode{ //定义单链表节点类型(结点)ElemType data; //每个节点存放下一数据元素(数据域)struct LNode *next; //指针指向下一个结点(指针域)
};struct LNode *p(struct LNode *)malloc(sizeof(struct LNode));//增加一个新的节点在内存中申请一个结点所需空间并用指针p指向这个结点。//typedef关键字--数据类型重命名
typedef数据类型别名
typedef struct LNode LNode;
LNode* p (LNode *)malloc(sizeof(LNode));用代码定义一个单链表
typedef struct LNode{ //定义单链表结点类型ElemType data; //每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode, *LinkList;//结点单链表结点指针struct LNode{ // 定义单链表结点类型ElemType data; // 每个结点存放一个数据元素struct LNode *next; // 指针指向下一个结点
};LNode *GetElem(Linklist L, int i){int j1;LNode *p L-next;if(i0)return L;if(i1)return NULL;while(p!NULL ji){pp-next;j;}return p;
}typedef struct LNode LNode;
typedef struct LNode *LinkList;//要表示一个单链表时只需要声明一个头指针L指向单链表的第一个结点
LNode *L; //声明一个指向单链表第一个结点的指针。强调这是一个结点。
或
LinkList L;//声明一个指向单链表第一个结点的指针。强调这是一个单链表。头插法建立单链表的算法如下
LinkList List_HeadInsert(LinkList L){//逆向建立单链表LNode *s; int x;L(LinkList)malloc(sizeof(LNode));//创建头节点L-nextNULL; //初始为空链表scanf(%d,x); //输入结点的值while(x!9999){ //输入9999表示结束s(LNode*)malloc(sizeof(LNode));//创建新结点s-data x;s-next L-next;L-next s; //将新节点插入表中L为头指针scanf(%d,x);}return L;
}不带头节点的和带头节点的单链表
#includestdio.h
#includestdlib.h//malloc、free函数的头文件typedef struct LNode{ //定义单链表结点类型ElemType data; //每个结点存放一个数据类型struct LNode *next; //指针指向下一个结点
}LNode, *LinkList;//初始化一个空的单链表
bool InitList(LinkList L){L NULL;//空表暂时还没有任何结点防止脏数据return true;
}//初始化一个单链表(带头结点)
bool InitList1(LinkList L){L(LNode *)malloc(sizeof(LNode));//分配一个头节点if(L NULL) //内存不足分配失败return false;L-next NULL; //头结点之后暂时还没有结点return true;
}//判断单链表是否为空
bool Empty(LinkList L){if(LNULL)return true;elsereturn false;//return (LNULL)
}void test(){LinkList L; //声明一个指向单链表的指针//初始化一个空表InitList(L);InitList1(L);//....后续代码....
}不带头节点V.S.带头结点
不带头节点写代码更麻烦对第一个数据结点和后续数据点的处理需要用不同的代码逻辑对空表和非空表的处理需要用不同的代码逻辑。
头结点是链表里面第一个结点他的数据域可以不存放任何信息有时候也会存放链表的长度等等信息他的指针区域存放的是链表中第一个数据元素的结点就是传说中的首元结点存放的地址。
带头结点写代码更方便用过都说好。
单链表的查找
单链表的查找分为按位查找和按值查找。
注意由于带头结点的方便写代码我们统一使用”双链表“。
GetElem(L, i):按位查找操作。获取表L中第i个位置的元素的值。
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
按位查找
LNode * GetElem(LinkList L, int i){if(i0)return NULL;LNode *p;//指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点不存数据while(p!NULL ji){pp-next;j;}return p;
}//时间复杂度On按值查找
//找到数据域e的结点
LNode *LocateElem(LinkList L,ElemType e){LNode *p L-next;//从第一个结点开始查找数据域为e的结点while(p ! NULL p-data !e)pp-next;return p; //找到后返回该结点的指针否则返回NULL
}//时间复杂度On求表长度
int length(LinkList L){int len 0; //统计表长LNode *p L;while(p-next ! NULL){p p-next;len;}return len;
}//时间复杂度On注意单链表不具备”随机访问“的特性只能依次扫描。
单链表的插入
按位序插入带头结点
ListInsert(L,i,e): 插入操作。在表L中的第i个位置从1开始上插入指定元素e。找到第i-1个结点将新节点插入其后。
//在第i个位置插入元素e带头结点
//在表L中的第i个位置从1开始上插入指定元素e。找到第i-1个结点将新节点插入其后。
//即找到第i-1个结点放在其后面
//边界情况①i1,即在头结点位置插入显然不满足②i1即在结点后面插入即i-1第0个结点插入头结点可行③i为最后一个位置即找到i-1的位置插入typydef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;//在第i个位置插入元素e带头结点
bool ListInsert(LinkList L, int i, ElemType e){if(i1)return false;LNode *p; //指针p指向当前扫描到的结点int j0;//当前p指向的第几个结点,(注意若要插入到表尾则p指向最后一个结点当pNULL时报错)p L;//L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){//循环找到第i-1个结点pp-next;j;}if(pNULL) //i值不合法return false;LNode *s (LNode *)malloc(sizeof(LNode));s-data e;s-next p-next;p-next s; //将结点s连到p之后return true; //插入成功
}按位序插入不带头结点
不存在第0个结点因此i1时需要特殊处理。
typydef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;//在第i个位置插入元素e不带头结点
bool ListInsert(LinkList L, int i, ElemType e){if(i1)return false;if(i1){ //插入第1个结点的操作与其他结点操作不同【不带头结点与带头结点的主要区别】LNode * s (LNode *)malloc(sizeof(LNode));s-data e;s-next L;Ls; //头指针指向新结点。}LNode *p; //指针p指向当前扫描到的结点int j0;//当前p指向的第几个结点,(注意若要插入到表尾则p指向最后一个结点当pNULL时报错)p L;//L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){//循环找到第i-1个结点pp-next;j;}if(pNULL) //i值不合法return false;LNode *s (LNode *)malloc(sizeof(LNode));s-data e;s-next p-next;p-next s; //将结点s连到p之后return true; //插入成功
}结论不带头结点写代码更不方便推荐用带头结点。
指定结点的后插操作
#includestdio.h
#includestdlib.h//malloc、free函数的头文件
typedef struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;//后插操作在p结点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {if (p NULL)return false;LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL) //内存分配失败||某些情况下有可能分配失败如内存不足return false;s-data e; //用结点s保存数据元素es-next p-next;p-next s; //将结点s连到p之后return true;
}指定结点的前插操作
#includestdio.h
#includestdlib.h//malloc、free函数的头文件
typedef struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;//前插操作在p结点之前插入元素e。前插操作方法先用后插操作然后两个结点数据调换即可实现
bool InsertPriorNode(LNode* p, ElemType e) {if (p NULL)return false;LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL) //内存分配失败||某些情况下有可能分配失败如内存不足return false;s-next p-next;p-next s; //新结点s连到p之后s-datap-data; //将p中元素复制到s中p-datae; //p中元素覆盖为ereturn true;
}按位序删除带头结点
ListDelete(L, i, e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。
头结点可以看成是”第0个“结点。
找到第i-1个结点将其指针指向第i1个结点并释放第i个结点。
bool ListDelete(LinkList L, int i, ElemType e){if(i1)return false;LNode *p;//指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点(不存数据)while(p!NULL ji-1){// 循环找到第i-1个结点p p - next;j;}if(pNULL) //i值不合法return false;if(p-next NULL) //第i-1个结点之后已无其他结点return false;LNode *q p-next;//令q指向被删除结点e q-data; //用e返回元素的值p-nextq-next; //将*q结点从链中“断开”free(q);return true; //删除成功}单链表
#define _crt_secure_no_warnings
#include stdio.h
#include stdlib.h/******************单链表**************************/typedef struct LNode { //定义单链表结点类型int data; //每个结点存放一个数据元素struct LNode* next; //指针指向下一个结点
}LNode, * LinkList;//结点单链表结点指针//初始化一个空的单链表(不带头结点)
bool InitList(LinkList L) {L NULL;//空表暂时还没有任何结点防止脏数据return true;
}//初始化一个单链表(带头结点)
bool InitList1(LinkList L) {L (LNode*)malloc(sizeof(LNode));//分配一个头节点if (L NULL) //内存不足分配失败return false;L-next NULL; //头结点之后暂时还没有结点return true;
}//判断单链表是否为空
bool Empty(LinkList L) {if (L NULL)return true;elsereturn false;//return (LNULL)
}//求表长度
int length(LinkList L) {int len 0; //统计表长LNode* p L;while (p-next ! NULL) {p p-next;len;}return len;
}//按位查找
LNode* GetElem(LinkList L, int i) {if (i 0)return NULL;LNode* p;//指针p指向当前扫描到的结点int j 0; //当前p指向的是第几个结点p L; //L指向头结点头结点是第0个结点不存数据while (p ! NULL j i) {p p-next;j;}return p;
}//按值查找找到数据域e的结点
LNode* LocateElem(LinkList L, int e) {LNode* p L-next;//从第一个结点开始查找数据域为e的结点while (p ! NULL p-data ! e)p p-next;return p; //找到后返回该结点的指针否则返回NULL
}//在第i个位置插入元素e带头结点
//在表L中的第i个位置从1开始上插入指定元素e。找到第i-1个结点将新节点插入其后。
//即找到第i-1个结点放在其后面
//边界情况①i1,即在头结点位置插入显然不满足②i1即在结点后面插入即i-1第0个结点插入头结点可行③i为最后一个位置即找到i-1的位置插入
bool ListInsertH(LinkList L, int i, int e) {if (i 1)return false;LNode* p;int j 0;p L;while (p ! NULL j i - 1) {p p-next;j;}if (p NULL)//i值不合法return false;LNode *s (LNode*)malloc(sizeof(LNode));s-data e;s-next p-next;p-next s;return true;
}//按位序插入不带头结点
bool ListInsert(LinkList L, int i, int e) {if (i 1) {return false;}if (i 1) {LNode* s (LNode*)malloc(sizeof(LNode));s-data e;s-next L;L s;}LNode* p;int j 0;p L;while (p ! NULL j i - 1) {p p-next;j;}if (p NULL)return false;LNode* s (LNode*)malloc(sizeof(LNode));s-data e;s-next p-next;p-next s;return true;
}/*指定结点的前插操作*/
bool InsertPriorNode(LNode* p, int e)
{if (p NULL) {return false;}LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL)return false;s-next p-next;p -next s;s-data p-data;p-data e;return true;
}
/*指定结点的后插操作*/
bool InsertNextNode(LNode* p, int e)
{if (p NULL)return false;LNode* s (LNode*)malloc(sizeof(LNode));if (s NULL)return false;s-data e;s-next p-next;p-next s;return true;
}
/* 按位序删除带头结点
ListDelete(L, i, e): 删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。
头结点可以看成是”第0个“结点。
找到第i-1个结点将其指针指向第i1个结点并释放第i个结点。*/
bool ListDelete(LinkListL, int i, int e) {if (i 1)return false;LNode* p;int j 0;p L;while (p ! NULL j i - 1) {p p-next;j;}if (p NULL)return false;LNode* q;q p-next;e q-data;p-next q-next;free(q);return true;
}
bool DeleteNode(LNode* p) {if (p NULL)return false;LNode* q;q p-next;p-data p-next-data;p-next q-next;free(q);return true;
}
双链表
/**********************双链表*********************************/typedef struct DNode { //定义双链表结点类型int data; //数据域struct DNode* prior, * next; //前驱和后继指针
}DNode, * DLinkList;//初始化双链表
bool InitDLinkList(DLinkList L) {L (DNode*)malloc(sizeof(DNode)); //分配一个头结点if (L NULL) //内存不足分配失败return false;L-prior NULL;//头结点的prior永远指向NULLL-next NULL;//头结点之后暂时还没有结点return true;
}//判断双链表是否为空带头结点
bool Empty(DLinkList L) {if (L-next NULL)return true;elsereturn false;
}//在p结点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {if (p NULL || s NULL)//非法参数return false;s-next p-next;//将结点*s插入到结点*p之后if (p-next ! NULL)//如果p结点有后继结点p-next-prior s;s-prior p;p-next s;return true;
}//删除p结点的后继节点
bool DeleteNextDNode(DNode* p) {if (p NULL)return false;DNode* q;q p-next; //找到p的后继节点qif (q NULL)return false; //p没有后继节点p-next q-next;if (q-next ! NULL) //q结点不是最后一个结点q-next-prior p;free(q); //释放结点空间return true;}void DestoryList(DLinkList L) {//循环释放各个数据点while (L-next ! NULL)DeleteNextDNode(L);free(L); //释放头结点L NULL; //头指针指向NULL
}void testDLinkList() {//初始链表DLinkList L;InitDLinkList(L);//后续代码
}循环单链表
#define _crt_secure_no_warnings
#include stdio.h
#include stdlib.h
/*************************1、循环单链表**********************************************/
typedef struct LNode {int data;struct LNode* next;
}LNode, * LinkList;//初始化一个循环单链表
bool InitList(LinkList L) {L (LNode*)malloc(sizeof(LNode)); //分配一个头结点if (L NULL) //内存不足分配失败return false;L-next L; //头结点next指向头结点return true;
}//判断循环单链表是否为空
bool Empty(LinkList L) {if (L-next L)return true;elsereturn false;
}//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode* p) {if (p-next L)return true;elsereturn false;
}循环双链表
/*************************2、循环双链表**********************************************/typedef struct DNode { //定义双链表结点类型int data; //数据域struct DNode* prior, * next; //前驱和后继指针
}DNode, * DLinkList;//初始化空的循环双链表
bool InitDLinkList(DLinkList L) {L (DNode*)malloc(sizeof(DNode)); //分配一个头结点if (L NULL) //内存不足分配失败return false;L-prior L; //头结点的prior指向头结点L-next L; //头结点的next指向头结点return true;
}//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinkList L, DNode* p) {if (p-next L)return true;elsereturn false;
}//在p结点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {if (p NULL || s NULL)return false;s-next p-next;p-next-prior s;s-prior p;p-next s;return true;
}//删除p的后继结点q
bool DeleteNextDNode(DLinkList L, DNode* p) {DNode *q;q p-next;if (q L)return false;p-next q-next;q-next-prior p;free(q);return true;
}栈
只允许在一端进行插入或删除操作的线性表一种操作受限的线性表只能在栈顶插入、删除
特点先进后出
术语栈顶、栈底、空栈
注意初始化栈需要分配内存空间销毁栈需要设防栈的内存空间。
队列
/*
* 栈Stack是只允许在一端进行插入或删除操作的线性表
* 队列Queue是只允许在一端进行插入在另一端删除的线性表
* 特点先进先出
*/
#includestdio.h
#includestdlib.h#define MaxSize 10 //定义队列中元素的最大个数typedef struct {int data[MaxSize]; //用静态数组存放队列元素int front, rear; //队头指针指向队头元素和队尾指针指向队尾元素的后一个位置下一个应该插入的位置
}SqQueue;//初始化队列
void InitQueue(SqQueue Q) {//初始时 队头、队尾指针指向0Q.rear 0;Q.front 0;Q.size 0;
}//判断队列是否为空 队尾指针队头指针时队列为空
bool QueueEmpty(SqQueue Q) {if (Q.rear Q.front) //队空条件return true;elsereturn false;
}//入队只能从队尾入队
bool EmQueue(SqQueue Q, int x) {if (Q.size MaxSize)return false; //队满则报错Q.data[Q.rear] x; //新元素插入队尾Q.rear (Q.rear 1) % MaxSize; //队尾指针加1取模当队尾指针达到数组的末尾时将其回到数组的开头使得队列可以继续从头部插入元素。
}/************************循环队列**********************************/
//用模运算将存储空间在逻辑上变成了“环状”//判断队列是否为空
bool QueueEmpty(SqQueue Q) {if (Q.rear Q.front) //队空条件队尾指针队头指针return true; elsereturn false;
}//入队
bool EnQueue(SqQueue Q, int x) {if ((Q.rear 1) % MaxSize Q.front)return false; //队满则报错队列已满的条件队尾指针的再下一个位置是队头其代价是牺牲一个存储单元Q.data[Q.rear] x; //新元素插入队尾Q.rear (Q.rear 1) % MaxSize; //队尾指针加1取模用模运算将存储空间在逻辑上变成了“环状”return true;
}//出队删除一个队头元素并用x返回
bool DeQue(SqQueue Q, int x) {if (Q.rear Q.front) //判断队空return false; //队空则报错x Q.data[Q.front];Q.front (Q.front 1) % MaxSize; //队头指针后移return true;
}//获得队头元素的值用x返回
bool GetHead(SqQueue Q, int x){if (Q.rear Q.front)return false; //队空则报错x Q.data[Q.front];return true;
}//判断队列已满、已空的方法
/*
* 方案一牺牲一个存储单元
* 队列已满的条件队尾指针的再下一个位置是队头即(Q.rear 1) % MaxSize Q.front;
* 队空条件Q.rear Q.front
* 方案二增减辅助变量tag、size
* ①增加辅助变量size
* 队满条件Q.size MaxSize
* 队空条件Q.size 0
* ②增加辅助变量tag
* 每次删除操作成功时都令Q.tag 0每次插入操作成功时都令Q.tag 1
* 只有删除操作才导致队空只有插入操作才可能导致队满
* 队满条件 front rear tag 1
* 队空条件 front rear tag 0
*
*/
#define MaxSize 10 //定义队列中元素的最大个数
typedef struct {int data[MaxSize]; //用静态数组存放队列元素int front, rear; //队头指针指向队头元素和队尾指针指向队尾元素的后一个位置下一个应该插入的位置int size; //队列当前长度
}SqQueue;队列的链式实现
#includestdio.h
#includestdlib.htypedef struct LinkNode { //链式队列结点int data;struct LinkNode* next;
}LinkNode;typedef struct { //链式队列LinkNode* front, * rear; //队列的队头和队尾指针
}LinkQueue; //初始化带头结点
void InitQueue(LinkQueue Q) {//初始时 front。rear都指向头结点Q.front (LinkNode*)malloc(sizeof(LinkNode));Q.rear (LinkNode*)malloc(sizeof(LinkNode));Q.front-next NULL;Q.rear-next NULL;
}//判断队列是否为空带头结点
bool IsEmpty(LinkQueue Q) {if (Q.front Q.rear)return true;elsereturn false;
}//入队带头结点
void EnQueue(LinkQueue Q, int x) {LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));s-data x;s-next NULL;Q.rear-next s; //新结点插入到rear之后Q.rear s; //修改表尾指针
}//出队带头结点队头元素出队
bool Dequeue(LinkQueue Q, int x) {if (Q.front Q.rear)return false; //空队LinkNode* p Q.front-next;x p-data; //用变量x返回队头元素Q.front-next p-next; //修改头结点的next指针if (Q.rear p) //此次是最后一个结点出队Q.rear Q.front; //修改rear指针free(p); //释放结点空间return true;
}//初始化不带头结点
void InitQueue(LinkQueue Q) {//初始时 front。rear都指向头结点Q.front-next NULL;Q.rear-next NULL;
}//判断队列是否为空不带头结点
bool IsEmpty(LinkQueue Q) {if (Q.front NULL)return true;elsereturn false;
}//入队不带头结点
void EnQueue(LinkQueue Q, int x) {LinkNode* s (LinkNode*)malloc(sizeof(LinkNode));s-data x;s-next NULL;if (Q.front NULL) { //在空队列中插入第一个元素Q.front s; //修改队头队尾指针Q.rear s; //不带头结点的队列第一个元素入队时需要特别处理}else {Q.rear-next s; //新结点插入到rear结点之后Q.rear s; //修改rear队尾指针}}//出队不带头结点队头元素出列
bool Dequeue(LinkQueue Q, int x) {if (Q.front NULL)return false; //空队LinkNode* p Q.front; //p指向此次出队的结点x p-data; //用变量x返回队头元素Q.front p-next; //修改front指针if (Q.rear p) { //此次是最后一个结点出队Q.front NULL; //Q.front指向NULLQ.rear NULL; //Q.front指向NULL}free(p); //释放结点空间return true;
}//队满条件
/*
* 顺序存储--预分配的空间耗尽时队满
* 链式存储--一般不会队满除非内存不足
*/
