C說話單鏈表的完成。本站提示廣大學習愛好者:(C說話單鏈表的完成)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話單鏈表的完成正文
單鏈表是一種鏈式存取的數據構造,用一組地址隨意率性的存儲單位寄存線性表中的數據元素。
鏈表構造:
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說話單鏈表的完成代碼,願望對年夜家有所贊助!