《第十章 用指针处理链表.ppt》由会员分享，可在线阅读，更多相关《第十章 用指针处理链表.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第十章第十章 用指针处理链表用指针处理链表第一节第一节 链表概述链表概述1 链表概述链表概述1）数据结构的组织形式：）数据结构的组织形式：非线性表：树、图等非线性表：树、图等 线性表：datappdatappdatappdatappdatapp 线性表：线性表：顺序存储：如数组等顺序存储：如数组等 链式存储链式存储:单向链表、双向链表等单向链表、双向链表等用指针处理链表（续 2）p 100p 150datap 120datap 230datap 000datahead1001501202302）链表概念：）链表概念：用结构体作为一个数据单位，每个结构体构成一个结用结构体作为一个数据单位，每个
2、结构体构成一个结 点，用指针把结点一一链接起来，构成链表点，用指针把结点一一链接起来，构成链表 结构体的数据组成：结构体的数据组成：两部分：数据、指针两部分：数据、指针 例：例：struct node int num;float score;struct node *p;用指针处理链表（续 3）3）链表的特点链表中各结点具有相同的结构链表的结点由系统随机分配，节点之间的联系通过指针域实现为准确的定位第一个结点，每链表要有一个表头指针链表的节点需要时用mallocz()函数或calloc()函数申请内存，不需要时，使用free()函数释放所占内存段不需实现说明节点数目，只在需要时增加或减少结点。
3、2 简单链表（不讲）简单链表（不讲）#define NULL 0 void main()struct student struct student a,b,c,*head,*p;int num;a.num=100;a.score=89;float score;b.num=101;b.score=90;struct student *sp;c.num=102;c.score=95;head=&a;a.sp=&b;b.sp=&c;c.sp=NULL;p=head;do printf(“%d,%f”,p-num,p-score);p=p-sp;while(p!=NULL);a.num 100a.sc
4、ore 89a.sp&bb.num 101b.score 90b.sp&cc.num 102c.score 95c.sp 0head&ap&a&b&c 03 内存动态分配和释放的函数内存动态分配和释放的函数 1）分配存储空间的函数）分配存储空间的函数 void *malloc(unsigned size);分配一个长度为分配一个长度为 size 字节的连续存储空间，成功执字节的连续存储空间，成功执 行，返回所分配的存储空间的起始地址，执行失败，行，返回所分配的存储空间的起始地址，执行失败，返回返回 0 地址地址 2）释放所分配的存储空间）释放所分配的存储空间 void free(void*p)
5、;释放由释放由 p 所指向的存储空间所指向的存储空间 例：例：4 建立结点的一般过程1）向系统申请一个内存段，大小由单个链表结点的数据类型决定。2）给该内存段制定数据类型3）给申请到的结点添加数据例：例：struct student*bp;bp=(struct student*)malloc(sizeof(struct student);bp-num=100;bp-score=95;。free(p);num 100score 95bp,psp5 建立新链表的一般过程即将节点一个个按顺序建立（从第一个结点开始）1）向系统申请一个内存段，大小由单个链表结点的数据类型决定。若是第一个结点，链表表头指
6、针head指向该内存地址。若不是，则是上一个结点的指针域指向该内存地址。2）给该内存段制定数据类型3）给申请到的结点添加数据（为结构体变量的各个成员赋值4）若本末结点，其指针域赋空指针值NULL。否则，返回1），继续建立下一个节点。动态链表的建立动态链表的建立例（不讲）例（不讲）#define L struct student*creat()sizeof(struct student)struct student *head,*p;#define NULL 0 head=(struct student*)malloc(L);struct student head-sp=NULL;int num
7、;p=(struct student*)malloc(L);float score;scanf(“%d,%s”,p-num,p-score);struct student *sp;while(p-num!=0);p-sp=head-sp;head-sp=p;p=(struct student*)malloc(L);scanf(“%d,%f”,p-num,p-score);return head;sp0 10 20 30 num 100 score 89 sp 20 num 101 score 90 sp 10 num 102 score 95 sp 010 20 30p 20 3010head
8、第二节 链表的基本操作一 链表结点的插入1 空链表中插入一个结点1）申请一个new结点（即链表的第一个节点，也是最后一个）如：new=（struct node*）malloc（sizeof（struct node）；2）为结点填数据，将要存得到数据对应传给数据域的各个成员3）修改有关的指针指向 如：new-next=NULL;head=new;2 在链表的p结点后插入一个结点1）使new的指针存d的首地址：new-next=p-next;2）把new的首地址存在p的指针域：p-next=new;10010 10010 68.5 68.5 10011 10011 77.8 77.8 headhe
9、adb bc c100121001288.5 88.5 NULL NULL d dnewnew2000200080.5 80.5 p例141二 链表结点的删除把制定的节点从链表中拿出：修改有关结点的指针域释放该结点的内存空间1）若p结点是链表的第一个节点：p指针域的地址保存在head中2）若不是第一个结点，找到p前一个链表q-next=p-next3）释放结点空间三三 链表的输出链表的输出#define NULL 0 void print(struct student *head)struct student struct student *p;int num;p=head-sp;float
10、score;while(p)struct student *sp;printf(“%d,%f”,p-num,;p-score);p=p-sp;用指针处理链表（续 7）sp0 10 20 30 num 100 score 89 sp 20 num 101 score 90 sp 10 num 102 score 95 sp 010 20 30p 20 3010head 四四 链表的检索和删除链表的检索和删除#define NULL 0 struct student*del(struct student *head,int num)struct student struct student *p1
11、,*p=head-sp;int num;if(p)float score;while(p-num!=num)&(p)struct student *sp;p1=p;p=p-sp;if(p-num=num)p1：被删去结点的：被删去结点的 p1-sp=p-sp;前一结点前一结点 p：被删去的结点：被删去的结点 return p;p 20 30headsp 30 num 100 score 89 sp 20 num 101 score 90 sp 10 num 102 score 95 sp 010 20 3010num 101p1 307 链表的检索和插入链表的检索和插入 void insert
12、(struct student *head,#define NULL 0 struct student *ip)struct student struct student *p1,*p=head-sp;int num;if(p=0)p-sp=0;head-sp=p;float score;else struct student *sp;while(p-num num)&(p);p1=p;p=p-sp;在在 p1 和和 p 之间插入之间插入 ip-sp=p;p1-sp=ip;headsp 30 num 100 score 89 sp 20 num 101 score 90 sp 10 num 112 score 95 sp 010 20 30num 110score 96sp 1050p1 30 20p 30 20 10ip 5050