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语言单链表的实现代码,希望对大家有所帮助!
赞 (0)