目录
1.回顾顺序表的缺点
2.链表
链表定义
链表结构
一个单向链表的结点代码示例
遍历打印单向链表代码示例
注意
1.回顾顺序表的缺点
1.由文章85.【C语言】数据结构之顺序表的中间插入和删除及遍历查找可知,在顺序表中间插入或删除效率低下
2.顺序表扩容会消耗多余的空间,导致浪费
链表可以解决上述问题
2.链表
在63.【C语言】再议结构体(上)文章提到过
链表定义
一种物理存储单元上非连续(因为用了指针)、非顺序(因为用了指针)的存储结构,用于线性方式存储数据(对比数组:元素的顺序集合)
链表的"链":链接
链表结构
中的每一个元素称为结点(node),结点包含两个部分:数据和链(链是下一个节点的地址(指针),指向下一个节点的数据),链最后一个元素包含一个空指针
*链表名是头指针(phead)的名字,下面这张图(摘自《计算机科学导论》)
一种典型的链表图:单向链表
单向链表的特点:一个节点只存一个指针
一个单向链表的结点代码示例
SList.h写入以下内容:
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
结构体包含两部分:数据和指针,符合单链表的定义
注:
SLTDataType的全称:Single List Data Type 单链表数据类型
SListNode的全称Single List Node 单链表结点
遍历打印单向链表代码示例
SLPrint函数(遍历打印链表)代码示例,写入SList.c
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur)//等价为cur != NULL{printf("%d->", cur->data);cur = cur->next;//cur被赋值为下一个结点的地址}printf("NULL");//读到链表的结尾存储的为空指针
}注意
1.不要为phead断言,和顺序表的指针ps的断言不同,ps指向的是结构体,而链表可以为空链表(phead->NULL),
2.while (cur)不要写成while(cur->next),否则链表的最后一个数据无法打印
3.由于是非连续访问,因此使用cur = cur->next;
4.严谨来说,NULL在x64下表示为0x0000000000000000,在x86下表示为0x00000000
