数据结构-->链表_01

时间：2021-04-14 00:59:16

首次书写链表有关的知识，先来明确什么是链表？

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

举一个形象化的现实生活中的例子  :> 老式的绿皮火车，车厢由链条，钩子链接在了一起！！

而链表也类似，只不过，链表是通过指针的指向有次序的链接在了一起！！每一个链表可存储一个数据，并且存储着下一个链表节点的地址！！如下图所示 :>

数据结构-->链表_01

由上图可以看出来，链表在逻辑上是连续的，但在物理结构上不一定连续！！

由于节点的空间，即每个数据单元是在堆上申请。而在堆上申请的空间有可能连续也有可能不连续！！

下面讲述链表的种类----->共有8种类型


如图所示 :>

数据结构-->链表_01

数据结构-->链表_01

而我们这里主要研究两种常用类型 :>

------------无头单向不循环-------------带头双向循环------------

1.无头单向不循环 :> 

结构简单，一般作为其他数据结构的子结构，如，哈系桶，图的链接表等等。另外笔试面试中出现较多！！

2.带头双向循环 :>

结构复杂，常用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外，此种链表虽然结构复杂，但会带来很多的优势，实现反而简单了！！

好的！！下面让我们开始今天的无头单向不循环链表

头文件“SList.h”

初步创建

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLTDataType;

typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;

}SLTNode;

测试环节“Test.c”

#include "SList.h"

void test_01()
{
SLTNode* plist = NULL;    //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数

SLTPushBack(&plist, 1);  
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 5);
SLTPushBack(&plist, 7);
SLTPushBack(&plist, 9);      //尾插数据

SLTPrint(plist);
}

int main()
{
test_01();
}

实现环节“SList.c”

#include "SList.h"

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

//开辟空间
SLTNode* SLT_BUY(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if(newnode == NULL)
  {
perror("malloc::fail");
return NULL;
  }
newnode ->data = x;
newnode ->next = NULL;  //防止野指针乱窜
return newnode;

}

//尾插数据
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
//开辟空间
SLTNode* newnode = SLT_BUY(x);
if(*pphead == NULL)
  {
*pphead = newnode;
  }
else
  {
SLTNode* tail = *pphead;
while(tail != NULL)
    {
tail = tail ->next;
    }
tail = newnode;
  }
}

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = SLT_BUY(x);
newnode ->next = *pphead;
*pphead = newnode;
}

//尾删数据
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);

//1.只有一个节点
//2.有两个及多个节点
if(*pphead == NULL)
  {
free(*pphead);
*pphead = NULL;
  }
else
  {
SLTNode* tail = *pphead;  
SLTNode* prev = NULL;
while(tail ->next != NULL)
    {
prev = tail;
tail = tail ->next;
    }
free(tail);
tail = NULL;
prev ->next = NULL;    //防止野指针乱窜
  }
}

//头删数据
void SLTPopFront(SLTNode** pphead)
{
SLTNode* first = *pphead;
*pphead = first ->next;  //运用了值覆盖原理
free(first);
first = NULL;    //防止野指针乱窜
}


头文件“SList.h”

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLTDataType;

typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;

}SLTNode;

//打印
void SLTPrint(SLTNode* phead);

//开辟空间
SLTNode* SLT_BUY(SLTDataType x);

//尾插数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//尾删数据
void SLTPopBack(SLTNode** pphead);

//头插数据
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//头删数据
void SLTPopFront(SLTNode** pphead);

测试环节“Test.c”

----->尾插尾删数据

#include "SList.h"

void test_01()
{
SLTNode* plist = NULL;    //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数

SLTPushFront(&plist, 1);  
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 5);
SLTPushFront(&plist, 7);
SLTPushFront(&plist, 9);      //尾插数据

SLTPrint(plist);

SLTPopFront(&plist);
SLTPopFront(&plist);        //尾删数据

SLTPrint(plist);

}

int main()
{
test_01();
}

下面是执行尾插尾删的运行结果 :>

数据结构-->链表_01


测试环节“Test.c”

----->头插头删数据

#include "SList.h"

void test_02()
{
SLTNode* plist = NULL;    //由于一个链表单元只存储一个数值，因此直接初始化即可
//而顺训表有多个变量，比如，sz, capcity需要进行初始化，因此需要分装一个初始化函数

SLTPushBack(&plist, 11);  
SLTPushBack(&plist, 13);
SLTPushBack(&plist, 15);
SLTPushBack(&plist, 17);
SLTPushBack(&plist, 19);      //头插数据

SLTPrint(plist);

SLTPopBack(&plist);
SLTPopBack(&plist);        //头删数据

SLTPrint(plist);

}

int main()
{
test_02();
}

下面是执行头插头删的运行结果 :>

数据结构-->链表_01

本期的链表就到这里了！！感谢阅读！！












标签：

相关文章