内容简介：数据结构——单链表
前面介绍了顺序表的特点和实现！但是顺序表有很多的不足，比如要给顺序表的前面插入一个数据，就必须先把后面的数据先一个一个的往后挪动，然后再将所要插入的数据放进去。就相当于一个数组一样。
还有就是顺序表的大小分配，如果采用静态分配内存的方式，那么势必就会造成剩余内存的浪费，不利于CPU工作。要是用动态内存分配，可以减少内存浪费情况，但是一次性开辟的内存不能太大也不能太小，遇到一个结构体数据刚刚存放满，这时候在想增加数据就要再申请空间，那么申请的空间只用了一个，其他的也就造成了浪费。
所以这时候为了方便存储，和更加节省空间，就采用了单链表的方式。先来看看为什么单链表有这么多好处
单链表采用上一个节点的头结点和下个节点相邻，相当于把好多的数据直接连起来，用的时候只需要改变节点之间的连接。而且增容是一次增加一个节点的大小，实现了真正的用多少分配多少。
写单链表的时候一定要注意你的首节点，别丢了，丢了就找不回来。还有就是在删除节点的时候一定要对那个节点负责，不然让它成为野指针了，对谁都不好。
单链表如何实现，还有接口怎么封装，具体在程序中看一下，重点部分都做了标识。
ListNode.h
#ifndef _LISTNODE_H_
#define _LISTNODE_H_
#include <stdio.h>
#include <windows.h>
#include <assert.h>
typedef int Datatype;
typedef struct ListNode
{
Datatype data;
struct ListNode *next;
}ListNode;
void PushBack(ListNode **pplist, Datatype x);//从后面插入一个data为x的节点
void PopBack(ListNode **plist); //从后面删除一个节点
void PrintList(ListNode *plist); //打印单链表
void PushFront(ListNode **pplist, Datatype x); //从前面插入一个data为x的节点
void PopFront(ListNode **pplist); //从前面删除一个节点
ListNode* Find(ListNode* pList, Datatype x); //查找data为x的节点，并返回这个节点
//在pos前插入||删除
void Insert(ListNode **pplist, ListNode *pos, Datatype x);//在所指定的节点前插入一个data为x的节点
void Erase(ListNode **pplist, ListNode *pos);//删除指定的节点
#endif
ListNode.cpp
#include "ListNode.h"
ListNode *BuyNode(Datatype x) //生成节点封装接口
{
ListNode *Node = (ListNode *)malloc(sizeof(ListNode));// 以动态的形式生成一个大小为一个结构体大小的节点
Node->data = x; //所要生成的节点数据
Node->next = NULL; //将生成节点的下个赋为空
return Node;
}
void PrintList(ListNode *plist)//打印单链表
{
ListNode *cur = plist;
while(cur != NULL)
{
printf("%d->",cur->data);//将单链表的数据正向输出
cur = cur->next;
}
printf("NULL\n");
}
void PushBack(ListNode **pplist, Datatype x)//在做这些之前要先理清思路，都有哪几种情况，然后敲
{
//1.空 2.只有一个 3.多个
assert(pplist);
if(*pplist == NULL)//没有节点的时候直接把节点给首节点
{
*pplist = BuyNode(x);
}
else if((*pplist)->next == NULL)
{
(*pplist)->next = BuyNode(x);//只有一个就把生成的节点串在首节点后面
}
else
{
ListNode *cur = *pplist;
while((cur)->next != NULL)
{
cur = cur->next;
}
cur->next = BuyNode(x);
}
}
void PopBack(ListNode **pplist)//和Push一样都要考虑清楚，然后就很好写
{
//1.NULL 2.1个 3.多个
assert(pplist);
if(*pplist == NULL)
{
return;
}
else if((*pplist)->next == NULL)
{
free(*pplist);//只有一个的话直接释放
*pplist = NULL;//一定要将这个节点置空，不然容易成为野指针
}
else
{
ListNode *tmp = *pplist;//先定义两个指针，分别保存要删除的节点和上一个节点
ListNode *cur = tmp;
while(tmp->next != NULL)
{
cur = tmp;
tmp = tmp->next;
}
free(tmp);//删除指定节点
cur->next = NULL;//将上个节点的next给置空
tmp = NULL;//记得置空
}
}
void PushFront(ListNode **pplist, Datatype x)//和尾插一样，只是情况还要具体分析
{
//1.NULL 2.一个 3.多个
assert(pplist);
if(*pplist == NULL)
{
*pplist = BuyNode(x);
}
else
{
ListNode *cur = BuyNode(x);
cur->next = *pplist;
*pplist = cur;
}
}
void PopFront(ListNode **pplist)
{
//1.NULL 2.一个 3.多个
assert(pplist);
if(*pplist == NULL)
{
return;
}
else if((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
ListNode *tmp = *pplist;
*pplist = tmp->next;
free(tmp);
}
}
ListNode* Find(ListNode* plist, Datatype x)//查找节点并不改变数据，所以不用传结构体指针的地址
{
while(plist)
{
if(plist->data == x)//当找到要查找的数时，就直接返回
{
return plist;
}
plist = plist->next;
}
//perror("Find"); //出错打印错误信息
//system("pause");
//exit(EXIT_FAILURE);//程序直接退出
return NULL;
}
void Insert(ListNode **pplist, ListNode *pos, Datatype x)//先调Find
{
//1.NULL 2.在第一个前插或只有一个数据 3.多个
assert(pplist);
assert(pos);
if(*pplist == NULL)
{
*pplist = BuyNode(x);
}
else if(((*pplist)->next == NULL) || (pos == *pplist))
{
PushFront(pplist, x);
}
else
{
ListNode *tmp = *pplist;//这里要找到指定插入节点的上个节点和下个节点
while(tmp->next != pos)
{
tmp = tmp->next;
}
ListNode *p = BuyNode(x);
tmp->next = p;
p->next = pos;
}
}
void Erase(ListNode **pplist, ListNode *pos)//要删除首先就要调用Find函数查找到相应的节点
{
//1.NULL或1个 2.多个
assert(pplist);
assert(pos);
if(((*pplist) == NULL) || ((*pplist)->next) == NULL)//只有一个或者没有节点时直接采用前删
{
PopFront(pplist);
}
else
{
ListNode *tmp = *pplist;
while(tmp->next != pos)
{
tmp = tmp->next;
}
tmp->next = pos->next;
free(pos);
pos = NULL;
}
}
test.cpp
#include "ListNode.h"
struct ListNode* plist;
void test1()
{
PushBack(&plist, 1);
PushBack(&plist, 2);
PushBack(&plist, 3);
PushBack(&plist, 4);
PopBack(&plist);
PopBack(&plist);
PopBack(&plist);
PopBack(&plist);
PopBack(&plist);
PrintList(plist);
}
void test2()
{
PushFront(&plist, 1);
PushFront(&plist, 2);
PushFront(&plist, 3);
PushFront(&plist, 4);
PrintList(plist);
PopFront(&plist);
PopFront(&plist);
PopFront(&plist);
PopFront(&plist);
PopFront(&plist);
PrintList(plist);
}
void test3()
{
ListNode *pos = NULL;
PushBack(&plist, 1);
/*PushBack(&plist, 2);
PushBack(&plist, 3);
PushBack(&plist, 4);*/
pos = Find(plist, 2);
Insert(&plist, pos, 5);
//Erase(&plist, pos);
PrintList(plist);
}
int main()
{
//test1();
//test2();
test3();
system("pause");
return 0;
}
为了更加明确的了解链表的增删查改，在 Linux 环境下来演示一下具体的过程
#include "ListNode.h"
struct ListNode* plist;
void test1()
{
int i = 0;
int j = 0;
printf("尾插，尾删\n");
printf("\n");
while(i<5){
PushBack(&plist, i++);
PrintList(plist);
sleep(1);
}
while(j<5){
PopBack(&plist);
PrintList(plist);
sleep(1);
j++;
}
}
void test2()
{
int i = 0;
int j = 0;
printf("前插，前删\n");
printf("\n");
while(i<5){
PushFront(&plist, i);
PrintList(plist);
sleep(1);
i++;
}while(j<5){
PopFront(&plist);
PrintList(plist);
sleep(1);
j++;
}
}
void test3()
{
int i = 0;
ListNode *pos = NULL;
printf("链表的节点插入、删除和查找\n");
printf("\n");
while(i<5){
PushBack(&plist, i++);
PrintList(plist);
sleep(1);
}
pos = Find(plist, 2);
printf("查找单链表里数据为2的节点i\n");
printf("给2的前面插入5\n");
Insert(&plist, pos, 5);
PrintList(plist);
sleep(1);
printf("删除2\n");
Erase(&plist, pos);
PrintList(plist);
}
int main()
{
test1();
test2();
test3();
return 0;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 数据结构 – 用于构建文件系统的数据结构？
- 荐 用Python解决数据结构与算法问题（三）：线性数据结构之栈
- 数据结构和算法面试题系列-C指针、数组和结构体
- 请问二叉树等数据结构的物理存储结构是怎样的？
- 常用数据结构
- 数据结构 - 树
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
