单链表数据结构.ppt
第二章 线性表,单链表(Singly linked list),线性表 单链表,单链表定义与特点单链表的C语言描述单链表基本形态单链表基本操作实现单链表的运用,一、单链表的定义与特点,定义特点,一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即指针）。,1.数据元素在“逻辑关系上的相邻”用“指针”来表示。2.单链表 中访问数据元素时需从头开始“顺序访问”。3.比顺序表的优势在于，提供高效地重排数据项的能力。,L,结点,链接项（指针域）每个链接项只链接其后一个结点,数据项(域),二、单链表的C语言描述,typedef struct LNode ElemType data;/数据域 struct LNode*next;/指针域 LNode,*LinkList;,LinkList L；/L为单链表的头指针,头指针指向单链表中的第一个结点,用结构体表示结点，结点是由数据项和链接组成的，链接用指针表示，用于指向下一个结点。,类型定义,实例声明,三、单链表的基本形态,空表非空表,为了操作方便，在第一个结点之前虚加一个“头结点”,L,L-next=NULL;,不允许删除操作,L,可以进行插入、删除操作,哑元结点不存储数据项,头结点,四、单链表基本操作,初始化操作(initialize)查找操作(locate/find)插入新元素操作(insert)删除元素操作(delete)清空操作(clear)销毁操作(destroy)其它操作,4.1 初始化操作,Stutas InitList(LinkList,需要预先创建头结点,j,1,2,3,4.2 查找操作,（1）查找指定位序的数据元素；（2）数据元素值匹配查找。,演示例子：取单链表中第3个元素值,找到！,4.2 查找操作,单链表是一种“顺序访问”的结构，为找第 i 个数据元素，必须先找到第(i-1)个数据元素。,1.指针p始终指向单链表中第j个结点；2.移动指针，比较 j 和 i，相等则找到。,Status GetElem_L(LinkList L,int i,ElemType/GetElem_L,算法时间复杂度为：O(ListLength(L),与顺序表相比，链表不适合于查找第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。,单链表中：,有序对 改变为 和,在单链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第(i-1)个结点的指针。,Status ListInsert_L(LinkList/LinstInsert_L,算法的时间复杂度为：O(ListLength(L),s,p,查找,插入,有序对 和 改变为,ai,4.4 删除元素操作,从单链表中删除第i个元素。,在单链表中删除第 i 个结点时，要找到单链表中第(i-1)个结点，修改其指向后继的指针。,ai,q=p-next;p-next=q-next;e=q-data;free(q);,p,q,Status ListDelete_L(LinkList/删除位置不合理/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;,空链表不允许删除操作,单链表和顺序表特性对比,两种实现方式特性不同，存在互补，在实际应用中应根据应用要求选择更适用的方式。,五、单链表的运用,建立单链表归并有序列表稀疏多项式相加,5.1 建立单链表,（1）顺序建立单链表,链表是一个动态结构，它不需要预分配空间，生成链表的过程是一个结点“逐个插入”的过程。,新结点插入在头结点的后面，作为重排链表后的第一个结点。,新结点插在尾结点的后面，作为重排链表后的最后一个结点。,（2）逆序建立单链表,逆序,顺序,5.1.1 顺序建立单链表,建立一个带头结点的空单链表；,输入数据元素ai，建立新结点，并把其插入在尾结点p之后成为最后一个结点。,重复执行步，直到完成单链表的建立。,创建出来的链表结点顺序与插入操作顺序相同。,void CreateList_N(LinkList/p指向新的尾结点/CreateList_L,算法的时间复杂度为：O(ListLength(L),步骤1,步骤2,指针p始终指向链表尾结点。,5.1.2 逆序建立单链表,建立一个带头结点的空单链表；,输入数据元素ai，建立新结点p，并把p插入在头结点之后成为第一个结点。,重复执行步，直到完成单链表的建立。,创建出来的链表结点顺序与插入操作顺序相反。,void CreateList_N(LinkList/头结点指向新的结点p/CreateList_L,算法的时间复杂度为：O(ListLength(L),步骤1,步骤2,5.2 归并有序链表,归并有序单链表La和有序单链表Lb得到有序单链表Lc。,链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可。,5.2 归并有序链表,归并思想：,需要设立3个指针pa、pb、pc，其中pa和pb分别指向La和Lb中当前待比较插入的结点，而pc指向Lc中当前最后一个结点（Lc的表头结点设为La的表头结点）。指针的初值为：pa和pb分别指向La和Lb表中的第一个结点，pc指向空表Lc中的头结点。通过比较指针pa和pb所指向的元素的值，依次从La或Lb中“摘取”元素值较小的结点插入到Lc的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。,void MergeList_L(LinkList,算法时间复杂度：O(m+n),算法空间复杂度：O(1),5.3 稀疏多项式相加,多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8,稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为O(1)。,5.3 稀疏多项式相加,对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。,规则：,typedef struct PNodefloat coef;/系数int expn;/指数struct PNode*next;PNode,*Polynomial;,用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。,5.3 稀疏多项式相加,实现方式：,void AddPolyn(Polynomial,稀疏多项式相加,指数相同,指数不同,5.3 稀疏多项式相加,稀疏多项式的创建,多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插入到此项的前面，这样即可保证多项式链表的有序性。,void CreatePolyn(Polynomial,5.3 稀疏多项式相加,根据当前指数值找到其在多项式有序链表中的位置。,顺序建立单链表。,稀疏多项式的创建,每个结点包含数据域和指针域，由指针连接后结点；只能顺序访问，查找访问效率不高；插入与删除操作只需修改指针，无需移动已有元素，效率较高；支持动态内存分配，使用灵活，需要额外指针域；在适合的场合，单链表的应用简单高效。,本节内容小结,
