1、 第2 章 线性表线性结构是最常用、最简单的一种数据结构(典型的线性结构)。其基本特点是线性表中的数据元素是有序且是有限的：存在一 唯一的被 “ 第一 ” 的 据元素；个 称为 个 数存在一 唯一的被 “ 最后一 ” 的 据元素；个 称为 个 数除第一 元素外，每 元素均有唯一一 直接前 ；个 个 个 驱除最后一 元素外，每 元素均有唯一一 直接后个 个 个 继。2.1 线性表的逻辑结构线性表(Linear List) ：是由n(n 0) 个数据元素(结点)a1，a2， an组成的有限序列。所有结点具有相同的数据类型。数据元素的个数n称为线性表的长度。当n=0时，为空表；当n0时，将非空线性表
2、记作： (a1，a2，an) 线性表中的数据元素ai代表不同的应用，定义中，只是一个抽象的表示符号。线性表中的结点可以是单值元素(每个元素只有一个数据项) 。例1:26个英文字母组成的字母表： (A，B，C、Z）2.1.1 线性表的定义例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188） 线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。例4 ： 某校2001级同学的基本情况：(2001414101，张里户，男，06/24/1983) ， (20
3、01414102，张化司，男，08/12/1984) ， (2001414102，李利辣，女，08/12/1984) 若线性表中的结点是按值( 或按关键字值) 由小到大( 或由大到小) 排列的，称线性表是有序的。 线性表相当灵活，其长度可根据需要增长或缩短。 对线性表的数据元素可以访问、插入和删除。2.1.2 线性表的抽象数据类型定义ADT List 数据对象：D = ai | aiElemSet, i=1,2,n, n0 数据关系：R = | ai-1, aiD, i=2,3,n 基本操作：InitList( /* 求线性表的长度 */Lb_len=ListLength(Lb);for(i=1;ielem_array=( ElemType* )malloc(MAX_SIZE*sizeof( ElemType ) ) ;if ( !L - elem_array ) return ERROR ; else L-length= 0 ; return OK ;
