c语言单链表怎样实现,C语言单链表的实现

待我称王封你为后i 2022-10-15 00:58 190阅读 0赞

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表结构：

SList.h

\#pragma once

typedef int DataType;

typedef struct SListNode

DataType data;

struct SListNode\* next;

\}SListNode;

// 如果要修改链表就必须加引用

SListNode\* \_BuyNode(DataType x); //建立节点

void PrintSlist(SListNode\* pHead); //打印单链表

void PushBack(SListNode\* & pHead, DataType x); //尾插 (这里用了引用，指明是list的别名，调用时传参，不用传地址)(引用在.c文件中不可用)

//void PushBack(SListNode\*\* pHead, DataType x); // 这里的第一个参数指向链表第一个节点的指针的地址(调用时传参，传的是地址)

void PopBack(SListNode\* & pHead); //尾删

void PushFront(SListNode\* & pHead, DataType x); //头插

void PopFront(SListNode\* & pHead); //头删

void DestoryList(SListNode\*& pHead); //清空整个链表

int GetSize(SListNode\* pHead); //获取链表长度

SListNode\* Find(SListNode\* pHead, DataType x); //查找

void Insert(SListNode\* pos, DataType x); //某位置后插入数据

void Erase(SListNode\*& pHead, SListNode\* pos); //删除某位置的数据

void DelNonTailNode(SListNode\* pos); //删除一个无头单链表的非尾节点

void InsertFrontNode(SListNode\* pos, DataType x); // 在无头单链表的一个非头节点前插入一个节点

SListNode\* FindMidNode(SListNode\* pHead); //查找中间节点

SListNode\* FindKNode(SListNode\* pHead, int k); //查找倒数第k个节点(要求只能遍历一次)

void PrintTailToHead(SListNode\* pHead); //倒着打印单链表(递归)

//SListNode\* Reverse\_(SListNode\* pHead); //逆置单链表(需要接收返回值)，原链表会面目全非

void Reverse(SListNode\*& pHead); // 将原链表逆置

SListNode\* Merge(SListNode\* pHead1, SListNode\* pHead2); //合并两个有序链表(合并后依然有序)(递归)

void Sort(SListNode\* pHead); //冒泡排序

SList.cpp

\#include"SList.h"

\#include

SListNode\* \_BuyNode(DataType x) //建立节点

SListNode\* tmp = (SListNode\*)malloc(sizeof(SListNode));

tmp->data = x;

tmp->next = NULL;

return tmp;

void PrintSlist(SListNode\* pHead) // 打印单链表

SListNode\* cur = pHead;

while (cur)

printf("%d->", cur->data);

cur = cur->next;

printf("NULL\\n");

//void PushBack(SListNode\*\* ppHead, DataType x) //尾插

//\{

// assert(ppHead);

// // 1.空

// // 2.不为空

// if(\*ppHead == NULL)

// \{

// \*ppHead = \_BuyNode(x);

// \}

// else

// \{

// // 找尾

// SListNode\* tail = \*ppHead;

// while(tail->next != NULL)

// \{

// tail = tail->next;

// \}

// tail->next = \_BuyNode(x);

// \}

//\}

void PushBack(SListNode\* & pHead, DataType x) //尾插

// 1.空

// 2.不为空

if (pHead == NULL)

pHead = \_BuyNode(x);

else

// 找尾

SListNode\* tail = pHead;

while (tail->next != NULL)

tail = tail->next;

tail->next = \_BuyNode(x);

void PopBack(SListNode\* & pHead) // 尾删

// 1.空

// 2.一个节点

// 3.多个节点

if (pHead == NULL)

return;

else if (pHead->next == NULL)

free(pHead);

pHead = NULL;

else

SListNode\* tail = pHead;

SListNode\* prev = NULL;

while (tail->next)

prev = tail;

tail = tail->next;

free(tail);

prev->next = NULL;

void PushFront(SListNode\* & pHead, DataType x) //头插

