单链表数据结构.ppt
第二章 线性表单链表(Singly linked list)线性表 单链表一一单链表定义与特点单链表定义与特点二二单链表的单链表的C C语言描述语言描述三三单链表基本形态单链表基本形态四四单链表基本操作实现单链表基本操作实现五五单链表的运用单链表的运用一、单链表的定义与特点定义定义特点特点一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即指针指针）。1.数据元素在“逻辑逻辑关系上的相邻相邻”用“指针指针”来表示。2.单链表 中访问数据元素时需从头开始“顺序访问顺序访问”。3.比顺序表的优势在于，提供高效地重排重排数据项的能力。a1a2a3a4anL结点结点链接项（指针域）链接项（指针域）每个链接项只链接其后一个结点数据项数据项(域域)二、单链表的C语言描述 typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList; LinkList L； / L为单链表的头指针头指针指向单链表中的用表示，结点是由和组成的，链接用表示，用于指向下一个结点。 a类型定义实例声明三、单链表的基本形态空表空表非空表非空表为了操作方便，在第一个结点之前虚加一个为了操作方便，在第一个结点之前虚加一个“头结点头结点”LL-next = NULL;不允许删除操作不允许删除操作La1a2a3an可以进行插入、删除操作可以进行插入、删除操作哑元结点哑元结点不存储数据项不存储数据项头结点头结点四、单链表基本操作1.1.初始化操作初始化操作(initialize)(initialize)2.2.查找操作查找操作(locate/find)(locate/find)3.3.插入新元素操作插入新元素操作(insert)(insert)4.4.删除元素操作删除元素操作(delete)(delete)5.5.清空操作清空操作(clear)(clear)6.6.销毁操作销毁操作(destroy)(destroy)7.7.其它操作其它操作4.1 初始化操作Stutas InitList(LinkList &L) L = (LinkList) malloc(sizeof(LNode) ; / 1.动态分配结点内存动态分配结点内存 if(!L) exit(overflow); L-next=NULL; / 2.结点指针初始化结点指针初始化 return OK;L头结点头结点L211830754256pppj1 2 34.2 查找操作（1）查找指定位序的数据元素；（2）数据元素值匹配查找。演示例子：取单链表中第3个元素值找到！找到！4.2 查找操作单链表是一种单链表是一种“顺序访问顺序访问”的结构，为找第的结构，为找第 i i 个数据个数据元素，必须先找到第元素，必须先找到第( ( i-1 i-1 ) )个数据元素。个数据元素。1.1.指针指针p p始终指向单链表中第始终指向单链表中第j j个结点；个结点；2.2.移动指针，比较移动指针，比较 j j 和和 i i，相等则找到。，相等则找到。Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以 e 返回第 i 个元素 p = L-next; / p指向第一个结点 j = 1; / j为计数器 / 顺指针向后查找顺指针向后查找，直到 p 指向第 i 个元素或 p 为空 while (p & j next; j +; if ( p & j=i ) / 找到 e = p-data; / 取得第 i 个元素 return OK; else /第 i 个元素不存在 return ERROR; / GetElem_L算法时间复杂度为：O(ListLength(L)与顺序表相比，链表不适合于查找与顺序表相比，链表不适合于查找第第i i个元素的操作。个元素的操作。按结点位序（位置序号）查找LNode * GetElem_L(LinkList L, ElemType e) / 查找第一个元素值为 e 的结点，返回其结点指针 p = L-next; / p指向第一个结点 / 顺指针向后查找顺指针向后查找，直到找到匹配项或 p 为空 while (p) if ( p-data = e )/ 找到，元素值匹配值 return p; / 返回结点指针 p = p-next; return NULL; / 无匹配项，返回空指针 / GetElem_L算法时间复杂度为：O(ListLength(L)按数据元素值匹配查找4.3 插入新元素操作在单链表中的第i个元素前插入元素e。单链表中：ai-1 有序对有序对 改变为改变为 和和 eai在单链表中在单链表中插入结点插入结点。若要在第若要在第 i i 个结点之前插入元素，修改的是第个结点之前插入元素，修改的是第 (i-1) (i-1) 个结点的指针。个结点的指针。Status ListInsert_L(LinkList &L, int i, ElemType e) / 链表中第链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e p = L; j = 0; while (p != NULL & j next; +j; / 查找第找第 (i-1) 个结点个结点 if (p != NULL & j = i-1) / 找到第找到第i个结点个结点 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; / 数据域赋值 s-next = p-next; /新结点指针指向后一结点 p-next = s; / 前一结点指针指向新结点 return OK; else / 未找到第未找到第i个结点个结点 return ERROR; / LinstInsert_L算法的时间复杂度为：O(ListLength(L)s ai ai-1 ep查找查找插入插入有序对有序对 和和 改变为改变为 aiai+1ai-1ai-14.4 删除元素操作从单链表中删除第i个元素。在单链表中在单链表中删除第删除第 i i 个结点个结点时，要找到单链表中第时，要找到单链表中第( (i-1i-1) )个结点，个结点，修改其指向后继的指针。修改其指向后继的指针。ai-1aiai+1q = p-next;p-next = q-next; e = q-data; free(q);pq Status ListDelete_L(LinkList &L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 p = L; j = 0; / 查找第 i-1 个结点，并令 p 指向它。 while (p-next & j next; +j; if (p-next& j = i-1) e = q-data; q = p-next; / q指向要删除结点 p-next = q-next; / 前一结点指针指向要删除结点的后一结点 free(q); / 释放删除结点内存 return OK; else return ERROR; / 删除位置不合理 / ListDelete_L算法的时间复杂度为：O(ListLength(L)查找查找删除删除4.5 清空操作5、清空while (L-next) p = L-next; / p指向当前结点 L-next = p-next; / 头结点指向当前结点的后结点 free(p); / 释放当前结点内存/ 清空完成后，仍保留头结点保留头结点L算法的时间复杂度为：O(ListLength(L)4.6 销毁操作6、销毁while(L) p = L-next; / p指向第一结点(头节点为“哑结点”) free(L); / 释放首结点 L=p; / L指向p/ 销毁完成后，L为空为空(NULL)算法的时间复杂度为：O(ListLength(L)4.7 其它操作判空if(L-next=NULL) return TRUE; / 空else return FALSE; /非空求表长int ListLength(LinkList L) p=L-next; i=0; / 计数 while(p) i+; p=p-next; return i;空链表不允空链表不允许删除操作许删除操作单链表和顺序表特性对比单链表顺序表按位序访问效率顺序访问，效率较低位序地址可计算，效率高查找效率顺序访问，效率较低排序后可用折半查找，效率较高插入、删除操作效率仅需通过修改指针即可实现，效率高需要移动元素，效率低动态改变大小支持不支持内存使用效率可利用内存碎片，但每个数据项需要额外的指针域需要完整内存块，无额外内存开销两种实现方式特性不同，存在互补，在实际应用中应根据应用要求选择更两种实现方式特性不同，存在互补，在实际应用中应根据应用要求选择更适用的方式。适用的方式。五、单链表的运用1.1.建立单链表建立单链表2.2.归并有序列表归并有序列表3.3.稀疏多项式相加稀疏多项式相加5.1 建立单链表（1）顺序建立单链表链表是一个动态结构，它不需要预分配空间，生成链表的过程是一个链表是一个动态结构，它不需要预分配空间，生成链表的过程是一个 的过程。的过程。新结点插入在新结点插入在，作为重排链表后的作为重排链表后的第一个结第一个结点点。新结点插在新结点插在，作为重排链表后的作为重排链表后的最后一最后一个结点。个结点。（2）逆序建立单链表La1a2an e逆序逆序顺序顺序 e5.1.1 顺序建立单链表a1建立一个带头结点的空单链表；建立一个带头结点的空单链表；输入数据元素输入数据元素ai，建立新结点，并，建立新结点，并把其插入在尾结点把其插入在尾结点p之后成为最后一之后成为最后一个结点。个结点。重复执行重复执行步，直到完成单链表的步，直到完成单链表的建立。建立。a2a1创建出来的链表结点顺序与插入操作。void CreateList_N(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表 p = L; / p指向L for (i = 1; i data); / 输入元素值 q-next = NULL; / q为尾结点 p-next = q; / 将q链接到p之后 p = q; / p指向新的尾结点 / CreateList_L算法的时间复杂度为：O(ListLength(L)步骤步骤1 1步骤步骤2 2指针指针p p始终指始终指向链表尾结向链表尾结点。点。5.1.2 逆序建立单链表a1建立一个带头结点的空单链表；建立一个带头结点的空单链表；输入数据元素输入数据元素ai，建立新结点，建立新结点p，并把并把p插入在头结点之后成为第一个插入在头结点之后成为第一个结点。结点。重复执行重复执行步，直到完成单链表的步，直到完成单链表的建立。建立。a1a2创建出来的链表结点顺序与插入操作。void CreateList_N(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i = 1; i data); / 输入元素值 p-next = L-next; / 将第一个数据结点链接到新结点之后 L-next = p; / 头结点指向新的结点p / CreateList_L算法的时间复杂度为：O(ListLength(L)步骤步骤1 1步骤步骤2 25.2 归并有序链表归并有序单链表归并有序单链表L La a和有序单链表和有序单链表L Lb b得到有序单链表得到有序单链表L Lc c。链表结点
