数据结构线性表入门.ppt

2024/8/152024/8/15算法与数据结构算法与数据结构Algorithms and Data StructuresCH2 线性表线性表 +++ +++教授教授教授教授 *** ***信息技术大学信息技术大学信息技术大学信息技术大学 计算机工程学院计算机工程学院计算机工程学院计算机工程学院2.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理提纲提纲2024/8/152024/8/152 2/114/1142.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/153 3/114/114线性结构：只有一个开始结点和一个结束结点，所有结点排线性结构：只有一个开始结点和一个结束结点，所有结点排成一个线性序列成一个线性序列串、栈、队列都是线性结构串、栈、队列都是线性结构线性表线性表线性表线性表（简称为表）是零个或多个元素的有穷序列。

简称为表）是零个或多个元素的有穷序列L L = = ( (k k0 0, k, k1 1, …, k, …, kn-1n-1) )线性表的逻辑结构：线性表的逻辑结构：L L=<= >其中其中K K={ ={ k k0 0, k, k1 1, …, k, …, kn-1n-1} }，，R={|>|0≤i≤n-2 0≤i≤n-2 } }i i称为元素称为元素k ki i的的索引索引索引索引或或下标下标下标下标基本概念基本概念2024/8/152024/8/154 4/114/114表中所含元素的个数称为表的表中所含元素的个数称为表的长度长度长度长度长度为零的表称为长度为零的表称为空表空表空表空表k k0 0称为称为第一个第一个第一个第一个元素，元素，k kn-1n-1称为称为最后一个最后一个最后一个最后一个元素，元素，k ki i(0≤i≤n-2)(0≤i≤n-2)是是k ki+1i+1的的前驱前驱前驱前驱，， k ki+1i+1是是k ki i的的后继后继后继后继k k0 0只有一个后继，只有一个后继， k kn-1n-1只有一个前驱只有一个前驱2024/8/152024/8/155 5/114/114例例1 1：：大写英文字母：大写英文字母：(A, B, C, D, …, Z)(A, B, C, D, …, Z)1-101-10的整数：的整数：(1, 2, 3, 4, …, 10)(1, 2, 3, 4, …, 10)例例2 2：某院系的学生名册：某院系的学生名册学号学号姓名姓名性别性别年龄年龄专业名称专业名称…………- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0900100109001001张丰张丰男男1717信息与计算科学信息与计算科学0900100209001002刘小红刘小红 女女1818信息与计算科学信息与计算科学0900100309001003李静李静女女1818数学与金融工程数学与金融工程0900100409001004王建平王建平 男男1818数学与金融工程数学与金融工程……………………………………2024/8/152024/8/156 6/114/1142024/8/152024/8/157 7/114/114某年南方GDP排名前20的城市 同年南方GDP排名前20的城市ListList：线性表类型，：线性表类型，DataTypeDataType：元素类型，：元素类型，PositionPosition：元素的：元素的下标类型。

可说明如下下标类型可说明如下: :List list;List list;DataType x;DataType x;Position p;Position p;[ [注注] ]元素的类型与讨论无关元素的类型与讨论无关抽象数据类型抽象数据类型(ADT)2024/8/152024/8/158 8/114/114线性表的抽象数据类型线性表的抽象数据类型(ADT)(ADT)ADTADT List List isisoperationsoperationsList List createNullListcreateNullList ( void ) ( void )// //创建并且返回一个空线性表创建并且返回一个空线性表int int insertPreinsertPre (List list, position p, DataType x) (List list, position p, DataType x)// //在在listlist中中p p位置前插入值为位置前插入值为x x的元素，并返回插入成功与否的标志的元素，并返回插入成功与否的标志int int insertPostinsertPost (List list, position p, DataType x) (List list, position p, DataType x)// //在在listlist中中p p位置后插入值为位置后插入值为x x的元素，并返回插入成功与否的标志的元素，并返回插入成功与否的标志int int deleteVdeleteV (List list, DataType x) (List list, DataType x)// //在在listlist中删除一个值为中删除一个值为x x的元素，并返回插入成功与否的标志的元素，并返回插入成功与否的标志2024/8/152024/8/159 9/114/114int int deletePdeleteP (List list, position p) (List list, position p)// //在在listlist中删除位置为中删除位置为p p的元素，并返回插入成功与否的标志。

的元素，并返回插入成功与否的标志Position Position locatelocate (List list, DataType x) (List list, DataType x)// //在在listlist中查找值为中查找值为x x的元素的位置的元素的位置int int isNullisNull (List list) (List list)// //判别判别listlist是否为空线性表是否为空线性表end ADTend ADT List List2024/8/152024/8/151010/114/1142.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/151111/114/114线性表最简单的存储方法是采用顺序方式，称作线性表的线性表最简单的存储方法是采用顺序方式，称作线性表的顺顺顺顺序表示序表示序表示序表示，通常可称此时的线性表为，通常可称此时的线性表为顺序表顺序表顺序表顺序表具体做法是：将线性表中的元素一个接一个地存储在一片具体做法是：将线性表中的元素一个接一个地存储在一片相相邻的存储区域邻的存储区域中。

线性表的顺序存储结构是一种可以中线性表的顺序存储结构是一种可以随机存随机存随机存随机存取取取取的存储结构的存储结构2024/8/152024/8/151212/114/114假设每个元素占用假设每个元素占用c c个存储单元，则下标为个存储单元，则下标为i+1i+1的元素的存储的元素的存储位置与下标为位置与下标为i i的元素的存储位置之间，满足下列关系：的元素的存储位置之间，满足下列关系：loc(kloc(ki i+1) = loc(k+1) = loc(ki i) + c) + c通常把顺序表中通常把顺序表中k k0 0的存储位置的存储位置loc(kloc(k0 0) )，称为线性表的，称为线性表的首地址首地址首地址首地址或或基地址基地址基地址基地址，下标为，下标为i i的元素的元素ki ki的存储位置为：的存储位置为：loc(kloc(ki i) = loc(k) = loc(k0 0) + i * c) + i * c存储结构存储结构2024/8/152024/8/151313/114/1142024/8/152024/8/151414/114/114顺序表定义顺序表定义(C(C语言语言) )：：2024/8/152024/8/151515/114/114#define MAXNUM 100DataType element[MAXNUM];#define MAXNUM 100int n; /* 存放线性表中元素的个n ≤ MAXNUM*/ DataType *element; /* element[0],element[1]，…，element[n- 1]存放线性表中的元素 */设设palistpalist是一个指向是一个指向SeqListSeqList类型的指针变量，则：类型的指针变量，则：palist->MAXNUMpalist->MAXNUM：顺序表中最大元素的个数；：顺序表中最大元素的个数；palist->npalist->n：顺序表中实际元素的个数；：顺序表中实际元素的个数；palist->element[0] palist->element[0] ，，……，，palist->element[palist->n - 1]palist->element[palist->n - 1]：顺序表：顺序表中的各个元素。

