线性结构之单链表详解
文章目录
- 前言
- 一.单链表的结构体
- 二、单链表的基本接口
- 1.SListMalloc（申请节点）
- 2.SListPushBack（尾插）
- 3.SListPushFront（头插）
- 4.SListPopBack（尾删）
- 5.SListPopFront（头删）
- 6.SListInsert（插入）
- 7.SListErase（删除）
- 8.SListFind（查找）
- 9.SListPrint（打印）
- 10.SListDestroy（销毁）
- 三、整体结构
- 1.头文件
- 2.源文件
- 结语
前言
我们前面学习了顺序表的实现，那么今天我们来学习单链表，当然单链表也有许多种类，在这里我当然是讲不完的，在这里我只介绍单链表最常见的无头单向非循环链表
一.单链表的结构体
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//指向下一个节点的指针
}SLN;
二、单链表的基本接口
1.SListMalloc（申请节点）
SLN* SListMalloc(SLTDataType x)
{
SLN* newnode = (SLN*)malloc(sizeof(SLN));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
我这里的命名可能不规范，你按照自己的命名习惯来
2.SListPushBack（尾插）
void SListPushBack(SLN** pphead ,SLTDataType x)
{
SLN*newnode= SListMalloc(x);
if (*pphead== NULL)//头结点如果为空
{
*pphead = newnode;
}
else
{
SLN* tail = *pphead;
while (tail->next != NULL)//找到含有NULL节点的位置；即最后的位置；
{
tail = tail->next;
}
tail->next = newnode;
}
}
这个函数为什么传参的时候需要二级指针呢？头节点如果为空，我们是需要修改头结点的内容的，头节点是一个一级指针，那么我们修改他就需要二级指针
3.SListPushFront（头插）
void SListPushFront(SLN** pphead, SLTDataType x)
{
SLN* newnode = SListMalloc(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
真理不管头指针是不是空指针，我们都是需要修改头指针的，当头插时，我们将新的节点的next指向phead之后，我们就要修改头指针为新的节点，所以我们都需要修改头指针
4.SListPopBack（尾删）
void SListPushBack(SLN** pphead ,SLTDataType x)
{
SLN*newnode= SListMalloc(x);
if (*pphead== NULL)
{
*pphead = newnode;
}
else
{
SLN* tail = *pphead;
while (tail->next != NULL)//找到含有NULL节点的位置；即最后的位置；
{
tail = tail->next;
}
tail->next = newnode;
}
}
5.SListPopFront（头删）
void SListPushFront(SLN** pphead, SLTDataType x)
{
SLN* newnode = SListMalloc(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
既然需要改变头部指针指向，那么就需要传二级指针
6.SListInsert（插入）
void SListInsert(SLN** pphead, SLN* pos, SLTDataType x)//在pos的前面插入
{
if (pos = *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLN* newnode = SListMalloc(x);
assert(newnode != NULL);
SLN* prev = *pphead;
while (prev->next != pos)//这里需要找到pos的前面的位置，遍历
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
7.SListErase（删除）
void SListErase(SLN** pphead, SLN* pos)
{
if (*pphead == pos)
{
SListPopBack(pphead);
}
else
{
SLN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
}
}
8.SListFind（查找）
SLN* SListFind(SLN** pphead, SLTDataType x)
{
SLN* temp = *pphead;
while (temp)
{
if(temp->data == x)
{
return temp;
}
else
{
temp = temp->next;
}
}
return NULL;//如果没有找到就返回一个NULL
}
9.SListPrint（打印）
void SListPrint(SLN*phead)
{
//遍历链表
SLN* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
}
这里是我个人加的接口，遍历一遍链表
10.SListDestroy（销毁）
void SListDestroy(SLN** pphead)
{
assert(*pphead != NULL);
while(*pphead!=NULL)
{
SLN* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
这里销毁指的是整个链表的删除
三、整体结构
1.头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLN;
SLN* SListMalloc(SLTDataType x);
void SListPrint(SLN* phead);
void SListPushBack(SLN** phead, SLTDataType x);
void SListPushFront(SLN** pphead, SLTDataType x);
void SListPopBack(SLN** pphead);
void SListPopFront(SLN** pphead);
SLN* SListFind(SLN** pphead,SLTDataType x);
void SListInsert(SLN** pphead, SLN* pos, SLTDataType x);
void SListErase(SLN** pphead, SLN* pos);
void SListDestroy(SLN** pphead);
2.源文件
#include"SList.h"
#include<assert.h>
SLN* SListMalloc(SLTDataType x)
{
SLN* newnode = (SLN*)malloc(sizeof(SLN));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPrint(SLN*phead)
{
//遍历链表
SLN* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
}
void SListPushBack(SLN** pphead ,SLTDataType x)
{
SLN*newnode= SListMalloc(x);
if (*pphead== NULL)
{
*pphead = newnode;
}
else
{
SLN* tail = *pphead;
while (tail->next != NULL)//找到含有NULL节点的位置；即最后的位置；
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLN** pphead, SLTDataType x)
{
SLN* newnode = SListMalloc(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
void SListPopBack(SLN** pphead)//这里需要考虑NULL，只有一个和两个及两个以上
{
SLN* tail=*pphead;
SLN* prev = NULL;
assert(*pphead != NULL);
if ((*pphead)->next == NULL)
{
*pphead = NULL;
}
else
{
while (tail->next !=NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SListPopFront(SLN** pphead)//这里不需要用考虑只有一个节点的情况，因为没有引用next
{
SLN* temp = *pphead;
assert(*pphead != NULL);
*pphead = (*pphead)->next;
free(temp);
}
SLN* SListFind(SLN** pphead, SLTDataType x)
{
SLN* temp = *pphead;
while (temp)
{
if(temp->data == x)
{
return temp;
}
else
{
temp = temp->next;
}
}
return NULL;
}
void SListInsert(SLN** pphead, SLN* pos, SLTDataType x)//在pos的前面插入
{
if (pos = *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLN* newnode = SListMalloc(x);
assert(newnode != NULL);
SLN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
void SListErase(SLN** pphead, SLN* pos)
{
if (*pphead == pos)
{
SListPopBack(pphead);
}
else
{
SLN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
}
}
void SListDestroy(SLN** pphead)
{
assert(*pphead != NULL);
while(*pphead!=NULL)
{
SLN* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
结语
说实话，感觉写的有点水，如果有什么好的提议欢迎讨论