• 
  流畅英语口语教程(第二版)(第三册)学生用书
  ￥5.50
• 
  工程力学(静力学与材料力学)（内容一致，印次、封面或原价不同，统一售价，随机发货）
  ￥6.80
• 
  中国近现代史纲要(2013年修订版)
  ￥2.80
• 
  理论力学(Ⅰ)(第7版)（内容一致，印次、封面或原价不同，统一售价，随机发货）
  ￥4.70

本书在选材与编排上,贴近当前普通高等院校“数据结构”课程的现状和发展趋势,内容难易适度,突出实用性和应用性。本书并未面面俱到地介绍各种数据结构,而是通过分类和讲解典型结构,使读者对数据结构形成宏观认识。根据内容侧重,本书共分为8章,分别为绪论、线性表、栈和队列、串和数组、树结构、图、内排序和查找。 本书可以作为普通高校计算机相关专业“数据结构”课程的教材,也可以供学习数据结构的读者单独使用(包括参加计算机等级考试或相关专业自学考试)参考。 本书是高等院校计算机科学、软件工程及相关专业“数据结构”课程的理想教材,也可以供程序员、系统工程师等相关人员阅读参考。

目录 第1章绪论 1.1引言 1.1.1学习目的 1.1.2课程内容 1.2基本概念 1.2.1数据与数据结构 1.2.2数据类型与抽象数据类型 1.3算法 1.3.1算法的概念 1.3.2算法描述 1.3.3算法分析 小结 习题1 第2章线性表 2.1线性表及其基本操作 2.1.1线性表的基本概念 2.1.2抽象数据类型描述 2.1.3线性表的存储和实现 2.2线性表的顺序存储 2.2.1顺序表 2.2.2顺序表的基本操作实现 2.3线性表的链式存储和实现 2.3.1单链表 2.3.2单链表的基本操作实现 2.3.3其他链表 2.4顺序表与链表的比较 小结 习题2 第3章栈和队列 3.1栈 3.1.1栈的基本概念 3.1.2栈的抽象数据类型描述 3.1.3顺序栈 3.1.4链栈 3.2队列 3.2.1队列的基本概念 3.2.2队列的抽象数据类型描述 3.2.3顺序队列 3.2.4链队列 3.2.5优先级队列 3.3栈和队列的比较 小结 习题3 第4章串和数组 4.1串 4.1.1串的基本概念 4.1.2串的抽象数据类型描述 4.1.3顺序串 4.1.4链串 4.2串的模式匹配 4.2.1Brute Force算法 4.2.2KMP算法 4.3数组 4.3.1数组的基本概念 4.3.2数组的特性 4.3.3数组的遍历 4.4特殊矩阵的压缩存储 4.4.1三角矩阵的压缩存储 4.4.2对称矩阵的压缩存储 4.4.3对角矩阵的压缩存储 4.4.4稀疏矩阵的压缩存储 小结 习题4 第5章树结构 5.1树 5.1.1树的基本概念 5.1.2树的术语 5.2二叉树 5.2.1二叉树的基本概念 5.2.2二叉树的性质 5.2.3二叉树的存储结构 5.2.4二叉树的遍历 5.2.5二叉树遍历算法的应用 5.2.6二叉树的建立 5.3哈夫曼树及哈夫曼编码 5.3.1哈夫曼树的基本概念 5.3.2哈夫曼树的构造 5.3.3哈夫曼编码 5.3.4构造哈夫曼树和哈夫曼编码的类的描述 5.4树和森林 5.4.1树的存储结构 5.4.2树的遍历规则 小结 习题5 第6章图 6.1图概述 6.1.1图的基本概念 6.1.2图的抽象数据类型描述 6.2图的存储结构 6.2.1邻接矩阵 6.2.2邻接表 6.3图的遍历 6.4*小生成树 6.4.1*小生成树的基本概念 6.4.2Kruskal算法 6.4.3Prim算法 6.5*短路径 6.5.1单源*短路径 6.5.2求任意两个顶点间的*短路径 6.6拓扑排序和关键路径 6.6.1拓扑排序 6.6.2关键路径 小结 习题6 第7章排序 7.1排序概述 7.1.1排序的基本概念 7.1.2排序算法的性能评价 7.1.3待排序的记录和顺序表的类描述 7.2插入排序 7.2.1直接插入排序 7.2.2希尔排序 7.3交换排序 7.3.1冒泡排序 7.3.2快速排序 7.4选择排序 7.4.1直接选择排序 7.4.2堆排序 7.5归并排序 小结 习题7 第8章查找 8.1查找的基本概念 8.1.1什么是查找 8.1.2查找表 8.1.3平均查找长度 8.2静态表查找 8.2.1顺序查找 8.2.2二分查找 8.2.3分块查找 8.3动态表查找 8.3.1二叉排序树查找 8.3.2平衡二叉树 8.3.3B-树和B 树 8.4哈希表查找 8.4.1哈希表的概念 8.4.2哈希函数 8.4.3解决冲突的方法 8.4.4哈希表查找性能分析 小结 习题8 附录A数据结构试卷 数据结构试卷(一) 数据结构试卷(二) 数据结构试卷(三) 数据结构试卷(四) 数据结构试卷(五) 附录B实践题 第2章线性表 第3章栈和队列 第4章串和数组 第5章树结构 第6章图 第7章排序 第8章查找 参考文献

第3章
栈 和 队 列







3.1栈
3.1.1栈的基本概念

栈是一种特殊的线性表,其插入、删除操作只能在表的尾部进行。在栈中允许进行插入、删除操作的一端称为栈顶,另一端称为栈底。在栈{a0,a1,…,an-1}中a0称为栈底元素,an-1称为栈顶元素。通常,栈的插入操作叫入栈,栈的删除操作叫出栈。
由于栈的插入和删除操作只允许在栈顶进行,每次入栈的元素即成为栈顶元素,每次*先出栈的总是栈顶元素,所以栈是一种后进先出的线性表。就像一摞盘子,每次将一个盘子摞在*上面,每次从*上面取一只盘子,不能从中间插进或者抽出。
3.1.2栈的抽象数据类型描述
栈中的数据元素和数据间的逻辑关系与线性表相同,是由n个具有相同数据类型的数据元素构成的有限序列,栈的抽象数据类型的Python描述如下:


1from abc import ABCMeta,abstractmethod,abstractproperty
2
3class IStack(metaclass=ABCMeta):
4@abstractmethod
5def clear(self):
6'''将栈置空'''
7pass
8@abstractmethod
9def isEmpty(self):
10'''判断栈是否为空'''
11pass
12@abstractmethod
13def length(self):
14'''返回栈的数据元素个数'''
15pass
16@abstractmethod
17def peek(self):
18'''返回栈顶元素'''
19pass
20@abstractmethod
21def push(self,x):
22'''数据元素x入栈'''
23pass
24@abstractmethod
25def pop(self):
26'''将栈顶元素出栈并返回'''
27pass
28@abstractmethod
29def display(self):
30'''输出栈中的所有元素'''
31pass

栈的抽象数据Python抽象类包含了栈的主要基本操作,如果要使用这个类还需要具体的类来实现。栈的Python抽象类的实现方法主要有以下两种。
(1) 基于顺序存储的实现,为顺序栈。
(2) 基于链式存储的实现,为链栈。