数据的线性结构

1、“计算机软件技术计算机软件技术”课群课群基础篇之基础篇之 数据结构数据结构第第2章章 数据的线性结构数据的线性结构 (3学时学时)第第3章章 查找与排序查找与排序 (2学时学时)第第2章章 数据的线性结构数据的线性结构2.1.1数据的逻辑结构和存储表示数据的逻辑结构和存储表示1.基本的概念和术语基本的概念和术语 计算机的应用计算机的应用: 科学计算科学计算=非数值计算非数值计算一、两个例子一、两个例子例例1、学生档案管理、学生档案管理 组织成一个二维表组织成一个二维表学号学号姓名姓名性别性别出生年月出生年月专业专业.10040305张明男1985.01.01计算机10041536李丽女1985

2、.05.30物理组织成一棵树组织成一棵树化 工 学 院0 3 级学 生 1 学 生 n0 4 级 0 5 级计 算 机 系自 动 化 系电 子 与 通 信 工 程 系信 息 科 学 与 工 程 学 院物 理 系化 学 系理 学 院学 校例例2、在、在n个城市间建立通信网络个城市间建立通信网络c1c1c4c4c2c2c3c3c5c51 13 36 66 67 75 59 97 78 84 4c1c4c2c3c51364代价最小代价最小从上面两个例子中可以看出：从上面两个例子中可以看出： 数据结构中元素之间存在着逻辑关系，数据结构中元素之间存在着逻辑关系，上述例子中给出了三种逻辑结构上述例子中给出

3、了三种逻辑结构线性表、线性表、树、图。树、图。数据结构主要解决：数据结构主要解决：如何分析数据元素之间的关系，并确定合适如何分析数据元素之间的关系，并确定合适的逻辑结构；的逻辑结构；如何在计算机中存储这些数据；如何在计算机中存储这些数据；为完成对数据的操作设计算法，并作出分析。为完成对数据的操作设计算法，并作出分析。二、概念和术语二、概念和术语1. 数据数据(data)：表示现实世界中的客观事物、能：表示现实世界中的客观事物、能输入计算机并能被计算机程序处理的符号的输入计算机并能被计算机程序处理的符号的总称。总称。2. 数据元素数据元素(data element)：数据集合中的一个：数据集合中

4、的一个个体，是数据的基本单位。个体，是数据的基本单位。(亦称为结点、记亦称为结点、记录等录等)3. 数据项数据项(data item)：数据的不可分割的、含有：数据的不可分割的、含有独立意义的最小单位。独立意义的最小单位。4. 数据对象数据对象(data object)：性质相同的数据元素：性质相同的数据元素的集合。的集合。5. 数据结构数据结构(data structure)：相互之间存在着一：相互之间存在着一种或多种关系的数据元素的集合。种或多种关系的数据元素的集合。 数据结构无公认定义，都认为其研究涉数据结构无公认定义，都认为其研究涉及三个方面：及三个方面：1) 数据元素间的逻辑关系数据

5、元素间的逻辑关系(逻辑结构逻辑结构)2) 数据元素的存储方式数据元素的存储方式(物理结构物理结构)3) 数据元素间的运算数据元素间的运算(操作操作) 一般地，一个数据结构中的数据元素一般地，一个数据结构中的数据元素属于同一个数据对象。属于同一个数据对象。2.1.2 2.1.2 数据的逻辑结构和存储方法数据的逻辑结构和存储方法一、数据的逻辑结构一、数据的逻辑结构 逻辑结构逻辑结构是指数据元素之间的特定关系，是指数据元素之间的特定关系，它独立于计算机，是元素之间关系的抽象。它独立于计算机，是元素之间关系的抽象。1 1、定义、定义 数据结构是一个二元组数据结构是一个二元组b=(db=(d，r)r)。