// 1.空

// 2.不空

if (pHead == NULL)

pHead = \_BuyNode(x);

else

SListNode\* tmp = \_BuyNode(x);

tmp->next = pHead;

pHead = tmp;

void PopFront(SListNode\*& pHead) //头删

// 1.空

// 2.一个节点

// 3.一个以上的节点

if (pHead == NULL)

return;

else if (pHead->next == NULL)

free(pHead);

pHead = NULL;

else

SListNode\* tmp = pHead;

pHead = pHead->next;

free(tmp);

void DestoryList(SListNode\*& pHead) //清空整个链表

SListNode\* cur = pHead;

while (cur)

SListNode\* tmp = cur;

cur = cur->next;

free(tmp);

pHead = NULL;

int GetSize(SListNode\* pHead) //获取链表长度

assert(pHead);

SListNode\* cur = pHead;

int count = 0;

while (cur)

count++;

cur = cur->next;

return count;

SListNode\* Find(SListNode\* pHead, DataType x) //查找节点

SListNode\* cur = pHead;

while (cur)

if (cur->data == x)

return cur;

cur = cur->next;

return NULL;

void Insert(SListNode\* pos, DataType x) // 某位置后插入节点

assert(pos);

SListNode\* tmp = \_BuyNode(x);

tmp->next = pos->next;

pos->next = tmp;

void Erase(SListNode\*& pHead, SListNode\* pos) //删除某位置的节点

assert(pos);

assert(pHead);

//pos为头结点

if (pHead == pos)

pHead = pHead->next;

free(pos);

return;

SListNode\* prev = pHead;

while (prev)

if (prev->next == pos)

prev->next = pos->next;

free(pos);

break;

prev = prev->next;

void DelNonTailNode(SListNode\* pos) 删除一个无头单链表的非尾节点

assert(pos);

assert(pos->next);

SListNode\* del = pos->next;

SListNode\* dnext = del->next;

pos->data = del->data;

pos->next = dnext;

free(del);

void InsertFrontNode(SListNode\* pos, DataType x) // 在无头单链表的一个非头节点前插入一个节点

assert(pos);

SListNode\* tmp = \_BuyNode(pos->data);

tmp->next = pos->next;

pos->next = tmp;

pos->data = x;

void Sort(SListNode\* pHead) //冒泡排序

assert(pHead);

int size = GetSize(pHead);

for (int i = 0; i < size - 1; i++)

SListNode\* left = pHead;

SListNode\* right = pHead->next;

for (int j = 0; j < size - i - 1; j++)

if (left->data>right->data)

int tmp = left->data;

left->data = right->data;

right->data = tmp;

right = right->next;

left = left->next;

SListNode\* FindMidNode(SListNode\* pHead) //查找中间节点

SListNode\* fast = pHead;

SListNode\* slow = pHead;

while (fast&&fast->next)

slow = slow->next;

fast = fast->next->next;

return slow;

SListNode\* FindKNode(SListNode\* pHead, int k) //查找倒数第k个节点

SListNode\* fast = pHead;

SListNode\* slow = pHead;

while (fast && k--)

fast = fast->next;

if (k > 0)

return NULL;

while (fast)

slow = slow->next;

fast = fast->next;

return slow;

void PrintTailToHead(SListNode\* pHead) //倒着打印单链表(递归)

if (pHead)

PrintTailToHead(pHead->next);

printf("%d ", pHead->data);

//SListNode\* Reverse\_(SListNode\* pHead) //逆置单链表(需要接收返回值)原链表会面目全非

//\{

// SListNode\* cur = pHead;

// SListNode\* newHead = NULL;

// while (cur)

// \{

// SListNode\* tmp = cur;

// cur = cur->next;

// tmp->next = newHead;

// newHead = tmp;

// \}

// return newHead;

//\}

void Reverse(SListNode\*& pHead) //逆置单链表

SListNode\* cur = pHead;

