赞
踩
顺序表是一组连续的存储单元来依次存储线性表中的结点,而链表是用一组任意的存储单元来存放线性表中的结点,这组存储单元可不连续分布在内存中的任何位置上。因此,链表中结点的逻辑顺序与存储顺序不一定相同。为了体现各结点存储单元之间的逻辑关系,再存储每个结点的同时,还必须存储与之联系的相邻结点的地址信息,这个信息称为指针或链。在C语言中,可以用指针实现。根据不同的链接方式,链表可以分为单链表,循环链表和双向链表。这里先介绍单链表的建立。
在单链表中,每个结点只有一个指针域指向下一个结点的地址,因此每个结点包括数据域和指针域。
第1个结点a1无前趋,故应设一个头指针head存储第1个结点的地址,也是链表的起始地址。由于最后一个结点a4无后继,因此它的指针域(指向下一个结点的地址)为空。
用C语言描述单链表的结点结构如下:
- typedef int datatype;
- typedef struct node //结点类型定义
- {
- datatype data;//结点的数据域类型
- struct node *next;//结点指针域类型
- } linklist;
建立单链表
为了建立一个能具体操作的单链表,假设结点的数据类型为字符型,下面介绍两种建立字符链表的方法。
1)头插法建表
头插法是按结点的逆序方法逐渐将结点插入到链表的头部,如图
头插法程序设计如下:
- linklist *CreatList1()
- {
- char ch;
- linklist *head,*p;
- head=NULL;//开始链表的头指针为空
- ch=getchar();// 输入最后一个结点字符值
- while(ch!='#')//输入为#时结束增加结点
- {
- p=(linklist *)malloc(sizeof(linklist));//分配内存
- p->data=ch;
- p->next=head;//使新增结点的指针域的值等于原链表的头指针head值,使其指向
- //原链表的头结点,达到新节点链到链表的头部目的
- head=p;
- ch=getchar();
- }
- return head;//返回头指针
- }
头插法建立链表的算法简单,但是生成链表的结点顺序与输入顺序想反,但人们习惯使用下面的尾插法。
2)尾插法建表
尾插法按结点的顺序逐渐将结点插入到链表尾部。
尾插法程序设计如下:
- linklist *CreatList2()
- {
- char ch;
- linklist *head;
- linklist *p;//p始终指向新分配的结点空间
- linklist *e;//e始终指向新建链表的尾结点
- head=NULL;
- e=NULL;
- ch=getchar();
- while(ch!='#')
- {
- p=(linklist *)malloc(sizeof(linklist));
- p->data=ch;
- if(head==NULL) head=p;
- else e->next=p;
- e=p;
- ch=getchar();
- }
- if(e!=NULL) e->next=NULL;
-
- return head;//返回头指针
- }
下节会继续介绍链表的查询,插入,删除。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。