中的各个元素2024/8/152024/8/151616/114/114struct SeqList { int MAXNUM; /*顺序表中最大元素的个数*/ int n; /* 存放线性表中元素的个n ≤ MAXNUM*/ DataType *element; /* element[0],element[1]，…，element[n- 1]存放线性表中的元素 */};typedef struct SeqList *PSeqList; 1. 1. 创建一个空顺序表创建一个空顺序表 PSeqList PSeqList createNullList_seqcreateNullList_seq(int m)(int m)分配顺序表空间分配顺序表空间(PSeqList) malloc(sizeof(struct SeqList))(PSeqList) malloc(sizeof(struct SeqList))为顺序表分配数组空间，大小为为顺序表分配数组空间，大小为mm(DataType *) malloc(sizeof(DataType)*m)(DataType *) malloc(sizeof(DataType)*m)MAXNUMMAXNUM置为置为mm，， n n置为置为0 0[ [说明说明] ]mallocmalloc：在内存的动态存储区域中分配一个长度为：在内存的动态存储区域中分配一个长度为sizesize的连续空的连续空间间. .如果未成功，返回空指针如果未成功，返回空指针NULL.NULL.freefree：释放由：释放由p p指向的内存区指向的内存区运算的实现运算的实现2024/8/152024/8/151717/114/1142024/8/152024/8/151818/114/114PSeqList createNullList_seq(int m) {/*创建新的顺序表*/ PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList)); if (palist!=NULL) { palist->element = (DataType*)malloc(sizeof(DataType)*m); if (palist->element) { palist->MAXNUM=m; palist ->n = 0; /*空表长度为0*/ return (palist); } else free (palist); } printf("Out of space!!!\n"); /*存储分配失败*/ return NULL;}2. 2. 判断线性表是否为空判断线性表是否为空 int isNullList_seq(PSeqList palist ) int isNullList_seq(PSeqList palist ) 判断判断palistpalist的的n n字段是否为字段是否为0 0即可即可2024/8/152024/8/151919/114/114int isNullList_seq(PSeqList palist) {/*判别palist所指顺序表是否为空表*/ return ( palist->n == 0 );} 3. 3. 求某元素位置求某元素位置 int locate_seq(PSeqList palist, DataType x)int locate_seq(PSeqList palist, DataType x)x x与表中元素依次，相同则返回下标与表中元素依次，相同则返回下标若表中没有若表中没有x x，则返回，则返回-1-12024/8/152024/8/152020/114/114int locate_seq(PSeqList palist, DataType x) {/* 求x在palist所指顺序表中的下标*/ int q; for ( q=0; qn ; q++) if ( palist->element[q] == x) return (q); return -1;}4. 4. 顺序表的元素插入顺序表的元素插入int insertPre_seq(PSeqList palist, int p, DataType x)int insertPre_seq(PSeqList palist, int p, DataType x)在下标为在下标为p-1p-1与下标为与下标为p p的元素之间插入一个新的元素的元素之间插入一个新的元素x x1) 1) 溢出检测：溢出检测： palist->n < palist->MAXNUM palist->n < palist->MAXNUM2) p2) p的有效性：的有效性：0≤p≤palist->n0≤p≤palist->n3) 3) 下标为下标为n~pn~p的元素依次后移一位的元素依次后移一位2024/8/152024/8/152121/114/1142024/8/152024/8/152222/114/1142024/8/152024/8/152323/114/114int insertPre_seq(PSeqList palist, int p, DataType x) {/*在palist所指顺序表中下标为p的元素之前插入元素x */ int q; if ( palist->n >= palist-> MAXNUM) { /*溢出*/ printf("Overflow! \n"); return 0; } if (p<0 || p>palist->n) { /*不存在下标为p的元素*/ printf("Not exist! \n"); return 0; } for(q=palist->n - 1; q>=p; q--) /*插入位置及之后的元素均后移一个位置*/ palist->element[q+1] = palist->element[q]; palist->element[p] = x; /*插入元素x*/ palist->n = palist->n + 1; /*元素个数加1*/ return 1;}同样的：同样的： int insertPost_seq(PSeqList palist, int p, DataType x) int insertPost_seq(PSeqList palist, int p, DataType x)2024/8/152024/8/152424/114/1145. 5. 顺序表中删除元素顺序表中删除元素( (按下标按下标) ) int deleteP_seq(PSeqList palist, int p)int deleteP_seq(PSeqList palist, int p)检查检查p p的有效性的有效性下标为下标为p+1~palist->n – 1p+1~palist->n – 1的元素依次前移一位的元素依次前移一位2024/8/152024/8/152525/114/1142024/8/152024/8/152626/114/1142024/8/152024/8/152727/114/114a1a2aiai+1ana1a2ai+1anai+22024/8/152024/8/152828/114/114int deleteP_seq(PSeqList palist, int p) {/*在palist所指顺序表中删除下标为ｐ的元素*/ int q; if (p<0 || p>palist->n-1) { /*不存在下标为p的元素*/ printf("Not exist!\n"); return 0; } for(q=p; qn-1; q++) /*被删除元素之后的元素均前移一个位置*/ palist->element[q] = palist->element[q+1]; palist->n = palist->n - 1; /*元素个数减1*/ return 1;}6. 6. 顺序表中按值删除元素顺序表中按值删除元素 int deleteV_seq(PSeqList palist, DataType x) int deleteV_seq(PSeqList palist, DataType x) 1) 1) 定位定位x x的位置：的位置：locate_seqlocate_seq2) 2) 删除该位置的元素删除该位置的元素( (参考参考deleteP_seqdeleteP_seq) )代码：略代码：略2024/8/152024/8/152929/114/1141. 1. 删除算法的时间复杂性删除算法的时间复杂性即：估算顺序表删除运算中的即：估算顺序表删除运算中的平均移动元素个数平均移动元素个数平均移动元素个数平均移动元素个数设设P Pi i是在下标为是在下标为i i的位置上删除元素的概率的位置上删除元素的概率删除下标为删除下标为i( i(第第i+1i+1个个) )的元素需要移动的元素需要移动n-i-1n-i-1个元素个元素于是，删除的平均移动数为：于是，删除的平均移动数为：若有若有P Pi i=1/n=1/n，则有：，则有：分析与评价分析与评价2024/8/152024/8/153030/114/1142. 2. 插入算法的时间复杂性插入算法的时间复杂性设设P Pi i' '是在下标为是在下标为i i的位置之前插入元素的概率的位置之前插入元素的概率在下标为在下标为i i的元素之前插入元素需要移动的元素之前插入元素需要移动n-in-i个元素个元素于是，删除的平均移动数为：于是，删除的平均移动数为：若有若有P Pi i'=1/(n+1)'=1/(n+1)，则有：，则有：2024/8/152024/8/153131/114/114因此，删除和插入算法的时间复杂度为：T(n)=O(n)观察插入算法：观察插入算法：如何补救？如何补救？重新申请一个比较大（如原数组大小重新申请一个比较大（如原数组大小* *2 2）的数组，以代替原来的）的数组，以代替原来的数组数组顺序表空间的扩展顺序表空间的扩展2024/8/152024/8/153232/114/114int insertPre_seq(PSeqList palist, int p, DataType x) { … … if ( palist->n >= palist-> MAXNUM) { /*溢出*/ printf("Overflow! \n"); return 0; } … …}可用以下代码代替插入算法中的相应代码可用以下代码代替插入算法中的相应代码2024/8/152024/8/153333/114/114pos1 = (DataType*)malloc(sizeof(DataType)*palist->MAXNUM*2);if (pos1==NULL){ printf("Overflow"); return 0; }for (q=0, q< palist->MAXNUM, q++) pos1[q]=palist->element[q];free(palist->element);palist->element =pos1;palist->MAXNUM *=2;(1) (1) 假设有两个集合假设有两个集合A A和和B B分别用两个线性表来表示分别用两个线性表来表示palistpalist和和pblistpblist（线性表中的数据元素即为集合的元素）。

