网站导航
> 文章列表 > 【数据结构】单链表(一)

【数据结构】单链表(一)

网友: 文章列表 2024-03-21 17:11:53

【数据结构】单链表(一)

作者：日出等日落

专栏：数据结构

想变成仲夏夜的一只萤火虫，只要抓住你的注意力，就已经满足了。

目录

前言：

 单链表的结构 ：

 逻辑结构：

物理结构：

BuySLTNode（动态申请一个结点）： 

 CreateSList(//循环创建结点)：

SLTPrint（单链表打印）：

 单链表的功能： 

SLTPushBack尾插:

plist不为NULL：

 plist为NULL：

SLTPopBack（尾删）：

SLTPushFront（头插）：

SLTPopFront（头删）：

SLTFind(查找)：

SLTInsertAfter（在pos位置之后插入）：

  SLTInsertFront（在pos位置之前插入）：

SLTEraseAfter（删除pos之后的位置）：

 SLTErase（删除pos位置）：

SLTDestory（释放空间）： 

完整代码： 

text.c：

SList.c:

SList.h:

 

前言：

 

我们之前学习了顺序表，那么，朋友们知道顺序表有什么缺陷吗？

顺序表的缺陷：

  1. 空间不够的时候，需要扩容。扩容（尤其是异地扩容）是由一定价值的。其次还可能存在一定的空间浪费。
  2. 头部或者中部插入删除，需要挪动数据，效率低下。

优化方案：

  1. 按需申请释放
  2. 不需要挪动数据

 

这就需要链表来实现

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

简单来说，单链表是一种链式存取的 数据结构 ，用一组地址任意的存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作 线性链表 （单链表），单链表是链式存取的结构。 链接方式存储的线性表简称为链表（Linked List）。 ② 链表中结点的逻辑次序和物理次序不一定相同。

 

 单链表的结构 ：

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//数据元素struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
}SLTNode;

 逻辑结构：

物理结构：

BuySLTNode（动态申请一个结点）： 

函数实现：

