第十二讲 链表研究分析.ppt

链表,内容要点,链表的概念链表的创建链表的遍历,3,链表的概念,一种按需动态分配内存进行存储的数据结构若干个同一结构类型的“结点”依次串接而成单向链表(即只能从头开始访问其它结点）、双向链表,4,链表的概念存储结构,线性表顺序存储结构特点：占用连续的内存空间链式存储结构特点：一般占用不连续的内存空间,直观地画成,1,2,3,4,5,顺序号,5,链表的概念数据类型,链表的图示链表组成一个链表由若干个结点组成结点组成数据(程序中要使用的数据)地址(下一个结点的地址)结点数据的存储数据类型,6,链表的概念数据类型,结构体,structlistintdata;structlist*next;,typedefstructlistintdata;structlist*next;LIST;,或者,数据域,指针域,返回,7,链表的创建,链表是一种动态地进行存储分配的数据结构，即根据需要动态地创建若干结点，并将其连成一个链。创建一个结点的步骤？1）开辟一个结点的内存空间2）给结点的数据域赋值3）给结点的指针域赋值如何开辟结点的内存空间？求字节数运算符强制类型转换运算符,8,求字节数运算符,sizeof(类型名)例如：intx,y;x=sizeof(int)计算一个int数据在内存占用的字节数y=sizeof(double)计算一个double数据在内存占用的字节数sizeof(变量名)例如：intdata=4;intlen;len=sizeof(data);计算int型变量data在内存占用的字节数,9,强制类型转换运算符,(类型名)分析以下程序的输出结果,#includevoidmain()floatx;x=(float)(5/2);printf(“%fn”,x);x=(float)5/2printf(“%fn”,x),输出结果：2.0000002.500000,10,开辟内存空间,void*malloc(unsignedintsize)函数返回值void*:返回值为开辟空间的首地址函数的形参开辟空间的大小(即空间的字节数),11,创建链表中的一个结点,符号常量NULL代表0，表示“空地址”例如：int*p1=NULL;int*p2=0;p1和p2指针，不指向任何对象用于标识链表中的尾结点，即尾结点的指针域值为NULL,#includetypedefstructlistintdata;structlist*next;LIST;voidmain()LIST*p,*head;head=(LIST*)malloc(sizeof(LIST);p=(LIST*)malloc(sizeof(LIST);p-data=30;p-next=NULL;head-next=p;,12,创建一个链表,创建链表的基本步骤定义结点数据类型定义指针变量创建结点数据域赋值指针域赋值,#includetypedefstructlistintdata;structlist*next;LIST;voidmain()LIST*p1,*p2,*p3,*head;head=(LIST*)malloc(sizeof(LIST);p1=(LIST*)malloc(sizeof(LIST);p1-data=34;head-next=p1;p2=(LIST*)malloc(sizeof(LIST);p2-data=10;p2next=p1;p3=(LIST*)malloc(sizeof(LIST);p3-data=56;p3-next=NULL;,从头到尾依次创建链表的各个结点,注意：尾结点的地址值为NULL或0,13,自定义函数实现创建链表,#include#defineN5typedefstructlistchardata;structlist*next;SLIST;SLIST*creatlist(char*a)SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST);for(i=0;idata=ai;p-next=q;p=q;p-next=NULL;returnh;main()SLIST*head;charaN=a,b,c,d,e;head=creatlist(a);,head,h,a,q,p,b,q,p,p,c,q,p,创建过程的演示图,d,q,p,q,p,e,NULL,返回,14,链表的遍历,head指向链表的头结点定义一个指针变量pp=head-next;循环(注意条件)while(p!=NULL)printf(“%c”,p-data);p=p-next;,移动指针,15,自定义函数实现创建链表，并输出,#include#defineN5typedefstructlistchardata;structlist*next;SLIST;SLIST*creatlist(char*a)SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST);for(i=0;idata=ai;p-next=q;p=q;p-next=NULL;returnh;,voidoutlist(SLIST*h)SLIST*p;p=h-next;while(p!=NULL)printf(%5c,p-data);p=p-next;main()SLIST*head;charaN=a,b,c,d,e;head=creatlist(a);outlist(head);,16,内容总结,结点的数据