数据结构-->链表_02

时间：2022-10-22 01:00:31

本期的链表继续进行，上期我们完成了链表的增加和删除。

现在接下来，我们进行链表的查改与优化

头文件“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);

//查找指定数值
SLTNode* SLT_FIND(SLTNode** pphead, SLTDataType x);

//删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

测试环节“Test.c”

#include "SList.h"

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

SLTPushBack(&plist, 21);  
SLTPushBack(&plist, 23);
SLTPushBack(&plist, 25);
SLTPushBack(&plist, 27);
SLTPushBack(&plist, 29);      //尾插数据

SLTPrint(plist);

SLTNode* ret = SLT_FIND(&plist, 25);
SLTErase(&plist, ret);      //指定数据25进行删除

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;    //防止野指针乱窜
}


//查找指定数值
SLTNode* SLT_FIND(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
while(cur)
  {
if(cur -> data == x)
    {
return cur;
    }
cur = cur ->next;
  }
return NULL;
}


//删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);

if(*pphead == pos)
  {
SLTPopFront(pphead);
  }

else
  {
SLTNode* prev = *pphead;
while(prev ->next != pos)
    {
prev = prev ->next;
    }
prev ->next = pos ->next;
free(pos);
  }
}

下面是优化后的指定删除的运行结果 :>

数据结构-->链表_02

下面再进一步完善

1.在指定位置pos之前进行插入数据

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

2.在指定位置pos之后进行插入数据

//在pos之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
SLTNode* newnode = SLT_BUY(x);
newnode ->next = pos ->next;
pos ->next = newnode;
}

3.在指定位置pos之后进行删除数据

//在pos位置之后进行删除
void SLTEraseAfter(SLTNode* pos)
{
SLTNode* del = pos ->next;
pos ->next = del ->next;
free(del);
del = 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);

//查找指定数值
SLTNode* SLT_FIND(SLTNode** pphead, SLTDataType x);

//删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

//在pos之前插入数据
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//在pos位置之后进行删除
void SLTEraseAfter(SLTNode* pos);

现在进入测试环节“Test.c”

---->pos之前插数据 :>

#include "SList.h"

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

SLTPushBack(&plist, 31);  
SLTPushBack(&plist, 33);
SLTPushBack(&plist, 35);
SLTPushBack(&plist, 37);
SLTPushBack(&plist, 39);      //尾插数据

SLTPrint(plist);

SLTNode* ret = SLT_FIND(&plist, 39);
SLTInsertBefore(&plist, ret, 38);    //在39之前进行插入数据38

SLTPrint(plist);
}

int main()
{
test_02();
}

测试运行结果 :>

数据结构-->链表_02


---->pos之后插数据 :>

#include "SList.h"

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

SLTPushBack(&plist, 31);  
SLTPushBack(&plist, 33);
SLTPushBack(&plist, 35);
SLTPushBack(&plist, 37);
SLTPushBack(&plist, 39);      //尾插数据

SLTPrint(plist);

SLTNode* ret = SLT_FIND(&plist, 35);
SLTInsertAfter(ret, 36);    //在指定位置35后面插入数据36

SLTPrint(plist);
}

int main()
{
test_03();
}

测试运行结果 :>

数据结构-->链表_02

---->pos之后删除数据 :>

#include "SList.h"

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

SLTPushBack(&plist, 31);  
SLTPushBack(&plist, 33);
SLTPushBack(&plist, 35);
SLTPushBack(&plist, 37);
SLTPushBack(&plist, 39);      //尾插数据

SLTPrint(plist);

SLTNode* ret = SLT_FIND(&plist, 31);
SLTInsertAfter(ret);    //在指定位置31后面删除数据33

SLTPrint(plist);
}

int main()
{
test_05();
}

​测试运行结果 :>

数据结构-->链表_02

本期链表的增删查改及其优化测试就已经结束了！！

下一期，会对本文中链表的一些代码进行解读和分析！！

感谢小伙伴们的阅读！！

​

​

​

​

​

​

标签：

相关文章