- 链表节点的删除与插入;
- 链表节点的查询;
- 链表的快慢指针用法;
- 链表的逆置(两种方法);(暂不考虑递归实现)
- 有序链表和合并;
头文件"Slist.h"
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DateType;
typedef struct PlistNode
{
DateType _date;
struct PlistNode* _next;
} PlistNode;
PlistNode* GetNode(DateType x);
void Print(PlistNode* plist); //打印函数
void PushBack(PlistNode** pplist, DateType x); //尾插
void PopBack(PlistNode** pplist); //尾删
void PushFront(PlistNode** pplist, DateType x); //头插
void PopFront(PlistNode** pplist); //头删
PlistNode* ListFind(PlistNode* plist, DateType x); //查找节点
void ListInsertAfter(PlistNode** pos, DateType x); //在一个链表的pos位后插入
void SListEraseAfter(PlistNode** pos); //删除某个链表pos后的一个节点
PlistNode* middleNode(PlistNode** head); //返回链表的中间节点(快慢指针实现)
PlistNode* reverseList1(PlistNode** head); //逆转链表(改变指针方向)
PlistNode* reverseList2(PlistNode** head); //逆转链表(头插法每一个原链表值插入新链表)
PlistNode* FindKNode(PlistNode** head, int k); //返回该链表中倒数第k个结点(含第k个节点)后所有结点(快慢指针实现)
源文件"Slist.c"
#include "Slist.h"
void Print(PlistNode* plist) //打印函数
{
PlistNode* cur = plist;
while (cur != NULL)
{
printf("%d\n", cur->_date);
cur = cur->_next;
}
printf("\n");
}
PlistNode* GetNode(DateType x) //得到一个新的节点,并将要插入得值赋给该节点
{
PlistNode* NewNode = (PlistNode*)malloc(sizeof(PlistNode));
NewNode->_date = x;
NewNode->_next = NULL;
return NewNode; //新节点的指针
}
void PushBack(PlistNode** plist, DateType x) //尾插
{
PlistNode* NewNode = GetNode(x);
if (*plist == NULL)
*plist = NewNode;
else
{
PlistNode* tail = *plist;
while (tail->_next != NULL)
tail = tail->_next;
tail->_next = NewNode;
}
}
void PopBack(PlistNode** plist) //尾删
{
if (*plist == NULL || (*plist)->_next == NULL)
{
free(*plist);
*plist = NULL;
}
else
{
PlistNode* cur = *plist;
PlistNode* prv = NULL;
while (cur->_next != NULL)
{
prv = cur;
cur = cur->_next;
}
free(cur);
cur = NULL;
prv->_next = NULL;
}
}
void PushFront(PlistNode** plist, DateType x) //头插
{
PlistNode* NewNode = GetNode(x);
if (*plist == NULL)
*plist = NewNode;
else
{
NewNode->_next = *plist;
*plist = NewNode;
}
}
void PopFront(PlistNode** plist) //头删
{
if (*plist == NULL)
return;
else if ((*plist)->_next == NULL)
{
free(*plist);
*plist = NULL;
}
else
{
PlistNode* cur = (*plist)->_next;
free(*plist);
*plist = cur;
}
}
PlistNode* ListFind(PlistNode* pslist, DateType x) //查找函数
{
assert(pslist);
PlistNode* cur = pslist;
while (cur != NULL)
{
if (x == cur->_date)
return cur;
cur = cur->_next;
}
return NULL;
}
void ListInsertAfter(PlistNode** pos, DateType x) //在一个链表的pos位后插入
{
PlistNode* cur = GetNode(x);
PlistNode* tmp = NULL;
tmp = (*pos)->_next;
(*pos)->_next = cur;
cur->_next = tmp;
}
void SListEraseAfter(PlistNode** pos) //删除某个链表pos后的一个节点
{
PlistNode* tmp = NULL;
PlistNode* cur = NULL;
tmp = (*pos)->_next;
cur = tmp->_next;
(*pos)->_next = cur;
free(tmp);
tmp = NULL;
}
PlistNode* middleNode(PlistNode** head) //返回链表的中间节点(快慢指针实现)
{
PlistNode* fast = *head;
PlistNode* slow = *head;
while (fast != NULL && fast->_next != NULL)
{
fast = fast->_next->_next;
slow = slow->_next;
}
return slow;
}
PlistNode* reverseList1(PlistNode** head) //逆转链表(改变指针方向)
{
if ((*head == NULL) || ((*head)->_next == NULL))
return *head;
PlistNode* n1 = (*head);
PlistNode* n2 = (*head)->_next;
PlistNode* n3 = n2->_next;
n1->_next = NULL;
while (n2 != NULL)
{
n2->_next = n1;
n1 = n2;
n2 = n3;
if (n3 != NULL) //判断是否逆置完成
n3 = n3->_next;
}
return n1;
}
PlistNode* reverseList2(PlistNode** head) //逆转链表(头插法每一个原链表值插入新链表)
{
if ((*head) == NULL || (*head)->_next == NULL)
return (*head);
PlistNode* cur = *head;
PlistNode* newhead = GetNode(cur->_date);
PlistNode* tmp = NULL;
while (cur->_next != NULL)
{
cur = cur->_next;
tmp = GetNode(cur->_date);
tmp->_next = newhead;
newhead = tmp;
}
return newhead;
}
PlistNode* FindKNode(PlistNode** head, int k) //返回该链表中倒数第k个结点(含第k个节点)后所有结点(快慢指针实现)
{
if ((*head) == NULL) //排除空指针情况
return NULL;
PlistNode* fast = *head;
PlistNode* slow = *head;
while (k--)
{
if (fast == NULL) //排除k大于链表总长度
return NULL;
fast = fast->_next;
}
while (fast != NULL)
{
fast = fast->_next;
slow = slow->_next;
}
return slow;
}
主函数"main.c"
#include "Slist.c"
void text()
{
PlistNode* head = NULL;
PlistNode* cur = NULL;
PlistNode* res1 = NULL;
PlistNode* res2 = NULL;
PlistNode* res3 = NULL;
PushBack(&head, 1);
PushBack(&head, 2);
PushBack(&head, 3);
PushBack(&head, 4);
PushBack(&head, 5);
Print(head);
PopBack(&head);
Print(head);
PushFront(&head, 0);
Print(head);
cur = ListFind(head, 4);
Print(cur);
ListInsertAfter(&cur, 100);
Print(head);
SListEraseAfter(&cur);
Print(head);
res1 = middleNode(&head);
printf("%d\n\n", res1->_date); //输出数据中间节点
res1 = reverseList1(&head);
Print(res1);
res2 = reverseList2(&res1); //head已为空,传head无效
Print(res2);
res3 = FindKNode(&res2, 3);
printf("%d\n\n", res3->_date); //输出倒数第k个节点数据
Print(res3); //输出倒数第k个节点后所有节点数据
}
int main()
{
text();
system("pause");
return 0;
}