单向链表和双向链表图解（单链表和双向链表的区别）

大家好，我是讯享网，很高兴认识大家。

用于代码记录，复习巩固

代码参考课程链接：【C++数据结构（看过c++提高之后再看）黑马培训课程】 ;vd_source=95f76c174fcbb64e00e8ec91f6a7d016

线性表：也称有序表，它的每一个实例都是元素的一个有序集合。零个或多个相同数据类型的元素的有限序列。

特征：1、数据元素之前是有顺序的

2、数据元素的个数是有限的

3 、数据元素的类型相同

链式描述：线性表的元素在内存中存储位置是随机的额，每个元素都有一个明确的指针指向线性表的下一个元素的位置(地址)。

如上图1，设l=(e0,e1, ·· ·,e忙1) 是一个线性表。在对这个线性表的一个可能的链式描述中， 每个元素都在一个单独的节点中描述、每一个节点都有一个链域，它的值是线性表的下一个元素的位置，即地址。这样一来，元素e(i)的节点链接着元素e(i+1) 的节点， 0≤i<n-1 。元素e(n-1)的节点没有其他节点可链接， 因此链域的值为NULL。

变量firstNode 用来指向链式描述的第1个节点。图1是线性表L 的链式描述。链域的值用箭头表示。为了确定元素e2 的位置，必须从firstNode 开始，从其中的链域找到e1节点的指针，再从e1节点的链域找到e2 节点的指针。

每一个节点只有一个链，这种结构称为单向链表。链表从左到右，每一个节点（最后一个节点除外）都链接着下一个节点，最后一个节点的链域值为NULL。这样的结构也称为链条。

二、参考课程代码：

头文件：LinkList.h

#ifndef LINKLIST_H

#define LINKLIST_H

#include<stdio.h>

#include<stdlib.h>

//链表节点结构体

typedef struct LINKNODE

{

//节点的数据域

//无类型指针指向任何数据

void* data;

//节点的指针域

//数据类型LINKNODE

struct LINKNODE next;

}Linknode;

//链表结构体

typedef struct LINKLIST

{

//头节点

Linknode* head;

//链表大小

int size;

}LinkList;

//打印的回调函数指针

typedef void(PRINTLINKNODE)(void);

//各类API

//1、初始化链表

LinkList* LinkList_Init();

//2、指定位置插入数据

void Insert_LinkList(LinkList* list,int pos,void* data);

//3、删除指定位置数据

void RemoveByPos_LinkList(LinkList* list, int pos);

//4、根据某个值查找某个值

int Find_LinkList(LinkList* list,void* data);

//5、返回链表长度

int Size_LinkList(LinkList* list);

//6、返回第一个节点

void* Front_LinkList(LinkList* list);

//7、释放链表内存

void FreeSpace_LinkList(LinkList* list);

//8、打印链表

//由于是无类型指针数据，所以需要有回调函数

void Print_LinkList(LinkList* list, PRINTLINKNODE print);

#endif

源文件：LinkList.c

#include“LinkList.h”

//1、初始化链表

LinkList* LinkList_Init()

{

//开辟空间

LinkList* list = (LinkList)malloc(sizeof(LinkList));

//链表初始化

list->size = 0;

//头节点

list->head = (Linknode)malloc(sizeof(Linknode));

//节点初始化-不保存数据信息

list->head->data = NULL;

list->head->next = NULL;

return list;

}

//2、指定位置插入数据

void Insert_LinkList(LinkList* list, int pos, void* data)

{

if (list == NULL)

{

return;

}

if (data == NULL)

{

return;

}

if (pos< -1 || pos>list->size)

{

return;

}

//插入数据-节点next域指向插入的是节点

//插入的数据都需要创建一个新节点，并且需要管理内存

Linknode* newnode = (Linknode)malloc(sizeof(Linknode));

newnode->data = data;

newnode->next = NULL;

//寻找插入的节点

//辅组节点存放pos的节点

Linknode pCurrent = list->head;

for (int i = 0; i < pos; i++)

{

pCurrent = pCurrent->next;

}

//插入

newnode->next = pCurrent->next;

pCurrent->next = newnode;

//更像大小

list->size++;

}

