补充内容_单向链表课件.pptVIP

补充内容：单向链表 信息工程系 8.6 用指针处理单向链表 通过组合使用结构和指针创建强大的数据结构（此节将讨论一种使用结构和指针的技巧，即单向链表） 这不仅因为它非常有用，而且许多用于操纵链表的技巧也适用于其它数据结构（如队列、栈等）。 8.6.1 链表的概述 链表的概念 链表：（linked list）就是一些包含数据的独立数据结构（通常称为节点）的集合。也就是说链表就是一种数据结构，是一组结点（node）的集合序列。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配（内存单元）的。 链表概述（谭浩强） 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。 下图表示最简单的一种链表(单向链表)的结构。 链表的构成 链表有一个“头指针”变量，图中以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。可以看出，head指向第一个元素；第一个元素又指向第二个元素……直到最后一个元素，该元素不再指向其他元素，它称为“表尾”，它的地址部分放一个“NULL”(表示“空地址”)，链表到此结束。 链表中的结点 前面介绍的结构体类型，用它作链表中的结点是最合适的。 struct　student { int　num； float　score； 　 struct　student *next； }； 8.6.2　处理动态链表所需的函数 1．malloc函数 其函数原型为 void *malloc(unsigned int size); 其作用是在内存的动态存储区中分配一个长度为size的连续空间。 malloc函数 此函数的返回值是一个指向分配域起始地址的指针(基类型为void)。 如果此函数未能成功地执行（例如内存空间不足），则其返回空指针（NULL） 。 2． calloc函数 其函数原型为 void *calloc(unsigned n, unsigned size);其作用是在内存的动态区存储中分配n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，返回NULL。 用calloc函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为size。 3． free函数 其函数原型为 void free(void *p); 其作用是释放由p指向的内存区，使这部分内存区能被其他变量使用。p是调用calloc或malloc函数时返回的值。free函数无返回值。 8.6.3　建立动态链表 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。 例 写一函数建立一个有3名学生数据的单向动态链表。 　 建立链表的函数可以如下： #define NULL 0 #define LEN sizeof(struct student) struct student { long num; int score; struct student *next; }; int n; /*n为全局变量，本模块中各函数均可使用它*/ struct student *creat(void)/*定义函数。此函数带回一个指向链表头的指针*/ { struct student *head； struct student *p1，*p2； n=0； p1=p2=( struct student *) malloc(LEN)；/*开辟一个新单元*/ scanf(%ld,%d ,p1-num,p1- score)； head=NULL； while(p1-num!=0) { n=n+1; if(n==1) head=p1; else p2-next=p1; p2=p1; p1=(struct student *)malloc(LEN); scanf(%ld,%d ,p1-num,p1- score); } p2-next=NULL; return(head); } 在main函数中调用creat函数： main( ) { struct student *head; head=creat( ); /*调用creat函数 后建立了一个单向动态链表*/ …… }