单链表数据结构

第二章线性表单链表(Singlylinkedlist)线性表–单链表单链表定义与特点单链表的C语言描述单链表基本形态单链表基本操作实现单链表的运用一、单链表的定义与特点定义特点一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即指针）。1.数据元素在“逻辑关系上的相邻”用“指针”来表示。2.单链表中访问数据元素时需从头开始“顺序访问”。3.比顺序表的优势在于，提供高效地重排数据项的能力。a1a2a3a4……anL^结点链接项（指针域）每个链接项只链接其后一个结点数据项(域)二、单链表的C语言描述

typedefstructLNode{ElemTypedata;//数据域

structLNode

*next;//指针域

}LNode,*LinkList;LinkListL；//L为单链表的头指针头指针指向单链表中的第一个结点用结构体表示结点，结点是由数据项和链接组成的，链接用指针表示，用于指向下一个结点。a类型定义实例声明三、单链表的基本形态空表非空表为了操作方便，在第一个结点之前虚加一个“头结点”L^L->next==NULL;不允许删除操作La1a2a3……an^可以进行插入、删除操作哑元结点不存储数据项头结点四、单链表基本操作初始化操作(initialize)查找操作(locate/find)插入新元素操作(insert)删除元素操作(delete)清空操作(clear)销毁操作(destroy)其它操作4.1初始化操作Stutas

InitList(LinkList&L){ L=(LinkList)malloc(sizeof(LNode));//1.动态分配结点内存

if(!L)exit(overflow);

L->next=NULL;//2.结点指针初始化

returnOK;}L头结点需要预先创建头结点L211830754256∧pppj1234.2查找操作（1）查找指定位序的数据元素；

（2）数据元素值匹配查找。演示例子：取单链表中第3个元素值找到！4.2查找操作单链表是一种“顺序访问”的结构，为找第i个数据元素，必须先找到第(i-1)个数据元素。1.指针p始终指向单链表中第j个结点；2.移动指针，比较j和i，相等则找到。StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素

p=L->next;//p指向第一个结点

j=1;//j为计数器

//顺指针向后查找，直到p指向第i个元素或p为空

while(p&&j<i){p=p->next;j++;}if(p&&j==i){//找到e=p->data;//取得第i个元素

returnOK;}else{//第i个元素不存在

returnERROR;}}//GetElem_L算法时间复杂度为：O(ListLength(L))与顺序表相比，链表不适合于查找第i个元素的操作。按结点位序（位置序号）查找LNode*GetElem_L(LinkListL,ElemTypee){//查找第一个元素值为

e的结点，返回其结点指针

p=L->next;//p指向第一个结点

//顺指针向后查找，直到找到匹配项或p为空

while(p){if(p->data==e){ //找到，元素值匹配值

returnp;//返回结点指针

}p=p->next;}returnNULL;//无匹配项，返回空指针}//GetElem_L算法时间复杂度为：O(ListLength(L))按数据元素值匹配查找4.3插入新元素操作在单链表中的第i个元素前插入元素e。单链表中：ai-1

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eai在单链表中插入结点只需要修改指针。若要在第i个结点之前插入元素，修改的是第(i-1)个结点的指针。StatusListInsert_L(LinkList&L,inti,ElemTypee){//链表中第i个结点之前插入新的元素ep=L;j=0;while(p!=NULL

&&j<i-1)

{p=p->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;//前一结点指针指向新结点

returnOK;

}else{//未找到第i个结点

returnERROR;}}//LinstInsert_L算法的时间复杂度为：O(ListLength(L))saiai-1ep查找插入有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>aiai+1ai-1ai-14.4删除元素操作从单链表中删除第i个元素。在单链表中删除第i个结点时，要找到单链表中第(i-1)个结点，修改其指向后继的指针。ai-1aiai+1q=p->next;p->next=q->next;

e=q->data;

free(q);pqStatusListDelete_L(LinkList&L,inti,ElemType

&e){//删除以L为头指针(带头结点)的单链表中第i个结点

p=L;j=0;//查找第i-1个结点，并令p指向它。

while(p->next&&j<i-1){p=p->next;++j;}if(p->next&&j==i-1){

e=q->data;q=p->next;//q指向要删除结点

p->next=q->next;//前一结点指针指向要删除结点的后一结点

free(q);//释放删除结点内存

returnOK;}else{

returnERROR;//删除位置不合理

}}//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)returnTRUE;//空elsereturnFALSE;//非空求表长intListLength(LinkListL){p=L->next;i=0;//计数

