当前位置: 首页 > >

C++单向链表之创建、插入、删除、查找、交换链表节点

发布时间:

链表:
? ?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。
? ?下面直接通过代码进行展示:包括初始化一个可以指向任何数据类型的链表、链表中指定位置插入节点元素、链表中删除指定位置的节点元素、获取链表的长度、在链表中查找指定的元素并返回当前元素所在的索引值、返回链表第一个节点、释放链表内存、打印链表、交换链表节点(链表从前向后第K个节点与从后向前第K个节点进行交换)。
LinkList.h


#pragma once
#include
#include

// 链表结点
typedef struct LINKNODE
{
void* data; // 可以指向任何类型的数据
LINKNODE* next;
}LinkNode;

// 链表结构体
typedef struct LINKLIST
{
int size;
LinkNode* head;
}LinkList;

// 打印函数指针
typedef void(*PRINTLINKNODE)(void*);

// 初始化链表
LinkList* Init_LinkList();

// 指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);

// 交换顺序与逆序对应的第Key个值
void Key_LinkList(LinkList* list, int key);

// 指定位置删除
void RemoveByPos_LinkList(LinkList* list, int pos);

// 获得链表的长度
int GetLinkListSize(LinkList* list);

// 查找(根据数据返回索引)
int Find_LinkList(LinkList* list, void* data);

// 返回第一个结点
void* Front_LinkList(LinkList* list);

// 释放链表内存
void FreeMem_LinkList(LinkList* list);

// 打印链表
void Print_LinkList(LinkList* list, PRINTLINKNODE);


LinkList.cpp


#include "LinkList.h"

// 初始化链表
LinkList* Init_LinkList()
{
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;
}

// 指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data)
{
if (list == NULL || data == NULL)
{
return;
}
if (pos < 0 || pos > list->size)
{
pos = list->size;
}
// 创建新的结点
LinkNode* InsertNode = (LinkNode*)malloc(sizeof(LinkNode));
InsertNode->data = data;
InsertNode->next = NULL;
// 找结点
LinkNode* pCurrent = list->head;
for (int i = 0; i < pos; i++)
{
pCurrent = pCurrent->next;
}
// 将新结点插入链表
InsertNode->next = pCurrent->next;
pCurrent->next = InsertNode;
// 链表大小加1
list->size++;
}

// 指定位置删除
void RemoveByPos_LinkList(LinkList* list, int pos)
{
if (list == NULL)
{
return;
}
if (pos < 0 || pos >= list->size)
{
return;
}
LinkNode* pCurrent = list->head;
for (int i = 0; i < pos; i++)
{
pCurrent = pCurrent->next;
}
LinkNode* pDel = pCurrent->next;
pCurrent->next = pCurrent->next->next;
free(pDel);
// 链表长度减一
list->size--;
}

// 获得链表的长度
int GetLinkListSize(LinkList* list)
{
if (list == NULL)
{
return -1;
}
return list->size;
}

// 查找(根据数据返回索引)
int Find_LinkList(LinkList* list, void* data)
{
if (list == NULL || data == NULL)
{
return -1;
}
int pos = -1;
LinkNode* pCurrent = list->head->next;
for (int i = 0; i < list->size; i++)
{
if (pCurrent->data == data)
{
pos = i;
break;
}
pCurrent = pCurrent->next;
}
return pos;
}

// 返回第一个结点
void* Front_LinkList(LinkList* list)
{
return list->head->next->data;
}

// 释放链表内存
void FreeMem_LinkList(LinkList* list)
{
if (list == NULL)
{
return;
}
LinkNode* pCurrent = list->head;
while (pCurrent != NULL)
{
LinkNode* pDel = pCurrent;
pCurrent = pCurrent->next;
free(pDel);
}
list->size = 0;
free(list);
}

// 打印链表
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;
}
}

// 交换 顺序与逆序对应的第Key个值
void Key_LinkList(LinkList* list, int key)
{
int total_len;
int change;

//获取链表长度
total_len = GetLinkListSize(list);

if (key / 2 == 1)
{
printf("交换后与交换前,链表数据无变化 !!
");
return;
}

if (key < (total_len - key))
{
change = key;
}
else
{
change = total_len - key - 1;
}

LinkNode* pCurrent = list->head;

for (int i = 0; i < total_len; i++)
{
pCurrent = pCurrent->next;
if (i == change)
{
Insert_LinkList(list, total_len - change, pCurrent->data);
}
else if (i == total_len - change - 1)
{
Insert_LinkList(list, change, pCurrent->data);
}
}
RemoveByPos_LinkList(list, change + 1);
RemoveByPos_LinkList(list, total_len - change - 1);
}

main.cpp


// list.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include
#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 = Init_LinkList();

//创建数据
Person p1 = { "aaa", 6, 6 };
Person p2 = { "bbb", 5, 5 };
Person p3 = { "ccc", 4, 4 };
Person p4 = { "ddd", 3, 3 };
Person p5 = { "eee", 2, 2 };
Person p6 = { "fff", 1, 1 };
Person p7 = { "ggg", 0, 0 };

//数据插入链表
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);
Insert_LinkList(list, 0, &p6);
Insert_LinkList(list, 0, &p7);

//打印
printf("打印原始链表数据:
");
Print_LinkList(list, MyPrint);
printf("
");
printf("
");

//交换,Key必须大于0
printf("给定一个数字Key,把从前向后第Key个节点与从后向前第Key个节点进行交换:
");
int Key = 2;

if (Key < 1 || Key > (GetLinkListSize(list) -1 ))
{
printf("error: key invaid !!");
return 0;
}

printf("Key = %d
",Key);
//交换
Key_LinkList(list, Key -1);
//打印
Print_LinkList(list, MyPrint);
printf("
");
printf("
");

//删除3
printf("测试删除某一个节点:
");
RemoveByPos_LinkList(list, 3);
//打印
Print_LinkList(list, MyPrint);
printf("
");
printf("
");

//返回第一个结点
printf("-----查找链表首个节点------------
");
Person* ret = (Person*)Front_LinkList(list);
printf("Name:%s Age:%d Score:%d
", ret->name, ret->age, ret->score);

//销毁链表
Front_LinkList(list);
getchar();
return 0;
}

如下效果图:



友情链接: