计算09赵威.ppt

1、第二章 线性表,本章基本内容： 线性表的逻辑结构定义和各种存储结构的描述方法， 在线性表的两类存储结构上如何实现基本运算。 学习要点： 1、了解线性表的逻辑结构特性是数据元素之间存在着 线性关系，在计算机中表示这种关系的不同方法 得到两类不同的存储结构。 2、熟练掌握这两类存储结构的描述方法，以及循环链表、 双向链表的特点等。 3、熟练掌握顺序表、线性链表实现的基本操作：如插入、删除等算法。,2.1 线性表概念及基本操作 2.2 线性表的顺序存储和实现 2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表,2.1 线性表的概念,一、线性表的逻辑结构

2、线性表是n 个类型相同数据元素的有限序列， 通常记作（a1, a2, a3, , an ）。 例1、数学中的数列（11，13，15，17，19，21) 例2、英文字母表（A, B, C, D, E Z )。 例3、某单位的电话号码簿。,设L=（a1,a2, .ai-1, ai , ai+1, , an ）是一线性表 1、 初始化操作 InitList(,typedef struct ElemType elemlistsize; int length; /当前线性表长度 ListTp2;,顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#def

3、ine LISTINCREMENT 10 / 线性表存储空间的分配增量typedef struct ElemType * elem; /线性表存储空间基址 int length; /当前线性表长度 int listsize; /当前分配的线性表存储空间大小 / (以sizeof(ElemType)为单位)SqList;,SqList ：类型名， SqList类型的变量是结构变量，它的三个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作 (建空表)时动态分配； length：存放线性表的表长； listsize：用于存放当前分配 (存放线性表元素)的存储空间的大小。,

4、存放线性表元素 的一维数组,L在内存中的状态如图所示：,顺序表通过元素的 存储顺序反映线性表 元素间的逻辑关系,SqList *L;,二、顺序表的基本操作算法 两个C函数1) Malloc(int size) 功能:在系统内存中分配size个存储单元, 并返回该空间的基址。使用方法： . int m = 100; float *p; p = (float*) malloc (m*sizeof(float );,p = (float*) malloc(m*sizeof(float) 图示,调用free ( p ),调用free ( p ) 图示,2) free ( p ) 功能：将指针变量p所指

5、示的存储空间，回收到系统内存 空间中去。,使用方法： . int m = 100; float *p; p = (float*) malloc(m*sizeof(float); / 一旦p所指示的内存空间不再使用， /调用free( ) 回收之 free(p);,100,1、初始化操作 InitList_Sq( SqList Lp=(Sqlist *)malloc(sizeof(SqList); InitList_Sq(Lp); ,InitList_Sq(SqList *L) L-elem =(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(!L-ele

6、m)exit(OVERFLOW); L-Length = 0; L-Listsize = LIST_INIT_SIZE; return OK; ,2、销毁操作 DestroyList_Sq(SqList L.elem =( ElemType*)malloc(LIST_INIT_SIZE* sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length = 0; L.Listsize = LIST_INIT_SIZE; return OK; ,ai,6、取元素操作 GetElem_Sq(SqList L,int i, ElemType 3) 将第i个

7、元素之后的元素(不包括第i个元素)依次向前移动一个位置; 4) 表长-1,删除操作算法:,Status ListDelete_Sq(SqList /ListDelete_Sq 算法2.5 a,为初学者易于理解 删除算法，这里通 过下标引用L.elem 中的元素。,Status ListDelete_Sq(SqList /ListDelete_Sq 算法2.5 b,删除操作算法:,算法2.5b与算法2.5a 唯一的不同是通过指针p引用L.elem中的元素。,21 18 30 75,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(2）将La并入Lb;3）将La、L

8、b并入Lc; (顺序表Lc中的空间是新分配的存储空间) 基本思想：同时对La.elem, Lb.elem 进行扫描，在扫描过程中按两表当前元素的大小，依次将其插入到Lc的表尾。,三、线性表其它操作的实现,1、利用基本操作实现线性表的其它操作,顺序表的归并图示(算法2.7a),0 1 99,2 3 5 6 8 8 9,100,建空表Lc,0,La,Lb归并,7,Void MergeList_Sq(SqList *La, SqList *Lb, SqList /MergeList_Sq 算法2.7 a,用线性表的基本 操作实现线性表 的其它操作,void MergeList_Sq(SqList *

9、La, SqList *Lb, SqList /插入Lb的剩余元素/MergeList_Sq 算法2.7b,2、直接对顺序表进行操作实现归并算法,直接对顺序表进 行操作实现顺序 表的其它操作,顺序表的归并图示(算法2.7 b),2 3 5 6 8 8 9,0,7,7,建空表Lc,La,Lb归并,顺序表是线性表最简单的一种存储结构,51,2.3 线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。,52,2.3.1 线性链表 一、线性链表的概念 二

10、、线性链表的基本操作算法 三、静态链表 四、线性链表的其它操作 2.3.2 循环链表2.3.3 双向链表 一、双向链表的概念 二、双向链表的基本操作算法,53,一、 线性链表的概念1、线性链表,2.3.1 线性链表,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。,用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,54,结点：数据元素及直接后继的存储位置(地址)组成一个数据 元素的存储结构，称为一个结点； 结点的数据域 ：结点中用于保存数据元素的部分; 结点的指针域 ：结点中用于保存数据元素直接后继

11、存储地址 的部分;,线性链表有关术语,存储数据元素,存储后继结点 存储地址,55,头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针;头结点：线性链表的第一个元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一个元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；,L是头指针,头结点,空指针,L,线性链表的每个结点中只有一个 指针域，故也称为单链表,首元元素,56,头结点,头指针,头指针,空指针,线性表为空表时， 头结点的指针域为空,怎样在计算机上 实现线性链表？,？,57,结点变量图示,typedef stru

12、ct LNode ElemType data; struct LNode *next;LNode, *LinkList;,data域：用于存放线性表的数据元素， next域：用于存放元素直接后继结点的地址；,data next,LNode类型 结构变量,L 是LinkList类型的指针变量,线性链表的结点类型定义及指向结点的指针类型定义,LinkList L;/L为单链表的头指针,58,LinkList L； / L为单链表的头指针 引人头结点的概念 加入头结点的作用 (1)判空 (2)使首元结点的操作和其它结点相同,59,二、 线性链表基本操作的算法,如何在线性链表L 上实现线性表的基本操作

13、？ 如何建空表？如何插入？删除？,？,约定用带头结点的 线性链表存储线性表,60,算法：Status InitList_L (LinkList L) L = (LinkList)malloc(sizeof(LNode); if (!L) exit(OVERFLOW); L-next = NULL; return OK; / InitList_L,1、初始化操作InitList_L(LinkList L) 功能： 建空线性链表L参数： L为线性链表的头指针 主要步骤：调用malloc( )分配一结点的空间,并将其地址赋值给L；,61,2、取元素操作 GetElem_L ( LinkList L,

14、 int i, ElemType / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;,s,p,68,4、删除操作 ListDelete_L(LinkList L, int i, ElemType p- next = q- next; e = q-data; free(q);,p,q,删除操作主要步骤： 1）查找链表的第 i-1个元素结点；2）修改第 i-1个元素结点指针，删除第i个元素结点；3) 将第i个元素结点中的数据元素赋值给e;4）回收被删除结点空间。,70,删除操作算法： Status ListDelete_

15、L(LinkList L, int i, ElemType /LinstDelete_L 算法： 2.10,71,5、表置空操作 ClearList_L(LinkList L) 功能:线性链表L已存在，将L重新置为一个空表 void ClearList_L(LinkList L) / L 为带头结点的单链表的头指针，本 算法将单链表重新置为一个空表 p= L-next; while (p) L-next = p-next; free(p); p = L-next; / ClearList,72,三、线性链表的其他操作的实现,例1：将两个有序线性链表归并成一个有序表。 设线性表A、B分别用头指针

16、为La 、 Lb 的两个带头结点 的线性链表存储。,利用基本操作 直接对链表进行操作,73,线性链表归并操作图示,1,74,线性链表归并操作算法(直接对链表进行操作) 算法 2.12 void MergeList_L(LinkList La, LinkList Lb, LinkList Lc) /已知线性链表La和Lb的元素按值非递减排列/归并La和Lb得到新的线性链表Lc,Lc的元素也按值非递减排列。pa = La-next; pb = Lb-next;Lc = pc = La; /用La的头结点作为Lc的头结点while (pa / 释放Lb的头结点 /MergeList_L,直接对线性链

17、表进行操作 实现线性链表的其它操作,75,例2、建立线性链表（直接对链表进行操作）,76,1、逆位序输入 n 个数据元素的值， 建立带头结点的单链表。,操作步骤：,(1)建立一个“空表”；,(2)输入数据元素an， 建立结点并插入；,(3)输入数据元素an-1， 建立结点并插入；,an,an,an-1,(4)依次类推，直至输入a1为止。,77,void CreateList_L(LinkList L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L,L = (LinkList) malloc (sizeof (LNode); L-next = N

18、ULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( / 插入 ,78,2、正序输入n个数据元素的值,建立带头结点的单链表。 void Create_L(LinkList L, int n) / 正序输入 n 个数据元素，建立带头结点的单链表 / Create_L,L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表 s = L; /保留的尾指针,for (i =1; i data); /

19、 输入元素值 s-next = p; / 插入 s=p; /修改尾指针 ,s-next = NULL;,79,四、静态链表,1、静态链表的概念 用数组实现的线性链表，称为静态链表。,SLinkList：数组的类型名； SLinkList类型的数组变量是结构数组,每一数组分量包括两个域; data：用于存储线性表元素； cur： 用于存储直接后继元素在数组中的位置(下标)；,#define MAXSIZE 1000 / 链表的最大长度typedef structElemType data; int cur; component, SLinkListMAXSIZE;,2、静态链表的类型定义,80,

20、静态链表图示,数组 下标,地址,3、静态链表图示,81,插入WANG,4、静态链表操作 静态链表的插入,插入前,插入后,82,删除SUN,静态链表的删除,删除前,删除后,83,线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点 1、通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2、插入删除操作通过修改结点的指针实现； 3、不能随机存取元素。,84,1、循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将 线性链表的最后一个结点的指针指向链表的第一个结点。 2、循环链表图示,2.3.2 循环链表,(a)非空表 (b)空表,85,说明 循环链表与线性链表操作的主要差别是算法中循环结束的条件； 和线性链表的差别仅在于，判别链表中最后一个结点的条件 不 再是“后继是否为空”，而是“后继是否为头结点”。 对循环链表，有时不给出头指针，而是给出尾指针,给出尾指针的循环链表,86,1、双向链表的概念,2.3.3 双向链表,(a)结点图示,存储数据元