//动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");exit(-1);}else{newnode->data = x;newnode->next = NULL;}return newnode;
}

 CreateSList(//循环创建结点)：

首先，为了防止最后找不到头指针，我们再定义一个结构体变量ptail来进行后续的操作实现

这个图中的代码是四个结点连接的操作，可以结合图理解一下。

那么在实际操作中，实现n个创建利用for循环来实现，利用BuyTNode创建动态结构体，我们再将下一个结构体的地址传给结构体的next指针以此类推.....

下面是循环创建结点的代码实现：

 函数实现：

//循环创建结点
SLTNode* CreateSList(int n)
{SLTNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; ++i){SLTNode* newnode = BuySLTNode(i);if (phead == NULL){phead = ptail = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}

SLTPrint（单链表打印）：

// 单链表打印
void SLTPrint(SLTNode *phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}

 单链表的功能： 

SLTPushBack尾插:

plist不为NULL：

尾插需要先找尾部，即NULL的地方，然后将newnode插到null后面

注：

  • tail为NULL和tail->next为NULL对于循环条件来说是不一样的。
  • tail为NULL代表没有这个结构体
  • tail->next为NULL代表没有下一个结构体了
void SLTPushBack(SLTNode* phead, SLDataType x)
{//尾插SLTNode* newnode = BuySLTNode(x);SLTNode* tail = phead;while (tail->next){tail = tail->next;}tail->next = newnode;
}

 plist为NULL：

注：这里要传地址

因此我们要改变NULL这个指针，我们需要传SLTNodepphead进去，那我们*pphead就可以改变NULL的值了！

void SLTPushBack(SLTNode pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else//找尾{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

 

SLTPopBack（尾删）：

找到尾部next指向为NULL的，将其释放掉，然后创建结构体第三变量prev记录前一个位置的next，将prev->next=NULL；

void SLTPopBack(SLTNode pphead)
{assert(*pphead);if ((*pphead) == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}

 

SLTPushFront（头插）：

void SLTPushFront(SLTNode pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

 

SLTPopFront（头删）：

void SLTPopFront(SLTNode pphead)
{assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}

 

SLTFind(查找)：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

 

SLTInsertAfter（在pos位置之后插入）：

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

 

  SLTInsertFront（在pos位置之前插入）：

有两种情况：

  • pos为链表第一个，那就相当于头插；
  • 除去第一个以外的位置：

 

         

// 在pos之前插入x
void SLTInsert(SLTNode pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}

 

SLTEraseAfter（删除pos之后的位置）：

找pos位置的下一个位置将它赋给一个指针nextNode，将pos的next连接到nextNode的下一个结构体的位置，这样就跳过这个指针了，最后释放这个被跳过的空间！！！

void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* nextNode = pos->next;pos->next = nextNode->next;free(nextNode);}
}

 

 SLTErase（删除pos位置）：

// 删除pos位置
void SLTErase(SLTNode pphead, SLTNode* pos)
{assert(pos);if (pos==*pphead){SLTPopFront(pphead);	}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

SLTDestory（释放空间）： 

void SLTDestory(SLTNode pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur=next;}*pphead = NULL;
}

完整代码： 

首先，我将通讯录分成了三个部分：

1、text.c                   //通讯录的菜单以及主函数

2、SList.h             //结构体和函数的声明，以及头文件的引用

3、SList.c              //通讯录各种功能函数的实现  

text.c：

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"
TextSList1()
{SLTNode* plist = CreateSList(10);SLTPrint(plist);}TextSList2()
{SLTNode* plist =NULL;SLTPushBack(&plist, 100);SLTPushBack(&plist, 200);SLTPushBack(&plist, 300);SLTPushBack(&plist, 400);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);}TextSList3()
{SLTNode* plist = NULL;SLTPushFront(&plist, 100);SLTPushFront(&plist, 200);SLTPushFront(&plist,500);SLTPushFront(&plist, 800);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);}TextSList4()
{SLTNode* plist = NULL;SLTPushFront(&plist, 100);SLTPushFront(&plist, 200);SLTPushFront(&plist, 500);SLTPushFront(&plist, 800);SLTPrint(plist);SLTNode* pos = SLTFind(plist,200);if (pos){printf("找到了\\n");}else{printf("找不到\\n");}
}TextSList5()
{SLTNode* plist = NULL;SLTPushBack(&plist, 100);SLTPushBack(&plist, 200);SLTPushBack(&plist, 300);SLTPushBack(&plist, 400);SLTPrint(plist);SLTNode* p = SLTFind(plist, 200);if (p){SLTInsertAfter(p, 2);printf("找到了\\n");SLTPrint(plist);SLTEraseAfter(p);SLTPrint(plist);SLTErase(&plist, p);SLTPrint(plist);}else{printf("找不到\\n");}}
TextSList6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 100);SLTPushBack(&plist, 200);SLTPushBack(&plist, 300);SLTPushBack(&plist, 400);SLTPrint(plist);SLTNode* p = SLTFind(plist, 200);if (p){SLTInsert(&plist, p, 1);SLTPrint(plist);SLTDestory(&plist);SLTPrint(plist);}else{printf("找不到了\\n");}
}int main()
{TextSList6();return 0;
}

SList.c:

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"
//动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");exit(-1);}else{newnode->data = x;newnode->next = NULL;}return newnode;
}//循环创建结点
SLTNode* CreateSList(int n)
{SLTNode* phead = NULL, * ptail = NULL;for (int i = 0; i < n; ++i){SLTNode* newnode = BuySLTNode(i);if (phead == NULL){phead = ptail = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}
// 单链表打印
void SLTPrint(SLTNode *phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\\n");
}void SLTPushBack(SLTNode pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else//找尾{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}void SLTPopBack(SLTNode pphead)
{assert(*pphead);if ((*pphead) == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}void SLTPushFront(SLTNode pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopFront(SLTNode pphead)
{assert(*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* nextNode = pos->next;pos->next = nextNode->next;free(nextNode);}
}
// 在pos之前插入x
void SLTInsert(SLTNode pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
// 删除pos位置
void SLTErase(SLTNode pphead, SLTNode* pos)
{assert(pos);if (pos==*pphead){SLTPopFront(pphead);	}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}void SLTDestory(SLTNode pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur=next;}*pphead = NULL;
}

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* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);void SLTPushBack(SLTNode pphead, SLTDataType x);
void SLTPopBack(SLTNode pphead);
void SLTPushFront(SLTNode pphead, SLTDataType x);
void SLTPopFront(SLTNode pphead);SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SLTInsertAfter(SLTNode* pos, SLTDataType x);// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SLTEraseAfter(SLTNode* pos);// 在pos之前插入x
void SLTInsert(SLTNode pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode pphead, SLTNode* pos);void SLTDestory(SLTNode pphead);

设计师之家

网络标签：

相关问题