6、其。其中中d d是数据元素是数据元素( (即结点即结点) )的有限集合；的有限集合；r r是是d d上的关系的有限集合。一般上的关系的有限集合。一般r r中只涉及一种中只涉及一种关系。关系。例如例如： 有有4个人，为别为个人，为别为a、b、c、d，其中，其中a是是b的父亲，的父亲，b是是c的父亲，的父亲，c是是d的父亲的父亲，如，如果只讨论他们所表达的果只讨论他们所表达的父子父子关系，则可关系，则可以用下面的二元组形式化地表示为：以用下面的二元组形式化地表示为： b(d，r) 其中其中 d=a，b，c，d r=r r = ，又如又如: 另有另有4个人，分别为个人，分别为e,f,g,h；其中；其

7、中e是是f和和g的父亲，的父亲，g是是h的父亲，则可用下面的二的父亲，则可用下面的二元组形式化地表示为：元组形式化地表示为： b(d，r) 其中其中 d=e，f，g，h r=r r = ，可以用图形方式分别表示为：可以用图形方式分别表示为：abcdfegh2、几个概念、几个概念 设设b=(d，r)是一个逻辑结构，是一个逻辑结构，rr，di、dj d。如果如果 r，则称，则称di是是dj的前驱，的前驱， dj是是di的后继。的后继。如果某个结点没有前驱，则称之为如果某个结点没有前驱，则称之为开始结点开始结点；如果某个结点没有后继，则称之为如果某个结点没有后继，则称之为终端结点终端结点；既非开始结

8、点，也非终端结点的结点称之为既非开始结点，也非终端结点的结点称之为内部结点内部结点。3、结构分类、结构分类线性结构线性结构 只有一个开始结点和一个终端结点，其它结点只有一只有一个开始结点和一个终端结点，其它结点只有一个前驱结点和一个后继结点，称之为线性结构。即元个前驱结点和一个后继结点，称之为线性结构。即元素之间存在着一对一的关系。素之间存在着一对一的关系。非线性结构非线性结构 如果一个结构不是线性结构，则称之为非线性结构。如果一个结构不是线性结构，则称之为非线性结构。一般地，结构中至少有一个结点存在不止一个前驱结一般地，结构中至少有一个结点存在不止一个前驱结点或后继结点。非线性结构有两类：点

9、或后继结点。非线性结构有两类： a、树形结构：元素之间存在着一对多的关系。、树形结构：元素之间存在着一对多的关系。 b、图形结构：元素之间存在着多对多的关系。、图形结构：元素之间存在着多对多的关系。141312112345678910456231 1 2 3 4 51二、数据的存储方法二、数据的存储方法 一般地，数据的存储方法有四种：一般地，数据的存储方法有四种：顺序存储顺序存储链式存储链式存储索引存储索引存储散列存储散列存储（后两种方法主要用于查找，本课程不作详述）（后两种方法主要用于查找，本课程不作详述）1、顺序存储、顺序存储 把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理

10、位置相邻的存储单元之中。通常借助理位置相邻的存储单元之中。通常借助于程序设计语言中的数组来实现。于程序设计语言中的数组来实现。2、链式存储、链式存储 逻辑上相邻的数据元素不要求其物逻辑上相邻的数据元素不要求其物理存储位置相邻，元素间的逻辑关系用理存储位置相邻，元素间的逻辑关系用附设的指针域来表示。通常借助于程序附设的指针域来表示。通常借助于程序设计语言中的指针来实现。设计语言中的指针来实现。例如：例如：有数据结构有数据结构b=(d，r)， 其中其中 d=d1,d2,d3,d4,d5 r=r r=,则用上述两种存储结构表示为：则用上述两种存储结构表示为：d1d2d3d4d510001005101

11、010151020d5d35000d14000d22000d41000 顺序存储顺序存储（假设每个元素占（假设每个元素占5个存储单元）个存储单元）链式存储链式存储10002000300040005000头指针变量头指针变量存储地址存储地址存储地址存储地址数据域数据域指针域指针域3000数据域数据域链式存储图示为：链式存储图示为：d1d5headd2d3d4线性结构和非线性结构均可采用这两种存储方法。线性结构和非线性结构均可采用这两种存储方法。 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：插入、删除、查找、排序、修改等数据的运算：插入、删除、查找、排序、修改等 线性结

