数据结构课件：第2章线性表 (1).ppt

1、数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第5 5章章 数组和广义表数组和广义表 线性结构线性结构在数据元素的非空有限集中，有且仅有一个开在数据元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。一个直接前趋和一个直接后继。可表示为可表示为：（：

2、（a1 , a2 , , an） 线性结构的特点：线性结构的特点：（逻辑、存储（逻辑、存储和运算）和运算）数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是组等等，其中，最简单、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的见第见第2章章数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院一、教学内容一、教学内容：1 1、线性表的定义和性质及基本运算；线性表的定义和性质及基

3、本运算；2 2、 线性表的顺序存储结构线性表的顺序存储结构3 3、 线性表的链式存储结构线性表的链式存储结构4 4、 多项式的代数运算多项式的代数运算数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院二、教学要求：二、教学要求：1 1、了解线性表的逻辑结构特性，以及线性表的两种存储实现方式了解线性表的逻辑结构特性，以及线性表的两种存储实现方式2 2、熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。、熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。3 3、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法

4、的实现；实现；4 4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；实际应用中选用适当的链表结构；5 5、能够从时间和空间复杂度的角度综合比较线性表两种存储结、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合构的不同特点及其适用场合。数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院（a1, a2, ai-1，ai, ai1 ，, an）1. 线性表的定义：线性表的定义：是是n个数据元素的有限序列个数据元素的有限序列n=0时称为时称为数据元素数据元素线性起

5、点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院例例1 1 分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女 182001级电信级电信016班班2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班200101181

6、0284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表的抽象数据类型的定义：线性表的抽象数据类型的定义： ADT List 数据对象：数据对象：D=ai|aiElemset,i=1,2,n,

7、n0 数据关系：数据关系：R1=|ai-1,aiD,i=2,n 基本操作：基本操作： InitList(&l) 操作结果：构造一个空的线性表操作结果：构造一个空的线性表L DestroyList(&l) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：销毁线性表操作结果：销毁线性表L 数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 ClearList(&l) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：置线性表操作结果：置线性表L为空表为空表 ListEmpty(L) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若线性表操作结果：若线性表L

