1、第第2章章 线性表线性表 2.1 线性表的类型定义线性表的类型定义 2.2 线性表的顺序存储线性表的顺序存储 2.3 线性表的链式存储线性表的链式存储 2.4 一元多项式的表示及相加一元多项式的表示及相加 本章主要重点和难点重点：1.线性表的类型定义2.线性表的表示和实现3.线性表的应用难点：1.线性表的链式存储2.线性表的实现 线性结构线性结构是一个数据元素的有序有序（次序）集合。它有四个基本特征：1集合中必存在唯一唯一的一个“第一元素”；2集合中必存在唯一唯一的一个“最后元素”；3除第一元素之外，其它数据元素均有唯一唯一的“前驱”。4除最后元素之外，其它数据元素均有唯一唯一的后继；线性表的
2、结构特点线性表的结构特点2.1 线性表的类型定义线性表的类型定义2.1.1 线性表的逻辑结构线性表的逻辑结构 表头表头表尾表尾序偶序偶 线线性性表表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记作（a1,a2,，ai-1，ai，ai+1，an），n为线性表的表长。对n0,除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每个数据元素只有一个直直接接前前驱驱和一个直直接后继接后继。n=0时，线性表为空表。线性表的定义：线性表的定义：例如：一个数、一个符号、字母表、学生登记表等都为线性表。例如：一个数、一个符号、字母表、学生登记表等都为线性表
3、数据元素为数据元素为原子型原子型数据元素为数据元素为结构体型结构体型线性表的特点：线性表的特点：同同一一性性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有有穷穷性性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有有序序性性：线性表中表中相邻数据元素之间存在着序偶序偶关系。2.1.2 线性表的抽象数据类型定义线性表的抽象数据类型定义 ADT LinearList 数据元素数据元素：D=ai|aiD0,i=1,2,，n,n0，D0为某一数据对象 关系关系：|ai,ai+1D0，i=1,2,n-1 基本操作：基本操作：（1）InitList（L）操作前提：L为未初始化
4、线性表。操作结果：将L初始化为空表。（2）DestroyList(L)操作前提：线性表L已存在。操作结果：将L销毁。（3）ClearList(L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。（7）GetData(L,i)操作前
5、提：表L存在，且i值合法，即1iListLength（L）。操作结果：返回线性表L中第i个元素的值。（8）InsList(L,i,e)操 作 前 提：表 L已 存 在，e为 合 法 元 素 值 且1iListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。（9）DelList(L,i,&e)操作前提：表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT LinearList 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储是指用一
6、组地地址址连连续续的存储单元依次依次存储线性表中的各个元素。特点：线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表顺序表。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)k其中loc(a1)称为基地址。例如：一个线性表的第一个元素的存储地址为100，每个元素的长度为2，则第5个元素的存储地址是多少？分析：已知：loc(a1)=100,k=2；求loc
7、a5)=？根据公式loc(ai)=loc(a1)+(i-1)*k loc(a5)=loc(a1)+(5-1)*2 =100+4*2=108 图2.2 顺序表存储示意图 线性表的动态分配存储结构：#define LIST_INIT_SIZE 100 /*存储空间初始分配量*/#define LISTINCREMENT 10/*空间分配增量*/typedef struct ElemType *elem；/*存储空间基址*/int length；/*当前长度*/int listsize；/*当前分配的存储容量*/SeqList；elemlengthlistsizeSeqListElemType线性
8、表的静态分配存储结构：define MAXSIZE=线性表可能达到的最大长度typedef struct ElemType elemMAXSIZE/*存储空间*/int length；/*记录线性表的长度*/SeqList；/*数组中的下标从0开始*/elem012MAXSIZE+1n说明：说明：1.结点类型定义中ElemType数据类型是抽象化的一般形式，用户可以根据自己实际需要来具体定义顺序元素的数据类型。2.从数组的下标为0的第一个单元开始存放第一个元素。需要注意数组的下标与元素的对应关系，即表中第i个数据元素是L.elemi-1。利用顺序表定义变量的数据类型1）通过变量定义语句：Seq
9、List L;将L定义为SeqList类型。访问顺序表中序号为i的元素ai：L.elemi-1顺序表的表长：L.length2)通过指针变量定义语句：SeqList *L，将L定义为指向SeqList类型的指针变量。访问顺序表中序号为i的元素：Lelemi-1 得到顺序表的表长：Llength2.2.2 线性表顺序存储结构上的基本运算线性表顺序存储结构上的基本运算 1.初始化顺序表status InitList_sq(seqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFL
10、OW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;010001299elemlengthlistsize 2.线性表的插入 线性表的插入运算是指在表的第i(1in+1)个位置，插入一个新元素e，使长度为n的线性表(e1，ei-1，ei，en)变成长度为n+1的线性表（e1，,ei-1，e，ei，en）。用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点e。当i=n+1时，是指在线性表的末尾插
11、入结点，所以无需移动结点，直接将e插入表的末尾即可。例如：已知线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请注意区分元素的序号和数组的下标。图2.3 顺序表中插入元素 1）算法设计：顺序表&L，插入为序i，插入元素e。插入分析：第i个位置存放e，则原表中的第i至第n个，共n-i+1个数据元素必须先依次后移1个位置，以腾出第i个位置。后移时从最后一个元素开始，逐个往后移。合法位置：1iL.length+1;上溢处理：上溢发生的条件是：L.l
12、engthL.listsize，此时先申请一个有一定增量的空间，修改L.listsize的值。2）算法描述：Status ListInsert_sq(SqList&L,int i,ElemType e)if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&
13、L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;3）算法动态演示4）算法时间复杂度的分析（1）当在表尾(即i=L.length+2)插入元素时，此时不需要移动元素，可直接在表尾插入e。（2）当在表头(即i=1)插入元素时，将表中已存在的n个元素依次后移一个位置才能将e插入。（3）一般情况下，在第i（1in）个元素前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。（4）语句*(p+1)=*p的执行次数和插入位置有关。算法的时间复杂度为O(f(n)=n。3.线性表的
14、删除（1）算法分析 线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(e1，,ei-1，ei，ei+1，en)变成长度为n-1的线性表(e1，,ei-1，ei+1，en)。例如：线性表(4,9,15,21,28,30,30,42,51,62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，删除元素后，线性表的表长减少1。2）算法描述Status ListDelete_sq(SeqList&L,int i,ElemType&e)if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-
15、1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;3)删除算法动态演示4)算法时间复杂度分析（1）若删除的是表尾元素，则此时不需要移动元素，仅将表长度减1即可。（2）若删除的是表头元素则表中除被删元素外，其余的元素将依次向前移动一个位置。（3）一般情况下，删除第i个元素时需要将第i+1至第n个元素共n-i个元素依次向前移动一个位置。（4）算法执行的时间复杂度为：f(n)=(n-1)/2,O(f(n)=n 3.线性表的查找操作1）算法分析线性表有两种基本的查找运算。1)按序号序号查找GetData(L,i):要求查找线性表L中第i个数据元素，其结果是L.
16、elemi-1。2)按内容内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”。查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在表中的序号；若e与表中的所有元素都不相等，则查找失败，返回“-1”2）算法描述int LocateElem_Sq(SeqList L,ElemType e)int i=0;while(i=L.length)return-1;elsereturn i;3)算法动态演示1.有序顺序表的合并 有两
17、个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。例如：LA=(2,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。2.2.3 顺序表应用举例顺序表应用举例 算算法法思思想想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针pa、pb分别指向表LA和LB中的元素，若LA.elem i LB.elem j，则 当 前 先 将LB.elem j 插 入 到 表 LC中;若LA.elem i LB.elem j，则 当 前 先 将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描
18、完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。2)算法描述void MergeList_Sq(SeqList La,SeqList Lb,SeqList&Lc)pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)exit(overflow);pa_last=La.elem+La.length-1;pb_lase=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(papa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*=pa+;
