今天实现了下链表的基本操作，包括节点的创建，头插尾插，头删尾删，一次遍历寻找链表的中间节点，寻找链表的倒数第x个节点，删除无头链表的非尾节点，链表的逆置，代码如下：
#include "SLinkList.h" #include <stdlib.h> #include <stdio.h> #include <assert.h> void PrintList(SListNode* pHead)//从指针位置打印链表 { while (pHead) { printf("->%d", pHead->data); pHead = pHead->next; } printf("\n"); } static SListNode* _BuyNode(DataType x)//创建新的节点 { SListNode*ret = (SListNode*)malloc(sizeof(SListNode)); ret->next = NULL; ret->data = x; if (ret) { return ret; } printf("创建节点失败\n");//创建失败给出提示 return NULL; } void PushBack(SListNode* & pHead, DataType x)//尾插 { if (pHead == NULL) { pHead = _BuyNode(x); } else { SListNode*tail = pHead; while (tail->next) { tail = tail->next; } tail->next = _BuyNode(x); } } void PopBack(SListNode* & pHead)//尾删 { if (pHead == NULL) { return; } else if (pHead->next->next == NULL) { free(pHead->next); pHead = NULL; } else { SListNode* tail = pHead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void PushFront(SListNode* & pHead, DataType x)//头插 { if (pHead == NULL) { pHead = _BuyNode(x); } else { SListNode*tmp = _BuyNode(x); tmp->next = pHead; pHead = tmp; } } void PopFront(SListNode* & pHead)//t头删 { if (pHead == NULL) { return; } else { SListNode*tail = pHead; pHead = pHead->next; tail->next = NULL; free(tail); } } SListNode* Find(SListNode *pHead, DataType x)//以x查找节点，若存在返回给节点，若不存在返回空 { if (pHead == NULL) { return NULL; } SListNode* tail = pHead; while (tail) { if (tail->data == x) { return tail; } tail = tail->next; } return NULL; } void Insert(SListNode* & pos, DataType x)//所给位置后插入一节点 { SListNode*tmp = _BuyNode(x); if (pos == NULL) { pos = tmp; } else { tmp->next = pos->next; pos->next = tmp; } } void Erase(SListNode * &pos)//删除无头链表的非尾节点 { if (pos == NULL) { return; } else if (pos->next == NULL) { printf("该节点为尾节点，无法删除\n"); } else { SListNode*tmp = pos->next; pos->data = pos->next->data; pos->next = pos->next->next; free(tmp); tmp = NULL; } } void ReveseList(SListNode * &pHead)//链表的逆置 { SListNode*tail = pHead; while (tail->next) { SListNode*tmp=NULL; tmp = tail->next; tail->next = tail->next->next; tmp->next = pHead; pHead = tmp; } } SListNode* FindminList(SListNode*pHead)//一次遍历，寻找链表的中间节点 { assert(pHead); SListNode *quick=pHead; SListNode *slow=pHead; while (quick) { slow = slow->next; if (quick->next) quick = quick->next->next; else return slow; } return slow; } SListNode* FindListPosList(SListNode*pHead, int lastpos)//寻找链表的倒数第lastpos个节点 { SListNode *quick = pHead; SListNode *slow = pHead; while (quick&&lastpos--) { quick = quick->next; } if (quick == NULL) { return slow; } while (quick) { quick = quick->next; slow = slow->next; } return slow; } |