8、为空表，则返回为空表，则返回TRUE，否则返回，否则返回FALSE ListLenght(L) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：返回线性表操作结果：返回线性表L数据元素个数数据元素个数 GetElem(L,i,&e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)） 操作结果：用操作结果：用e返回线性表返回线性表L中第中第i个数据元素的值个数据元素的值数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 locatElem(L,e,comare() 初始条件：线性表已存在初始条件：线性表已存在,comare()是数据元素判

9、定函数是数据元素判定函数 操作结果：返回线性表操作结果：返回线性表L中第中第1个与个与e满足关系满足关系comare()的数的数据元素的位序据元素的位序 PriorElem(L,cur_e,&pre_e) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若操作结果：若cur_e是线性表是线性表L的数据元素，且不是第一个，的数据元素，且不是第一个，则用则用pre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义无定义 NextElem(L,cur_e,&) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若操作结果：若cur_e是线性表是线性表L的数据元

10、素，且不是第最后一的数据元素，且不是第最后一个，则用个，则用next_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义无定义数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 ListInsert(&L,i,e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)+1） 操作结果：在线性表操作结果：在线性表L中第中第i个数据元素之前插入新元素个数据元素之前插入新元素e，L长度加长度加1 ListDelete(&L,i,&e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)） 操作结果：删除

11、线性表操作结果：删除线性表L中第中第i个数据元素，用个数据元素，用e返回其值，返回其值，L长度减长度减1 ListTraverse(L,visit() 初始条件：线性表已存在初始条件：线性表已存在 操作结果：依次对线性表操作结果：依次对线性表L的每个数据元素调用的每个数据元素调用visit()函函数，一旦数，一旦visit()失败，则操作失败失败，则操作失败 ADT List数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院上述是线性表抽象数据类型的定义，其中只是一些上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。如：将两个线性表合基本操作，另外可以更复

12、杂。如：将两个线性表合并等。复杂的操作可用基本操作实现。并等。复杂的操作可用基本操作实现。例例2-12-1假设假设: :有两个集合有两个集合 A 和和 B 分别用两个线性表分别用两个线性表 LA 和和 LB 表示，表示， 现要求一个新的集合现要求一个新的集合AAB 作如下操作：作如下操作：扩大线性表扩大线性表 LA，将存在于线性表，将存在于线性表LB 中而不存在于中而不存在于线性表线性表 LA 中的数据元素插入到线性表中的数据元素插入到线性表 LA 中去。中去。数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 GetElem(Lb, i, e); / 取取Lb中第中第i个数

13、据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院例例2-2La和和Lb是按非递减有

14、序排列是按非递减有序排列,构建构建Lcvoid MergeList(List la,List lb,list &lc) IninList(lc); I=j=1;k=0; la_len=ListLength(la);lb_len=ListLength(lb);while(I=la_len&j=lb_len)GetElem(la,I,ai);GetElem(lb,j,bj);if(ai=bj)ListList(lc,+k,ai);I+;else ListInsert(lc,k+,bj);j+;数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院while(I=la_len)GetE

15、lem(la,I+,ai);ListInsert(lc,k+,ai);while(j=lb_len)GetElem(lb,j+,bj);ListInsert(lc,k+,bj);数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院时间复杂度分析时间复杂度分析假设假设GetElem和和ListInsert与表长无关与表长无关,LocateElem的执行时间与表长成正比的执行时间与表长成正比.例例2.1的时间复杂度为的时间复杂度为O(ListLength(LA) *ListLength(LB)例例2.2的时间复杂度为的时间复杂度为O(ListLength(LA)+ListLengt

16、h(LB)数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.2.1 2.2.1 顺序表的表示顺序表的表示用一组地址连续的存储单元依次用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现。存储线性表的元素，可通过数组来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表

17、示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出存放位置亦可求出（利用数组下标）（利用数组下标）。3. 计算方法是计算方法是设首元素设首元素a1的存放地址为的存放地址为LO

18、C(a1)（称称为首地址为首地址）设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L 4.可随机存取可随机存取数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1

19、Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院一个一维数组，下标的范围是到，一个一维数组，下标的范围是到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储器存储。存储器按字节编址，设存储数组元素按字节编址，设存储数组元素 的第一个的第一个字节的地址是字节的地址是，则，则 的第一个字节的的第一个字节的地址是地址是 113因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址计算通式为：地

20、址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表的顺序存储结构定义（静态）线性表的顺序存储结构定义（静态）#define MAXSIZE 100typedef struct ElemType elemMAXSIZE; int length;SqList;数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表的顺序存储结构定义线性表的顺序存储结构定义(动态动态)typedef struct SqList; #define LIST_INIT_SIZE 100 / 线性表存储空间的初

21、始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量ElemType *elem; / 存储空间基址存储空间基址int length; / 当前长度当前长度int listsize; / 当前分配的存储容量当前分配的存储容量 / (以以sizeof(ElemType)为单位为单位)数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare()

22、 / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT

23、_SIZEreturn OK;数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.2.2 2.2.2 顺序表的实现（或操作）顺序表的实现（或操作）回忆回忆：数据结构基本运算操作有：数据结构基本运算操作有：插入、删除插入、删除、查找、排序、修改查找、排序、修改数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院1)1)插入插入 在线性表的第在线性表的第i i个位置个位置前前插入插入一个元素一个元素实现步骤：实现步骤： 将第将第n至第至第i 位的元素向后移动一个位置；位的元素向后移动一个位置； 将要插入的元素写到第将要插入的元素写到第i个位置；个位置； 表长加表

24、长加1。注意：注意：事先应判断事先应判断: 插入位置插入位置i 是否合法是否合法?表是表是否已满否已满? 长度为长度为n的线性表变为长度为的线性表变为长度为n+1的线性表的线性表 （a1,a2,ai-1,ai,an）（a1,a2,ai-1,x,ai,an）数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院程序：程序：Status

25、ListInsert_sq(SqList &l,int i,elemtype x)if (il.length) return(ERROR);if(l.length=MAXSIZE) return(OVERFLOW);for(j=l.length;j=i;j-) l.elemj=l.elemj-1;l.elemj=x;l.length+;return(OK);数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院实现步骤：实现步骤： 将第将第i +1至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除

26、位置i 是否合法是否合法?3)3)删除删除 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素 使：长度为长度为n的线性表变为长度为的线性表变为长度为n-1的线性表。的线性表。（a1,a2,ai-1,ai,ai+1,an）（a1,a2,ai-1,ai+1,an）数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院Statu

