有了动态内存分配的基础,要实现链表就不难了。
所谓链表,就是用一组任意的存储单元存储线性表元素的一种数据结构。链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。所谓单链表,是指数据接点是单向排列的。一个单链表结点,其结构类型分为两部分:
1、数据域:用来存储本身数据
2、链域或称为指针域:用来存储下一个结点地址或者说指向其直接后继的指针。
例:
typedef struct node { char name[20]; struct
node *link; }stud;
这样就定义了一个单链表的结构,其中char
name[20]是一个用来存储姓名的字符型数组,指针*link是一个用来存储其直接后继的指针。
定义好了链表的结构之后,只要在程序运行的时候在数据域中存储适当的数据,如有后继结点,则把链域指向其直接后继,若没有,则置为NULL。
单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。 注意:
链表由头指针唯一确定,单链表可以用头指针的名字来命名。 下面就来看一个建立带表头(若未说明,以下所指链表均带表头)的单链表的完整程序。
#include <stdio.h> #include <malloc.h> #define N
10 typedef struct node { char name[20]; struct node
*link; }stud; stud * creat(int n) { stud *p,*h,*s; int
i; if((h=(stud
*)malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } h->name[0]='\0'; h->link=NULL; p=h; for(i=0;i<n;i++) { if((s=
(stud *)
malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->link=s; printf("请输入第%d个人的姓名",i+1); scanf("%s",s->name); s->link=NULL; p=s; } return(h); } main() { int
number; stud
*head; number=N; head=creat(number); }
这样就写好了一个可以建立包含N个人姓名的单链表了。写动态内存分配的程序应注意,请尽量对分配是否成功进行检测。
|