第11章线性表

《第11章线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机教学实验中心西安交通大学C语言程序设计第11章线性表教学目标介绍线性表的两种存储结构定义：一种是顺序表；另一种是链表。学习要求掌握线性表顺序存储结构的定义，顺序表的插入和删除；掌握线性表非顺序存储结构的定义，单链表的插入和删除。区分带头结点链表和不带头结点链表异同领会循环链表、双向链表结构11.1线性表概述计算机的处理效率与数据的组织形式和存储结构密切相关。这类似于人们所用的“英语词典”，它是由按英文字母的顺序组织排列的“词条”组成,这样人们查阅词典时可以按照自己熟悉的排列顺序去查找。查找的速度较快。另外在当今网络世界中数据通讯更加依赖于数据的组织形式和存储结构。总

2、之计算机处理数据要追求“时间”和“空间”上的双重效率。而“时空效率”与数据的组织存储结构密切相关。这里我们研究在日常生活中一类常见的表格数据（即用表格形式存放的数据）的处理方法。观察下列表格数据：列车时刻表、学生成绩单和英文周名缩写名称表等，如表11-1、表11-2、表11-3所示：表11-1列车时刻表车次火车种类始发站终点站始发时间到达时间140特快西安上海20：3019：4542特快西安北京17：307：45361普快西安铜川9：4513：10………………………………表11-2学生成绩单学号姓名性别分数99011001周敏女8699011002苏伊诗女92990110

3、03王苏朋男76……………………表11-3英文周名缩写名称表Sun.Mon.Tue.Wen.Thu.Fri.Sat.线性表概述（续）这些表格形式的数据具有如下共同特点：1）表中每一行信息虽然组成的内容不同，但都具有某个明确独立的含义，将表中每一行信息称之为一个数据元素；2）每个数据元素在表中的位置固定，除了第一个元素和最后一个元素外，其余元素都有唯一一个前驱元素和唯一一个后继元素；3）表中数据元素的个数不一定相等，有长有短；4）大多数表格中数据元素会增加或减少，是动态变化的。如表11-1和表11-2。但也有线性表是固定不变，如表11-3。将这些表格形式的数据加以抽象，统称

4、为线性表。线性表的定义线性表的抽象定义：线性表是由n（n≥0）个类型相同的数据元素a1，a2，a3，…，an组成的有限序列，记为：（a1，a2，a3，…，an）。线性表中当前存储的数据元素数目叫做表的长度，n为表长，当线性表中不包含任何数据元素即n=0时，称为空表。注意两点：1）数据元素ai（1≤i≤n）表示某个具体意义的信息，它可以是一个数，或者是一个字符串，或者是由数和字符串组成的更复杂的信息。但同一个线性表中的所有数据元素必须具有相同的属性（或者说具有相同的数据类型）；2）若线性表是非空表，则有：（ⅰ）第一个元素a1无前趋元素；（ⅱ）最后一个元素an无后继元素；（ⅲ

5、）其它元素ai（1

6、各种各样的统计报表等等都是线性表。因此研究线性表的存储结构便于拓宽计算机在各行各业中的应用。线性表的另一种形式化定义在计算机系的《数据结构》专业课程中，对于线性表给出了如下形式化的定义：linear_list=(D,R)其中，D是数据元素的集合，D={a1，a2，a3，…，an}R是数据元素之间关系的集合，R={,,……}。其中给出了数据元素的一种先后次序关系，即表中的数据元素都有固定的位置。线性表的操作经过分析研究，人们总结出线性表应该具有如下常用的基本操作：1）求表长：设L代表某个线性表，统

7、计L里总共有多少个元素。记作Length（L）。例如股民要了解有多少股票；学校要了解学生人数；政府要掌握本地区人口数量等。2）取元素：获取L中某个数据元素的信息，记作Get（L，i），i为表中元素的位置或序号，仅当1≤i≤Length（L）时，取得线性表L中的第i个元素ai（或ai的存储位置），否则无意义。3）置换元素:置换或修改L中某个数据元素的信息。记作Replace（L，i，x）。4）插入元素:在L中某个位置上增加一个数据元素。记作Insert（L，i，x），在L的第i个位置上插入元素x。例如某班转来一名新学生；股票市场