现在要求一（线性表中的数据元素即为集合的元素）现在要求一个新集合个新集合A=AUBA=AUB思路：思路：从线性表从线性表B B中依次取得每个元素：中依次取得每个元素：retrieve_seq(pblist, p) retrieve_seq(pblist, p)  x x性表性表A A中查找中查找x x：：locate_seq(palist, x )locate_seq(palist, x )若不存在则插入到表最后：若不存在则插入到表最后：insertPost_seq( palist, palist->n-1, x )insertPost_seq( palist, palist->n-1, x )思考：线性表应用举例思考：线性表应用举例2024/8/152024/8/153434/114/114(2)(2) 求顺序表中第一个值为求顺序表中第一个值为x x的元素的前驱和后继的位置的元素的前驱和后继的位置(3) (3) 合并有序合并有序( (非递减顺序非递减顺序) )线性表线性表A A和和B B，合并后的线性表，合并后的线性表C C也也具有同样的特性具有同样的特性2024/8/152024/8/153535/114/114优点：优点：逻辑相邻，物理相邻逻辑相邻，物理相邻存储空间使用紧凑存储空间使用紧凑可随机存取任一元素可随机存取任一元素缺点：缺点：插入、删除操作需要移动大量的元素插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分预先分配空间需按最大空间分配，利用不充分表容量难以扩充表容量难以扩充小结：线性表示的优缺点小结：线性表示的优缺点2024/8/152024/8/153636/114/1142.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/153737/114/114特点：特点：逻辑相邻但物理不相邻逻辑相邻但物理不相邻增加指针来指示其后继增加指针来指示其后继链接表示链接表示2024/8/152024/8/153838/114/114每个节点有两个域：每个节点有两个域：数据域数据域(info)(info)：数据元素本身的信息：数据元素本身的信息指针域指针域(link)(link)：后继结点的存储位置：后继结点的存储位置最后一个元素没有后继，其指针为空最后一个元素没有后继，其指针为空设一线性表有设一线性表有n n个元素，则此个元素，则此n n个结点就通过指针链接成一个个结点就通过指针链接成一个链表链表链表链表，由于每个结点只有一个指针域，故又称为，由于每个结点只有一个指针域，故又称为单链表单链表单链表单链表。

指指向链表中第一个结点的指针称为向链表中第一个结点的指针称为头指针头指针头指针头指针单链表表示单链表表示2024/8/152024/8/153939/114/1142024/8/152024/8/154040/114/114结点类型和单链表类型定义：结点类型和单链表类型定义：[ [说明说明] PNode] PNode与与LinkListLinkList实为同一类型，既可以是指向某一结点的实为同一类型，既可以是指向某一结点的指针类型，也可以看成单链表的类型指针类型，也可以看成单链表的类型( (即头指针的类型即头指针的类型) )2024/8/152024/8/154141/114/114struct Node; /*单链表结点类型*/typedef struct Node * PNode; /*结点指针类型*/struct Node { /*单链表结点结构*/ DataType info; PNode link;};typedef struct Node * LinkList; /*单链表类型*/ struct Node { DataType info; Node link;};2024/8/152024/8/154242/114/114头结点：头结点：infoinfo字段一般存放与整个链表相关的信息（如元素个数等）字段一般存放与整个链表相关的信息（如元素个数等）linklink字段指向第一个结点字段指向第一个结点头结点的引入头结点的引入增加了额外的空间增加了额外的空间使得对于第一个结点的处理（如插入、删除等）与其它结点的处使得对于第一个结点的处理（如插入、删除等）与其它结点的处理一致起来理一致起来2024/8/152024/8/154343/114/1141. 1. 创建空链表创建空链表 LinkList createNullList_link(void)LinkList createNullList_link(void)为单链表的头结点申请空间，若成功则返回单链表为单链表的头结点申请空间，若成功则返回单链表单链表运算的实现单链表运算的实现2024/8/152024/8/154444/114/114LinkList createNullList_link(void) {/*创建一个带头结点的空链表*/ /*申请表头结点空间*/ LinkList llist = (LinkList)malloc( sizeof( struct Node)); if (llist != NULL) llist->link = NULL; else printf("Out of space! \n"); /*创建失败*/ return (llist);}2. 2. 判断单链表是否为空判断单链表是否为空 int isNullList_link(LinkList llist) int isNullList_link(LinkList llist) 只要检查头结点的指针只要检查头结点的指针(llist->link)(llist->link)是否为空。

是否为空 2024/8/152024/8/154545/114/114int isNullList_link( LinkList llist) {/*判断带有头结点的单链表llist是否是空链表*/ return (llist->link == NULL);} 3. 3. 在单链表中求某元素的存储位置在单链表中求某元素的存储位置 Pnode locate_link(LinkList llist, DataType x)Pnode locate_link(LinkList llist, DataType x)在带头结点的单链表在带头结点的单链表llistllist中求第一个值为中求第一个值为x x的结点的存储位置的结点的存储位置依次查找、对比，若找不到则返回依次查找、对比，若找不到则返回NULLNULL2024/8/152024/8/154646/114/114PNode locate_link(LinkList llist, DataType x) {/*在llist带有头结点的单链表中找第一个值为x的结点存储位置*/ PNode p; if (llist==NULL) return(NULL); p = llist->link; while( p != NULL && p->info != x) p = p->link; return (p);}4. 4. 在某结点后插入新节点在某结点后插入新节点int insertPost_link(LinkList llist, PNode p, DataType x)int insertPost_link(LinkList llist, PNode p, DataType x)在结点在结点p p后面插入值为ｘ的新结点后面插入值为ｘ的新结点2024/8/152024/8/154747/114/114pabxq(1) q->link=p->link;(2) p->link=q;注意：注意：(1)、、(2)顺序不能反！顺序不能反！2024/8/152024/8/154848/114/114int insertPost_link(LinkList llist, PNode p, DataType x) {/*在llist带头结点的单链表中,p所指结点后面插入元素x */ PNode q = (PNode)malloc(sizeof( struct Node)); /*申请新结点*/ if ( q == NULL ) { printf("Out of space!!!\n"); return(0); } else { q->info = x; q->link = p->link; p->link = q; return(1); }} 5. 5. 在某结点前插入新节点在某结点前插入新节点int insertPre_link(LinkList llist, PNode p, DataType x)int insertPre_link(LinkList llist, PNode p, DataType x)在结点在结点p p前面插入值为ｘ的新结点前面插入值为ｘ的新结点1) 1) 先找到结点先找到结点p p的前驱的前驱( (locatePre_linklocatePre_link) )2) 2) 在在p p的前驱之后插入新结点的前驱之后插入新结点2024/8/152024/8/154949/114/1142024/8/152024/8/155050/114/114PNode locatePre_link(LinkList llist, PNode p) {/*在单链表中求p所指结点的前驱结点*/ PNode p1; if (llist==NULL) return(NULL); p1 = llist; while( p1 != NULL && p1->link != p ) p1 = p1->link; return (p1);} 6.6.单链表中按值删除元素单链表中按值删除元素 int deleteV_link(LinkList llist, DataType x)int deleteV_link(LinkList llist, DataType x)删除第一个元素值为删除第一个元素值为x x的结点，并返回删除成功与否的标志的结点，并返回删除成功与否的标志从第一个结点开始查找第一个元素值为从第一个结点开始查找第一个元素值为x x的结点的结点删除该结点删除该结点( (修改指针修改指针) )需记录其前驱结点需记录其前驱结点2024/8/152024/8/155151/114/114pabcp->link=p->link->link;2024/8/152024/8/155252/114/114int deleteV_link( LinkList llist, DataType x ) {/*在llist带有头结点的单链表中删除第一个值为x的结点*/ PNode p, q; p = llist; if (p==NULL) return(0); while ( p->link != NULL && p->link->info != x ) p = p->link; /*找值为x的结点的前驱结点的存储位置*/ if ( p->link == NULL ) { /*没找到值为x的结点*/ printf("Not exist!\n"); return 1; } else { q = p->link; /*找到值为x的结点*/ p->link = q->link; /*删除该结点*/ free( q ); return 1; }} 7. 7. 单链表中按位置删除元素单链表中按位置删除元素 int deleteP_link(LinkList llist, PNode p) int deleteP_link(LinkList llist, PNode p) 删除链表中的结点删除链表中的结点p p ，并返回删除成功与否的标志。

