创建链表
链表的物理存储结构是用一组地址任意的存储单元存储数据
链表结构中,存储的每个数据元素记录都存放到链表的一个结点(node)中,而每个结点之间由指针将其连接在一起。
链表存在以下特征:
1、每一个结点包括两部分:数据域和指针域、其中数据域用来存放数据元素本身的信息,指针域用来存放后继结点的地址。
2、链表逻辑上连续,物理上并不一定连续存储结点。
3、只要获得的头结点,就可以通过指针遍历整条链表
//链表结点用C语言描述:
typedef struct node{
ElemType data; //数据域
struct node *next; //指针域
}LNode, *LinkList;
定义一个指向LNode类型数据的指针类型变量时,语句LNode *L;
和 LinkList L;
是等价的。
建立一个链表的过程可以通过下面代码:
LinkList GreatLinkList(int n){
//建立一个长度为n的链表
LinkList p, r, list=NULL;
ElemType e;
int i;
for(i=1; i<=n; i++){
Get(e);
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=NULL;
if(!list)
list=p;
else
r->next=p;
r=p;
}
return list;
}
销毁链表
destroyLinkList()
的作用是销毁一个链表list。
1、首先将*list
的内容赋值给p,这样p也指向链表的第一个结点,成为了链表的表头
2、然后判断只要p不为空(NULL)
,就将p指向的下一个结点的指针(地址)赋值给q,并应用函数free()释放掉p所指向的结点,p再指向下一个结点。如此循环,直到链表为空为止。
3、最后将*list
的内容置为NULL
,这样主函数中的链表list
就为空了
void destroyLinkList(LinkList *list) {
LinkList p, q;
p=*list;
while(p){
q=p->next;
free(p);
p=q;
}
*list=NULL;
}