C语言-链表.ppt

111.7 用指针处理链表用指针处理链表1.链表概述链表概述1)动态数据结构概念 数组和结构体是定长数据结构，而链表、堆栈、队列、树、图等是执行时大小可变的动态数据结构。链表是连成一行连成一行的数据项集合，每一个数据项(元素)称为节点，可以在链表中的任意位置进行节点插入或删除操作，使链表数据项的个数随之增加或减少。22)链表的构成单向链表图示：单向链表图示：1048 1370 1012 头节点 表内节点 尾节点 210189.513702304901012291885NULL1048head其中：其中：各节点是相同的结构体类型，该类型有三个成员；head是指针变量，存放链表的头节点指针1048；各节点应包含一个指针成员存放下一节点的地址；各节点存储有可能不连续，但各节点逻辑上连续。33)节点的构成上图每个节点具有如下结构体类型：struct student long num;float score;structer student *next;/*链节成员*/其中：其中：成员num、score用于存放一个节点的具体数据；成员next是指针类型，用于存放下一节点指针，最后一个节点的next 成员存放空指针NULL；成员next是指向与自身同一类型的结构，这种结 构称为自引用结构。(只有指针成员可自引用)节点是在运行时动态生成的。44)动态内存分配和释放 建立和维护动态数据结构需要实现动态内存分配；如在链表中插入节点需要先申请一段存储区域，而删除一个节点需要释放该节点原先占用的存储区域，这可由标准函数实现。内存分配函数原形：内存分配函数原形：void*malloc(unsigned size);功能：功能：申请长度为size个字节的内存空间；若申请 成功，返回存储块起始指针，该指针类型为 void*；否则返回空指针(NULL)。内存释放函数原形：内存释放函数原形：void free(void*p);功能：功能：释放p所指向的内存块。包含文件：包含文件：malloc.h、stdlib.h中均有其原型声明。55)采用链表的意义与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。即：链表特别适合于对大线性表频繁插入和删除元素、或成员数目不定的数据结构。66)链表的类型单链表：单链表：每个节点只有一个指向后继节点的指针双向链表：双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点循环链表：循环链表：使最后一个节点的指针指向第一个节点72.单链表的建立和输出单链表的建立和输出建立链表的准备工作建立链表的准备工作:1)定义链表的节点类型；2)定义与节点同类型的链表头指针变量head并赋值0，表示链表在建立之前是空的；3)定义与节点同类型的工作指针变量p1、p2。8建立链表的步骤：建立链表的步骤：1)开辟第一个节点的存储区域，使head、p1、p2 指向第一个节点，并输入第一个节点数据；210189.5headp1p2操作：操作：len=sizeof(struct student);p1=(struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);head=p2=p1;92)开辟下一节点的存储区域，使p1指向新节点、输入新节点数据，并将上一个节点的next成员 指向新节点；210189.5headp1p22304901048操作：操作：p1=(struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);p2-next=p1;p2=p1;/*使p2也指向新节点*/13701370p2p1103)重复第2步，建立并链接多个节点直至所需长度，将末尾节点的next成员赋值0。210189.51370headp2230490291885p2NULL1048 1370p110121012p2p1操作：操作：p1=(struct student*)malloc(len);scanf(%ld,%f,&p1-num,&p1-score);p2-next=p1;p2=p1;/*使p2也指向新节点*/p2-next=NULL;/*末尾节点next赋值0*/11【例】建立并输出有3名学生数据的单链表。#include /*包含NULL的定义*/#include#define N 3struct student /*结构体类型定义*/long num;float score;struct student*next;/*自引用结构体指针*/;void main()12void main()struct student*head,*p1,*p2;int i,len;sqrt(5.5);/*TC激活浮点运算*/head=NULL;/*head不指向任何位置*/len=sizeof(struct student);/*求类型长*/for(i=1;inum,&p1-score);if(i=1)head=p2=p1;/*指向首节点*/else p2-next=p1;p2=p1;/*节点链接*/if(i=N)p2-next=NULL;/*标记末尾节点*/13 void main()for(i=1;i=N;i+)/*建立链表*/for(i=1;inext;/*p1指向下一节点*/printf(%d:num=%ld,score=%5.2fn,i,p1-num,p1-score);/*main*/14【例】将上题利用函数实现，并求平均成绩。定义如下函数：定义如下函数：建立链表函数:struct student*create(void);输出链表函数:void plink(struct student*head);求平均值函数:float averf(struct student*head);函数间信息传递：函数间信息传递：主函数createplinkaverf无参头指针头指针无返回值平均值头指针15#include#include#define N 3struct student /*全局结构类型*/long num;float score;struct student*next;void main()16void main()struct student*head,*create(void);void plink(struct student*head);float averf(struct student*head);int i,len;float aver;sqrt(5.5);clrscr();/*TC中使用 head=NULL;head=create();/*返回链表头指针*/plink(head);aver=averf(head);/*返回平均值*/printf(Average=%5.2fn,aver);17struct student *create()struct student*head,*p1,*p2;int i,len;len=sizeof(struct student);for(i=1;inum,&p1-score);if(i=1)head=p2=p1;/头节点 else p2-next=p1;p2=p1;/中间节点 if(i=N)p2-next=NULL;/尾节点 return(head);/返回链表头指针 18void plink(struct student*head)/*输出各节点*/struct stduent*p;int i;for(i=1;inext;printf(%d:num=%ld,score=%5.2fn,i,p-num,p-score);return;PP19float averf(struct student*head)struct student*p;float sum=0;int c=0;p=head;/*使p指向首节点*/while(p!=NULL)c+;/*c统计节点数*/sum=sum+p-score;p=p-next;return(sum/c);/*返回平均值*/2013703.节点的删除节点的删除步骤：步骤：1)从头节点开始按查找关键字查找要删除的节点；2)找到，则将要删除节点的“链节”成员赋给前一节点的“链节”成员，使删除的节点脱离链表。若：要删除节点为首节点，则将首节点“链节”成 员赋给链头指针变量。3)释放已被删除节点占用的空间。1048 1012210189.51370head2304901012pNULL1048291885101221【例】按上例删除指定学号的节点struct student*del(struct student*head,long n)struct student*p1,*p2;/*n：要删除学号*/p1=head;if(p1-num=n)head=p1-next;/*删除首节点*/else do p2=p1;p1=p1-next;/*继续找*/while(p1!=NULL&p1-num!=n);if(p1-num=n)p2-next=p1-next;/*找到*/else printf(Not be found!n);/*未找到*/free(p1);/*释放被删除节点的存储区*/return(head);/*返回头指针*/22void plink(struct student*head)/*更具通用性*/struct student*p;p=head;while(p!=NULL)printf(num=%ld,score=%5.2fn,p-num,p-score);p=p-next;return;注：注：本形式的链表输出函数具有通用性，可适应由于删除或插入节点引起的链表长度的变化。234.节点的插入节点的插入 插入可分为随意插入和按顺序插入，随意插随意插入入包括插入到头部、尾部或中间指定位置；按顺按顺序插入序插入是指按某关键字的顺序插入，而在插入前链表必须已按该关键字进行了排序。按顺序插入的步骤：按顺序插入的步骤：1)开辟待插入节点的存储区域并输入数据；2)查找插入位置：从链表首节点开始按关键字成 员与待插入节点相同成员进行比较，直到确定了插入位置；243)将插入位置前一节点的“链节”成员赋给待插入节 点的“链节”成员；若：插入点在链头，则将头指针赋给待插入节点的 “链节”成员；4)将待插入节点的指针赋给前一节点“链节”成员；若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。210189.51370head 10482304901012241478 1048 1370 1012101226802680291885NULL25【例】按上例在链表中按学号顺序插入节点插入函数：插入函数：struct student*insert(struct student*head)struct student*p0,*p1,*p2;long n;int len;len=sizeof(struct student);p0=(struct student*)malloc(len);/*申请新节点*/printf(Enter num,score to insert:);scanf(%ld,%f,&p0-num,&p0-score);n=p0-num;/*产生学号副本n*/p1=head;/*从首节点开始查找*/26 p1=head;/*插入在头部*/if(nnum)p0-next=head;head=p0;else do /*查找插入位置*/p2=p1;p1=p1-next;while(p1!=NULL&np1-num);p0-next=p2-next;/*插入在其余位置*/p2-next=p0;return(head);/*insert*/27【例】编写一个通用的函数，可根据需要建立任意节点数的链表。struct student *creat()/*无参有返回值*/struct student*head=NULL,*p1,*p2;int len;long n;float s;len=sizeof(struct student);while(1)/*循环次数不确定*/printf(Enter number,score:);scanf(%ld,%f,&n,&s);if(n=0)break;/*输入0表示数据结束*/p1=(struct student*)malloc(len);return(head);28 while(1)printf(Enter number,score:);scanf(%ld,%f,&n,&s);if(n=0)break;/*以0表示数据结束*/p1=(struct student*)malloc(len);p1-num=n;p1-score=s;/*转存入节点*/if(head=NULL)head=p2=p1;else p2-next=p1;p2=p1;p2-next=NULL;/*末尾链节成员赋空*/return(head);/*返回链表头指针*/*creat*/