并返回删除成功与否的标志先调用先调用locatePre_link(llist, p )locatePre_link(llist, p )找到找到p p所指结点的前驱结点所指结点的前驱结点然后实现结点删除然后实现结点删除 2024/8/152024/8/155353/114/114单链表单链表(n(n个结点个结点) )的结点查找的结点查找最坏情况下要查找最坏情况下要查找n n个结点，平均情况下需要查找个结点，平均情况下需要查找n/2n/2个结点，因个结点，因此时间复杂度为此时间复杂度为O(n)O(n)其它操作的时间复杂度？其它操作的时间复杂度？分析与比较分析与比较2024/8/152024/8/155454/114/114优点优点: :不要预先按最大的需要分配连续空间；不要预先按最大的需要分配连续空间；线性表的插入和删除只需修改指针域，而不需移动其他元素线性表的插入和删除只需修改指针域，而不需移动其他元素缺点：缺点：每个结点中的指针域需额外占用存储空间，存储密度小；每个结点中的指针域需额外占用存储空间，存储密度小；链式存储结构是一种非随机存储结构，查找任一结点都要从头指链式存储结构是一种非随机存储结构，查找任一结点都要从头指针开始，沿指针域一个一个地搜索，这增加了有些算法的时间代针开始，沿指针域一个一个地搜索，这增加了有些算法的时间代价。

价小结：链接表示的优缺点小结：链接表示的优缺点2024/8/152024/8/155555/114/1141. 1. 循环链表循环链表单链表：最后一个结点的指针为单链表：最后一个结点的指针为NULLNULL循环链表：最后一个结点的指针指向头一个结点循环链表：最后一个结点的指针指向头一个结点优点：从循环链表中任一结点出发，都能访问遍所有结点优点：从循环链表中任一结点出发，都能访问遍所有结点单链表的改进和扩充单链表的改进和扩充2024/8/152024/8/155656/114/1142. 2. 双链表双链表单链表：找到某结点的前驱比较困难单链表：找到某结点的前驱比较困难双链表：每个结点有两个指针域：一个指向前驱，一个指向后继双链表：每个结点有两个指针域：一个指向前驱，一个指向后继2024/8/152024/8/155757/114/1142. 2. 双链表双链表 – cont.– cont.双链表及其结点的定义：双链表及其结点的定义：2024/8/152024/8/155858/114/114struct DoubleNode; /*双链表结点*/typedef struct DoubleNode * PDoubleNode; /*结点指针类型*/struct DoubleNode { /*双链表结点结构*/ DataType info; PDoubleNode llink, rlink; };struct DoubleList { /*双链表类型*/ PDoubleNode head; /*指向第一个结点*/ PDoubleNode rear; /*指向最后一个结点*/}; 2. 2. 双链表双链表 – cont.– cont.双链表中，删除指针变量双链表中，删除指针变量p p所指的结点：所指的结点：p->llink->rlink = p->rlink;p->llink->rlink = p->rlink;p->rlink->llink = p->llink;p->rlink->llink = p->llink;free(p);free(p);2024/8/152024/8/155959/114/1142. 2. 双链表双链表 – cont.– cont.双链表中，在双链表中，在p p所指结点后插入一个新结点：所指结点后插入一个新结点：q = (PDoubleNode)malloc(sizeof(struct DoubleNode));q = (PDoubleNode)malloc(sizeof(struct DoubleNode));q->llink = p;q->llink = p;q->rlink = p->rlink;q->rlink = p->rlink;p->rlink->llink = q;p->rlink->llink = q;p->rlink = q;p->rlink = q;2024/8/152024/8/156060/114/1143. 3. 循环双链表循环双链表双链表双链表+ +循环链表循环链表头结点由头指针头结点由头指针cdlistcdlist指出，并链接在头结点和尾结点之间指出，并链接在头结点和尾结点之间2024/8/152024/8/156161/114/1142.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/156262/114/114问题描述：问题描述：设有设有n n个人围坐在一个圆桌周围，现从第个人围坐在一个圆桌周围，现从第s s个人开始报数，数到第个人开始报数，数到第mm的人出列，然后从出列的下一个人重新开始报数，数到第的人出列，然后从出列的下一个人重新开始报数，数到第mm的人的人又出列，又出列，……，如此反复直到所有的人全部出列为止。

如此反复直到所有的人全部出列为止JosephusJosephus问题：问题：对于任意给定的对于任意给定的n, sn, s和和mm，求出按出列次序得到的，求出按出列次序得到的n n个人员的个人员的序列序列Josephus问题问题2024/8/152024/8/156363/114/1142024/8/152024/8/156464/114/114以以n=8n=8，，s=1s=1，，m=4m=4为例为例(a) n4(b) n4n8(c) n4n8n5(d) n4n8n5n22024/8/152024/8/156565/114/114(e) n4n8n5n2n1(f) n4n8n5n2n1n3(g) n4n8n5n2n1n3n7(h) n4n8n5n2n1n3n7n6求解求解JosephusJosephus问题的一般步骤：问题的一般步骤：(1) (1) 利用线性表的一些运算利用线性表的一些运算构造构造JosephusJosephus表表; ;如：创建空线性表、插入元素等如：创建空线性表、插入元素等(2) (2) 从从JosephusJosephus表中的第表中的第s s个结点开始个结点开始寻找、输出和删除寻找、输出和删除表中的第表中的第mm个结点，然后再从该结点后的下一结点开始寻找、输出和删除个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第表中的第mm个结点，重复此过程，直到个结点，重复此过程，直到JosephusJosephus表中的所有元素表中的所有元素都删除。

