1.链表的概念及结构
链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。
2. 顺序表带来的问题
(1)中间/头部的插⼊删除,时间复杂度为O(N)
(2)增容需要申请新空间,拷⻉数据,释放旧空间。会有不⼩的消耗。
(3)增容⼀般是呈2倍的增⻓,势必会有⼀定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插⼊了5个数据,后⾯没有数据插⼊了,那么就浪费了95个数据空间。
Ps:单链表的好处就是比顺序表结构简单,节省内存空间,随时申请内存随时使用。链表其实就是由节点组成的,节点中存储数据+指向下一节点的位置指针。
3.单链表实现头部、尾部、任意位置增加删除节点、销毁链表等操作
//SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;//定义节点中的数据类型
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;//定义节点的结构体数据,以及下一结构体节点的(指针)地址,然后重命名为 SLTNode
void SLTPrint(SLTNode* phead);//打印节点数据
void SLTPushBack(SLTNode** pphead);//尾插
void SLTPushFront(SLTNode** pphead);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//查找
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之前插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos(指定位置)节点
void SLTEraseAfter(SLTNode* pos);//删除pos之后的节点
void SListDesTroy(SLTNode** pphead);//销毁链表
//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)//打印节点数据
{
while (phead) //从第一个节点开始遍历,遇到NULL结束
{
printf("%d->", phead->data);
phead=phead->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* NEWNode = (SLTNode*)malloc(sizeof(SLTNode)); //内存分配时一定要注意写规范sizeof(SLTNode)=8不要写为sizeof(SLTNode*)=4, 大小就不一样肯定就会报错,分配了一个指向 SLTNode 的指针的内存,而不是分配一个 SLTNode 本身的内存。
if (NEWNode == NULL)
{
perror("malloc");
exit(1);
}
NEWNode->data = x;
NEWNode->next = NULL;
return NEWNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
assert(pphead);
if (*pphead==NULL)//*pphead代表指向第一个节点的指针,如果是“空链表”进行尾插
{
*pphead = SLTBuyNode(x);
}
else //如果是“非空链表”进行尾插
{
SLTNode* ptail = *pphead;
while (ptail->next) //从第一个节点开始遍历,判断指向下一个节点的指针是否为NULL 不能判断当前节点是否为空while (ptail) 进行结束循环,这不能代表下一节点是NULL
{
ptail = ptail->next;
}
//此时此刻ptail已经是尾节点了,ptail->next=NULL
ptail->next = SLTBuyNode(x);
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
assert(pphead);
// *pphead代表指向第一个节点的指针,如果是“空链表”进行头插
SLTNode* pur = SLTBuyNode(x);
pur->next = *pphead;
*pphead = pur;
}
void SLTPopBack(SLTNode** pphead)//尾删
{
assert(pphead && *pphead);//链表不能为空
//如果链表只有一个节点 // ->优先级高于*所以要加上()
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//如果链表有多个节点
else
{
SLTNode* prev = *pphead; //保存末尾的上一个节点的地址,目的是等释放末尾节点后,使上一个节点的指向地址为NULL(prev->next= NULL;)
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next= NULL;
}
}
void SLTPopFront(SLTNode** pphead)//头删
{
assert(pphead && *pphead);
//如果链表只有一个节点
//if ((*pphead)->next == NULL)
//{
// free(*pphead);
// *pphead = NULL;
//}
//else//如果链表有多个节点
//{
// SLTNode* Nextnode = *pphead;
// *pphead = Nextnode->next;
//}
//通用
//方案一
//SLTNode* Nextnode = *pphead;
//*pphead = Nextnode->next;
//方案二
SLTNode* Nextnode = (*pphead)->next;
free(*pphead);
*pphead = Nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
//assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
printf("找到了!\n");
return pcur;//找到了
}
pcur = pcur->next;
}
return NULL;//没找到
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
assert(pos);
SLTNode* pcur = *pphead;
SLTNode* newnode = SLTBuyNode(x);//申请一个空间,存储要插入的节点
if (pos == *pphead)
{
SLTPushFront(pphead, x);//头插
}
else
{
while (pcur->next != pos)
{
pcur = pcur->next;
}
//pcur->newnode->pos
newnode->next = pos;
pcur->next = newnode;
}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next= newnode;
}
//删除pos(指定位置)节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
SLTNode* prev = *pphead;
if (*pphead == pos)//执行头删
{
SLTPopFront(pphead);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* after = pos->next;
pos->next = pos->next->next;
free(after);
after = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* Nextnode = pcur->next;
free(pcur);
pcur = Nextnode;
}
*pphead = NULL;
}
//SeqList-test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SList_test()
{
//给节点里创建数据
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//内存分配时一定要注意写规范sizeof(SLTNode)=8不要写为sizeof(SLTNode*)=4, 大小就不一样肯定 就会报错,分配了一个指向 SLTNode 的指针的内存,而不是分配一个 SLTNode 本身的内存。
node4->data = 4;
//给节点之间建立联系
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//调用链表打印
SLTNode* plist = node1;
//SLTNode* plist = NULL; //SLTPushBack(NULL, 5);//尾插
//SLTPrint(plist);//打印节点数据
SLTPushBack(&plist, 5);//尾插
SLTPrint(plist);//打印节点数据
SLTPushFront(&plist, 0);//头插
SLTPrint(plist);//打印节点数据
SLTPopBack(&plist);//尾删
SLTPrint(plist);//打印节点数据
SLTPopFront(&plist);//头删
SLTPrint(plist);//打印节点数据
}
void SList_test1()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);//尾插
SLTPrint(plist);//打印节点数据
SLTPushBack(&plist, 2);//尾插
SLTPrint(plist);//打印节点数据
SLTPushBack(&plist, 3);//尾插
SLTPrint(plist);//打印节点数据
//SLTPushFront(&plist, 0);//头插
//SLTPrint(plist);//打印节点数据
//SLTPopBack(&plist);//尾删
//SLTPrint(plist);//打印节点数据
//SLTPopFront(&plist);//头删
//SLTPrint(plist);//打印节点数据
//SLTFind(plist,1);//查找
//SLTFind(plist, 3);//查找
SLTNode* find=SLTFind(plist, 3);//查找位置
SLTInsert(&plist, find, 0);//在指定位置之前插入数据
SLTPrint(plist);//打印节点数据 1->2->0->3->NULL
find = SLTFind(plist, 2);//查找位置
SLTInsertAfter(find, 4);//在指定位置之后插入数据
SLTPrint(plist);//打印节点数据 1->2->4->0->3->NULL
find = SLTFind(plist, 3);//查找位置
SLTErase(&plist, find);//删除pos(指定位置)节点
SLTPrint(plist);//打印节点数据 1->2->4->0->NULL
find = SLTFind(plist, 4);//查找位置
SLTEraseAfter(find);
SLTPrint(plist);//打印节点数据 1->2->4->NULL
SListDesTroy(&plist);//销毁链表
SLTPrint(plist);//打印节点数据
//SLTPushBack(&plist, 1);//尾插
//SLTPrint(plist);//打印节点数据
}
int main()
{
//SList_test();
SList_test1();
//printf("%zd %zd", sizeof(SLTNode), sizeof(SLTNode*)); //8, 4
return 0;
}