#pragma oncetypedef int DataType;typedef struct SListNode{DataType data;struct SListNode* next;}SListNode;// 如果要修改鏈表就必須加引用SListNode* _BuyNode(DataType x); //建立節(jié)點void PrintSlist(SListNode* pHead); //打印單鏈表void PushBack(SListNode* & pHead, DataType x); //尾插 （這里用了引用，指明是list的別名，調(diào)用時傳參，不用傳地址）（引用在.c文件中不可用）//void PushBack(SListNode** pHead, DataType x); // 這里的第一個參數(shù)指向鏈表第一個節(jié)點的指針的地址（調(diào)用時傳參，傳的是地址）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); //某位置后插入數(shù)據(jù)void Erase(SListNode*& pHead, SListNode* pos); //刪除某位置的數(shù)據(jù)void DelNonTailNode(SListNode* pos); //刪除一個無頭單鏈表的非尾節(jié)點void InsertFrontNode(SListNode* pos, DataType x); // 在無頭單鏈表的一個非頭節(jié)點前插入一個節(jié)點SListNode* FindMidNode(SListNode* pHead); //查找中間節(jié)點SListNode* FindKNode(SListNode* pHead, int k); //查找倒數(shù)第k個節(jié)點(要求只能遍歷一次)void PrintTailToHead(SListNode* pHead); //倒著打印單鏈表（遞歸）//SListNode* Reverse_(SListNode* pHead); //逆置單鏈表（需要接收返回值），原鏈表會面目全非void Reverse(SListNode*& pHead); // 將原鏈表逆置SListNode* Merge(SListNode* pHead1, SListNode* pHead2); //合并兩個有序鏈表（合并后依然有序）（遞歸）void Sort(SListNode* pHead); //冒泡排序

#include"SList.h"#include <stdio.h>#include<assert.h>#include <malloc.h>SListNode* _BuyNode(DataType x) //建立節(jié)點{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.一個節(jié)點// 3.多個節(jié)點//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.一個節(jié)點// 3.一個以上的節(jié)點//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) //查找節(jié)點{SListNode* cur = pHead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}void Insert(SListNode* pos, DataType x) // 某位置后插入節(jié)點{assert(pos);SListNode* tmp = _BuyNode(x);tmp->next = pos->next;pos->next = tmp;}void Erase(SListNode*& pHead, SListNode* pos) //刪除某位置的節(jié)點{assert(pos);assert(pHead);//pos為頭結(jié)點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) //// 刪除一個無頭單鏈表的非尾節(jié)點{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) // 在無頭單鏈表的一個非頭節(jié)點前插入一個節(jié)點{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é)點{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個節(jié)點{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;}

#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é)點 在某位置插入節(jié)點 刪除某位置節(jié)點 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);// 刪除一個無頭單鏈表的非尾節(jié)點 /*SListNode* pos = Find(list, 2);DelNonTailNode(pos);PrintSlist(list);*/// 在無頭單鏈表的一個非頭節(jié)點前插入一個節(jié)點/*SListNode* pos = Find(list, 2);InsertFrontNode(pos, 0);PrintSlist(list);*///查找中間節(jié)點//PrintSlist(FindMidNode(list));//查找倒數(shù)第k個節(jié)點//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;}