C语言笔记27 •单链表介绍•

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;//定义节点的结构体数据，以及下一结构体节点的（指针）地址，然后重命名为 SLTNodevoid 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=NULLptail->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->posnewnode->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->NULLfind = SLTFind(plist, 2);//查找位置SLTInsertAfter(find, 4);//在指定位置之后插入数据SLTPrint(plist);//打印节点数据  1->2->4->0->3->NULLfind = SLTFind(plist, 3);//查找位置SLTErase(&plist, find);//删除pos(指定位置)节点SLTPrint(plist);//打印节点数据  1->2->4->0->NULLfind = SLTFind(plist, 4);//查找位置SLTEraseAfter(find);SLTPrint(plist);//打印节点数据  1->2->4->NULLSListDesTroy(&plist);//销毁链表SLTPrint(plist);//打印节点数据//SLTPushBack(&plist, 1);//尾插//SLTPrint(plist);//打印节点数据
}int main()
{//SList_test();SList_test1();//printf("%zd %zd", sizeof(SLTNode), sizeof(SLTNode*)); //8, 4return 0;
}