线性存储的链式存储
链式存储又叫链表,分可以分为单链表 双链表,循环链表,静态链表。
单链表
何为单链表:使用链式存储的结构实现线性存储(逻辑结构)。顺序表在物理上是连续存放的,单链表无需这样,原因就是 每个简单除了存放数据元素之外,还存储了指向下一个节点的指针
优点: 不要求大片连续存储空间,改变容量方便。
缺点: 不可以随机读取,要花费一定的空间存储指针。
单链表有两种实现方式,带头节点和不带头节点的。
实现单链表
typedef struct
{
int data; //数据域
struct LNode *next; //指针域
} LNode;
增加一个新的结点:在内存中申请空间,并用指针p指向这个节点
LNode *P = (LNode *)malloc(sizeof(struct LNode));
typedef 的使用
基本语法: typedef <数据类型> <别名>
。
使用typedef 我们可以简化很多。
typedef struct LNode
{
int data; //数据域
struct LNode *next; //指针域
} LNode, *LinkList;
其实 只要把 struct LNode{}
看出一个整体就好理解了,结合 typedef <数据类型> <别名>
,是不用一目了然。
等价于 typedef struct LNode LNode; typedef struct LNode* linkList;
我们就可 声明 LinkList
声明头指针, LNode
声明结构体。
初始化单链表 和判断是否为空
不带头节点
不带头节点其实非常好理解
bool InitList(LinkList &L)//无比传入引用,要不然操作的就是局部变量
{
L = NULL;
return true;
}
//判断是否为空
bool Empty(LinkList L)
{
return (L==NULL);
}
使用话 用 LinkList
开辟头指针就好了。
void test()
{
LinkList L; //声明指向单链表的指针
InitList(L);
}
带头节点
其实带头节点有一点点不好理解。
bool InitList(LinkList &L)
{
//开辟头节点,并且是头指针指向头节点
L = (LNode *)malloc(sizeof(LNode));
//开辟空间失败retrun flase
if (L == NULL)
{
return false;
}
L->next = NULL;
return true;
}
bool Empty(LinkList L)
{
return (L->next == NULL);
}
void test()
{
LinkList L; //声明指向单链表的指针
InitList(L);
}

