抽象数据类型线性表的定义
ADT List { 数据对象 数据关系 基本操作 IniList（&L） //构建空表L ListLength(&L) //求表L的长度 GetElem(L,i,&e) //去元素ai 由e返回ai PriorElem(L,ce,&pre_e) //求ce的前驱，由pre_e返回 InsertElem(&L,i,e) //在元素ai之气插入新元素e DeleteElem(&L,i) //删除第i个元素 EmptyList(L) //判断L是否为空表 }ADT List删除表L中第i个数据元素为
L = (a1,a2,...,ai-1.ai..,an) 若删除 表中i的元素 记作 DeleteElem(&L,i) 若删除 表中x的元素 记作 DeleteElem(&L,x) // 若ai = x 优先删除ai在元素ai之前插入新元素e
InsertElem(&L,i,e) L= (ai,a2,....,ai-1,e,ai,...)查找 — 确定元素值（或数据项的值为e的元素） 给定 L = (a1,a2,…,ai,…an)何元素e 若由一个ai = e 则 查找成功 否则 查找失败
5.排序 – -按元素值或某个数据项值的递增（或递减）次序 重新排列表中各元素的位置 列如 ：排序前 L = (90,60…) 排序后 ： L = (10,20,30,60)
6.将表La 和表Lb 合并为表Lc 列入 设有序表： La = （2，14，20，45，80） Lb = （8，10，19，20，22，85，90） 合并成表 Lc = （2，8，10，14，19，20）
7,将表La复制成表Lb La = （2，14，20，45，80） Lb= （2，14，20，45，80）
线性表的顺序表示 （顺序存储结构） 2.2.1 顺序分配 ---- 将线性表中的数据元素依次存放到计算机的存储器中一组地址连续的存储单位中，这种分配方式称为顺序分配 ，或者顺序映像。由此得到的存储结构结构或向量（一维数组） l例如 线性表 a = ( 30,40,10,55,24,80,66) 静态一维数组 定义 int a[11]; a[0] 30 a[1] 40 a[2] 55
顺序存储结构的一般形式 ： 序号 存储状态 存储地址 1 a1 b 2 a2 b+q i ai b+(i-1)*p … n an b+(n-1)*p maleng b+ (maxleng- 1 )*p b是首地址/基地址 元素ai的地址 p -------------- 1 个数据元素所占存储单位的数目 maxleng -------------最大长度 ，为某个常数
线性表顺序结构在C语言的定义
#define maxleng 100 { ElemType la[maxleng + 1]; / / 下标 0 1 maxleng int length; //当前长度 int last; //an的位置 }线性表顺序结构在C语言中的定义 （静态分配） 例2： 元素所占用空间 和 表长合并 为C语言的一个结构类型
#define maxleng 100 typedef struct { Elemtype elem[maxleng];//小标 0，1，... ,maxleng-1 int length; }SqList; SqList La;其中 ，typedef – 别名定义，SqList — 结构类型名 La ---- 结构类型变量名 La.length ----- 表长 La.elem[0] ------ a1 La.eleml[La,length - 1] ----an
线性表顺序结构在C语言中的定义 （动态分配） #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { Lb - }
