C語言單鏈表的實(shí)現(xiàn)
更新時(shí)間：2016年04月13日 14:28:37 作者：Lynn-Zhang
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。這篇文章主要介紹了C語言單鏈表的實(shí)現(xiàn) 的相關(guān)資料,需要的朋友可以參考下
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。
鏈表結(jié)構(gòu)：
SList.h
#pragma once
typedef int DataType;
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SListNode;
// 如果要修改鏈表就必須加引用
SListNode* _BuyNode(DataType x); //建立節(jié)點(diǎn)
void PrintSlist(SListNode* pHead); //打印單鏈表
void PushBack(SListNode* & pHead, DataType x); //尾插 （這里用了引用，指明是list的別名，調(diào)用時(shí)傳參，不用傳地址）（引用在.c文件中不可用）
//void PushBack(SListNode** pHead, DataType x); // 這里的第一個(gè)參數(shù)指向鏈表第一個(gè)節(jié)點(diǎn)的指針的地址（調(diào)用時(shí)傳參，傳的是地址）
void PopBack(SListNode* & pHead); //尾刪
void PushFront(SListNode* & pHead, DataType x); //頭插
void PopFront(SListNode* & pHead); //頭刪
void DestoryList(SListNode*& pHead); //清空整個(gè)鏈表
int GetSize(SListNode* pHead); //獲取鏈表長度
SListNode* Find(SListNode* pHead, DataType x); //查找
void Insert(SListNode* pos, DataType x); //某位置后插入數(shù)據(jù)
void Erase(SListNode*& pHead, SListNode* pos); //刪除某位置的數(shù)據(jù)
void DelNonTailNode(SListNode* pos); //刪除一個(gè)無頭單鏈表的非尾節(jié)點(diǎn)
void InsertFrontNode(SListNode* pos, DataType x); // 在無頭單鏈表的一個(gè)非頭節(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn)
SListNode* FindMidNode(SListNode* pHead); //查找中間節(jié)點(diǎn)
SListNode* FindKNode(SListNode* pHead, int k); //查找倒數(shù)第k個(gè)節(jié)點(diǎn)(要求只能遍歷一次)
void PrintTailToHead(SListNode* pHead); //倒著打印單鏈表（遞歸）
//SListNode* Reverse_(SListNode* pHead); //逆置單鏈表（需要接收返回值），原鏈表會(huì)面目全非
void Reverse(SListNode*& pHead); // 將原鏈表逆置
SListNode* Merge(SListNode* pHead1, SListNode* pHead2); //合并兩個(gè)有序鏈表（合并后依然有序）（遞歸）
void Sort(SListNode* pHead); //冒泡排序
SList.cpp
#include"SList.h"
#include <stdio.h>
#include<assert.h>
#include <malloc.h>
SListNode* _BuyNode(DataType x) //建立節(jié)點(diǎn)
{
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.一個(gè)節(jié)點(diǎn)
// 3.多個(gè)節(jié)點(diǎn)
//
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.一個(gè)節(jié)點(diǎn)
// 3.一個(gè)以上的節(jié)點(diǎn)
//
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) //清空整個(gè)鏈表
{
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) //查找節(jié)點(diǎn)
{
SListNode* cur = pHead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void Insert(SListNode* pos, DataType x) // 某位置后插入節(jié)點(diǎn)
{
assert(pos);
SListNode* tmp = _BuyNode(x);
tmp->next = pos->next;
pos->next = tmp;
}
void Erase(SListNode*& pHead, SListNode* pos) //刪除某位置的節(jié)點(diǎn)
{
assert(pos);
assert(pHead);
//pos為頭結(jié)點(diǎn)
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) //// 刪除一個(gè)無頭單鏈表的非尾節(jié)點(diǎn)
{
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) // 在無頭單鏈表的一個(gè)非頭節(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn)
{
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) //查找中間節(jié)點(diǎn)
{
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) //查找倒數(shù)第k個(gè)節(jié)點(diǎn)
{
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) //逆置單鏈表（需要接收返回值）原鏈表會(huì)面目全非
//{
// 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) //合并兩個(gè)有序鏈表（合并后依然有序）遞歸
{
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()
{
// 查找節(jié)點(diǎn) 在某位置插入節(jié)點(diǎn) 刪除某位置節(jié)點(diǎn)
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);
// 刪除一個(gè)無頭單鏈表的非尾節(jié)點(diǎn)
/*SListNode* pos = Find(list, 2);
DelNonTailNode(pos);
PrintSlist(list);*/
// 在無頭單鏈表的一個(gè)非頭節(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn)
/*SListNode* pos = Find(list, 2);
InsertFrontNode(pos, 0);
PrintSlist(list);*/
//查找中間節(jié)點(diǎn)
//PrintSlist(FindMidNode(list));
//查找倒數(shù)第k個(gè)節(jié)點(diǎn)
//SListNode* ret = FindKNode(list, 2);
//PrintSlist(ret);
//倒著打印單鏈表（遞歸）
//PrintTailToHead(list);
//逆置單鏈表
//SListNode* ret = Reverse(list);
//PrintSlist(ret);
//PrintSlist(Reverse_(list));
}
void Test4()
{ //合并兩個(gè)有序鏈表（合并后依然有序）
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;
}
以上內(nèi)容是小編給大家介紹的C語言單鏈表的實(shí)現(xiàn)代碼，希望對(duì)大家有所幫助！
您可能感興趣的文章:
相關(guān)文章
C++實(shí)現(xiàn)數(shù)組的排序/插入重新排序/以及逆置操作詳解
將新的數(shù)字與已經(jīng)排序好的數(shù)組中的數(shù)字一一比較，直到找到插入點(diǎn)，然后將插入點(diǎn)以后的數(shù)字都向后移動(dòng)一個(gè)單位（a[i+1]=a[i]），然后將數(shù)據(jù)插入即可2013-10-10
C語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表&循環(huán)鏈表&靜態(tài)鏈表詳解
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)據(jù)結(jié)構(gòu)中雙鏈表&循環(huán)鏈表&靜態(tài)鏈表的原理與使用，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-09-09
C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(137.單獨(dú)的數(shù)字之二),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
離線安裝visual?studio2022+QT5.12的實(shí)現(xiàn)步驟
近期有需求離線配置C++與QT環(huán)境,本文主要介紹了離線安裝visualstudio2022+QT5.12的實(shí)現(xiàn)步驟,具有一定的參考價(jià)值,感興趣的可以了解一下2024-06-06
關(guān)于C++數(shù)組中重復(fù)的數(shù)字
這篇文章主要介紹得是關(guān)于C++數(shù)組中重復(fù)的數(shù)字，文章以問題描述得形式，對(duì)問題展開分析用不同得方法去解決問題并附上方法得詳細(xì)代碼,需要的朋友可以參考以下文章得具體內(nèi)容2021-11-11
C語言中g(shù)etchar(?)?函數(shù)使用詳解
getchar()?字符輸入函數(shù)，沒有參數(shù)，從輸入緩沖區(qū)里面讀取一個(gè)字，需要注意一次只能讀取一個(gè)字符，這篇文章主要介紹了C語言中g(shù)etchar函數(shù)使用詳解,需要的朋友可以參考下2022-12-12
這篇文章主要為大家詳細(xì)介紹了C語言編寫一個(gè)鏈表，文中安裝步驟介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
這篇文章主要介紹了C++ Virtual關(guān)鍵字的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
C語言動(dòng)態(tài)內(nèi)存的分配最全面分析
動(dòng)態(tài)內(nèi)存是相對(duì)靜態(tài)內(nèi)存而言的。所謂動(dòng)態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動(dòng)態(tài)內(nèi)存是指在堆上分配的內(nèi)存，而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存，本文帶你深入探究C語言中動(dòng)態(tài)內(nèi)存的管理2022-08-08
這篇文章主要給大家介紹了關(guān)于C/C++中宏/Macro的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C/C++具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06