优秀的链表PPT课件.pptx

链表成俊燕mail：2024/1/30 周二1链表的定义节点离散分布节点之间通过指针连接每个节点只有一个前驱，一个后继节点首节点没有前驱，尾节点没有后继术语：首节点，尾节点，头结点，头指针，尾指针。2024/1/30 周二2线性表的链式存储结构可编辑特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点2024/1/30 周二3可编辑ZHAOQIANSUNLIZHOUWUZHENGWANGH例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针2024/1/30 周二4单链表可编辑实现typedef struct node datatype data;struct node *link;JD;JD *h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD*)malloc(sizeof(JD);系统回收p结点：free(p)n定义：结点中只含一个指针域的链表叫，也叫单链表2024/1/30 周二5单链表基本算法l查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULLl算法描述：l算法评价JD*dlbcz(JD*h,int x)JD*p;p=h;while(p!=NULL&p-data!=X)p=p-link;return(p);While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n2024/1/30 周二6单链表基本算法l插入：在线性表两个数据元素a和b间插入x，已知p指向al算法描述l算法评价可编辑pabxss-link=p-link;p-link=s;void dlbcr(JD*p,int x)JD*s;s=(JD*)malloc(sizeof(JD);s-data=x;s-link=p-link;p-link=s;2024/1/30 周二72024/1/30 周二8单链表基本算法l删除：单链表中删除b，设p指向al算法描述l算法评价可编辑void dlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);pabcp-link=p-link-link;2024/1/30 周二9单链表基本算法l动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针l算法描述可编辑JD*dlbjl(int a,int n)JD*s,*h;int i;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);2024/1/30 周二10单链表基本算法l删除：单链表中删除b，设p指向al算法描述l算法评价可编辑void dlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);pabcp-link=p-link-link;2024/1/30 周二11单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢可编辑2024/1/30 周二12请编程序建立一个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束。（链表头结点的data域不放数据，表空的条件是ph-next=NULL).2024/1/30 周二13有两个链表a和b。设结点中包含学号、姓名。从a链表中删去与b链表中有相同学号的那些结点。2024/1/30 周二142024/1/30 周二15