网站建设和优化要求,网站建设的目标人群是什么,wordpress数据库优化2018,中国制造网官方网站首页在之前我们已经学习了数据结构中线性表里面的顺序表与链表#xff0c;了解了如何实现顺序表与链表增、删、查、该等功能。其实在线性表中除了顺序表和链表还有其他的类别#xff0c;在本篇中我们就将学习另外一种线性表——栈#xff0c;在通过本篇的学习后#xff0c;你将…在之前我们已经学习了数据结构中线性表里面的顺序表与链表了解了如何实现顺序表与链表增、删、查、该等功能。其实在线性表中除了顺序表和链表还有其他的类别在本篇中我们就将学习另外一种线性表——栈在通过本篇的学习后你将会对栈的结构有充足的了解在了解完结构后我们还将进行栈的实现。一起加油吧 1.栈的概念与结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出先进后出LIFOLast In First Out的原则。
压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 那么栈的底层结构是基于什么的呢其实基于数组还是基于单链表或者是双链表都是可以的那么哪一种是最优解呢接下来我们就来分析基于不同底层结构的利与弊 若底层结构基于数组则可以让数组的低地址处表示栈底数组的高地址处表示栈顶使用一个size变量来表示数组有效数据个数这样就可以要入栈时直接在size位置插入数据之后size加一出栈时就可以直接让size减一这样就可以让数组的有效个数减一。以上使用数组来作为栈的底层结构时间复杂度为O(1) 在数组当中虽然每次在空间不足时都会以之前二倍的方式申请新空间这时可能会存在内存的浪费当时由于数组在内存中是连续存放的这就使得在入栈和出栈不需要再每次都申请空间而且数组在取数据的时候可能缓存中就有不一定要在主存中取。 若栈的底层结构为单链表如果是在单链表尾部表示栈顶头部表示栈底这样在无论是在入栈还是在出栈时因为都需要通过遍历来找到单链表的尾节点所以时间复杂度都为O(N)。所以这时就要改变栈顶为单链表的头部栈底为单链表的尾部这时在入栈和出栈时就不需要遍历单链表时间复杂度就都为O(1)。 但是单链表每次在入栈和出栈时都要申请节点和销毁节点并且由于单链表每个节点空间在内存当中不一定是连续的所以每次访问数据都需要区主存取。 而在双链表中无论是让头部作为栈顶尾部作为栈底还是让尾部作为栈顶头部作为栈底由于双链表每个节点内部都有指向前一个节点和下一个节点的指针所以在入栈和出栈时都不需要遍历链表所以入栈和出栈时的时间复杂度都为O(1)。 但是双链表在每个节点内部相比单链表都多一个指针变量在32位环境下每个节点大小就会多4个字节在64位环境下每个节点大小就会多8字节。因此使用双链表就会造成更多的内存损耗。 通过以上的分析可以发现无论栈的底层结构是基于数组还是单链表还是双链表在入栈和出栈时的时间复杂度都为O(1)但是综合其他因素使用数组是最优解 2.栈的实现
在实现栈的代码内在Stack.h头文件内定义栈的结构以及对各种功能函数进行声明在Stack.c文件内实现各个函数在test.c文件内对实现的各函数进行测试
2.1栈结构的定义
在Stack.h中创建一个结构体来定义栈的结构在该结构体中的成员变量和顺序表中基本是相同的只不过将顺序表中表示有效元素个数的size改名位top让top来表示栈顶
//定义栈的结构
typedef int STDataType;
typedef struct stack
{STDataType* a;int capacity;//栈空间大小int top;//栈顶
}stack;
2.2栈的初始化
要完成栈的初始化函数首先要在Stack.h完成初始化函数的声明
//初始化栈
void stackInit(stack* ps);
将该函数命名为stackInit,函数的参数就为指向结构体的指针
接下来就是在stack.c内完成初始化函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言
//初始化栈
void stackInit(stack* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}
2.3检测栈是否为空
要完成检测栈是否为空函数首先要在Stack.h完成该函数函数的声明
//检测栈是否为空
bool stackEmpty(stack* ps);
将该函数命名为stackEmpty,函数的参数就为指向结构体的指针函数的返回类型为布尔类型
接下来就是在stack.c内完成检测栈是否为空函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言 在该函数中若数组内的有效个数top为0函数就会返回true不为0就返回false
//检测栈是否为空
bool stackEmpty(stack* ps)
{assert(ps);return ps-top0;
}
2.4入栈
要完成入栈函数首先要在Stack.h完成初始化函数的声明
void stackPush(stack* ps,STDataType x);
将该函数命名为stackPush,函数的参数有两个第一个为指向结构体的指针第二个为要进入栈的数据
接下来就是在stack.c内完成入栈函数的实现 由于在入栈时数组的空间可以已经满了因此在进行插入数据之前要判断数组的有效个数是否与数组的空间大小相同如果相同就需要进行增容。增容的代码就和之前的顺序表检测数组空间大小函数一样。 在调整完空间大小之后的入栈就和顺序表中得尾插一样ps-a[ps-top] x一句代码就可以实现
//入栈
void stackPush(stack* ps,STDataType x)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}ps-atmp;ps-capacity newcapacity;}ps-a[ps-top] x;
}
2.5出栈
要完成出栈函数首先要在Stack.h完成出栈函数的声明
//出栈
void stackPop(stack* ps);
将该函数命名为stackPop,函数的参数为指向结构体的指针
接下来就是在stack.c内完成出栈函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言 同时在出栈时栈不能为空所以要对satckEmpt(ps)进行assert断言在出栈就和顺序表中得尾删一样将top减一就可
//出栈
void stackPop(stack* ps)
{assert(ps);assert(!stackEmpty(ps));--ps-top;
}
2.6取栈顶元素
要完成取栈顶元素函数首先要在Stack.h完成取栈顶元素函数的声明
//获取栈顶元素
STDataType stackTop(stack* ps);
将该函数命名为stackTop,函数的参数为指向结构体的指针函数的返回值就为栈顶的元素
接下来就是在stack.c内完成取栈顶原始函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言 同时在出栈时栈不能为空所以要对satckEmpt(ps)进行assert断言 由于top指向数组的尾元素的后一位所以只要将size-1就可以得到栈顶元素
//获取栈顶元素
STDataType stackTop(stack* ps)
{assert(ps);assert(!stackEmpty(ps));return ps-a[ps-top - 1];
}
2.7获取栈中有效元素个数
要完成获取栈中有效元素个数函数首先要在Stack.h完成获取栈中有效元素个数函数的声明
//获取栈中有效元素个数
int stackSize(stack* ps);
将该函数命名为stackSize,函数的参数为指向结构体的指针函数的返回值就为栈的元素个数
接下来就是在stack.c内完成获取栈中有效元素个数函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言 因为在结构体中的top就为数组的有效元素个数所以在该函数中返回ps-top即可
//获取栈中有效元素个数
int stackSize(stack* ps)
{assert(ps);return ps-top;
}
2.8销毁栈
要完成销毁栈函数首先要在Stack.h完成销毁栈函数的声明
//销毁栈
void stackDestory(stack* ps);
将该函数命名为stackDestory,函数的参数为指向结构体的指针
接下来就是在stack.c内完成销毁栈函数的实现 由于ps指针是指向结构体的指针所以该指针不能为空所以要对ps进行assert断言 在销毁时由于栈的空间是由realloc申请来的所以在使用完后要用free来释放内存空间并且在释放后将指针ps-a置为NULL且将top和capacity都赋值为0
//销毁栈
void stackDestory(stack* ps)
{assert(ps);if (ps-a){free(ps-a);}ps-a NULL;ps-top ps-capacity 0;
}
2.9栈的打印
因为在栈和顺序表以及链表不同由于栈只能在一端进和出所以栈是不能遍历所以我们不能通过创建一个函数来遍历栈
所以要打印栈就只能在test.c内调用相关函数来实现例如以下栈先依次入栈1234之后要打印就通过以下循环来实现
#includestack.hvoid test()
{stack ps;stackInit(ps);stackPush(ps, 1);stackPush(ps, 2);stackPush(ps, 3);stackPush(ps, 4);while (!stackEmpty(ps)){STDataType p stackTop(ps);printf(%d , p);stackPop(ps);}stackDestory(ps);
}int main()
{test();return 0;
} 3.栈的实现完整代码
stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.h
//定义栈的结构
typedef int STDataType;
typedef struct stack
{STDataType* a;int capacity;//栈空间大小int top;//栈顶
}stack;//初始化栈
void stackInit(stack* ps);
//销毁栈
void stackDestory(stack* ps);
//检测栈是否为空
bool stackEmpty(stack* ps);
//入栈
void stackPush(stack* ps,STDataType x);
//出栈
void stackPop(stack* ps);
//获取栈顶元素
STDataType stackTop(stack* ps);
//获取栈中有效元素个数
int stackSize(stack* ps);
stack.c
#includestack.h//初始化栈
void stackInit(stack* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}//销毁栈
void stackDestory(stack* ps)
{assert(ps);if (ps-a){free(ps-a);}ps-a NULL;ps-top ps-capacity 0;
}//检测栈是否为空
bool stackEmpty(stack* ps)
{assert(ps);return ps-top0;
}//入栈
void stackPush(stack* ps,STDataType x)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail!);exit(1);}ps-atmp;ps-capacity newcapacity;}ps-a[ps-top] x;
}//出栈
void stackPop(stack* ps)
{assert(ps);assert(!stackEmpty(ps));--ps-top;
}//获取栈顶元素
STDataType stackTop(stack* ps)
{assert(ps);assert(!stackEmpty(ps));return ps-a[ps-top - 1];
}//获取栈中有效元素个数
int stackSize(stack* ps)
{assert(ps);return ps-top;
}
文章转载自： http://www.morning.rrjzp.cn.gov.cn.rrjzp.cn http://www.morning.qjzgj.cn.gov.cn.qjzgj.cn http://www.morning.qnypp.cn.gov.cn.qnypp.cn http://www.morning.mknxd.cn.gov.cn.mknxd.cn http://www.morning.fyglr.cn.gov.cn.fyglr.cn http://www.morning.hcgbm.cn.gov.cn.hcgbm.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.qnyf.cn.gov.cn.qnyf.cn http://www.morning.lkgqb.cn.gov.cn.lkgqb.cn http://www.morning.ykrkb.cn.gov.cn.ykrkb.cn http://www.morning.ryztl.cn.gov.cn.ryztl.cn http://www.morning.gpnfg.cn.gov.cn.gpnfg.cn http://www.morning.jrqcj.cn.gov.cn.jrqcj.cn http://www.morning.ryglh.cn.gov.cn.ryglh.cn http://www.morning.ggmls.cn.gov.cn.ggmls.cn http://www.morning.syhwc.cn.gov.cn.syhwc.cn http://www.morning.zqkr.cn.gov.cn.zqkr.cn http://www.morning.rgkd.cn.gov.cn.rgkd.cn http://www.morning.rlnm.cn.gov.cn.rlnm.cn http://www.morning.ngqdp.cn.gov.cn.ngqdp.cn http://www.morning.cwrpd.cn.gov.cn.cwrpd.cn http://www.morning.drnjn.cn.gov.cn.drnjn.cn http://www.morning.xstfp.cn.gov.cn.xstfp.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.hxpff.cn.gov.cn.hxpff.cn http://www.morning.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.mtbsd.cn.gov.cn.mtbsd.cn http://www.morning.sgfpn.cn.gov.cn.sgfpn.cn http://www.morning.dyzbt.cn.gov.cn.dyzbt.cn http://www.morning.zqcsj.cn.gov.cn.zqcsj.cn http://www.morning.wnmdt.cn.gov.cn.wnmdt.cn http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.kkqgf.cn.gov.cn.kkqgf.cn http://www.morning.ttxnj.cn.gov.cn.ttxnj.cn http://www.morning.qlxgc.cn.gov.cn.qlxgc.cn http://www.morning.nhrkl.cn.gov.cn.nhrkl.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.zkdmk.cn.gov.cn.zkdmk.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.krdb.cn.gov.cn.krdb.cn http://www.morning.xfhms.cn.gov.cn.xfhms.cn http://www.morning.lmdkn.cn.gov.cn.lmdkn.cn http://www.morning.ctlbf.cn.gov.cn.ctlbf.cn http://www.morning.lkthj.cn.gov.cn.lkthj.cn http://www.morning.kpxzq.cn.gov.cn.kpxzq.cn http://www.morning.mdwtm.cn.gov.cn.mdwtm.cn http://www.morning.rmxgk.cn.gov.cn.rmxgk.cn http://www.morning.sthgm.cn.gov.cn.sthgm.cn http://www.morning.ygflz.cn.gov.cn.ygflz.cn http://www.morning.qjtbt.cn.gov.cn.qjtbt.cn http://www.morning.dmxzd.cn.gov.cn.dmxzd.cn http://www.morning.qckwj.cn.gov.cn.qckwj.cn http://www.morning.qhczg.cn.gov.cn.qhczg.cn http://www.morning.mcjyair.com.gov.cn.mcjyair.com http://www.morning.tdscl.cn.gov.cn.tdscl.cn http://www.morning.pprxs.cn.gov.cn.pprxs.cn http://www.morning.fjptn.cn.gov.cn.fjptn.cn http://www.morning.gqjqf.cn.gov.cn.gqjqf.cn http://www.morning.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.dpppx.cn.gov.cn.dpppx.cn http://www.morning.zjrnq.cn.gov.cn.zjrnq.cn http://www.morning.zrlwl.cn.gov.cn.zrlwl.cn http://www.morning.qfrmy.cn.gov.cn.qfrmy.cn http://www.morning.lpnb.cn.gov.cn.lpnb.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.lxfqc.cn.gov.cn.lxfqc.cn http://www.morning.xgxbr.cn.gov.cn.xgxbr.cn http://www.morning.pzrrq.cn.gov.cn.pzrrq.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.ptlwt.cn.gov.cn.ptlwt.cn http://www.morning.lgnrl.cn.gov.cn.lgnrl.cn http://www.morning.snygg.cn.gov.cn.snygg.cn http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn http://www.morning.yrkdq.cn.gov.cn.yrkdq.cn http://www.morning.pcqdf.cn.gov.cn.pcqdf.cn http://www.morning.rlns.cn.gov.cn.rlns.cn http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.dqdss.cn.gov.cn.dqdss.cn