都删除2024/8/152024/8/156666/114/114主要步骤：主要步骤：(1) (1) 将整数序列将整数序列(1(1，，2 2，，3 3，，……，，n)n)存储在一个存储在一个palistpalist所指顺序表中所指顺序表中用整数用整数i i来代替来代替n ni i(2) (2) 最初从第最初从第s s个人开始个人开始( (即即palist->element[s-1])palist->element[s-1])，则第一个报数出，则第一个报数出列的元素编号应为：列的元素编号应为： (s-1+m-1) % n( (s-1+m-1) % n(设该编号为设该编号为i) i)是否是否s ≤ ns ≤ n对程序并不影响对程序并不影响(3) (3) 输出元素输出元素palist->element[i]palist->element[i]，并将该元素从顺序表中删除，并将该元素从顺序表中删除(4) (4) 继续在新的顺序表中进行以上继续在新的顺序表中进行以上(2)(2)、、(3)(3)操作，直至顺序表为空操作，直至顺序表为空为止为止相关代码：相关代码：采用顺序表模拟采用顺序表模拟2024/8/152024/8/156767/114/1142024/8/152024/8/156868/114/114#include #include #include "SeqList.h“void josephus_seq(PSeqList palist, int s, int m) { int s1, i, w; s1 = s - 1; for(i = palist->n; i>0; i--) { /*找出列的元素*/ s1 = (s1 + m - 1) % i ; w = palist->element[s1]; /*求下标为s1的元素的值*/ printf("Out element %d \n", w); /*元素出列*/ deleteP_seq(palist,s1); /*删除出列的元素*/ }}2024/8/152024/8/156969/114/114void main() { int i, n, s, m; printf("\n please input the values(<100) of n = "); scanf("%d",&n); printf(" please input the values of s = "); scanf("%d",&s); printf(" please input the values of m = "); scanf("%d",&m); PSeqList jos_alist=createNullList_seq( n ); /*创建空顺序表*/ if (jos_alist!=NULL) { for( i = 0; i < n; i++ ) /*线性表赋值*/ insertPre_seq( jos_alist, i, i+1 ); josephus_seq(jos_alist,s,m); free(jos_alist->element); free(jos_alist); }}主要步骤：主要步骤：(1) (1) 将整数序列将整数序列(1(1，，2 2，，3 3，，……，，n)n)存储在一个循环单链表中存储在一个循环单链表中init_clinkinit_clink函数：函数：建立一个头指针为建立一个头指针为jos_clistjos_clist的的JosephusJosephus循环单链表循环单链表(2) (2) 在循环单链表中的第在循环单链表中的第s s个结点开始寻找、反复输出和删除其中个结点开始寻找、反复输出和删除其中的第的第mm个结点个结点( (由由josephus_clistjosephus_clist函数实现函数实现) )其主要步骤为：其主要步骤为：(a) (a) 找找jos_clistjos_clist所指的循环单链表中的第所指的循环单链表中的第s s个结点放在指针变量个结点放在指针变量p p中中; ;(b) (b) 从从p p所指结点开始计数寻找第所指结点开始计数寻找第mm个结点个结点; ;(c) (c) 输出该结点的元素值输出该结点的元素值; ;(d) (d) 删除该结点，并将该结点的下一个结点放在指针变量删除该结点，并将该结点的下一个结点放在指针变量p p中，转中，转去执行去执行(b)(b)，直到所有结点被删除为止，直到所有结点被删除为止. .采用循环链表模拟采用循环链表模拟2024/8/152024/8/157070/114/1142024/8/152024/8/157171/114/114#include #include #include "LinkList.h"#define FALSE 0#define TRUE 1int init_clist(PLinkList pclist, int n) {/*用1, …, n为*pclist所示的循环表初始化*/ PNode p, q; int i; q = (PNode)malloc(sizeof(struct Node)); if (q == NULL) return (FALSE); *pclist=q; q->info = 1; q->link = q; if (n==1) return (TRUE); for(i=2;iinfo=i; p->link=q->link; q->link=p; q=p; } return (TRUE);}2024/8/152024/8/157272/114/114void josephus_clist( PLinkList pclist, int s, int m) { PNode p,pre; int i; p=*pclist; /*找第s个元素*/ if (s==1) { pre =p; p=p->link; while (p!=*pclist) { pre =p; p=p->link; } } else for(i=1;ilink; } /*当链表中结点个数大于1时*/ while (p!=p->link) { /*找第m个结点*/ for (i=1;ilink; } /*输出该结点*/ printf(" out element: %d \n", p->info); if (*pclist ==p) *pclist =p->link; pre->link = p->link; /*删除该结点*/ free(p); p = pre->link; } /*输出最后一个结点*/ printf(" out element: %d \n",p->info); *pclist=NULL; free(p);}2024/8/152024/8/157373/114/114void main() { LinkList jos_clist; int n, s, m; /*输入所需各参数的值*/ do { printf("\n please input the values of n = "); scanf("%d",&n); } while (n<1); do { printf(" please input the values of s = "); scanf("%d",&s); } while (s<1); do { printf(" please input the values of m = "); scanf("%d",&m); } while (m<1); if (init_clist(&jos_clist,n)) josephus_clist(&jos_clist,s,m); else printf("Out of space!\n");}2.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/157474/114/114矩阵作为一种线性表的推广矩阵作为一种线性表的推广在矩阵的逻辑结构在矩阵的逻辑结构(K, R)(K, R)中，可以定义中，可以定义K K是一个线性表的集合，是一个线性表的集合，R R是是K K上的一个线性关系。

上的一个线性关系矩阵可看做是线性表的线性表矩阵可看做是线性表的线性表矩阵矩阵2024/8/152024/8/157575/114/1141. 1. 行优先顺序行优先顺序即元素按行向量顺序排列，第即元素按行向量顺序排列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个行向量后面个行向量后面矩阵矩阵A Am*nm*n中元素的排列顺序是：中元素的排列顺序是：a a0 00 0, a, a0 10 1, …, a, …, a0 n-10 n-1, a, a1 01 0, a, a1 11 1, …, a, …, a1 n-11 n-1, ……, a, ……, am-1 0m-1 0, a, am-1 1m-1 1, …, a, …, am-1 n-1m-1 n-1其地址计算公式为（假设每个元素占一个单元）：其地址计算公式为（假设每个元素占一个单元）：Loc(aLoc(aij ij) ) = loc(a= loc(a0000) + i*n + j) + i*n + j2. 2. 列优先顺序列优先顺序即元素按列向量顺序排列，第即元素按列向量顺序排列，第j+1j+1个列向量紧接在第个列向量紧接在第j j个列向量后面个列向量后面矩阵矩阵A Am*nm*n中元素的排列顺序是：中元素的排列顺序是：a a0 00 0, a, a1 01 0, …, a, …, am-1 0m-1 0, a, a0 10 1, a, a1 11 1, …, a, …, am-1 1m-1 1, ……, a, ……, a0 n-10 n-1, a, a1 n-11 n-1, …, a, …, am-1 n-1m-1 n-1其地址计算公式为：其地址计算公式为：Loc(aLoc(aij ij) ) = loc(a= loc(a0000) + j*m + i) + j*m + i矩阵的顺序表示矩阵的顺序表示2024/8/152024/8/157676/114/114按行优先按行优先按行优先按行优先顺序存储，其地址计算公式为（以下都假设每个元顺序存储，其地址计算公式为（以下都假设每个元素占一个单元）：素占一个单元）：Loc(aLoc(aij ij) ) = loc(a= loc(a0000) + i*n + j) + i*n + j按列优先按列优先按列优先按列优先顺序存储，其地址计算公式为：顺序存储，其地址计算公式为：Loc(aLoc(aij ij) ) = loc(a= loc(a0000) + j*m + i) + j*m + i矩阵的顺序表示的特点：矩阵的顺序表示的特点：存储密度很高，存取的速度很快。

存储密度很高，存取的速度很快2024/8/152024/8/157777/114/114对于某些特殊情况，可以改进考虑考虑n×nn×n的的下三角矩阵下三角矩阵A A：：因为所有因为所有i

阵元素的优点存储稀疏矩阵的方法是多种多样的，下面介绍其中几种：存储稀疏矩阵的方法是多种多样的，下面介绍其中几种：(1) (1) 三元组表示法三元组表示法 (2) (2) 伪地址表示法伪地址表示法 (3) (3) 带辅助行向量的二元组表示法带辅助行向量的二元组表示法(4) (4) 行行- -列表示法列表示法稀疏矩阵的表示方法稀疏矩阵的表示方法2024/8/152024/8/157979/114/114(1) (1) 三元组表示法三元组表示法 这个方法用一个数组（顺序结构）来表示稀疏矩阵这个数组中这个方法用一个数组（顺序结构）来表示稀疏矩阵这个数组中只存放稀疏矩阵的非零元素每个结点包括只存放稀疏矩阵的非零元素每个结点包括3 3个字段，分别为该非个字段，分别为该非零元素的行下标、列下标和值结点间的顺序按矩阵的行优先顺零元素的行下标、列下标和值结点间的顺序按矩阵的行优先顺序排列（跳过非零元素）序排列（跳过非零元素） 设行下标和列下标也占一个存储单元，那么这种方法需要设行下标和列下标也占一个存储单元，那么这种方法需要3k3k个存个存储单元储单元 2024/8/152024/8/158080/114/1142024/8/152024/8/158181/114/114对于矩阵X：其稀疏矩阵的三元组表示为： 行下标行下标行下标行下标 列下标列下标列下标列下标 值值值值 0 0 0 150 0 0 15 1 0 3 22 1 0 3 22 2 0 5 -15 2 0 5 -15 3 1 1 11 3 1 1 11 4 1 2 3 4 1 2 3 5 2 3 -6 5 2 3 -6 6 4 0 91 6 4 0 91 7 5 2 28 7 5 2 28分析分析设行下标和列下标也占一个存储单元，那么这种方法需要３ｋ个设行下标和列下标也占一个存储单元，那么这种方法需要３ｋ个存储单元（ｋ为非零元素个数，在上面的例子中存储单元（ｋ为非零元素个数，在上面的例子中k=8k=8）。