首先加了头节点是为了实现某些操作方便,头节点不存储数据。
带头节点和不带头节点有何区别
不带头节点,写代码比较麻烦,因为第一个数据点和后续数据不一样,所以需要不同的代码逻辑,并且对空表和非空表的处理也需要不同的逻辑。
结论:我们使用带头节点的,不适用不带头节点的。
单链表插入
带头节点
插入操作,在第i个位置上出入指定元素e。头节点可以作为第零个节点。
其实我们要做的事情就是
- 判断 i是否合法
- 在 i处 插入节点,就获取它前面一个节点 i-1
- 判断找到的i-1个节点是否存在
- 开辟新的节点并 连接到链表中
bool ListInsert(LinkList &L, int i, int e)
{
if (i < 1)//i表示为序 不允许小于1
return false;
LNode *p = L; //p 指向当前扫描到的节点
int j = 0; //当前p指向的是那个节点
//循环时为了获取 i-1节点
while (p != NULL && j < i - 1) //扫描到 第i-1节点 当p == NULL说明到了表尾
{
p = p->next;
j++;
}
// 如果在大于表尾的地方插入数据,那节点存在 ,那么插入失败
if (p == NULL)
return false;
//开始新的节点,并存储数据 e
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
// 将s指向下一个节点,并且p(第i-1)节点的next指向 s
s->next = p->next;
p->next = s;
return true;
}
不带头节点
其实就多了一个处理插入第一个位置的特殊情况 ,由于没有头节点 ,那么就要改 头地址LinkList
的指向,
if(i==1)
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
// 将s指向原来的下一个节点,并且头指针指向 s
s->next = L->next;
L->next = s;
return true;
}
所以不带头节点就有点麻烦,以后的情况就说明有头节点。
任意节点后插操作
bool InsertNextNode(LNode* p,int e)
{
//传入节点不存在 失败
if(p==NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s==NULL)//开辟空间失败
return false;
s->data=e;
s->next = p->next;
p->next = s;
return true;
}
前插操作
由于我们单链表,知道某一个节点就可以知道它后面的所有节点,但是在他之前的呢,就单单这个条件的话无法知道的。
所以还要传入参数 头指针 LinkList
,通过它来找到它前面节点,但是这样的算法时间复杂度无疑是 O(n);没有更简单的方法呢?
偷天换日
虽然节点是死的,但是数据是活的。找不到前驱节点就创造节点
- 我们继续指向后插操作
- 插入的节点覆盖插入节点的数据
- 原来的节点覆盖新数据。
bool InsertPriorNode(LNode *p, int e)
{
//传入节点不存在 失败
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) //开辟空间失败
return false;
// 继续查到后面
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
很妙。
删除节点
删除操作,我们就需要进行如下几步
- 找到删除节点的前驱节点
- 让前驱节点的next指针跳过删除节点指向下一个节点。
- 释放删除节点的空间
按位序删除
// 按序位删除
bool ListDelete(LinkList &L, int i, int &e)
{
if (i < 1)
return false;
LNode *p;
int j = 0;
p = L;
// 扫描它前面一个节点
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
if (p->next == NULL) //发现i-1节点是 尾巴 就失败
return false;
//删除节点i
LNode *q = p->next; //q是被删除节点
e = q->data;//e是返回删除节点的值
p->next = q->next;
free(q);
return true;
}
删除指定节点
和前插操作一样,我们这样进行
- 让它的后驱节点和自己交换数据域data 和指针域
- 释放后驱节点
bool DeleteNode(LNode *p)
{
if (p == NULL)
return false;
LNode *q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
return true;
}
但是这样是有bug的时候,假如删除最后一个节点就无法后驱节点(此时后驱节点是NULL)和自己交换数据域data 和指针域。
所以当时最后一个节点的时候,就要扫描到它的前驱节点
查找
按位查找
其实这个就简单多了,一个循环就可以解决
LNode *GetElem(LinkList L, int i)
{
if (i < 0)
return NULL;
LNode *p = L;
int j = 0;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
按元素查找
LNode *LocaleElem(LinkList L, int e)
{
LNode *p = L->next;
while (p != NULL && p->data != e)
p = p->next;
return p;
}
求表的长度
int Length(LinkList L)
{
int len = 0;
LNode *p = L;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
建立单链表
尾插法
所谓尾插法就是在链表的后面的节点插入数据。
LinkList List_TailInsert(LinkList &L)
{
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s, *r = L; //s表示开创的节点,r 为尾指针
scanf("%d", &x);
while (x != 9999) //9999 作为退出标志
{
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s; //新开辟的节点接入s 链表
r = s; //r有和新开创的节点重合
scanf("%d", &x);
}
r->next = NULL;
return L;
}
头插法
所谓头插法就是 一致在头节点插入数据
我们使用头插法,插入数据的话,插入数据是输入数据的逆序。
输入的数据是 1 2 3 那么存储数据恰好是 3 2 1, 这就叫逆置
LinkList List_HeadInsert(LinkList &L)
{
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s;
L->next = NULL;
scanf("%x", &x);
while (x != 9999)
{
s = (LNode *)malloc(sizeof(LNode));
//头插入操作
s->data = x;
s->next = L->next;
L->next = s;
scanf("%x", &x);
}
return L;
}
我们就可以更具这个写出一个逆置的函数, 其实就把后一个元素前插到前一个元素
void Inverse(LinkList &L)
{
LNode *p, *q;
p = L->next;
L->next = NULL; //初始化空表
while (p != NULL)
{
q = p; //p,q同时指向next结点
p = p->next;//p为下一个指针。
//头插操作
q->next = L->next; //第一次执行时L->next为NULL
L->next = q;
}
}
总结
其实获取单链表这么多运算离不开,前插,后插操作,扫描节点的这几个操作。
Q.E.D.