线性表数据结构.pptx

数据结构-线性表Linear List of Data Structures前言数据结构数据结构是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元素的集合。同样是结构，从不同的角度来讨论，会有不素的集合。同样是结构，从不同的角度来讨论，会有不同的分类，如图同的分类，如图1所示。所示。逻辑结构逻辑结构：数据对象中数据元素之间的相互关系。：数据对象中数据元素之间的相互关系。物理结构物理结构：数据结构在计算机中的表示（映像）称为：数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。数据的物理（存储）结构。线性结构：线性结构：线性表线性表、栈和队列、串、数组和广义表。、栈和队列、串、数组和广义表。图1 线性表的数据结构前言抽象数据类型抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。抽象数据类型描述的一般形式抽象数据类型描述的一般形式如下：ADT 抽象数据类型名称 数据对象：数据关系：操作集合：操作名1：操作名n：ADT抽象数据类型名称线性表线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 01020304线性表的概念及运算The Concepts and Operations of Linear List线性表的顺序存储Sequence Storage of Linear List线性表的链式存储 Linked Storage of Linear List顺序表与链表的比较Comparision between the two Linear ListsCONTENT01线性表的概念及运算The Concepts and Operations of Linear ListPART ONE1.线性表的概念及运算线性表线性表(Linear List)是由n (n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1， ，an）。对于n0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每一个数据元素只有一个直接前驱和一个直接后继。线性表线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。图1.1 线性表的逻辑结构1.线性表的概念及运算线性表存储方式线性表存储方式实现线性表在计算机中的存放有顺序存储与链式存储两种方式。线性表顺序存储（顺序表）：线性表顺序存储（顺序表）：采用静态分配方式静态分配方式，借助于C语言的数组类型数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序会在存储顺序之中。线性表链式存储（链表）：线性表链式存储（链表）：采用动态分配方式动态分配方式，借助于C语言的指针类型指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。1.线性表的概念及运算抽象数据类型定义 ：ADT LinearList数据元素：D=ai| aiD0, i=1,2,，n n0 ，D0为某一数据对象结构关系： | ai, ai+1D0，i=1,2, ,n-1基本操作： （1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L) 操作前提：线性表L已存在 。 操作结果：将表L置为空表。 1.线性表的概念及运算 （4）EmptyList（L） 操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则为假。 （5）ListLength(L) 操作前提：线性表L已存在。 操作结果：如果L为空表则返回0，否则返回表中元素个数。 （6）Locate(L,e) 操作前提：表L已存在，e为合法元素值。 操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。 1.线性表的概念及运算 （7）GetData（L,i） 操作前提：表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 LinearList02线性表的顺序存储Sequence Storage of Linear ListPART TWO2.线性表的顺序存储基本概念2.1基本运算2.2优缺点分析2.32.1 基本概念线性表的顺序存储线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系关系。采用顺序存储结构的线性表通常称为顺序表顺序表。将顺序表顺序表归纳为：关系线性化，结点顺序存关系线性化，结点顺序存。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可通过如下公式计算出第i个元素的地址loc(ai)为： loc(ai) =loc(a1)+(i-1)k 其中loc(a1)称为基地址。2.1 基本概念图2.1 顺序存储结构示意图存储地址 内存空间状态 逻辑地址 Loc(a1) a11 Loc(a1)+(2-1)k a2 2 loc(a1)+(i-1)k ai i loc(a1)+(n-1)k an n . loc(a1)+(maxlen-1)k 空闲2.1 基本概念顺序存储结构的顺序存储结构的C语言定义语言定义#definemaxsize=线性表可能达到的最大长度；typedef struct ElemType elemmaxsize； /* 线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/ SeqList； 注意区分元素的序号和数组的下标序号和数组的下标，如a1的序号为1， 而其对应的数组下标为0。2.2 基本算法查找操作2.2.1插入操作2.2.2删除操作2.2.3顺序表合并算法2.2.42.2.1 查找操作按序号序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。按内容内容查找Locate(L,e)： 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。2.2.1 查找操作按内容查找：按内容查找：int Locate(SeqList L，ElemType e)i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.last)&(L.elemi!=e) ) i+; /*顺序扫描表，直到找到值为顺序扫描表，直到找到值为key 的元素的元素,扫描到表尾而没找到扫描到表尾而没找到*/ if (i=L.last) return(i+1); /*若找到值为e的元素，则返回其序号*/ else return(-1); /*若没找到，则返回空序号*/图2.2.查找操作2.2.2 插入操作线性表的插入运算插入运算是指在表的第i (1in+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，,ei-1，e，ei，en）。线性表的插入运算算法插入运算算法已知：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置。要点：将第9个到第4个的元素依次后移一个位置，将“21”插入到第4个位置。2.2.2 插入操作序号移动元素插入元素123456781094915 28 30 30 42 51 62491528 30 304262514915 2128 30 30426251int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判断插入位置是否合法*/ printf(“插入位置i值不合法”)；return(ERROR); if(L-last=maxsize-1) printf(“表已满无法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*为插入元素而移动位置为插入元素而移动位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在在C语言中数组第语言中数组第i个元素的下标为个元素的下标为i-1*/ L-last+; return(OK);图2.3 插入操作2.2.3 删除操作线性表的删除运算删除运算是指将表的第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个元素删除。 序号123456781094915212830304262514915213030425162删除28后图2.4.删除操作2.2.3 删除操作int DelList(SeqList *L,int i,ElemType *e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ int k; if(iL-last+1) printf(“删除位置不合法！”)； return(ERROR)； *e= L-elemi-1; /* 将删除的元素存放到将删除的元素存放到e所指向的变量中所指向的变量中*/ for(k=i;ilast;k+) L-elemk-1= L-elemk; /*将后面的元素依次前移将后面的元素依次前移*/ L-last-; return(OK); 序号123456781094915212830304262514915213030425162删除28后图2.5 删除操作2.2.4 顺序表合并算法已知 ：有两个顺序表两个顺序表LA和和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表合并成一个顺序表LC，要求要求LC也是也是非递减有序排列。非递减有序排列。 算法思想算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将，则当前先将LB.elemj插入到表插入到表LC中，若中，若LA.elemiLB.elemj ，当前先将，当前先将LA.elemi插插入到表入到表LC中中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。2.2.4 顺序表合并算法void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast&jlast) if(LA-elemielemj) LC-elemk= LA-elemi; i+; k+; else LC-elemk=LB-elemj; j