优秀的链表PPT课件

,链表成俊燕mail：zjucheng,1,-,链表的定义,节点离散分布节点之间通过指针连接每个节点只有一个前驱，一个后继节点首节点没有前驱，尾节点没有后继术语：首节点，尾节点，头结点，头指针，尾指针。,2,-,线性表的链式存储结构,-,特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置,3,-4页,例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,4,-,单链表,-,实现,typedefstructnodedatatypedata;structnode*link;JD;,JD*h,*p;,(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域,生成一个JD型新结点：p=(JD*)malloc(sizeof(JD);系统回收p结点：free(p),定义：结点中只含一个指针域的链表叫，也叫单链表,5,单链表基本算法,查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL算法描述：算法评价,JD*dlbcz(JD*h,intx)JD*p;p=h;while(p!=NULL,6,-,单链表基本算法,插入：在线性表两个数据元素a和b间插入x，已知p指向a算法描述算法评价,-,s-link=p-link;,p-link=s;,voiddlbcr(JD*p,intx)JD*s;s=(JD*)malloc(sizeof(JD);s-data=x;s-link=p-link;p-link=s;,7,单链表基本算法,删除：单链表中删除b，设p指向a算法描述算法评价,-,voiddlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);,p-link=p-link-link;,8,单链表基本算法,动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法描述,-,JD*dlbjl(inta,intn)JD*s,*h;inti;h=(JD*)malloc(sizeof(JD);h-data=0;h-link=NULL;for(i=n;i0;i-)s=(JD*)malloc(sizeof(JD);s-data=ai-1;s-link=h-link;h-link=s;return(h);,9,单链表基本算法,删除：单链表中删除b，设p指向a算法描述算法评价,-,voiddlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);,p-link=p-link-link;,10,单链表特点,它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢,-,11,请编程序建立一个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束。（链表头结点的data域不放数据，表空的条