12、构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：2.2 线性表的基本概念线性表的基本概念一、线性表的定义一、线性表的定义 它是最常用且又最简单的线性结构。它是最常用且又最简单的线性结构。定义：定义： 线性表是线性表是n(n0)个性质相同的数据元个性质相同的数据元素所构成的有限序列素所构成的有限序列(a1,a2,a3,.,an)。 n称为线性表的长度。称为线性表的长度。 当当n=0时，称为空表。时，称为空表。 数据元素数据元素可以是很简单的整数、英文字母等，可以是很简单的整数、英文字

13、母等，也可以是较复杂的元素。由复杂元素构成的线也可以是较复杂的元素。由复杂元素构成的线性表又称为文件，复杂数据元素称为记录。性表又称为文件，复杂数据元素称为记录。 例如：例如： （1，2，7，5，3，9） ( a，d，c，b，e )19851985年年4 4月月19861986年年1 1月月男男女女王东林王东林吴红吴红10041001100410011004100210041002出生年月出生年月性别性别姓名姓名学号学号上面这些都是线性表。上面这些都是线性表。二、线性表的基本运算二、线性表的基本运算 线性表的初始化（构造一个空的线性表）线性表的初始化（构造一个空的线性表） 求表长求表长 取第取

14、第i个数据元素个数据元素 查找具有特定值的结点，确定其序号查找具有特定值的结点，确定其序号 插入操作（在原表的第插入操作（在原表的第i个位置上插入新元素）个位置上插入新元素） 删除操作（删除原表中第删除操作（删除原表中第i个元素）个元素） 随着线性表的存储方法不同，各种运算的实现随着线性表的存储方法不同，各种运算的实现方法也不一样。下面结合线性表的不同存储结方法也不一样。下面结合线性表的不同存储结构，讨论实现上述一些运算的算法。构，讨论实现上述一些运算的算法。2.3 线性表的顺序存储（顺序表）线性表的顺序存储（顺序表）一、顺序表的表示方法一、顺序表的表示方法 用一组地址连续的存储单元依次存放用

15、一组地址连续的存储单元依次存放线性表的元素。线性表的元素。 假设每个元素占用假设每个元素占用b个存储单元，并以个存储单元，并以元素的第一个存储单元地址作为元素的元素的第一个存储单元地址作为元素的存储地址（结点始址），则存储地址（结点始址），则 loc(ai+1) = loc(ai)+b 一般地，第一般地，第i个元素的存个元素的存储地址为储地址为 loc(ai)=loc(a1)+(i-1)*b 通常称线性表的第一个元通常称线性表的第一个元素素a1的存储地址为线性表的的存储地址为线性表的基地址，设为基地址，设为h，则有，则有 loc(ai)=h+(i-1)*banaia2a1hh+bh+(i-1)

16、bh+(n-1)b顺序表特点：顺序表特点：1. 逻辑上相邻的元素在物理存储上亦相邻；逻辑上相邻的元素在物理存储上亦相邻；2. 任一元素的存取时间相同，是一种随机任一元素的存取时间相同，是一种随机存取结构。存取结构。（用类用类c语言描述顺序表语言描述顺序表）define maxnum 100 /*最大元素个数最大元素个数*/typedef struct datamaxnum; int length; /*当前长度当前长度*/sqlist;返回返回二、顺序表上基本运算的实现二、顺序表上基本运算的实现1、顺序表的初始化、顺序表的初始化 把当前表长置把当前表长置0。即：即： void initlist

17、_sq( sqlist *l ) *l.length = 0; /*或或l-length = 0*/ 2、顺序表的插入操作、顺序表的插入操作 要求在顺序表的第要求在顺序表的第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。 原线性表原线性表: (a1, a2, , ai-1, ai, ai+1, , an ) 长度为长度为n 插入后的线性表插入后的线性表: (a1, a2, , ai-1, x , ai, ai+1, , an ) 长度为长度为n+1设设i的取值范围为的取值范围为1in+1，插入操作的步，插入操作的步骤如下：骤如下： （算法描述算法描述）1. 将将anai依次向