SListNode\* newHead = NULL;

while (cur)

SListNode\* tmp = cur;

cur = cur->next;

tmp->next = newHead;

newHead = tmp;

pHead = newHead;

//return newHead;

SListNode\* Merge(SListNode\* pHead1, SListNode\* pHead2) //合并两个有序链表(合并后依然有序)递归

if (pHead1 == NULL)

return pHead2;

else if (pHead2 == NULL)

return pHead1;

SListNode\* pMergedHead = NULL;

if (pHead1->data < pHead2->data)

pMergedHead = pHead1;

pMergedHead->next = Merge(pHead1->next, pHead2);

else

pMergedHead = pHead2;

pMergedHead->next = Merge(pHead1, pHead2->next);

return pMergedHead;

Test.cpp

\#include "SList.h"

\#include

void Test1()

// 尾插 打印 尾删 头插 头删 清空链表

SListNode\* list = NULL;

PushBack(list, 1);

PushBack(list, 2);

PushBack(list, 3);

PushBack(list, 4);

PrintSlist(list);

PopBack(list);

PrintSlist(list);

PushFront(list,0);

PrintSlist(list);

PopFront(list);

PrintSlist(list);

DestoryList(list);

PrintSlist(list);

void Test2()

// 查找节点 在某位置插入节点 删除某位置节点

SListNode\* list = NULL;

PushBack(list, 1);

PushBack(list, 2);

PushBack(list, 3);

PushBack(list, 4);

PrintSlist(list);

SListNode\* pos = Find(list, 2);

Insert(pos, 0);

PrintSlist(list);

Erase(list, Find(list, 0));

PrintSlist(list);

void Test3()

SListNode\* list = NULL;

PushBack(list, 1);

PushBack(list, 2);

PushBack(list, 3);

PushBack(list, 4);

PushBack(list, 5);

PushBack(list, 6);

PrintSlist(list);

// 删除一个无头单链表的非尾节点

/\*SListNode\* pos = Find(list, 2);

DelNonTailNode(pos);

PrintSlist(list);\*/

// 在无头单链表的一个非头节点前插入一个节点

/\*SListNode\* pos = Find(list, 2);

InsertFrontNode(pos, 0);

PrintSlist(list);\*/

//查找中间节点

//PrintSlist(FindMidNode(list));

//查找倒数第k个节点

//SListNode\* ret = FindKNode(list, 2);

//PrintSlist(ret);

//倒着打印单链表(递归)

//PrintTailToHead(list);

//逆置单链表

//SListNode\* ret = Reverse(list);

//PrintSlist(ret);

//PrintSlist(Reverse\_(list));

void Test4()

\{ //合并两个有序链表(合并后依然有序)

SListNode\* list = NULL;

PushBack(list, 4);

PushBack(list, 2);

PushBack(list, 1);

PushBack(list, 4);

PrintSlist(list);

Sort(list);

PrintSlist(list);

/\*SListNode\* list1 = NULL;

PushBack(list1, 2);

PushBack(list1, 3);

PushBack(list1, 0);

PrintSlist(list);

Sort(list1);

PrintSlist(list1);

SListNode\* ret = Merge(list, list1);

PrintSlist(ret);

PrintSlist(list);

PrintSlist(list1);\*/

int main()

//Test1();

//Test2();

//Test3();

Test4();

system("pause");

return 0;

以上内容是小编给大家介绍的C语言单链表的实现代码，希望对大家有所帮助！

c语言单链表怎样实现,C语言单链表的实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【数据结构】---单链表【C语言实现】

相关 c语言单链表怎样实现,C语言单链表的实现

相关 c语言链表的尾指针,C语言单链表实现方法详解

相关 C语言单链表

相关 C语言实现单链表

相关 C语言单链表

相关 C语言单链表

相关 [c语言]单链表的实现

相关链表的C语言实现之单链表的实现

相关顺序表单链表C语言实现