赞
踩
顺序表:顺序存储的线性表
链式表:链式存储的线性表,简称链表
由于顺序表的缺点(数据连续存储),顺序存储的数据因为挤在一起而导致需要成片移动,那很容易想到的解决方案是将数据离散地存储在不同内存块中,然后再用指针将他们串起来,这种朴素的思路所形成的链式线性表,就是所谓的链表。顺序表和链表存在的基本样态如下图所示
根据链表中各个节点之间使用指针的个数,以及首尾节点是否相连,可以将链表细分为如下种类:
1、单向链表
2、单向循环链表
3、双向循环链表
不同链表的操作都是差不多的,只是指针数目的异同
最简单的单向链表的示意图如下:
上图中,所有节点均保存一个指针,指向其逻辑上相邻的下一个节点(末尾节点指向空),整条链表用一个所谓的头指针head来指向,由head开始可以找到链表中的任意一个节点。head通常被称为给头指针。
1、节点设计
2、初始化空链表
3、增删节点
4、链表遍历
5、销毁链表
单向链表的节点非常简单,节点中除了要保存用户数据之外(以整形数据为例),只需要增加一个指向本类节点的指针即可
- //单向链表的节点设计
- typedef struct node
- {
-
- //数据域
- int data;
-
- //指针域
- //指向相邻的下一个节点的指针
- struct node* next;
-
- }node;
单向链表的初始化:
空链表有两种常见的形式,一种是带所谓的头结点,一种是不带头结点,所谓的头结点是不存放有效数据的节点,仅仅用来方便操作
注意:头指针head是必须的,是链表的入口。头结点是可选的,是为了方便某些操作。
由于头结点是不存放有效数据,因此如果空链表中带有头结点,那么头指针head将永远不变,一会给以后的链表操作带来些许便捷。
以带头结点的链表为例,首先是初始化单向链表
- node* init()
- {
- node* head = malloc(sizeof(node));
- if(head == NULL)
- {
- return NULL;
- }
-
- //将头结点的 next指针 置空
- //不对head的数据data任何处理
- head->next = NULL;
-
-
- return head;
- }
初始完单向链表之后,需要对链表执行增加节点,也可以对不为空的链表执行删除节点的动作。相对于顺序表需要整片移动数据,链表增删节点只需要修改几个相关指针的指向,动作非常快速。
与顺序表类似,可以对一条链表中的任意节点进行增删操作,在增加节点动作之前需要创建一个新节点,然后把这个节点插入到链表中
- //创建一个单向链表的新节点
- node* newNode(int data)
- {
- //分配一个新节点的内存
- node* new = malloc(sizeof(node));
- if(new == NULL)
- {
- return NULL;
- }
-
- //新节点的数据域与指针域
- new->next = NULL;
- new->data = data;
-
- return new;
- }
-
- //把一个节点头插到链表的表头
- void insertHead(node* head,node* new);
- {
- //新节点的指针域指向当前链表的首个节点
- new->next = head->next;
-
- //当前链表的收个节点更新为新插入的节点
- head->next = new;
- }
-
- //删除节点之前需要对链表进行一个判断,为空则删除失败
- bool isEmpty(node* head)
- {
- return head->next == NULL; //最简洁的判断方式,当链表不为空的时候除了头结点至少存在一个节点,那么头结点的指针域必定不指向空
- }
-
- //删除单向链表的节点
- node* removeNode(node* head,int data)
- {
- //创建一个临时节点用来帮助释放要删除的节点
- node* tmp;
-
- for(node* p = head;p != NULL;p = p->next)
- {
- if(p->next != NULL && p->next->data == data)
- {
- tmp = p->next;
- p->next = tmp->next;
- tmp->next = NULL;
- return tmp;
- }
- }
-
- return NULL;
- }
-
删除功能函数里面有不少代码和查找功能函数的实现效果是一样的,也就是说,我们可以让删除功能拆分一部分作为查找功能函数
- //查找单向链表的某个节点
- node* findNode(node* head,int data)
- {
- //创建一个临时节点指向要查找的节点
- node* tmp;
-
- for(node* p = head;p != NULL;p = p->next)
- {
- if(p->next != NULL && p->next->data == data)
- {
- tmp = p->next;
- return tmp;
- }
- }
-
- return NULL;
- }
-
执行完初始化,增删节点的动作之后,我们就需要有一个测试代码测试一下是否完成操作,所以就需要有一个查看链表内容的功能函数。也就是链表的遍历,遍历的意思就是逐个访问每一个节点,对于线性表而言,由于路径唯一的选择就是从头走到尾,因此相当而言比较简单
- //遍历查看链表
- void show(node* head)
- {
- //查看链表是否为空
- if(isEmpty(head))
- {
- return;
- }
-
- //遍历打印链表的数据域里面的内容
- for(node* p = head;p != NULL;p = p->next)
- {
- printf("%d ",p->data);
- }
-
- printf("\n");
-
- }
在我们使用完单链表之后,需要对我们初始化的单链表进行销毁,开辟了堆空间,在程序退出之前需要手动删除,不然可能会造成内存空间泄露,程序崩溃等情况。由于链表中的各个节点被离散地分布在各个随机的内存空间,因此销毁链表必须遍历每一个节点,释放每一个节点。
注意:销毁链表时,遍历节点要注意不能弄丢相邻节点的指针
- //销毁链表
- node* destroy(node* head)
- {
- //遍历销毁链表
- for(node* tmp = head,*n = tmp->next;tmp != NULL;tmp = n)
- {
- n = tmp->next; //n为销毁节点的指针域所指向的节点
- free(tmp);
- }
-
- return NULL:
- }
链式存储中,所有节点的存储位置是随机的,他们之间的逻辑关系用指针来确定,跟物理存储位置无关,在增删数据都非常迅速,不需要移动任何数据。又由于位置与逻辑关系无关,一次也无法直接访问某一个指定的节点,只能从头到尾按遍历的方式一个个找到想要的节点。简单地说,链式存储的优缺点与顺序存储几乎是i相对的
总结其特点如下:
优点:
1、插入、删除时只需要调整几个指针,无需移动任何数据
2、当数据节点数量较多时,无需一整片较大的连续内存空间,可以灵活利用离散的内存
3、当数据节点数量变化剧烈时,内存的释放和分配灵活,速度快
缺点:
1、在节点中,需要多余的指针来记录节点之间的关联
2、所有数据都是随机存储的,不支持立即访问任意一个随机数据
所谓的循环,指的时将链表末尾节点循环指向链表表头。示意图如下:
循环链表的操作跟普通链表操作基本上是一致的,只要针对循环特性稍作修改即可,比如:
- //初始化循环单向链表
- node* init()
- {
- node* head = malloc(sizeof(node));
-
- //初始化空链表是,需要将末尾指针指向自身
- if(head != NULL)
- {
- head->next = head;
- }
-
-
- return head;
- }
-
- //若链表头节点的下一个指向自身
- //则代表链表为空
- bool isEmpty(node* head)
- {
- return head->next == head;
- }
最后附上我测试的主代码
- //单向链表
- int main()
- {
- //初始化一个带头节点的空链表
- node* head = initList();
-
- //插入一些数据到链表的头部
- for (int i = 1; i <= 5; i++)
- {
- //1、创建新节点
- node* new = newNode(i);
-
- //2、将新节点置入链表
- insertHead(head, new);
- }
-
- //遍历链表,打印各个元素
- show(head);
-
- //输入你删除的节点
- int n;
- printf("请输入你要删除的节点:\n");
- while (1)
- {
- scanf("%d", &n);
- node *p = removeNode(head, n);
- if (p == NULL)
- {
- printf("没有你要删除的节点!\n");
- continue;
- }
-
- free(p);
- show(head);
- }
-
- //销毁链表,销毁之后返回NULL
- head = destroy(head);
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。