数据结构与算法源代码

《数据结构与算法源代码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程说明：数据结构一共四天课程，dayO1~~~day04.CSDDataStructureDAY011.基于顺序表的堆栈2.基于链式表的堆栈1基于顺序表的堆栈栈是一种特殊的线性表，是限定在线性表表尾进行插入删除操作的线性表。由栈的概念衍生出儿个子概念，它们是：1）栈顶，即允许进行插入、删除操作的一端，又称为表尾，用栈顶指针（）来指示栈顶元素。2）栈底，即固定端，乂称为表头3）空栈，即栈当中没有数据元素。顺序栈是采用顺序存储结构的栈，即使用一•组连续的存储单元（-•般使用数组）來模拟栈，依次存放栈中的数据元素。1.1方案顺序栈的基本操作包括：1）初始化操作，在初始化操作中将建立

2、一个空栈。2）判断栈空，判断栈中的数据元素个数是否为0。3）入栈，在栈中加入一个数据元素。4）出栈，在栈屮删除一个数据元素。5）取栈顶元素，将栈顶元素取出，但并不在栈屮删除该元素。1.2步骤实现此案例需要按照如下步骤进行。步骤一：定义栈在C语言中：1）定义一个一维数组来表示栈的顺序存储空间。2）定义一个变量来指出栈顶的位置。3）这两方而的信息共同描述一个栈，可将它们用结构体封装在一起。代码如下：1.#defineLISTSIZE101.typedefintDataType;2.structStack{3.DataTypedata[LISTSIZE];4.int;〃除了记录大小还

3、吋以记录栈顶位置6・}；上述代码中，以下代码：1.#defineLISTSIZE100是用一个宏常量來定义顺序表的容量，这样定义的好处是当需要修改顺序表的容量的时候，只需要修改该宏常量即可。上述代码中，以下代码：1.typedefintDataType;是将数据类空int起了一个别名叫做DataType,并在后面的程序中只使用DataType,而不使川int。这样做的好处是当堆栈屮的数据类型发牛变化时，只需要修改此句屮的int为要改变的数据类型，即可将程序屮所有数据变疑的数据类型变成指定的类型。步骤二：初始化操作在主程序屮，定义栈结构体的变量。在初始化函数中将该变量中的栈顶指针

4、初始化为0,表示为空栈。代码如下：1.voidinit(structStack*stack)2.{3.stack->=0;4.}5.intmain(intargc,constchar*argv[])6.{7.structStackstack;8.init(&stack);9.}步骤三：判断栈空判断栈空实际上是判断栈顶指针是否为0,因为当栈顶指针为0时，代表栈屮没有数据元素。代码如下：1.boolempty(structStack*stack){2.returnstack->==0;3.}步骤四：入栈入栈是在栈中加入一个数据元素，在入栈时，首先需要判断栈是否为满，如果栈满了,则就

5、不能在向其中添加元素了，判断栈是否满的操作只有在顺序存储结构才会出现，因为采川顺序存储结构的栈是要事先定义栈的容量的。然后将数据元索放入栈小，并使栈顶指针加1,指向下一个位置。代码如下：voidpush(structStack*stack,DataTyped){1.if(stack->==LISTSIZE)2.return;3.stack->data[stack->++]=d;4.}上述代码屮，以卜•代码：1.if(stack->==LISTSIZE)是判断栈是否满，判断栈顶指针是否与栈的容量相等，如果是，则表示栈己经满了。步骤九：出栈出栈操作实际上是将栈中的栈顶元索删除，在出

6、栈时，首先判断栈是否为空，如果栈为空则代表栈中已经没有数据元素了，此吋是不可能进行出栈操作的。然后，将栈顶指针减1。代码如下：1.voidpop(structStack*stack){2.if(empty(stack))3.return;4.stack->-;5.}步骤六：取栈顶元素取栈顶元索操作实际上是仅返回栈顶元素，而栈顶指针并不变动。在取栈顶元索时，首先也耍判断栈是否为空，因为空栈同样是不可能有数据元素的。代码如下：1.DataTypeData(structStack*stack){2.returnstack->data[stack->・1];3.}1.3完整代码本案例的

7、完整代码如下所示：1.#inelude2.#inelude3.3.#defineLISTSIZE105.6.7.&9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.typedefintDataType;structStack{DataTypedata[LISTSIZE];int;//处了记录大小还对以记录栈顶位置}