27、s ListDelete_sq(Sqlist &L，int i,ElemType &e) if(iL.length) return ERROR; for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; L.length-; 数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析时间效率分析时间效率分析: 插入算法花费的时间，主要在于循环中元素的后移（其它语句插入算法花费的时间，主要在于循环中元素的后移（其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都花费的时间可以省去）

28、，即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值要后移一位，使空出的位置插入元素值x。但是，插入的位置是。但是，插入的位置是不固定的，当插入位置不固定的，当插入位置i=1时，全部元素都得移动，需时，全部元素都得移动，需n次移动，次移动，当当i=n时，不需移动元素，故在时，不需移动元素，故在i位置插入时移动次数为位置插入时移动次数为n-i+1， 删除算法花费的时间，主要在于循环中元素的前移（其它语删除算法花费的时间，主要在于循环中元素的前移（其它语句花费的时间可以省去），即从删除位置到最后位置的所有元素句花费的时间可以省去），即从删除位置到最后位置的所有元素都要前移一位都要

29、前移一位.但是，删除的位置是不固定的，当删除位置但是，删除的位置是不固定的，当删除位置i=1时，时，全部元素都得移动，需全部元素都得移动，需n-1次移动，当次移动，当i=n时，不需移动元素，故时，不需移动元素，故在在i位置删除时移动次数为位置删除时移动次数为n-i.数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院假定在表中任意位置插入、删除元素都是等概率的，假定在表中任意位置插入、删除元素都是等概率的，插入概率插入概率p(i)=1/(n+1) ，删除概率，删除概率q(i)=1/n ，则：，则：插入操作时间效率（平均移动次数）插入操作时间效率（平均移动次数） 2) 1(11)

