优秀的链表ppt.pptx

《优秀的链表ppt.pptx》由会员分享，可在线阅读，更多相关《优秀的链表ppt.pptx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、链表成俊燕mail：链表的定义节点离散分布节点之间通过指针连接每个节点只有一个前驱，一个后继节点首节点没有前驱，尾节点没有后继术语：首节点，尾节点，头结点，头指针，尾指针。线性表的链式存储结构第3页特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点第4页ZHAOQIANSUNLIZHOUWUZHENGWANGH例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL37

2、71925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针单链表第5页实现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定义：结点中只含一个指针域的链表叫，也叫单 链表单链表基本算法l查

3、找：查找单链表中是否存在结点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在表中的序号否则，为n单链表基本算法l插入：在线性表两个数据元素a和b间插入x，已知p指向al算法描述l算法评价第7页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=

4、p-link;p-link=s;单链表基本算法l删除：单链表中删除b，设p指向al算法描述l算法评价第8页void dlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);pabcp-link=p-link-link;单链表基本算法l动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针l算法描述第9页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

5、*)malloc(sizeof(JD);s-data=ai-1;s-link=h-link;h-link=s;return(h);单链表基本算法l删除：单链表中删除b，设p指向al算法描述l算法评价第10页void dlbsc(JD*p)JD*q;if(p-link!=NULL)q=p-link;p-link=q-link;free(q);pabcp-link=p-link-link;单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢第11页请编程序建立一个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束。（链表头结点的data域不放数据，表空的条件是ph-next=NULL).有两个链表a和b。设结点中包含学号、姓名。从a链表中删去与b链表中有相同学号的那些结点。