数据结构—单链表

1.单链表

    1.1 概念

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

   我们可以把链表的结构理解为火车的结构。

 

1.2 结点 

虽然有这么多的链表的结构，但我们实际中最常用还是两种结构：单链表和双向带头循环链表 。

1.4 性质

   1、链式结构在逻辑上是连续的，在物理结构上不⼀定连续

   2、结点⼀般是从堆上申请的

   3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

1.5 优缺点

   优点：插入和删除效率高；内存利用率高。

   缺点：查找的效率低。

1.6 链表的打印

1.7 完整代码

 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;

void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x);


//尾删
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);

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode * pos);

//删除pos之后的结点
void SLTEraseAfter(SLTNode * pos);

//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#include"SList.h"

void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}


//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail");
exit(1);
}
node->data = x;
node->next = NULL;

return node;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead=newnode;
}
else
{
//找尾结点
SLTNode* pcur = *pphead;
while (pcur->next)
{
pcur = pcur->next;
}
pcur->next = newnode;
}
}


//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);

SLTNode* newnode = SLTBuyNode(x);

newnode->next = *pphead;
*pphead = newnode;
}


void SLTPopBack(SLTNode** pphead)
{
//链表为空，不可以删除
assert(pphead && *pphead);
//处理一个结点的情况：要删除的是头结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead == NULL;
}
else
{
//找尾结点
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}

}



void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}


//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);

SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->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);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
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* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;

}


void SListDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while(pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}

test.c

#include"SList.h"
//创建一个链表，并打印链表

void createSList()
{
//链表是由一个个的结点组成
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));
node4->data = 4;

node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;

//第一个节点的地址作为参数传递过去
SLTNode* plist = node1;
SLTPrint(plist);
}

void SListTest01()
{
SLTNode* plist = NULL;
/*SLTPushBack(&plist, 1);
SLTPrint(plist);
SLTPushBack(&plist, 2);
SLTPrint(plist);
SLTPushBack(&plist, 3);
SLTPrint(plist);
SLTPushBack(&plist, 4);
SLTPrint(plist);*/

SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist); 


//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
    //SLTPopBack(&plist);
//SLTPrint(plist);


/*SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);*/


SLTNode* find = SLTFind(plist,4);
//if (find == NULL)
//{
//printf("未找到！\n");
//}
//else
//{
//printf("找到了！\n");
//}


//SLTInsert(&plist, find, 11);
//SLTInsertAfter(find, 11);
//SLTErase(&plist, find);
//删除pos之后的结点
    //SLTEraseAfter(find);
SListDestroy(&plist);
SLTPrint(plist);
}




int main()
{
//createSList();
SListTest01();
return 0;
}

原文地址：https://blog.csdn.net/2301_80151359/article/details/142284286

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！