网志栈编辑推荐
本书全面系统地介绍了数据结构的基本概念和知识，既注重理论知识，又注重算法设计的训练。在重点章节中，结合精心编写的应用实例，介绍了应用数据结构和算法解决实际问题和进行程序设计的方法，增强了读者对基本知识的理解与掌握，更有利于分析问题能力和程序设计能力的提高。 ；
内容简介
本书结合编者多年教学经验，全面系统地介绍了数据结构的基本概念和知识，条理清晰、重点突出，内容循序渐进、深入浅出，既注重理论知识的讲解，又注重算法设计的训练，突出了理论性与实用性。全书共分9章，第1章作为全书的综述和基础，介绍了数据结构、算法的相关概念和算法分析方法等，其后各章分别讨论了线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、数据结构的定义、表示和实现，*后两章介绍了查找和内部排序的各种方法。在重点章节中，还结合精心编写的应用实例，介绍了应用数据结构和算法解决实际问题及进行程序设计的方法，增强了读者对基本知识的理解与掌握，有利于提高分析问题的能力和程序设计的能力。全书采用C语言作为数据结构和算法的描述语言。 本书可作为高等学校计算机类、信息类及相近专业本科生的数据结构课程教材，也可供从事计算机软件开发和工程应用的人员学习和参考。
作者简介
暂无
目录
第1章概论1
1.1什么是数据结构1
1.1.1数据和数据元素1
1.1.2数据对象与数据类型2
1.1.3数据结构2
1.2为什么要学习数据结构5
1.2.1学习数据结构的重要性5
1.2.2数据结构的应用举例5
1.3算法和算法分析7
1.3.1什么是算法7
1.3.2算法的描述和设计7
1.3.3算法分析8
本章小结10
习题10
前沿
数据结构是计算机程序设计的重要理论基础，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。它不仅是计算机专业的核心课程，也是其他理工专业的热门选修课。在计算机的应用领域中，数据结构有着广泛的应用。
计算机的程序是对信息进行加工处理，而信息的表示和组织又直接关系到处理信息程序的效率。随着计算机的普及、信息量的增加、信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂，因此，为了编写出一个“好”的程序，必须分析待处理对象的特征及各对象之间存在的关系。这就是数据结构这门课所要研究的问题。数据的结构，直接影响算法的选择和效率。
本书共分9章，第1章介绍了数据结构的基本概念和算法分析的初步知识；第2章到第5章介绍了线性表、栈和队列、串、多维数组和广义表等线性结构的基本概念及常用算法的实现；第6章和第7章介绍了非线性结构的树、二叉树、图等数据结构的存储结构和不同存储结构上的一些操作的实现；第8章介绍了各种查找表及查找方法；第9章介绍了各种排序算法。本书计划学时为64学时左右，其中上机实习为12学时左右。教师可根据专业情况，选讲或不讲目录中带*的章节。
免费在线读
第
3
章
栈 和 队 列
第3章栈 和 队 列本章要点
栈
栈的应用举例
队列
队列的应用举例
本章学习目标
理解栈的定义及其基本运算。
掌握顺序栈和链栈的各种操作实现。
理解队列的定义及其基本运算。
掌握循环队列和链队列的各种操作实现。
学会利用栈和队列解决一些问题。
3.1栈
栈和队列是在程序设计中被广泛使用的两种重要的数据结构。由于从数据结构角度看，栈和队列是操作受限的线性表，因此，也可以将它们称为限定性的线性表结构。
3.1.1栈的定义与基本操作
在日常生活中，我们会发现有许多这样的趣事，如把许多书籍依次放进一个大小相当的箱子中，当我们在取书时，就得先把后放进去的书取走，才能拿到先放入的被压在底层的书；又如一叠洗净的盘子，洗的时候总是将盘子逐个叠放在已洗好的盘子上面，而用的时候则是从上往下逐个取用，即后洗好的盘子比先洗好的盘子先被使用。这种后进先出的结构称为栈。
1. 栈的定义
栈(Stack)是一种仅允许在一端进行插入和删除运算的线性表。栈中允许进行插入和删除的那一端，称为栈顶(Top)。栈顶的第一个元素被称为栈顶元素。栈中不可以进行插入和删除的那一端(即线性表的表头)，称为栈底(Bottom)。在一个栈中插入新元素，即把新元素放到当前栈顶元素的上面，使其成为新的栈顶元素，这一操作称为进栈、入栈或压栈(Push)。从一个栈中删除一个元素，即把栈顶元素删除，使其下面的元素成为[1][1]新的栈顶元素，称为出栈或退栈(Pop)。例如:
注： 遵循“后进先出”的原则。
进栈顺序为a1，a2，…，an，如图31(a)所示，而出栈顺序为an，an-1，…，a2，a1。
注意： 插入和删除都只能在栈顶一端进行。
由于栈的插入和删除操作只能在栈顶一端进行，后进栈的元素必定先出栈，所以栈又称为后进先出(Last In First Out)的线性表(简称LIFO结构)，它的这个特点可用图31(b)所示的铁路调度站形象地表示。
图31栈的图示
思考：
① 栈是什么？它与一般线性表有何不同？
② 一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？
讨论： 有无通用的判别原则？
答: 有!若输入序列是 …Pj…Pk…Pi …(Pj
定义在栈上的基本操作有以下几种。
(1) InitStack(S)： 构造一个空栈S。
(2) ClearStack(S)： 清除栈S中的所有元素。
(3) StackEmpty(S)： 判断栈S是否为空，若为空，则返回TRUE；否则返回FALSE。
(4) GetTop(S)： 返回S的栈顶元素，但不移动栈顶指针。
(5) Push(S,x)： 插入元素x为新的栈顶元素(入栈操作)。
(6) Pop(S)： 删除S的栈顶元素并返回其值(出栈操作)。
由于栈是运算受限的线性表，因此线性表的存储结构对栈也同样适用。与线性表相似，栈也有两种存储表示方法，即顺序存储和链式存储两种结构，顺序存储的栈称为顺序栈，链式存储的栈称为链栈。
3.1.2顺序栈的存储结构和操作的实现
1. 顺序栈存储结构的定义
顺序栈是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，可以用一维数组描述顺序栈中数据元素的存储区域，并预设一个数组的最大空间。栈底设置在0下标端，栈顶随着插入和删除元素而变化，可用一个整型变量top来指示栈顶的位置。为此，顺序栈存储结构的描述如下： #define Maxsize 100/设顺序栈的最大长度为100,可依实现情况而修改/
typedef int datatype;
typedef struct
{
datatype stack[Maxsize];
int top;/栈顶指针/
}SeqStack;/顺序栈类型定义/
SeqStack S;/S为顺序栈类型变量的指针/由于C语言中数组下标是从0开始的，即S->stack[0]是栈底元素，而栈顶指针S->top是正向增长的，即进栈时栈顶指针S->top加1，然后把新元素放在top所指的空单元内；退栈时S->top减1，因此S->top等于-1(或S->top小于0)表示栈空，S->top等于Maxsize-1表示栈满。由此可知： 对顺序栈插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为O(1)。一个栈的几种状态以及在这些状态下栈顶指针top和栈中节点的关系如图32所示。
图32栈顶指针和栈中元素之间的关系
通过分析，我们可以得出结论：
(1) 若top=-1，则表示栈空；
(2) 若top=Maxsize-1，则表示栈满。
2. 顺序栈的基本操作
由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多。值得一提的是： 在入栈操作前，首先要判定栈是否满；在出栈操作前，又要先判定栈是否空。
(1) 构造一个空栈。SeqStack InitStack()
{SeqStack S;
S=(SeqStack )malloc(sizeof(SeqStack));
if(!S)
{printf("空间不足");
return NULL;}
else
{S->top=-1;
return S;}
}(2) 取栈顶元素。datatype GetTop(SeqStack S)
{if(S->top==-1)
{printf("\n栈是空的!");
return FALSE;}
else
return S->stack[S->top];
} (3) 入栈。SeqStack Push(SeqStack S,datatype x)
{ if(S->top==Maxsize-1)
{printf("\n栈是满的!");
return NULL; }
else
{S->top ;
S->stack[S->top]=x;
return s;}
} (4) 出栈。datatype Pop(SeqStack S)
{if(S->top==-1)
{printf("\nThe sequence stack is empty!");
return FALSE;}
S->top--;
return S->stack[S->top 1];
}(5) 判别空栈。intStackEmpty(SeqStackS)
{if(S->top==-1)
return TRUE;
else
return FALSE;
}例31若增加main()函数以及display()函数，则可以调试上述各种栈的基本操作算法。#define Maxsize 50
typedef int datatype;
typedef struct
{datatype stack[Maxsize];
int top;
}SeqStack;
void display(SeqStack s)
{int t;
t=s->top;
if(s->top==-1)
printf("the stack is empty!\n");
else
while(t!=-1)
{t--;
printf("%d->",s->stack[t]);}
}
main()
{int a[6]={3,7,4,12,31,15},i;
SeqStack p;
p=InitStack();
for(i=0;i<6;i )Push(p,a[i]);
printf("output the stack values: ");
display(p);
printf("\n");
printf("the stacktop value is:%d\n",GetTop(p));
Push(p,100);
printf("output the stack values:");
display(p);
printf("\n");
printf("the stacktop value is:%d\n",GetTop(p));
Pop(p);
printf("the stacktop value is:%d\n",GetTop(p));
printf("Pop the stack value :");
while(!StackEmpty(p))
printf("%4d",Pop(p));
printf("\n");
}运行结果如下： output the stack values: 15->31->12->4->7->3->
the stacktop value is: 15
output the stack values: 100->15->31->12->4->7->3->
数据结构 pdf下载声明
本pdf资料下载仅供个人学习和研究使用，不能用于商业用途，请在下载后24小时内删除。如果喜欢，请购买正版