18、后移动，为新元素让出位依次向后移动，为新元素让出位置；置；2. 将将x置入空出的第置入空出的第i个位置；个位置；3. 修改表长。修改表长。#define error 0#define ok 1int listinsert_sq ( sqlist *l, int i, x ) int j; if ( l-length = maxnum ) printf( “list is full” ); return (error); if ( il-length+1 ) printf( “ i is invalid value” ); return (error); for ( j=l-length-1;

19、j=i-1; j- ) l-dataj+1 = l-dataj; /*元素后移元素后移*/ l-datai-1 = x; /*新元素插入新元素插入*/ l-length+; /*表长加表长加1*/ return ( ok ); 返回返回3、顺序表的删除操作、顺序表的删除操作 要求删除顺序表的第要求删除顺序表的第i个位置上的元素。个位置上的元素。 原线性表原线性表 (a1, a2, , ai-1, ai, ai+1, , an ) 长度为长度为n 删除后的线性表删除后的线性表 (a1, a2, , ai-1, ai+1, , an ) 长度为长度为n-1设设i的取值范围为的取值范围为1in，删除

20、操作的步骤如下：，删除操作的步骤如下： 将将ai+1an依次向前移动；依次向前移动； （算法描述算法描述） 修改表长修改表长int listdelete_sq ( sqlist *l, int i ) int j; if ( il-length-1 ) printf( “i is invalid value” ); return( error ); for ( j=i; jlength; j+ ) l-dataj-1 = l-dataj; /*元素前移元素前移*/ l-length-; /*长度减长度减1*/ return ( ok );顺序表插入和删除操作的时间复杂度均为顺序表插入和删除操作

21、的时间复杂度均为o(n)。 返回返回2.4 线性表的链式存储（链表）线性表的链式存储（链表）2.4.1单链表单链表1、单链表、单链表 结点结构：结点结构： 链表中每个结点有一个存放数据元素链表中每个结点有一个存放数据元素的域，另有一个域存放指向后继结点的的域，另有一个域存放指向后继结点的指针（表示逻辑关系），故称为单链表。指针（表示逻辑关系），故称为单链表。 （用类用类c语言描述为一个结构语言描述为一个结构）数据域 指针域typedef struct node data; /*数据域数据域*/ struct node * next; /*指针域指针域*/node; 返回返回 单链表的两种形式单

22、链表的两种形式heada1ana2heada1a2an带头结点的单链表带头结点的单链表不带头结点的单链表不带头结点的单链表指针变量指针变量head中存放了链表中第一个结点的起始地中存放了链表中第一个结点的起始地址，称之为址，称之为头指针头指针。该指针变量是。该指针变量是“静态静态”定义定义的，即用的，即用node * head;定义了指针变量定义了指针变量head。链表中的结点是链表中的结点是“动态动态”生成的生成的(称之为结点变量称之为结点变量)，每个结点可以存放一个数据元素和后继结点的起每个结点可以存放一个数据元素和后继结点的起始地址。最后一个结点因为没有后继结点，故其始地址。最后一个结点

23、因为没有后继结点，故其指针域中存放指针域中存放null(空地址空地址)。 当链表中没有数据元素当链表中没有数据元素(即空表即空表)时，第一种单链表时，第一种单链表保留头结点。即保留头结点。即 ，后一种，后一种head中为中为null。head 建立一个空表的算法为建立一个空表的算法为(带头结点带头结点)： node *initlist_link （ ） node *p; p = (node *) malloc ( sizeof(node) ); p-next = null; return ( p ); 2、两个标准函数、两个标准函数 malloc 和和 free 设有变量定义：设有变量定义：

