C語(yǔ)言單鏈表的實(shí)現(xià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); //獲取鏈表長(zhǎng)度 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è)無(wú)頭單鏈表的非尾節(jié)點(diǎn) void InsertFrontNode(SListNode* pos, DataType x); // 在無(wú)頭單鏈表的一個(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) //獲取鏈表長(zhǎng)度 { 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è)無(wú)頭單鏈表的非尾節(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) // 在無(wú)頭單鏈表的一個(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è)無(wú)頭單鏈表的非尾節(jié)點(diǎn) /*SListNode* pos = Find(list, 2); DelNonTailNode(pos); PrintSlist(list);*/ // 在無(wú)頭單鏈表的一個(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語(yǔ)言單鏈表的實(shí)現(xiàn)代碼,希望對(duì)大家有所幫助!
- C語(yǔ)言之單鏈表的插入、刪除與查找
- C語(yǔ)言實(shí)現(xiàn)單鏈表逆序與逆序輸出實(shí)例
- C語(yǔ)言單鏈表常見(jiàn)操作匯總
- c語(yǔ)言實(shí)現(xiàn)單鏈表算法示例分享
- C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加
- 數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言實(shí)現(xiàn)循環(huán)單鏈表的實(shí)例
- C語(yǔ)言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)
- C語(yǔ)言實(shí)現(xiàn)單鏈表實(shí)現(xiàn)方法
- C語(yǔ)言單鏈表版學(xué)生信息管理系統(tǒng)
- C語(yǔ)言單鏈表實(shí)現(xiàn)方法詳解
相關(guān)文章
Qt連接MySQL數(shù)據(jù)庫(kù)的實(shí)現(xiàn)(保姆級(jí)成功版教程)
本文主要介紹了Qt連接MySQL數(shù)據(jù)庫(kù)的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06C++模擬實(shí)現(xiàn)vector示例代碼圖文講解
這篇文章主要介紹了C++容器Vector的模擬實(shí)現(xiàn),Vector是一個(gè)能夠存放任意類型的動(dòng)態(tài)數(shù)組,有點(diǎn)類似數(shù)組,是一個(gè)連續(xù)地址空間,下文更多詳細(xì)內(nèi)容的介紹,需要的小伙伴可以參考一下2023-02-02C語(yǔ)言將24小時(shí)制轉(zhuǎn)換為12小時(shí)制的方法
這篇文章主要介紹了C語(yǔ)言將24小時(shí)制轉(zhuǎn)換為12小時(shí)制的方法,涉及C語(yǔ)言針對(duì)時(shí)間的相關(guān)操作技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下2015-07-07C++實(shí)現(xiàn)簡(jiǎn)單校園導(dǎo)游系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單校園導(dǎo)游系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03C/C++?Qt?數(shù)據(jù)庫(kù)與ComBox實(shí)現(xiàn)多級(jí)聯(lián)動(dòng)示例代碼
Qt中的SQL數(shù)據(jù)庫(kù)組件可以與ComBox組件形成多級(jí)聯(lián)動(dòng)效果,在日常開(kāi)發(fā)中多級(jí)聯(lián)動(dòng)效果應(yīng)用非常廣泛,今天給大家分享二級(jí)ComBox菜單如何與數(shù)據(jù)庫(kù)形成聯(lián)動(dòng),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2021-12-12