因为是顺序存储，行下标和列下标又是递增排列的，可以因为是顺序存储，行下标和列下标又是递增排列的，可以( (把把ij ij连连接成为一个整数，作为关键码接成为一个整数，作为关键码) )用二分法检索，查找一个矩阵元素用二分法检索，查找一个矩阵元素的时间为Ｏ的时间为Ｏ(log2k)(log2k)（关于二分法检索的算法，将在第（关于二分法检索的算法，将在第6 6章中介绍）章中介绍）这种表示的缺点是修改不便若矩阵元素的值发生变化，一个原这种表示的缺点是修改不便若矩阵元素的值发生变化，一个原来值为零的元素现在变成非零，就要往表里插入结点为了保持来值为零的元素现在变成非零，就要往表里插入结点为了保持表示的行优先顺序，以便进行二分法检索，那么插入时就必须在表示的行优先顺序，以便进行二分法检索，那么插入时就必须在存储器里移动所有后面的元素存储器里移动所有后面的元素 2024/8/152024/8/158282/114/114(2) (2) 伪地址表示法伪地址表示法 元素的伪地址就是元素在矩阵里按行优先顺序的相对位置（包括元素的伪地址就是元素在矩阵里按行优先顺序的相对位置（包括零元素一起算）伪地址法和三元组法相似，只是数组的每个结零元素一起算）。

伪地址法和三元组法相似，只是数组的每个结点只包括两个字段，分别为矩阵非零元素的伪地址和值点只包括两个字段，分别为矩阵非零元素的伪地址和值这种方法需用这种方法需用2k2k个存储单元，比三元组法要节省，它付出的代价个存储单元，比三元组法要节省，它付出的代价是计算伪地址，而伪地址是很好算的，元素是计算伪地址，而伪地址是很好算的，元素a aij ij的伪地址为的伪地址为i*n+ji*n+j 2024/8/152024/8/158383/114/1142024/8/152024/8/158484/114/114 伪地址伪地址伪地址伪地址 值值值值 0 00 01515 1 13 32222 2 25 5-15-15 3 37 71111 4 48 8-3-3 5 51515 -6 -6 6 624249191 7 732322828稀疏矩阵伪地址表示稀疏矩阵伪地址表示(3) (3) 带辅助行向量的二元组表示法带辅助行向量的二元组表示法这个方法是三元组表示法的一个变种在三元组表示法中，去掉这个方法是三元组表示法的一个变种。

在三元组表示法中，去掉行下标字段，而加上一个有ｍ＋１个元素的辅助行向量行下标字段，而加上一个有ｍ＋１个元素的辅助行向量NRA NRA ，它，它的值定义如下：的值定义如下：NRA[0] = 0;NRA[0] = 0;NRA [i] = NRA[i-1] + NRA [i] = NRA[i-1] + 矩阵第矩阵第i-1i-1行中非零元素的个数行中非零元素的个数用带辅助行向量的二元组表示法表示稀疏矩阵，每个非零元素只用带辅助行向量的二元组表示法表示稀疏矩阵，每个非零元素只需要两个字段表示：分别为非零元素的列下标和值需要两个字段表示：分别为非零元素的列下标和值2024/8/152024/8/158585/114/1142024/8/152024/8/158686/114/114(4) (4) 行行- -列表示法列表示法矩阵的一个非零元素用一个结点表示，每个结点包括五个字段，矩阵的一个非零元素用一个结点表示，每个结点包括五个字段，分别为元素的行下标、列下标、值，以及指向本行下一个非零元分别为元素的行下标、列下标、值，以及指向本行下一个非零元素的指针和指向本列下一个非零元素的指针另外还有行的头指素的指针和指向本列下一个非零元素的指针。

另外还有行的头指针向量和列的头指针向量，行的头指针向量有ｍ个元素，分别指针向量和列的头指针向量，行的头指针向量有ｍ个元素，分别指向代表各行的第一个非零元素的结点列的头指针向量有ｎ个元向代表各行的第一个非零元素的结点列的头指针向量有ｎ个元素，分别指向代表各列的第一个非零元素的结点素，分别指向代表各列的第一个非零元素的结点 2024/8/152024/8/158787/114/1142024/8/152024/8/158888/114/114讨论讨论时间代价和空间代价始终是数据结构与算法设计的最主要因素，时间代价和空间代价始终是数据结构与算法设计的最主要因素，然而它们往往是相互对立的然而它们往往是相互对立的一个好的设计总是在时间代价和空间代价之间作出了一个好的权一个好的设计总是在时间代价和空间代价之间作出了一个好的权衡，而这种权衡的标准需要根据实际计算机的资源情况和求解问衡，而这种权衡的标准需要根据实际计算机的资源情况和求解问题的特点来确定题的特点来确定顺序表和单链表是两种最简单的数据结构，但是它们的应用非常顺序表和单链表是两种最简单的数据结构，但是它们的应用非常广泛本节中对于稀疏矩阵的所有表示都是这两种结构的扩充和广泛。

本节中对于稀疏矩阵的所有表示都是这两种结构的扩充和组合稀疏矩阵本身也是许多复杂结构的抽象稀疏矩阵本身也是许多复杂结构的抽象 2024/8/152024/8/158989/114/1142.1 2.1 基本概念与基本概念与ADTADT2.2 2.2 顺序表示顺序表示2.3 2.3 链接表示链接表示2.4 2.4 应用举例应用举例2.5 2.5 矩阵矩阵2.6 2.6 广义表与动态存储管理广义表与动态存储管理2024/8/152024/8/159090/114/114广义表是线性表的推广，具有广泛的应用价值它是表处理广义表是线性表的推广，具有广泛的应用价值它是表处理语言（例如语言（例如LISPLISP）的基础结构，也可以用于表示动态存储空）的基础结构，也可以用于表示动态存储空间的整体模型间的整体模型2024/8/152024/8/159191/114/114从逻辑上看，从逻辑上看，广义表广义表广义表广义表也是零个或多个元素组成的序列但是，也是零个或多个元素组成的序列但是，广义表中的元素允许以不同形式出现广义表中的元素允许以不同形式出现: :它可以是一个原子（逻它可以是一个原子（逻辑上不能再分解的元素），也可以又是一个广义表。

