数据结构单链表

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

typedef

structLNode{ElemTypedata;//数据域

structLNode*next;//指针域

}LNode,*LinkList;

LinkListL；

//L为单链表的头指针头指针指向单链表中的第一个结点用指针表示链接，用结构体表示结点，结点是由数据项和链接组成的，链接是指向下一结点的指针。2021/5/93单链表的基本形态空表非空表为了操作方便，在第一个结点之前虚加一个“头结点”哑元结点L^L->next==NULL;不允许删除操作a1a2a3……anL^可以进行插入、删除操作2021/5/94单链表基本操作1、初始化（动态分配）StutasInitList(LinkList&L){ L=(LinkList)malloc(sizeof(LNode)); if(!L)exit(overflow);

L->next=NULL; returnOK;}L头结点2021/5/95L211830754256∧pppj123单链表基本操作2、取单链表中指定位序的数据元素演示例子：取单链表中第3个元素值2021/5/96取元素的基本操作单链表是一种“顺序访问”的结构，为找第i个数据元素，必须先找到第(i-1)个数据元素。1.指针p始终指向单链表中第j个结点；2.移动指针，比较j和i，相等则找到。2021/5/97

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素}//GetElem_L算法时间复杂度为:O(ListLength(L))p=L->next;j=1;//p指向第一个结点，j为计数器while(p&&j<i){p=p->next;j

++;}//

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

//

或p为空if(p&&j==i){e=p->data;

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

returnERROR;}与顺序表相比，链表不适合于查找第i个元素的操作。2021/5/98单链表基本操作3、插入（在第i个元素前插入e）单链表中：ai-1

有序对<ai-1,ai>

改变为<ai-1,e>和<e,ai>eaiai-1在单链表中插入结点只需要修改指针。若要在第i个结点之前插入元素，修改的是第(i-1)个结点的指针。2021/5/99StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L为带头结点的单链表的头指针，本算法

//在链表中第i个结点之前插入新的元素e

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))……}elsereturnERROR;p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第(i-1)个结点if(p&&j==i-1){2021/5/910s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp2021/5/911有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-1单链表基本操作4、删除（第i个元素）在单链表中删除第i个结点时，要找到单链表中第(i-1)个结点，修改其指向后继的指针。2021/5/912

ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq2021/5/913StatusListDelete_L(LinkList&L,inti,ElemType&e){

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

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i-1个结点，并令p指向它。if(p->next&&j==i-1)

{q=p->next;p->next=q->next;

//删除并释放结点e=q->data;free(q);returnOK;}elsereturnERROR;//删除位置不合理2021/5/914对比单链表和顺序表的基本操作插入和删除的简单性是链表存在的理由只修改相关结点的指向保持链表特性单链表的访问方式是顺序访问查找第i个数据项的代价，沿着链表，一个一个结点地访问，直到找的这个数据项2021/5/915算法时间复杂度：O(ListLength(L))单链表基本操作5、清空while(L->next){

p=L->next; L->next=p->next;

free(p);}2021/5/916算法时间复杂度：O(ListLength(L))单链表基本操作6、销毁while(L){p=L->next;

free(L); L=p;}2021/5/917单链表基本操作7、判空if(L->next==NULL) returnTRUE;else returnFALSE;8、求表长intListLength(LinkListL){ p=L->next; i=0; while(p){

i++;

p=p->next; } returni;}2021/5/918单链表基本操作9、搜索（查找元素）p=L->next;i=1;while(p&&p->data!=e){

p=p->next;i++;}if(p) returni;else return0;从第一个结点开始搜索搜索成功，返回位序；否则，返回02021/5/919单链表的应用1.建立单链表链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。逆序建立单链表顺序建立单链表新结点插入在头结点的后面，作为重排链表后的第一个结点新结点插入在尾结点的后面，作为重排链表后的最后一个结点2021/5/920逆序建立单链表操作步骤①建立一个带头结点的空单链表；②输入数据元素ai，建立新结点p，并把p插入在头结点之后成为第一个结点。③重复执行②步，直到完成单链表的建立。a1a1a22021/5/921voidCreateList_N(LinkList&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))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;

//插入}2021/5/922顺序建立单链表操作步骤①建立一个带头结点的空单链表；②输入数据元素ai，建立新结点，并把其插入在尾结点p之后成为最后一个结点。③重复执行②步，直到完成单链表的建立。a1pa1ppa2pa3p……ppan2021/5/923顺序建立单链表：即新元素插入表尾L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

//先建立一个带头结点的单链表时间复杂度为O(n)p=L;for(i=1;i<=n;i++){

q=(LinkList)malloc(sizeof(LNode));scanf(&q->data);

q->next=p->next;p->next=q;p=q;}2021/5/924单链表的应用2.归并有序链表归并有序单链表La和有序单链表Lb得到有序单链表Lc。链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可。2021/5/925单链表的应用归并思想：需要设立3个指针pa、pb、pc，其中pa和pb分别指向La和Lb中当前待比较插入的结点，而pc指向Lc中当前最后一个结点（Lc的表头结点设为La的表头结点）。指针的初值为：pa和pb分别指向La和Lb表中的第一个结点，pc指向空表Lc中的头结点。通过比较指针pa和pb所指向的元素的值，依次从La或Lb中“摘取”元素值较小的结点插入到Lc的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。2021/5/926归并有序单链表voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){ pa=La->next;pb=Lb->next;//pa和pb初值指向第一个结点

Lc=La;

//用La的头作为Lc的头结点

pc=Lc;

//pc初值指向Lc的头结点

while(pa&&pb

){//La和Lb均未到达表尾，依次“摘取”两表中值较小的结点插入到Lc的最后

if(pa->data<=pb->data){ pc->next=pa; pc=pa; pa=pa->next; }else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; free(Lb);}算法时间复杂度：O(m+n)算法空间复杂度：O(1)2021/5/927单链表的应用3.稀疏多项式的运算稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为O(1)。多项式A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x870517A^319881B^227-982021/5/928单链表的应用稀疏多项式的相加规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式链表中摘取。70517^111^227A2021/5/929稀疏多项式相加typedefstructPNode{ floatcoef; intexpn; structPNode*next;}PNode,*Polynomial;用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数（coef）和指数（expn）两个数据域以及一个指针域（next）。2021/5/930稀疏多项式相加假设头指针pa和pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数较小的项插入到“和多项式”链表中去。2021/5/931稀疏多项式相加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