第章线性表及其顺序存储.pdf

高等学校精品课程（省级） 国家十二五规划教材 数据结构 李云清 杨庆红 揭安全 人民邮电出版社 高等学校精品课程（省级） 国家十二五规划教材 第2章 线性表及其顺序存储 揭安全 jieanquan@163.com 江西师范大学计算机信息工程学院 线性表 顺序表 栈 队列 退出 线性表是一种常用的数据结构，本章介绍线性表 及其顺序存储，并对栈和队列及它们的顺序实现给出 了详细的设计描述。 2.1线性表 线性表是一个线性结构，它是一个含有n≥0个 结点的有限序列，对于其中的结点，有且仅有一个 开始结点没有前驱但有一个后继结点，有且仅有一 个终端结点没有后继但有一个前驱结点，其它的结 点都有且仅有一个前驱和一个后继结点。一般地， 一个线性表可以表示成一个线性序列：k ,k ,…,k ， 1 2 n 其中k 是开始结点，k 是终端结点。 1 n 退出 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、某校从1978年到1983年各种型号的计 算机拥有量的变化情况。 （6，17，28，50，92，188） 退出 例3 学生健康情况登记表如下： 姓 名 学 号 性 别 年 龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 贫血 …….. …….. ……. ……. ……. 退出 例4、一副扑克的点数 （2，3，4，…，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a ，它 1 没有直接前趋，而仅有一个直接后继a ； 2 有且仅有一个终端结点a ，它没有直接后继，而 n 仅有一个直接前趋an-1； 其余的内部结点a (2≦i≦n-1)都有且仅有一个直 i 接前趋ai-1和一个直接后继ai+1。  线性表是一种典型的线性结构。 退出 2.2顺序表 2.2.1顺序表 线性表采用顺序存储的方式存储就称之为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组 地址连续的存储单元中。