辑上不能再分解的元素），也可以又是一个广义表作为广义表元素的广义表称作广义表的子（广义）表一个作为广义表元素的广义表称作广义表的子（广义）表一个广义表还允许直接或间接地作为它自身的子（广义）表广义表还允许直接或间接地作为它自身的子（广义）表为了区分广义表和原子，可以用圆括号把一个广义表括起来，为了区分广义表和原子，可以用圆括号把一个广义表括起来，再用逗号来分隔广义表中的元素再用逗号来分隔广义表中的元素 一个广义表中所包含的元素的个数，称为这个广义表的长度一个广义表中所包含的元素的个数，称为这个广义表的长度长度为零的广义表称为空（广义）表长度为零的广义表称为空（广义）表一个广义表的一个广义表的深度深度深度深度，就是指广义表中所含子表的层数就是指广义表中所含子表的层数 广义表广义表2024/8/152024/8/159292/114/114书写中约定：用大写字母表示广义表，用小写字母表示原子书写中约定：用大写字母表示广义表，用小写字母表示原子例如：例如：Ｅ＝（）Ｅ＝（）Ｌ＝（ａ，ｂ）Ｌ＝（ａ，ｂ）Ａ＝（ｘ，Ｌ）＝（ｘ，（ａ，ｂ））Ａ＝（ｘ，Ｌ）＝（ｘ，（ａ，ｂ））Ｂ＝（Ａ，ｙ）＝（（ｘ，（ａ，ｂ）），ｙ）Ｂ＝（Ａ，ｙ）＝（（ｘ，（ａ，ｂ）），ｙ）Ｃ＝（Ａ，Ｂ）＝（（ｘ，（ａ，ｂ）），（（ｘ，（ａ，ｂ））Ｃ＝（Ａ，Ｂ）＝（（ｘ，（ａ，ｂ）），（（ｘ，（ａ，ｂ）），ｙ）），ｙ））Ｄ＝（ｚ，Ｄ）＝（ｚ，（ｚ，（ｚＤ＝（ｚ，Ｄ）＝（ｚ，（ｚ，（ｚ……））））））2024/8/152024/8/159393/114/114广义表的分类广义表的分类如果广义表中的元素全部都是原子（例如广义表Ｌ），这种广义如果广义表中的元素全部都是原子（例如广义表Ｌ），这种广义表就是表就是线性表线性表线性表线性表；；如果广义表中的元素允许有子广义表，但所有各层子广义表均无如果广义表中的元素允许有子广义表，但所有各层子广义表均无共享（例如广义表Ａ、Ｂ），这种广义表，称为共享（例如广义表Ａ、Ｂ），这种广义表，称为纯表纯表纯表纯表；；在各层子广义表中允许共享的广义表（例如广义表Ｃ的子表在各层子广义表中允许共享的广义表（例如广义表Ｃ的子表B B中共中共享了享了A A），称为），称为再入表再入表再入表再入表；；允许（子）广义表直接（或间接）地把作为自己的子广义表时，允许（子）广义表直接（或间接）地把作为自己的子广义表时，这样的广义表（例如广义表Ｄ），称为这样的广义表（例如广义表Ｄ），称为递归表递归表递归表递归表。

2024/8/152024/8/159494/114/114广义表的操作广义表的操作建立一个广义表；建立一个广义表；取广义表的头一个元素；取广义表的头一个元素；在广义表中插入一个元素，在广义表中插入一个元素，删除一个元素；删除一个元素；取删除头一个元素后的广义表；取删除头一个元素后的广义表；把一个广义表拆成两个部分；把一个广义表拆成两个部分；把两个广义表合并成一个新广义表；把两个广义表合并成一个新广义表；周游一个广义表；周游一个广义表；拷贝一个广义表；拷贝一个广义表；判别某元素是否原子；判别某元素是否原子；判别两个广义表是否相等；判别两个广义表是否相等；判别某广义表是否空广义表判别某广义表是否空广义表…………2024/8/152024/8/159595/114/114广义表的表示方法主要有：广义表的表示方法主要有：单链表示法单链表示法 带头结点的单链表示法带头结点的单链表示法 2024/8/152024/8/159696/114/114单链表示法单链表示法 每个结点由三个字段组成：每个结点由三个字段组成：atomatom，，infoinfo，，linklink其中其中atomatom是一标志位：是一标志位：atomatom＝＝0 0表示本结点为子广义表，这时字段表示本结点为子广义表，这时字段infoinfo存放子广义表中第存放子广义表中第一个元素所对应结点的地址；一个元素所对应结点的地址；atomatom＝＝1 1表示本结点为原子，字段表示本结点为原子，字段infoinfo存放本原子的信息（当信息存放本原子的信息（当信息量比较大时，也可以存放本原子信息存放的地址）。

量比较大时，也可以存放本原子信息存放的地址）字段字段linklink存放与本元素同层的下一个元素所对应结点的地址，当本存放与本元素同层的下一个元素所对应结点的地址，当本元素是所在层的最后一个元素时，元素是所在层的最后一个元素时，linklink＝＝NULLNULL 2024/8/152024/8/159797/114/1142024/8/152024/8/159898/114/114带头结点的单链表示法带头结点的单链表示法上述单链表示法的一个主要缺点是：如果要删除广义表（或子广上述单链表示法的一个主要缺点是：如果要删除广义表（或子广义表）中某一元素（例如删除义表）中某一元素（例如删除A A中的中的x x）则需要搜索广义表中所有）则需要搜索广义表中所有结点后才能进行结点后才能进行解决办法：对每个子广义表，增设一个广义表头结点解决办法：对每个子广义表，增设一个广义表头结点为区分是一般结点或者是表头结点，不妨令表头结点为区分是一般结点或者是表头结点，不妨令表头结点atomatom字段为字段为- -1 1；表头结点的；表头结点的infoinfo字段可以用来存放本广义表（或子广义表）的字段可以用来存放本广义表（或子广义表）的有关信息，表头结点的有关信息，表头结点的linklink字段指向广义表中第一个元素对应的结字段指向广义表中第一个元素对应的结点。

点 2024/8/152024/8/159999/114/1142024/8/152024/8/15100100/114/114单链表中的元素的个数是任意的，允许自由变化单链表中的元素的个数是任意的，允许自由变化习惯上把这种在使用期间，可自由插入和删除的数据结构称习惯上把这种在使用期间，可自由插入和删除的数据结构称为为动态数据结构动态数据结构动态数据结构动态数据结构在程序运行过程中，对于动态数据结构结点的分配和回收需在程序运行过程中，对于动态数据结构结点的分配和回收需要采用要采用动态存储管理动态存储管理动态存储管理动态存储管理的方法 结点的动态分配与回收结点的动态分配与回收2024/8/152024/8/15101101/114/114在前面的讨论中，当单链表插入值为在前面的讨论中，当单链表插入值为x x的元素时，只需调用的元素时，只需调用函数函数mallocmalloc，便能得到一个所需结点的空间，并返回这个结，便能得到一个所需结点的空间，并返回这个结点的起始地址；点的起始地址；在某指针所指向的结点删除后，调用函数在某指针所指向的结点删除后，调用函数freefree，就可以将该，就可以将该结点所占的空间释放，以利于再分配。

结点所占的空间释放，以利于再分配函数函数mallocmalloc和和freefree就是实现动态存储管理的两个最基本的函就是实现动态存储管理的两个最基本的函数2024/8/152024/8/15102102/114/114等长结点的分配与回收等长结点的分配与回收可利用空间表可利用空间表2024/8/152024/8/15103103/114/114不等长结点的分配与回收不等长结点的分配与回收一个处理方法是，在动态区中建立多个可利用空间表，每个可利一个处理方法是，在动态区中建立多个可利用空间表，每个可利用空间表对应一种固定长度的结点缺点是，难以真正解决多个用空间表对应一种固定长度的结点缺点是，难以真正解决多个可利用空间表的共享问题另外，要管理多个可利用空间表，系可利用空间表的共享问题另外，要管理多个可利用空间表，系统开销也较大不详细讨论）统开销也较大不详细讨论）另一种办法是：组织一个可以管理各种大小结点的可利用空间表另一种办法是：组织一个可以管理各种大小结点的可利用空间表分配时按申请的长度在可利用空间表中进行检索，找到其长度大分配时按申请的长度在可利用空间表中进行检索，找到其长度大于或等于申请长度的结点，从中截取合适的长度。

