优秀的链表ppt精编版

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

2、指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针单链表 实现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 算法评价pabxss-link=p-link;p-link=s; 1OnTvoid dlbcr(JD *p,int x)JD *s;s=(JD*)malloc(sizeof(JD);s-data=x

4、;s-link=p-link;p-link=s;单链表基本算法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;单链表基本算法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

5、=n;i0;i-)s=(JD*)malloc(sizeof(JD); s-data=ai-1; s-link=h-link; h-link=s;return (h);单链表基本算法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;单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢 请编程序建立一个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束。（链表头结点的data