C语言单链表的实现

2024-10-02 20:00:08

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

链表结构：

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 <stdio.h>
#include<assert.h>
#include <malloc.h>
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<stdlib.h>
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, 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语言实现单链表算法示例分享

复制代码代码如下: #include <stdio.h>#include <stdlib.h>typedef char DataType;typedef struct Node{ DataType data; struct Node * Next;}ListNode,* LinkList;void Judement(LinkList head){ //判断分配内存 if (!head){ printf("Overflow.");
C语言单链表常见操作汇总

C语言的单链表是常用的数据结构之一,本文总结了单链表的常见操作,实例如下: #include<stdio.h> #include<stdlib.h> //定义单链表结构体 typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }LNode,*LinkList; //创建单链表 void Build(LinkList L) { int n; LinkList p,q; p=L; pr
C语言实现单链表实现方法

C语言实现单链表实现方法链表和我们之前实现过的顺序表一样,都是简单的数据结构,链表分为单向链表.双向链表.循环链表.而单向链表又分为两种实现方法,一种为带头节点的单链表,一种为不带头节点的单链表.我们来具体看看不带头节点的单链表的实现单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点. 今天我们来实现一些单链表的简单接口先看看单链表的结构: (为了通用性,我们将类型重命名为DataType) typedef int DataType; //
用C语言实现单链表的各种操作(二)

上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序. 复制代码代码如下: /* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){ LinkList *p; int n,i,j; int temp; n = ListLength(head); if(head == NULL || head->next == NULL) return head;
C语言单链表实现多项式相加

本文实例为大家分享了C语言单链表实现多项式相加的具体代码,供大家参考,具体内容如下 //多项式的相加和相乘 #include<stdio.h> #include<stdlib.h> #pragma warning(disable:4996)//兼容scanf typedef struct node { int coef; int expon; struct node* link; }Polynode,*Polynomial; Polynomial InsertPolyLinklis
数据结构 C语言实现循环单链表的实例

数据结构 C语言实现循环单链表的实例实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环
C语言创建和操作单链表数据结构的实例教程

1,为什么要用到链表数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性.但数组也同样存在一些弊病.如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一.我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费. 我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要.链表就是我们需要的动态数组.它是在程序的执行过程中根据需要有数据存储就向系统要求
用C语言实现单链表的各种操作(一)

最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的<数据结构>(C 语言版),中的例子和后面的习题进行改编的.首先,是单链表的各种实现,其中,包含了一些常考的知识点.例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现.下面这个是单链表的结构体的定义: 复制代码代码如下: typedef struct LNode{ ElemType data; struct LNode *next;}LinkList; 下面的基本的单链表的操作:其
C语言实现单链表逆序与逆序输出实例

单链表的逆序输出分为两种情况,一种是只逆序输出,实际上不逆序:另一种是把链表逆序.本文就分别实例讲述一下两种方法.具体如下: 1.逆序输出实例代码如下: #include<iostream> #include<stack> #include<assert.h> using namespace std; typedef struct node{ int data; node * next; }node; //尾部添加 node * add(int n, node * h
C语言之单链表的插入、删除与查找

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素.要实现对单链表中节点的插入.删除与查找的功能,就要先进行的单链表的初始化.创建和遍历,进而实现各功能,以下是对单链表节点的插入.删除.查找功能的具体实现: #include<stdio.h> #include<stdlib.h> #include<string.h> typedef int ElemType; /** *链表通用类型 *ElemType 代表自定义的数据类型 *struct

C语言单链表的实现

相关推荐

随机推荐