回收时考虑刚于或等于申请长度的结点，从中截取合适的长度回收时考虑刚刚被删除的结点空间能否与可利用空间表中的某些结点合并，组刚被删除的结点空间能否与可利用空间表中的某些结点合并，组成较大的结点成较大的结点2024/8/152024/8/15104104/114/114为了便于管理，在不等长的可利用空间表中，每个结点除了为了便于管理，在不等长的可利用空间表中，每个结点除了要有一个要有一个linklink字段指向表中下一个结点以外，还应有一个存字段指向表中下一个结点以外，还应有一个存放本结点大小的字段放本结点大小的字段sizesize系统运行初期，整个动态区就可系统运行初期，整个动态区就可以看成一个大的结点（称为以看成一个大的结点（称为可利用块可利用块可利用块可利用块）2024/8/152024/8/15105105/114/114动态分配动态分配1. 1. 最佳适配最佳适配检索可利用空间表中的全部结点，在所有检索可利用空间表中的全部结点，在所有sizesize≥ ≥N N的块中，找出最的块中，找出最小的一块进行分配，这种分配策略称为最佳适配小的一块进行分配，这种分配策略称为最佳适配2. 2. 首先适配首先适配如果在可利用空间表中，找到第一个如果在可利用空间表中，找到第一个sizesize≥ ≥N N的可利用块就进行分的可利用块就进行分配，则称为首先适配。

配，则称为首先适配3. 3. 最大适配最大适配如果在可利用空间表中，每次都用最大的可利用块来分配，当最如果在可利用空间表中，每次都用最大的可利用块来分配，当最大的块长度小于Ｎ时，则分配失败这种方法称为最大适配大的块长度小于Ｎ时，则分配失败这种方法称为最大适配2024/8/152024/8/15106106/114/114例例1 1：最佳适配分配过程：最佳适配分配过程2024/8/152024/8/15107107/114/114例例2 2：首先适配分配：首先适配分配2024/8/152024/8/15108108/114/114例例3 3：最大适配分配：最大适配分配2024/8/152024/8/15109109/114/114回收过程回收过程必须随时考查能否和相邻的块合并的问题如果在可利用空间表必须随时考查能否和相邻的块合并的问题如果在可利用空间表中有与被释放的结点相邻的可利用块，应把它合关成较大的可利中有与被释放的结点相邻的可利用块，应把它合关成较大的可利用块为了减少查找的时间，可作如下两种改进：为了减少查找的时间，可作如下两种改进：第一：可以把可利用空间表中结点，按内存单元地址的递增顺序第一：可以把可利用空间表中结点，按内存单元地址的递增顺序链接起来。

链接起来第二：可以在每个结点（包括已分配结点和可利用块）的两端各第二：可以在每个结点（包括已分配结点和可利用块）的两端各加上一个标志位加上一个标志位tagtag，已分配的，已分配的tag = 1tag = 1，可利用的，可利用的tag = 0tag = 0；在可利；在可利用块的两端都标明用块的两端都标明sizesize字段，并将可利用块之间的链接方式，改字段，并将可利用块之间的链接方式，改换成双链循环表结构，分别指向本可利用块在可利用空间表中的换成双链循环表结构，分别指向本可利用块在可利用空间表中的前驱和后继前驱和后继2024/8/152024/8/15110110/114/114讨论讨论这样处理方法的优点是可以解决存储空间的共享问题，缺点是分这样处理方法的优点是可以解决存储空间的共享问题，缺点是分配和回收的算法复杂了配和回收的算法复杂了另外，在系统长期动态运行的过程中，这种方法有可能使整个空另外，在系统长期动态运行的过程中，这种方法有可能使整个空间被分割成许多大小不等的碎块，而某些碎块由于太小而长期得间被分割成许多大小不等的碎块，而某些碎块由于太小而长期得不到使用不到使用这就产生所谓这就产生所谓“ “碎片问题碎片问题碎片问题碎片问题” ”。

2024/8/152024/8/15111111/114/114内存的资源是有限的，加上存储管理功能的限制和使用的不内存的资源是有限的，加上存储管理功能的限制和使用的不当，随着系统的长期运行，动态区可能出现严重的浪费系当，随着系统的长期运行，动态区可能出现严重的浪费系统能够提供给动态分配的空间，常常不能满足用户的需求统能够提供给动态分配的空间，常常不能满足用户的需求下面介绍的废料收集和存储压缩技术，就是在动态区快要溢下面介绍的废料收集和存储压缩技术，就是在动态区快要溢出时的补救方法出时的补救方法废料收集与存储压缩废料收集与存储压缩2024/8/152024/8/15112112/114/114废料收集废料收集在动态区中还可能存在一些被无用结点占用的空间，简称为在动态区中还可能存在一些被无用结点占用的空间，简称为无用无用无用无用结点结点结点结点（也称为（也称为废料废料废料废料）这些结点曾经属于已利用空间，但是在删）这些结点曾经属于已利用空间，但是在删除时没有得到及时回收，所以它们既不在可利用空间的广义表中，除时没有得到及时回收，所以它们既不在可利用空间的广义表中，也不在已利用空间的广义表中。

也不在已利用空间的广义表中废料收集废料收集废料收集废料收集需要解决的问题是：从整个动态区的已利用空间中，找需要解决的问题是：从整个动态区的已利用空间中，找出哪些结点是无用结点，并且把它们送入可利用空间表中出哪些结点是无用结点，并且把它们送入可利用空间表中 为了寻找无用结点，只要系统搜索（或称周游）整个已利用空间为了寻找无用结点，只要系统搜索（或称周游）整个已利用空间的广义表，凡是周游经过的结点，都是有用的，可以做上标志；的广义表，凡是周游经过的结点，都是有用的，可以做上标志；凡是没有周游到的结点（未做标志的结点），都应该回收凡是没有周游到的结点（未做标志的结点），都应该回收在执行周游和标志的算法以后，只要扫描一遍动态区，将所有未在执行周游和标志的算法以后，只要扫描一遍动态区，将所有未做标志的结点（包括原来就在可利用空间表中的结点和废料）全做标志的结点（包括原来就在可利用空间表中的结点和废料）全部送入可利用空间表中，即完成了废料的回收部送入可利用空间表中，即完成了废料的回收2024/8/152024/8/15113113/114/114存储压缩存储压缩碎片碎片碎片碎片与废料不同，它出现在可利用空间中，但是因为太小，长期与废料不同，它出现在可利用空间中，但是因为太小，长期无法分配使用。

无法分配使用为了从根本上解决碎片问题，可以采用为了从根本上解决碎片问题，可以采用存储压缩存储压缩存储压缩存储压缩的方法 所谓存储压缩，就是把有用的结点压缩到动态区的一端，把可利所谓存储压缩，就是把有用的结点压缩到动态区的一端，把可利用的结点（包括碎片）压缩到动态区的另一端，使全部可利用的用的结点（包括碎片）压缩到动态区的另一端，使全部可利用的空间连成一片，构成一个大的可利用块空间连成一片，构成一个大的可利用块 在实际系统中，常常把废料的收集和存储压缩一起进行在实际系统中，常常把废料的收集和存储压缩一起进行 2024/8/152024/8/15114114/114/114Q&A2024/8/152024/8/15115115/114/114。