C语言单链表的实现
更新时间:2020年4月25日 17:36 点击:1740
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
链表结构:
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/C++产生随机数函数简单介绍
下一篇: 实例详解C/C++中extern关键字
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了R语言作图:坐标轴的设置方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了R语言删除指定变量或对象的操作方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
- 这篇文章主要介绍了Go语言压缩和解压缩tar.gz文件的方法,实例分析了使用Go语言压缩文件与解压文件的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-05-03
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了R语言基本画图函数与多图多线的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25