while(p){i++;p=p->next;}returni;}空链表不允许删除操作单链表和顺序表特性对比单链表顺序表按位序访问效率顺序访问，效率较低位序地址可计算，效率高查找效率顺序访问，效率较低排序后可用折半查找，效率较高插入、删除操作效率仅需通过修改指针即可实现，效率高需要移动元素，效率低动态改变大小支持不支持内存使用效率可利用内存碎片，但每个数据项需要额外的指针域需要完整内存块，无额外内存开销两种实现方式特性不同，存在互补，在实际应用中应根据应用要求选择更适用的方式。五、单链表的运用建立单链表归并有序列表稀疏多项式相加5.1建立单链表（1）顺序建立单链表链表是一个动态结构，它不需要预分配空间，生成链表的过程是一个结点“逐个插入”的过程。新结点插入在头结点的后面，作为重排链表后的第一个结点。新结点插在尾结点的后面，作为重排链表后的最后一个结点。（2）逆序建立单链表La1a2……an^

e逆序顺序

e^5.1.1顺序建立单链表a1①建立一个带头结点的空单链表；②输入数据元素ai，建立新结点，并把其插入在尾结点p之后成为最后一个结点。③重复执行②步，直到完成单链表的建立。a2a1创建出来的链表结点顺序与插入操作顺序相同。voidCreateList_N(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表p=L;//p指向Lfor(i=1;i<=n;i++){q=(LinkList)malloc(sizeof(LNode));scanf(&q->data);//输入元素值q->next=NULL;//q为尾结点p->next=q;//将q链接到p之后p=q;//p指向新的尾结点}}//CreateList_L算法的时间复杂度为：O(ListLength(L))步骤1步骤2指针p始终指向链表尾结点。5.1.2逆序建立单链表a1①建立一个带头结点的空单链表；②输入数据元素ai，建立新结点p，并把p插入在头结点之后成为第一个结点。③重复执行②步，直到完成单链表的建立。a1a2创建出来的链表结点顺序与插入操作顺序相反。voidCreateList_N(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);//输入元素值p->next=L->next;//将第一个数据结点链接到新结点之后L->next=p;//头结点指向新的结点p}}//CreateList_L算法的时间复杂度为：O(ListLength(L))步骤1步骤25.2归并有序链表归并有序单链表La和有序单链表Lb得到有序单链表Lc。链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可。a1a2……an^Lab1b2……bn^Lb5.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所指结点之后即可。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;//pa和pb初值指向第一个结点Lc=La;//用La的头作为Lc的头结点pc=Lc;//pc初值指向Lc的头结点//依次“摘取”两表中值较小的结点插入到Lc的最后while(pa&&pb){//La和Lb均未到达表尾if(pa->data<=pb->data){//La当前结点值小于等于Lb的当前结点值pc->next=pa;pc=pa;

pa=pa->next;

}else{//Lb当前结点值小于La的当前结点值

pc->next=pb;pc=pb;pb=pb->next;

}}pc->next=pa?pa:pb;//将剩余的部分直接链接到Lc上free(Lb);}算法时间复杂度：O(m+n)算法空间复杂度：O(1)5.3稀疏多项式相加多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x870517A^319881B^227-98稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为O(1)。5.3稀疏多项式相加70517^111^227A对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。规则：typedefstructPNode{

floatcoef;//系数

intexpn;//指数

structPNode*next;}PNode,*Polynomial;用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。5.3稀疏多项式相加实现方式：voidAddPolyn(Polynomial&pa,Polynomial&pb){p1=pa->next;p2=pb->next;p3=pa;while(p1&&p2){if(p1->expn==p2->expn){sum=p1->coef+p2->coef;if(sum!=0){

p1->coef=sum;p3->next=p1;

p3=p1;p1=p1->next;

r=p2;p2=p2->next;

free(r);

}else{

r=p1;p1=p1->next;free(r);

r=p2;p2=p2->next;free(r);

}}elseif(p1->expn<p2->expn){p3->nex