数据结构与算法源代码.doc

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

1、课程说明：数据结构一共四天课程，day01~~~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.DataTypedat

3、a[LISTSIZE];4.int;//除了记录大小还可以记录栈顶位置5.};上述代码中，以下代码：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

5、->==0;3.}步骤四：入栈入栈是在栈中加入一个数据元素，在入栈时，首先需要判断栈是否为满，如果栈满了，则就不能在向其中添加元素了，判断栈是否满的操作只有在顺序存储结构才会出现，因为采用顺序存储结构的栈是要事先定义栈的容量的。然后将数据元素放入栈中，并使栈顶指针加1，指向下一个位置。代码如下：1.voidpush(structStack*stack,DataTyped){2.if(stack->==LISTSIZE)3.return;4.stack->data[stack->++]=d;5.}上述代码中，以下代码：1.if(stack->==LIS

6、TSIZE)是判断栈是否满，判断栈顶指针是否与栈的容量相等，如果是，则表示栈已经满了。步骤五：出栈出栈操作实际上是将栈中的栈顶元素删除，在出栈时，首先判断栈是否为空，如果栈为空则代表栈中已经没有数据元素了，此时是不可能进行出栈操作的。然后，将栈顶指针减1。代码如下：1.voidpop(structStack*stack){2.if(empty(stack))3.return;4.stack->--;5.}步骤六：取栈顶元素取栈顶元素操作实际上是仅返回栈顶元素，而栈顶指针并不变动。在取栈顶元素时，首先也要判断栈是否为空，因为空栈同样是不可能有数据元素的

7、。代码如下：1.DataTypeData(structStack*stack){2.returnstack->data[stack->-1];3.}1.3完整代码本案例的完整代码如下所示：1.#include2.#include3.4.#defineLISTSIZE101.typedefintDataType;2.structStack{3.DataTypedata[LISTSIZE];4.int;//处了记录大小还可以记录栈顶位置5.};6.7.voidinit(structStack*stack)8.{9.

8、stack->=0;10.}11.12.boolempty(structStack*stack){13.re