30、 1(1111ninninpEniniiis删除操作时间效率（平均移动次数）删除操作时间效率（平均移动次数） 21)(1)(11ninninqEniniidl显然，顺序表的显然，顺序表的空间空间复杂度复杂度S(n)=O(1)S(n)=O(1)（没有占用辅助空间）（没有占用辅助空间）数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的：逻辑关系上相邻的两个元素在物理存储位置上也相邻；两个元素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素可以随机存取表中任一元素O(1)；存储；存储空间使用紧凑空间使用紧凑缺

31、点：缺点：在插入，删除某一元素时，需要移动大在插入，删除某一元素时，需要移动大量元素量元素O(n); ;预先分配空间需按最大空预先分配空间需按最大空间分配，利用不充分间分配，利用不充分; ;表容量难以扩充表容量难以扩充为克服这一缺点，我们引入另一种存储形式：为克服这一缺点，我们引入另一种存储形式：链式存储结构链式存储结构见见2.3节节数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院测一下测一下1. 在顺序表中插入或删除一个元素，需要平均移动在顺序表中插入或删除一个元素，需要平均移动 元素，元素，具体移动的元素个数与具体移动的元素个数与 有关。有关。 2. 线性表中结点的集合

32、是线性表中结点的集合是 的，结点间的关系是的，结点间的关系是 的的 3. 向一个长度为向一个长度为n的表的第的表的第i个元素个元素(1in+1)之前插入一个元素时之前插入一个元素时，需向后移动，需向后移动 个元素。个元素。 4. 向一个长度为向一个长度为n的表中删除第的表中删除第i个元素个元素(1in)时，需向前时，需向前移动移动 个元素。个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺，因此，顺序表也称为序表也称为 的数据结构。的数据结构。 6. 顺序表中逻辑上相邻的元素的物理位置顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻

33、相邻。单链表中逻辑上相邻的元素的物理位置辑上相邻的元素的物理位置 相邻。相邻。 数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院单项选择题单项选择题（ ）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：续的，称之为：（A）存储结构）存储结构 （B）逻辑结构）逻辑结构 （C）顺序存储结构）顺序存储结构 （D）链式存储结构）链式存储结构（ ）2. 一个表第一个元素的存储地址是一个表第一个元素的存储地址是100，每个元素的长度为，每个元素的长度为2，则第，则第5个个元素的地址是元素的地址是 （A）

34、110 （B）108 （C）100 （D）120（ ）3. 在在n个结点的顺序表中，算法的时间复杂度是个结点的顺序表中，算法的时间复杂度是O（1）的操作是：）的操作是： (A） 访问第访问第i个结点（个结点（1in）和求第）和求第i个结点的直接前驱（个结点的直接前驱（2in） （B） 在第在第i个结点后插入一个新结点（个结点后插入一个新结点（1in） （C )删除第删除第i个结点（个结点（1in） （D） 将将n个结点从小到大排序个结点从小到大排序（ ）4. 向一个有向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动，平均

35、要移动 个元素个元素 （A）8 （B）63.5 （C）63 （D）7 数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.3.1 链表的表示链表的表示2.3.2 链链表的实现表的实现2.3.3 链链表的运算效率分析表的运算效率分析本节小结本节小结数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.3 .1 链表的表示链表的表示特点：特点： 用一组用一组任意任意的存储单元存储线性表的数据元素的存储单元存储线性表的数据元素 利用利用指针指针实现了用不相邻的存储单元存放逻辑实现了用不相邻的存储单元存放逻辑上相邻的元素上相邻的元素 每个数据元素每个数据元素ai，

36、除存储本身信息外，还需存除存储本身信息外，还需存储其直接后继的信息储其直接后继的信息 结点结点数据域：元素本身信息数据域：元素本身信息指针域：指示直接后继的存储位置指针域：指示直接后继的存储位置数据域 指针域结点数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院ZHAOQIANSUNLIZHOUWUZHENGWANGH例例 线性表线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针数数 据据 结结 构

37、构武武 汉汉 大大 学学 测测 绘绘 学学 院院1、结点结点：数据元素的存储映像。由数据域和指针域两部分组成；数据元素的存储映像。由数据域和指针域两部分组成；2、链表链表： n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为结点只有一个指针域的链表，称为单链表单链表或或线性链表线性链表；有两个指针域的链表，称为有两个指针域的链表，称为双链表双链表；有多个指针域的链表，称为有多个指针域的

38、链表，称为多链表多链表；首尾相接的链表称为首尾相接的链表称为循环链表循环链表。a1heada2anhead循环链表示意图：循环链表示意图：数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院头指针头指针是指向链表中第一个结点（或为是指向链表中第一个结点（或为头结点头结点或或为为首元结点首元结点）的指针。）的指针。 单链表可由一个头指针唯一确定。单链表可由一个头指针唯一确定。头结点头结点是在链表的是在链表的首元结点首元结点之前之前附设附设的一个结点；的一个结点；数据域内只放空表标志和表长等信息数据域内只放空表标志和表长等信息; ;首元结点首元结点是指链表中存储线性表第一个数据元素

39、是指链表中存储线性表第一个数据元素a a1 1的结点。的结点。 头指针头指针头结点头结点 首元结点首元结点a1数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存储结构用单链表表示如下，储结构用单链表表示如下，请问其请问其头指针头指针的的值值是多少？是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO

40、737ZHENG1943ZHOU25答：答：头指针头指针是指向是指向链表中第一个结点链表中第一个结点的指针，因此关键的指针，因此关键是要寻找是要寻找第一个结第一个结点的地址。点的地址。7ZHAOH31头指针的值是头指针的值是31数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别： 无头结点无头结点 有头结点有头结点数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘

41、学学 院院答：答：讨论1. 在链表中设置头结点有什么好处？讨论2. 如何表示空表空表？头结点头结点即在链表的首元结点之前附设的一个结点，该结即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对进行操作时，可以对空表、非空表空表、非空表的情况以及对的情况以及对首元结点首元结点进行进行统一处理，编程更方便。统一处理，编程更方便。答：答：无头结点时，无头结点时，当头指针的值为空当头指针的值为空时表示空表；时表示空表；有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示

42、空表。时表示空表。头指针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院typedef struct Lnode ElemType data; /数据域数据域 struct Lnode *next; /指针域指针域Lnode, *LinkList; / *LinkList为为Lnode类型的指针类型的指针教材P28对于单链表的抽象描述:介绍三个有用的库函数（都在介绍三个有用的库函数（都在 中）：中）：sizeof(x)计算变量计算变量x的长度；的长度；malloc(m) 开辟开辟m字节长度的地址空间，并返回这段空

43、间的字节长度的地址空间，并返回这段空间的首地址；首地址；free(p) 释放指针释放指针p所指变量的存储空间，即彻底删除一个所指变量的存储空间，即彻底删除一个变量。变量。数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院2.3.2 2.3.2 链表的实现链表的实现1. 1. 单链表的建立和输出单链表的建立和输出2. 2. 单链表的修改单链表的修改3. 3. 单链表的插入单链表的插入4. 4. 单链表的删除单链表的删除5. 5. 应用举例应用举例6. 6. 其它链表形式其它链表形式数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院实例实例：用单链表结构来存放用

44、单链表结构来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z）,请写出请写出C语言程序。语言程序。难点分析难点分析：每个数据元素在内存中是每个数据元素在内存中是“零散零散”存放的，存放的，其首地址怎么找？又怎么一一链接？其首地址怎么找？又怎么一一链接？实现思路实现思路：先开辟头指针，然后陆续为每个数据元先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的素开辟存储空间并赋值，并及时将地址送给前面的指针。指针。数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院#include#includetypedef struct listc

45、har data; struct list*next; Lnode, *LinkList; Lnode *p,*q,*head; /一般需要一般需要3个指针变量个指针变量int n ; / 数据元素的个数数据元素的个数int m=sizeof(Lnode); /*结构类型定义好之后，每个结构类型定义好之后，每个变量的长度就固定了，变量的长度就固定了，m求一求一次即可次即可*/ 数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 int i;head=(LinkList)malloc(m); /m=sizeof(Lnode) 前面已求出前面已求出p=head;for(i=1;i

46、data=i+a-1; / 第一个结点值为字符第一个结点值为字符ap-next=(LinkList)malloc(m); /为后继结点开新空间！为后继结点开新空间！p=p-next； /让指针变量让指针变量P改为指向后继结点改为指向后继结点p-data=z; /最后一个元素要单独处理最后一个元素要单独处理p-next=NULL ; /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！新手特别容易忘记！新手特别容易忘记！数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院p=head;while (p-next!=NULL) /* 只要没到最后一个元只要没到最后一个元素，就

47、不停地素，就不停地“顺藤摸顺藤摸瓜瓜”输出输出*/printf(%c,p-data);p=p-next; printf(“%cn”,p-data); /别忘记输出尾结点数别忘记输出尾结点数据据讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？ sum +;数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院思路：思路：要修改第要修改第i个数据元素，关键是要先找到该结个数据元素，关键是要先找到该结点的指针点的指针p，然后用，然后用p-data=new_value 即可。难点：单链表是一种顺序存取的结构难点：单链表是一种顺序存取的结构, ,

48、单链表中想取单链表中想取得第得第i i个元素，必须从头指针出发寻找（顺藤摸瓜），个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取不能随机存取 。必须先找到第。必须先找到第 i-1 i-1 个数据元素。个数据元素。因此，查找第因此，查找第 i i 个数据元素的基本操作为：移动指个数据元素的基本操作为：移动指针，比较针，比较 j j 和和 i i 。令指针。令指针 p p 始终指向线性表中始终指向线性表中第第 j j 个数据元素。个数据元素。，数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院 Status GetElem_L(LinkList L, int i, Elem

49、Type &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p = L-next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji ) return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第

50、取得第 i i 个元素个元素return OK;数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：插入步骤（即核心语句）：Step 1Step 1：s-next=p-next;Step 2Step 2：p-next=s ；p-nexts-next元素x结点应预先生成：s=(LinkList)malloc(m);s-data=x;s-next=p-next数数 据据 结结 构构武武 汉汉 大大 学学 测测 绘绘 学学 院院Status ListInsert(LinkLis