线性表_数据结构课件

1、数据结构-线性表Linear List of Data StructuresXXXXXXXXXXXXXXXXXXXXX前言数据结构数据结构是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元素的集合。同样是结构，从不同的角度来讨论，会有不素的集合。同样是结构，从不同的角度来讨论，会有不同的分类，如图同的分类，如图1所示。所示。逻辑结构逻辑结构：数据对象中数据元素之间的相互关系。：数据对象中数据元素之间的相互关系。物理结构物理结构：数据结构在计算机中的表示（映像）称为：数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。数据的物理（存储）结构。线性结构：线性结

2、构：线性表线性表、栈和队列、串、数组和广义表。、栈和队列、串、数组和广义表。图1 线性表的数据结构前言抽象数据类型抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。抽象数据类型描述的一般形式抽象数据类型描述的一般形式如下：ADT 抽象数据类型名称 数据对象：数据关系：操作集合：操作名1：操作名n：ADT抽象数据类型名称线性表线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯

3、一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 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.线性表的概念及运

4、算线性表线性表(Linear List)是由n (n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1， ，an）。对于n0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每一个数据元素只有一个直接前驱和一个直接后继。线性表线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。图1.1 线性表的逻辑结构1.线性表的概念及运算线性表存储方式线性表存储方式实现线性表在计算机中的存放有顺序存储与链式存储

5、两种方式。线性表顺序存储（顺序表）：线性表顺序存储（顺序表）：采用静态分配方式静态分配方式，借助于C语言的数组类型数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序会在存储顺序之中。线性表链式存储（链表）：线性表链式存储（链表）：采用动态分配方式动态分配方式，借助于C语言的指针类型指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。1.线性表的概念及运算抽象数据类型定义 ：ADT LinearList数据元素：D=ai| aiD0, i=1,2,，n n0 ，D0为某一数据对象结构关系： | ai, ai+1D0，i=1,2, ,n-1基本操作： （1）

6、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中存在元

7、素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线

8、性表的顺序存储Sequence Storage of Linear ListPART TWO2.线性表的顺序存储基本概念2.1基本运算2.2优缺点分析2.32.1 基本概念线性表的顺序存储线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系关系。采用顺序存储结构的线性表通常称为顺序表顺序表。将顺序表顺序表归纳为：关系线性化，结点顺序存关系线性化，结点顺序存。假设线性表中有n个元素，每个

9、元素占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 struc

10、t 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相等

11、的数据元素，其结果是：若在表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 retur

12、n(-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 插入操作序号

13、移动元素插入元素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-) /*为插入元素而移动位置为插入元素而移动位置*/

14、 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后

15、图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); 序号123456781094

16、915212830304262514915213030425162删除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插插入

17、到表入到表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+; k+; while(ilast)/*当表LA长则将表LA余下的元素赋给表LC*/ LC-elemk= LA-elemi; i+; k+; while(j

18、last) /*当表LB长则将表LB余下的元素赋给表LC*/ LC-elemk= LB-elemj; j+; k+; LC-last=LA-last+LB-last; 2.3 优缺点分析优点优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间； 2.可方便地随机存取表中的任一元素。 缺点缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低； 2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。03线性表的链式存储Linked Storage of Linear Lis

19、tPART THREE2.线性表的顺序存储基本概念3.1 单链表的基本运算3.2其它链表3.33.1 基本概念结点：结点：存储线性表的每个数据元素值的信息与元素间逻辑关系（即后继结点地址信息）的两部分存储映象。链表：链表：采用链式存储结构的线性表称为链表 。单链表单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。单链表包括两个域单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。头指针头指针 ：指向链表头结点的指针。现在我们从两个角度来讨论链表：1.从实现角度看，链表可分为动态链表和静态链表；2.从链接方式的角度看，链表可分为单链表、循环

20、链表和双链表。图3.1 带头结点的单链表3.1 基本概念头指针H存储地址数据域指针域1 D 437 B 1313 C 119 H NULL25 F 3731 A 737 G 1943 E 25313.2 单链表的示例图3.1 基本概念单链表的存储结构描述单链表的存储结构描述typedef struct Node / * 结点类型定义 * / ElemType data； struct Node * next；Node, *LinkList；/* LinkList为结构指针类型*/ 3.2 基本算法 建立单链表3.2.1单链表查找3.2.2单链表插入3.2.3 单链表删除3.2.43.2.1 建

21、立单链表尾插法建表尾插法建表Linklist CreateFromTail() /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*为头结点分配存储空间*/ L-next=NULL; r=L; /*r指针始终动态指向链表的当前表尾*/ while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/ c=getchar();if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s el

