文档介绍：第14章线性表
本章目标
介绍线性表的概念及其存储结构的C++定义:顺序表和链表
学习要求
掌握线性表的顺序存储结构C++定义----即顺序表类的定义
掌握顺序表的插入函数和删除函数
掌握线性表的非顺序存储结构C++定义----即单链表类的定义
掌握单链表的插入函数和删除函数
什么是线性表
日常生活中常见到表格形式的一类数据
列车时刻表
学生成绩表
周名缩写表
车次
火车种类
始发站
终点站
始发时间
到达时间
140
特快
西安
上海
20:30
19:45
42
特快
西安
北京
17:30
7:45
361
普快
西安
铜川
9:45
13:10
……
……
……
……
……
……
列车时刻表
学号
姓名
性别
分数
99011001
周敏
女
86
99011002
苏伊诗
女
92
99011003
王苏朋
男
76
……
……
……
……
学生成绩表
Sun.
Mon.
Tue.
Wen.
Thu.
Fri.
Sat.
周名缩写表
1)表中每一行信息虽然组成的内容不同,但都代表某个明确独立的含义,将表中每一行信息称之为一个数据元素;
2)每个数据元素在表中的位置固定,除了第一个元素和最后一个元素外,其余元素都有唯一一个前驱元素和唯一一个后继元素;
3)表中数据元素的个数不相同,有长有短;
4)大多数表中数据元素会增加或减少,是动态变化的。但也有一些表是固定不变,
将这些表格形式的数据加以抽象,统称为线性表。
上述表格形式的数据具有如下共同特点:
线性表是由n(n≥0)个数据元素a 1,a 2,a 3,…,a n 组成的有限序列,记为:( a 1,a 2,a 3,…,a n )。
线性表中当前存储的数据元素数目叫做表的长度,n为表长,当线性表中不包含任何数据元素时,称为空表。显然n=0时称为空表。
1)数据元素a i(1≤i≤n)表示某个具体意义的信息,它可以是一个数,或者是一个字符串,或者是由数和字符串组成的更复杂的信息。但同一个线性表中的所有数据元素必须具有相同的属性(或者说具有相同的数据类型);
2)若线性表是非空表,则有:(ⅰ)第一个元素a 1无前趋元素;(ⅱ)最后一个元素a n无后继元素;(ⅲ)其它元素a i(1<i<n)均只有一个直接前趋a i-1 和一个直接后继a i+1。
线性表的定义
日常生活中线性表的例子
某校1998—2003年在校学生人数(2500,3450,5000,5100,5400,5500)是一个线性表,每个数据元素是一个正整数,表长为6;
每个月份英文缩写名称组成一个线性表(JAN.,FEB.,MAR.,APR.,MAY.,JUN.,JUL.,AUG.,SEP.,OCT.,NOV.,DEC.),表中数据元素是一字符串,表长为12;
屏幕上若干像素((50,50,RED),(100,150,RED),(200,200,BLUE),(200,250,GREEN))亦是一线性表,表中数据元素是由行坐标、列坐标和颜色三个数据项组成的一个像素信息,表长为4。
电话号码簿、股票市场里的信息列表、航班时刻表、各种各样的统计报表等等
对线性表有哪些处理(或操作)呢?
1)统计线性表里总共有多少个元素。简称求表长,记作Length(L),
2)获取线性表中某个数据元素的信息。简称取元素,记作Get(L,i)
3)置换或修改线性表中某个数据元素的信息。简称置换元素,记作Replace(L,i,x)
4)在线性表中某个位置上增加一个数据元素。简称插入元素,记作Insert(L,i,x)
5)删除线性表中某个位置上的一个数据元素。简称删除元素,记作Delete(L,i)
6)查找某个数据元素是否在线性表中存在。简称查找元素,记作Locate(L,x)
7)求前驱元素,记作Prior(L,i),取元素ai的直接前驱
8)求后继元素,(L,i)
9)对线性表中的数据元素按某个数据项的值递增(或递减)的顺序排列。简称排序,记作Sort(L)。
基本的、常用的处理如下:
顺序表类