24、node *p;则则p=(node *) malloc (sizeof(node)的作用是由系的作用是由系统生成（得到）一个统生成（得到）一个node类型的结点，同时将类型的结点，同时将该结点的起始地址赋给指针变量该结点的起始地址赋给指针变量p。 free(p)的作用是由于系统回收（释放）一个由的作用是由于系统回收（释放）一个由p所指向的所指向的node类型的结点。类型的结点。 注意点：注意点： 每次调用每次调用malloc或或free函数只能得到或释放一个结点空间；函数只能得到或释放一个结点空间； 用用malloc函数得到的结点中无确定的内容，必须由程序函数得到的结点中无确定的内容，必须由程

25、序员给予；员给予； 用用free函数释放一个结点空间，指针变量本身并未释放。函数释放一个结点空间，指针变量本身并未释放。2.4.2单链表上基本运算的实现单链表上基本运算的实现建立单链表建立单链表a. 正向建：正向建： b. 逆向建：逆向建：heada1ana2a1headp2 p1p2p1anan-1a1headan-2a1headpp算法的详细描述读者可参见本教材实践篇的实验算法的详细描述读者可参见本教材实践篇的实验2 单链表的插入操作单链表的插入操作 要求在带头结点的单链表中第要求在带头结点的单链表中第i个位置上插入一个值为个位置上插入一个值为x的新元素。的新元素。算法思想：算法思想： 定

26、义三个指针变量定义三个指针变量p、q和和s； (算法描述算法描述)a)在单链表中寻找第在单链表中寻找第i个元素位置，若找到，则由个元素位置，若找到，则由q指指向第向第i个位置，个位置，p指向第指向第i-1个位置，继续个位置，继续b)；否则结；否则结束。束。b)向系统申请一个由向系统申请一个由s指向的新结点，并在数据域置入指向的新结点，并在数据域置入新元素新元素x。c)将将s指向的新结点插入指向的新结点插入q之前，结束。之前，结束。xp 第第i-1个位置个位置q 第第i个位置个位置sint listinsert( node *l, int i, x ) int j; node *p, *q, *

27、s; p = l; q = l-next; j = 1; while( q!=null & jnext; +j; if ( q=null | ji ) /*找不到插入点找不到插入点*/ return (error); s = (node*) malloc ( sizeof(node) ); /*建立新结点建立新结点*/ s-data = x; s-next = q; /* 插入新结点插入新结点*/ p-next = s; return ( ok ); 该算法的时间复杂度为该算法的时间复杂度为o(n)。 返回返回单链表的删除操作单链表的删除操作 要求在带头结点的单链表中删除第要求在带头结

28、点的单链表中删除第i个位置的个位置的元素。元素。pq 第第i个位置个位置算法思想：算法思想： （算法描述算法描述） 定义两个指针变量定义两个指针变量p和和q。a)在单链表中寻找第在单链表中寻找第i个元素位置，若找到则由个元素位置，若找到则由q指向第指向第i个位置，个位置，p指向第指向第i-1个位置，继续个位置，继续b)，否则结束。，否则结束。b)从链表中删除从链表中删除q所指向的结点。所指向的结点。c)释放释放q所指向的结点空间，结束。所指向的结点空间，结束。int listdelete ( node *l, int i ) int j; node *p, *q; p = l; q = l-n