//3、删除指定位置数据

void RemoveByPos_LinkList(LinkList* list, int pos)

{

if (list == NULL)

{

return;

}

if (pos< -1 || pos>list->size)

{

return;

}

//辅助指针

Linknode* pCurrent = list->head;

for (int i = 0; i < pos; i++)

{

pCurrent = pCurrent->next;

}

//缓存删除

Linknode* pDel = pCurrent->next;

pCurrent->next = pDel->next;

//释放删除节点的内存

free(pDel);

//更新大小

list->size–;

}

讯享网

//4、根据某个值查找某个值

//地址查找

int Find_LinkList(LinkList* list, void* data)

{

if (list == NULL)

{

return -1;

}

if (data == NULL)

{

return -1;

}

//查找

Linknode* pCurrent = list->head->next;

int i = 0;

//最后一个节点的标识为NULL

while (pCurrent != NULL)

{

if (pCurrent->data == data)

{

break;

}

i++;

//节点移动

pCurrent = pCurrent->next;

}

return i;

}

//5、返回链表长度

int Size_LinkList(LinkList* list)

{

return list->size;

}

//6、返回第一个节点

void* Front_LinkList(LinkList* list)

{

return list->head->next->data;

}

//7、释放链表内存

void FreeSpace_LinkList(LinkList* list)

{

if (list == NULL)

{

return;

}

//每一个节点都需要释放

Linknode* pCurrent = list->head;

int i = 0;

while (pCurrent != NULL)

{

//缓存下一个节点

Linknode* pNext = pCurrent->next;

free(pCurrent);

//节点移动

pCurrent = pNext;

}

//释放链表内存

list->size = 0;

free(list);

}

//8、打印链表

//由于是无类型指针数据，所以需要有回调函数

void Print_LinkList(LinkList* list, PRINTLINKNODE print)

{

if (list == NULL)

{

return;

}

//辅助指针变量

Linknode* pCurrent = list->head->next;

while (pCurrent != NULL)

{

print(pCurrent->data);

//节点移动

pCurrent = pCurrent->next;

}

main文件：02 线性表链式存储_单向链表.c

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include“LinkList.h”

//链表

//数据域指针域

//自定义数据

typedef struct PERSON

{

char name[64];

int age;

int score;

}Person;

//打印函数

void MyPrint(void* data)

{

//类型转化

Person* p = (Person)data;

printf(“Name:%s Age:%d Score:%d ”, p->name, p->age, p->score);

}

int main()

{

//创建链表

LinkList list = LinkList_Init();

//创建数据

Person p1 = { “aaa”,12,99 };

Person p2 = { “bbb”,27,87 };

Person p3 = { “ccc”,42,78 };

Person p4 = { “ddd”,13,95 };

Person p5 = { “eee”,16,86 };

//插入数据

Insert_LinkList(list, 0, &p1);

Insert_LinkList(list, 0, &p2);

Insert_LinkList(list, 0, &p3);

Insert_LinkList(list, 0, &p4);

Insert_LinkList(list, 0, &p5);

//打印数据

//数据类型-回调函数

Print_LinkList(list, MyPrint);

//删除3号位置

RemoveByPos_LinkList(list, 3);

printf(“——————– ”);

//打印

Print_LinkList(list, MyPrint);

//返回第一个节点

printf(“——返回结果——- ”);

Person* ret = (Person*)Front_LinkList(list);

printf(“Name:%s Age:%d Score:%d ”, ret->name, ret->age, ret->score);

//销毁链表

FreeSpace_LinkList(list);

system(“pause”);

return 0;

}

单向链表和双向链表图解（单链表和双向链表的区别）

相关推荐