单链表及其相关函数

实现功能

BuySListNode ————————————申请一个新节点并赋值

SListLength —————————————计算链表的长度

SListPushBack————————————尾插

SListPushFront————————————头插

SListPopBack—————————————尾删

SListPopFront————————————头删

SListFindByVal————————————按值查找链表

SListFindByPos————————————按位置查找链表

SListInsertAfter————————————任意位置插入

SListEraseAfter————————————任意位置删除

SListPrint——————————————打印链表

SList.h

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int SLTDataType;typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//申请一个新节点并赋值
extern SLTNode* BuySListNode(SLTDataType x);//计算链表的长度
extern int SListLength(SLTNode* phead);//尾插
extern void SListPushBack(SLTNode** pphead, SLTDataType x);//头插
extern void SListPushFront(SLTNode** pphead, SLTDataType x);//尾删
extern void SListPopBack(SLTNode** pphead);//头删
extern void SListPopFront(SLTNode** pphead);//按值查找链表
extern SLTNode* FindByVal(SLTNode* phead, SLTDataType x);
extern void SListFindByVal(SLTNode* phead, SLTDataType x);//按位置查找链表
void FindByPos(SLTNode* phead, int pos, SLTNode** pp_aim1, int* p_aim2);
extern void SListFindByPos(SLTNode* phead, int pos);//任意位置插入
extern void SListInsertAfter(SLTNode** pphead, int pos, SLTDataType x);//任意位置删除
extern void SListEraseAfter(SLTNode** pphead, int pos);//打印链表
extern void SListPrint(SLTNode* phead);

SList.c

#include "SList.h"SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (!newnode){perror("create newnode");exit(-1);}newnode->next = NULL;newnode->data = x;return newnode;
}int SListLength(SLTNode* phead)
{SLTNode* tail = phead;int count = 0;for (count = 1; tail->next != NULL; ++count){tail = tail->next;}return count;
}bool CheckEmpty(SLTNode* phead)
{return (phead) ? false : true;
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{if (CheckEmpty(*pphead)){*pphead = BuySListNode(x);}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = BuySListNode(x);}
}void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopBack(SLTNode** pphead)
{if (CheckEmpty(*pphead)){printf("SList is empty!\n");return;}//注意仅存有一个节点的情况if (!(*pphead)->next){free(*pphead);*pphead = NULL;}//寻找前一个节点else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SListPopFront(SLTNode** pphead)
{if (CheckEmpty(*pphead)){printf("SList is empty!\n");return;}SLTNode* ret = *pphead;*pphead = (*pphead)->next;free(ret);
}SLTNode* FindByVal(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}elsecur = cur->next;}return NULL;
}
void SListFindByVal(SLTNode* phead, SLTDataType x)
{SLTNode* pos = FindByVal(phead, x);if (!pos){printf("Don't find it!\n");return;}//进行多次查找int i = 1;while (pos){printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);pos = FindByVal(pos->next, x);}
}void FindByPos(SLTNode* phead, int pos, SLTNode** pp_aim1, int* p_aim2)
{if (pos < 0 || pos > SListLength(phead)){printf("The position is illegal!\n");}else{SLTNode* tail = phead;//注意循环只需进行pos-1，所以使用--poswhile (--pos){tail = tail->next;}*pp_aim1 = tail;*p_aim2 = tail->data;}
}
void SListFindByPos(SLTNode* phead, int pos)
{SLTNode* aim1;int aim2 = 0;FindByPos(phead, pos, &aim1, &aim2);printf("%d号节点:%p->%d\n", pos, aim1, aim2);
}void SListInsertAfter(SLTNode** pphead, int pos, SLTDataType x)
{if (pos < 0 || pos > SListLength(*pphead)){printf("The position is illegal!\n");}else{if (*pphead == NULL){*pphead = BuySListNode(x);}else if ((*pphead)->next == NULL){(*pphead)->next = BuySListNode(x);}else{SLTNode* dest = *pphead;while (--pos){dest = dest->next;}SLTNode* newnode = BuySListNode(x);newnode->next = dest->next;dest->next = newnode;}}
}void SListEraseAfter(SLTNode** pphead, int pos)
{if (pos <= 0 || pos >= SListLength(*pphead)){printf("The position is illegal!\n");}else{SLTNode* prev = *pphead;while (--pos){prev = prev->next;}SLTNode* afet = prev->next->next;free(prev->next);prev->next = afet;}
}void SListPrint(SLTNode* phead)
{if (CheckEmpty(phead)){printf("SList is empty!\n");return;}SLTNode* tail = phead;while (!tail == NULL){printf("%d->", tail->data);tail = tail->next;}printf("NULL\n");
}

test.c

#include "SList.h"void test1()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);
}void test2()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPrint(pList);
}void test3()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPopBack(&pList);SListPrint(pList);
}void test4()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);SListPopFront(&pList);SListPopFront(&pList);SListPopFront(&pList);SListPopFront(&pList);SListPrint(pList);SListPopFront(&pList);SListPrint(pList);
}void test5()
{SLTNode* pList = NULL;SListPushFront(&pList, 3);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 3);SListPushFront(&pList, 1);SListPrint(pList);SListFindByVal(pList, 3);
}void test6()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);SListFindByPos(pList, 5);}void test7()
{SLTNode* pList = NULL;SListPushFront(&pList, 1);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPrint(pList);SListInsertAfter(&pList, 1, 2);SListPrint(pList);
}void test8()
{SLTNode* pList = NULL;SListPushFront(&pList, 2);SListPushBack(&pList, 3);SListPushBack(&pList, 4);SListPushBack(&pList, 5);SListPushFront(&pList, 1);SListPrint(pList);SListEraseAfter(&pList, 1);SListEraseAfter(&pList, 1);SListEraseAfter(&pList, 1);SListEraseAfter(&pList, 1);SListEraseAfter(&pList, 0);SListPrint(pList);
}void main()
{test1();printf("-------------------------------\n");test2();printf("-------------------------------\n");test3();printf("-------------------------------\n");test4();printf("-------------------------------\n");test5();printf("-------------------------------\n");test6();printf("-------------------------------\n");test7();printf("-------------------------------\n");test8();printf("-------------------------------\n");
}