29、ext; j = 1; while ( q != null & j next; +j; if ( q=null | ji ) /*删除位置不合理删除位置不合理*/ return ( error ); p-next = q-next; /*删除删除q所指向结点所指向结点*/ free ( q ); return ( ok ); 该算法的时间复杂度为该算法的时间复杂度为o(n)。 返回返回 2.4.3线性表的其它链式存储线性表的其它链式存储1、单循环链表、单循环链表 单循环链表是一种特殊的单循环链表是一种特殊的单链表单链表，其最，其最后一个结点的指针域中不存放后一个结点的指针域中不存放nu

30、ll(空空地址地址)，而是放入了链表的头指针。，而是放入了链表的头指针。带头结点的单循环链表带头结点的单循环链表不带头结点的单循环链表不带头结点的单循环链表heada1ana2a1a2anhead空表时空表时 head2、双向链表、双向链表 结点结构：结点结构： 链表中每一个结点除数据域和指向后继结点的指针链表中每一个结点除数据域和指向后继结点的指针域外，增加了一个指向前驱结点的指针域。域外，增加了一个指向前驱结点的指针域。 用类用类c语言描述为：语言描述为： typedef struct dlnode data; struct dlnode *prior, *next; dlnode; 双向

31、链表在做插入和删除操作时，不需要再用双向链表在做插入和删除操作时，不需要再用两个指针在链表上移动。两个指针在链表上移动。后继指针域后继指针域数据域数据域前驱指针域前驱指针域 双向链表的形式双向链表的形式带头结点的双向链表带头结点的双向链表不带头结点的双向链表不带头结点的双向链表a1an非循环非循环循环循环heada1anhead非循环非循环循环循环headheada1ana1an3、静态链表、静态链表 用结构数组来描述静态链表。用结构数组来描述静态链表。 描述方法：描述方法： #define maxsize 1000 /*定义链表的最大长度定义链表的最大长度*/ typedef struct

32、data; int next; snode; snode sdmaxsize; int sl; 上图是一个带头结点的单链表，表示了线性表上图是一个带头结点的单链表，表示了线性表(a1,a2,a3,a4,a5,a6)的链式存储，的链式存储，sl为头指针变量。为头指针变量。1a24a5-1a66a15a42a33datanext0123456maxsize -1sl = 02.5 栈栈2.5.1 栈的定义和基本运算栈的定义和基本运算1、栈的定义、栈的定义 实例：装网球的纸筒、子弹夹实例：装网球的纸筒、子弹夹 a1an定义：栈是限定在表的一端（表尾）进行定义：栈是限定在表的一端（表尾）进行 插入和删

33、除操作的线性表。插入和删除操作的线性表。表尾表尾表头表头允许插入和删除的表尾端称为栈顶。允许插入和删除的表尾端称为栈顶。相应的表头端称为栈底。相应的表头端称为栈底。a1an栈顶栈顶栈底栈底栈的两个要素：存放栈元素的栈的两个要素：存放栈元素的存储空间和栈顶指针。存储空间和栈顶指针。 栈的特点：数据元素后进先出栈的特点：数据元素后进先出 ( li folast in first out)2、 栈的基本运算栈的基本运算栈初始化栈初始化 initstack( s )建立一个空栈建立一个空栈s入栈入栈 push( s, x) 把元素把元素x推入栈推入栈s的栈顶的栈顶出栈出栈 pop( s ) 删除栈删除

34、栈s的栈顶元素的栈顶元素取栈顶元素取栈顶元素 gettop( s, x ) 取出栈取出栈s的栈顶元素送入的栈顶元素送入x，由由x返回返回a1an出栈出栈入栈入栈2.5.2栈的存储结构和运算的实现栈的存储结构和运算的实现1、 顺序存储的栈顺序存储的栈(顺序栈顺序栈) 用一组地址连续的存储单元依次存放自栈底到用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设栈顶指针栈顶的数据元素，同时附设栈顶指针top指示栈顶元指示栈顶元素在顺序栈中的位置。（素在顺序栈中的位置。（类类c语言描述为一个结构语言描述为一个结构） 例如：例如：43210432104321043210top=-1top =

35、 010top = 410157168top = 210157#define maxsize 5typedef struct stackint elemmaxsize;int top;stack;返回返回在顺序栈上基本运算的实现：在顺序栈上基本运算的实现：栈初始化栈初始化 算法描述算法描述43210top = -1栈顶指针赋初值栈顶指针赋初值 -1void initstack ( stack *s )(*s).top = -1;返回入栈入栈 算法描述算法描述4321043210top = 11015top = 2if ( 栈不满栈不满 ) 栈顶指针加栈顶指针加1； 将将x的值推入栈顶；的值推入栈顶；else 出错；出错；10157x = 7#define error 0#define ok 1int push( stack *s,