登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

sunwenhua168的博客

海纳百川,有容乃大

 
 
 

日志

 
 

链表类型   

2009-09-23 20:45:53|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

链表类型

链表类型  - sunwenhua168 - sunwenhua168的博客链表的基本结构

    链表结构是利用指针进行动态存储分配的最简单的一种结构。动态存储分配是指根据需要临时分配内存单元以存放有用的数据,当数据不用时又可以随时释放存储单元,此后这些存储单元又可以用来分配给其它数据使用。在前面的程序中,一个变量如果被指定为全局变量,它在整个程序运行期间都占据存储单元.

  例如:如果要存放一个班的学生的数据(如学号、姓名、各门成绩等)就要定义一个数组。如果不能事先不能确定人数的多少,就要定义一个足够大的数组;可以看出,用这种方法处理问题缺乏灵活性,往往会浪费许多内存。链表是指若干个数据(每一个数据组称为一?quot;结点")按一定的原则连接起来。这个原则是:前一个结点"指向"下一个结点,只能通过前一个结点才能找到下一个结点。不象对数组元素的访问可以是随机的。

    链表中每个元素称为结点,图中链表的每个结点包含两个域,一个域中存放数据,另一域中存放下一个结点的地址。在表尾结点中,由于不必指向任何地址,因此放入一个NULL值。NULL是一个符号常量,被定义为0,也就是将0地址赋给最后一个结点中的地址项。 链表中的每个结点至少应该包含两个域:用一个域来存放数据,其类型根据存放数据的类型而定(例如可以是结构体类型的数据);另一个域用来存放地址,因此必然是一个指针类型,此指针类型是所指向的表结点的类型。

注意:链表中各结点在内存中并不是占连续的一片内存单元。各个结点可以分别存放在内存的各个位置,只要知道其地址,就能访问此结点。当链表结点中的指针失去了下一个结点的地址后,链表就会断开,其后的结点将会全部丢失。

    当使用链表结构时,如果需要,可以采用适当的操作步骤使链表加长或缩短,而使存储分配具有一定的灵活性。

链表类型  - sunwenhua168 - sunwenhua168的博客用含指针项的结构体变量构成结点

链表中的每一结点是由两部分组成的:

(1)对用户有用的数据,是链表的结点的实体部分。

(2)用来存放下一个结点地址的一个指针类型数据项,是用来建立结点间的联系的,也就是用它来构成"链"。用C语言实现链表这种数据结构是很方便的。包含指针项的结构体变量就是一个结点。例如:

struct stud_ score

{

long num;

float score;

struct stud_score *next;

};

num和score成员用来存放学号和成绩,next是指针变量,它指向struct stud_score类型的变量。next指针项必须指向与next所在的结点是同一类型的结点。

可以用下面的方法建立一个简单的链表:

struct stud_score stud1,stud2,stud3,stud4,*head;

stud1.num=970101; stud1.score=85.5; /* 赋值 */

stud2.num=970102; stud2.score=90.5;

stud3.num=970103; stud3.score=75.5;

stud4.num=970104; stud4.score=68.0;

head.next=&stud1; /* 形成链 */

stud1.next=&stud2;

stud2.next=&stud3;

stud3.next=NULL;

用以上方法可建立一个简单链表。用户不必其体了解每个结点中next成员的值是什么,只需将需要链入的下一结点的地址赋给它即可。系统在对程序编译时对每一个变量都分配了确定的地址。

注意:head不是一个结构体变量而只是一个指向结构体变量的指针变量,它不包括有用数据

链表类型  - sunwenhua168 - sunwenhua168的博客输出链表中的数据

对于前面已建立的链表,如果想逐项输出其中学生的数据,可用以下函数来实现。

void print(void)

{

struct stud_score *p;

int i;

if(head==NULL)

{

printf("\nempty list.\n");

return;

}

p=head; /* 使指向第一个结点 */

do {

printf("\nrecord number%d\n",++i);

printf("num:%ld\n",p->num);

printf("score:%6.1f\n",p->score);

p=p->next;

}

while(p!=NULL)/* 输出最后一个结点不再输出*/

head代表链表的头指针,p从第一个结点开始,通过p=p->next操作,顺序指向链表中的每一个结点并输出该结点内容,直到遇到最后一个结点。 以上的方法虽然也能实现简单的链表结构,但它必须在程序中事先确定个数的结构体变量(结点),这就缺乏灵活性,想再增加一个结点就要修改程序,并且所有结点都自始至终占据内存单元,而不是动态地进行存储分配。为了能动态地开辟和释放内存单元,要用到C标准函数库中的malloc函数和free函数。

链表类型  - sunwenhua168 - sunwenhua168的博客用于动态存储分配的函数

C语言新标准ANSI C要求各C编译版本提供的标准库函数中应包括动态存储分配的函数,它们是:

malloc( );

calloc( );

free( );

recalloc( );

1.malloc函数

其作用是在内存开辟指定大小的存储空间,并将此存储空间的起始地址作为函数值带回。

malloc函数的形式: void *malloc(unsigned int size) 或 char *malloc(unsigned int size)

它的形参size为无符号整型。函数值为指针(地址),例如:用malloc(8)来开辟一个长度为8个字节的内存空间,如果系统分配的此段空间的起始地址为1362,则malloc(8)的函数返回值为1362。

如果内存缺乏足够大的空间进行分配,则malloc函数值为"空指针",即地址为0。

2.calloc函数

其函数模型为: void *calloc(unsigned int num,unsigned int size)

它有两个形参num和size,其作用是分配num个大小为size字节的空间,例如:用calloc(10,16)可以开辟10个(每个大小为16字节)的空间,共160字节。函数返回值为该空间的首地址。

3.free函数其函数模型为: void free(void *ptr)

其作用是将指针变量ptr指向的存储空间释放,系统可以另分配。注意:ptr值不能是任意的地址,而是在程序中执行过的malloc或calloc函数所返回的地址。free函数无返回值。

4.realloc

用来使已分配的空间改变大小,即重新分配。其函数模型为: void *recalloc(void *ptr,unsigned int size)其作用是将ptr指向的存储区(用malloc函数分配的)的大小改为size个字节。它的返回值是新的存储区的首地址。

使用这些函数时要用#include命令将stdlib.h文件包含进来。但有的系统用malloc.h而不是stdlib.h。在使用时请注意系统的规定。有的系统则不要求包括任何"头文件"。

  评论这张
 
阅读(2201)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018