资源描述：
《C语言程序设计 教学课件 作者 唐云廷第12章 链表及其应用(09_09_NIT_L).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第12章链表及其应用112.1链表的定义链表是一种重要的数据结构,它能根据需要动态分配存储空间,可以节省内存空间.最简单,基本的单向链表,其结构如下:1249headA13561249B14751356CD14751021NUll1021表尾说明：a.“头指针”变量,现用head表示,存放一个地址,即指向表中第一个元素(结点).头指针(表头)元素(结点)21249headA13561249B14751356CD14751021NUll1021头指针(表头)元素(结点)表尾单向链表示意图b.每个元素有二部分内容:(1).实际数据.(2).下一个元素(结点)的地址.3124
2、9headA13561249B14751356CD14751021NUll1021c.从图中可看出:head指向第一个元素d.第一个元素又指向第二个元素,……直到最后一个元素,它的地址部分放一个“NULL”,即意为空地址,链表到此结束.41249headA13561249B14751356CD14751021NUll1021e.还可以观察到,表中各元素在内存中可以不连续,要访问其中一个元素,只要找到上一个元素,根据它的地址部分就可以找到下一个元素.如果不提供“头指针”(head),整个链表将无法访问.5链表的实现可用如下结构体类型:structstudent{intnu
3、m;floatscore;structstudent*next;}8910189.5numscorenext89107868910390成员next是指针类型, 指向本结构体类型.利用上述结构可建立如下形式的链表:6介绍几个有关函数:刚才定义的structstudent类型,并未实际分配内存 空间.动态开辟和释放一片存储单元可用下列函数:内存分配函数:(1).void*malloc(unsignedsize)在内存申请一个长度为size的连续空间,函数返回值是一个指向已分配内存的起始地址的指针.如果申请失败,则返回0.(2).voidfree(voidptr)ptr是最
4、近一次调用malloc()函数的返回值.其作用就是释放由ptr指向的一片内存区.7关于void是指针类型:可以用void定义一个指针变量,它可以指向一个抽象(或空)的类型数据.在将它的值赋予另一个指针变量时,要进行强制类型转换,使它变成适合于被赋值的变量类型.如:char*p1;void*p2;….p1=(char*)p2;8二.长度运算符:sizeof()长度运算符可以用来计算某种类型的对象,在内存中所占的字节数.该操作符使用的语法形式:sizeof(类型名)或:sizeof(表达式)如：main(){inti=4,j=2; i=i+j;printf("%d,%d
5、",sizeof(int),sizeof(i=i+j));}输出结果：4，4运算结果为所指定的类型,或“表达式”结果的类型所占的字节数.并不计算表达式本身的值.9例:设变量定义为charcc[]=“12345”,则表达式sizeof(cc)的值是7.102.链表的建立:例:编一个函数,建立一个5个学生数据的单向链表.先 分析一下实现的过程:(1).先定义三个结构体类型指针变量:head,p1,p2用malloc()开辟一个结点,用指针p1,p2指向它,然后将一个学生的数据读入该结点.8910189.5p1p211约定:(1).输入的学号不为零,如果为零,则结束.(2
6、).head值先为NULL如果输入的P1→num不等于零,又同时是给第一个结点输入数据时(n=1),则令head=P1:head8910189.5p1p2n=112(2).然后接着开辟下一个结点,并使p1指向它,并输入第二个结点的数据:8910189.5p2head8910390n=2p113(3).如果输入的第二个节点的num≠0,(也即:p1->num≠0),则把第二个结点链入表内.8910189.5p2head(由于n≠1),将:P1的值赋给P2→next,也就是使第一个结点的next成员指向第二个结点.8910390p114(4)然后,通过语句:P2=P1,使P
7、2指向刚建立的结点.8910189.58910390n=2headp1p2p215(5).再开辟一个结点,并使p1指向新结点,同时读入新结点的数据.8910189.58910390headp2p18910785n=316(6).这时n=3,使P1的值赋给P2→next,(即接入第三个结).并使P2=P1,使P2指向最后一个结点.8910189.58910390head8910785p1p2n=3p217(7).再开辟一个新结点,并使P1指向它,输入该结点的数据,设:P1→num的值为0.8910189.58910390head891078