22、se flag=0; r-next=NULL; 图3.3 尾插法建表3.2.1 建立单链表头插法建表头插法建表Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /* 设置一个标志，初值为1，当输入“$” 时，flag为0，建表结束*/ L=(Linklist)malloc(sizeof(Node)；/*为头结点 分配存储空间*/ L-next=NULL; while(flag) c=getchar(); if(c!=$) /*为读入的字符分配存储空间*/ s=(Node*)malloc(sizeof(Node); s-data

23、=c; s-next=L-next; L-next=s; elseflag=0; 图3.4 头插法建表3.2.2 单链表查找按序号查找按序号查找 算法描述算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针头指针L出发出发，从头结点（L-next）开始顺着链域扫描顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL-next），用j做记数做记数器器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点 。/ * 在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置; 否则返回NULL *

24、 /Node * Get(LinkList L, int i) Node *p； p=L；j=0； / * 从头结点开始扫描 * / while (p-next!=NULL)&(jnext； j+； / * 扫描下一结点扫描下一结点 * / / * 已扫描结点计数器已扫描结点计数器 * / if（i= =j）return p； / * 找到了第i个结点 * / else return NULL； / * 找不到，i0或in * /图3.5 按序号查找3.2.2 单链表查找按值查找按值查找算法描述：算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的

25、结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。/ * 在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL * /Node *Locate( LinkList L,ElemType key) Node *p; p=L-next; / * 从表中第一个结点比较 * / while (p!=NULL) if (p-data!=key) p=p-next; else break; / * 找到结点key，退出循环 * / return p;图3.6 按值查找3.3.3 单链表插入插入操作插

26、入操作要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。void InsList(LinkList L,int i,ElemType e) /*在带头结点的单链表L中第i个结点之前插入值为e的新结点。 */ Node *pre,*s; pre=L; int k=0; while(pre!=NULL&knext; k=k+1; if(k!=i-1) printf(“插入位置不合理！”)； return;

27、 s=(Node*)malloc(sizeof(Node); /*为为e申请一个新的结点申请一个新的结点*/ s-data=e; /*将待插入结点的值将待插入结点的值e赋给赋给s的数据域的数据域*/ s-next=pre-next; pre-next=s;3.7 单链表插入3.3.4 单链表删除删除操作删除操作欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第删除第i个结点并释放结点个结点并释放结点空间。空间。 void DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个

28、元素，并保存其值到变量*e中*/ Node *p,*r; p=L; int k =0;while(p-next!=NULL&knext; k=k+1; if(k!=i-1) /* 即while循环是因为p-next=NULL而跳出的*/ printf(“删除结点的位置i不合理！”); return ERROR; r=p-next; p-next=p-next-next /*删除结点删除结点r*/free(r); /*释放被删除的结点所占的内存空间*/3.8单链表删除3.3 其它链表双向链表：双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的

29、链，我们称之为双双 ( 向向) 链表链表 (Double Linked List)。有时候以倒序扫描链表很方便。标准实现方法此时无能为力，然而解决方法却很简单。只要在数据结构上附加一个域，使它包含指向前一个单元的指针即可。其开销是一个附加的链，它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。另一方面，它简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字；这个信息是现成的。表示一个双链表。双向链表的结构定义：typedef struct Dnode ElemType data； struct DNode *prior，*next； DNode

30、,* DoubleList；3.9 双向链表3.3 其它链表循环链表循环链表(Circular Linked List) 是一个首尾相接的链表。将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。让最后的单元反过来直指第一个单元是一种流行的做法。它可以有表头，也可以没有表头（若有表头，则最后的单元指向它），并且还可以是双向链表（第一个单元的前驱元指针指向最后的单元）。这无疑会影响某些测试，不过这种结构在某些应用程序中却很流行。显示了一个无表头的双向循环链表。 3.10 循环链表04

31、顺序表与链表的比较Comparision between the two Linear ListsPART FOUR4.顺序表与链表的比较简要概述4.1 实际比较4.2 相关技术4.34.1 简要概述顺序表的特点是逻辑上相邻的数据元素，物理存储位置顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。也相邻，并且，顺序表的存储空间需要预先分配。它的优点是它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示节点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。缺点：缺点：（1）在顺序表中做插入、删除操作时，

32、平均移动表中的一半元素，因此对n较大的顺序表效率低。（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。4.1 简要概述在链表中逻辑上相邻的数据元素，物理存储位置不在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。且，链表的存储空间是动态分配的。链表的最大特点是：链表的最大特点是：插入、删除运算方便。缺点：缺点：（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所

33、占的存储单元之比。（2）链表不是一种随机存储结构，不能随机存取元素。4.2.1 基于空间的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。 因此，当线性表的长度变化较大，难以估计其存储规模

34、时，采用动态链因此，当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。表作为存储结构较好。存储密度(Storage Density)是指结点数据结构本身所占的存储量和整个结点结构所占的存储量之比。一般地，存储密度越大，存储空间的利用率就高。显然，顺序表的存储密度为1，而链表的存储密度小于1。因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。储空间，则采用顺序表作为存储结构比较适宜。4.2.2 基于时间的考虑顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1)。而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。表做存储结构。在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的；在链表中的任何位置进行插入和删除时，都只需要修改指