4.3.1初阶数据结构(C语言)(无头不循环单链表)

1.完整的单链表+注释：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>typedef int SLTDateType;     // 重定义数据类型typedef struct SListNode              // 定义结构体类型的节点
{SLTDateType data;struct SListNode* next;
}SListNode;extern SListNode* BuySListNode(SLTDateType x);                                        // 动态申请一个节点   extern void SListPrint(SListNode* plist);                                             // 1.单链表打印extern void SListPushBack(SListNode** pplist, SLTDateType x);                         // 2.单链表尾插extern void SListPushFront(SListNode** pplist, SLTDateType x);                        // 3.单链表的头插extern void SListPopBack(SListNode** pplist);                                         // 4.单链表的尾删extern void SListPopFront(SListNode** pplist);                                        // 5.单链表头删extern SListNode* SListFind(SListNode* plist, SLTDateType x);                         // 6.单链表查找extern void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDateType x);     // 7.单链表在pos位置之前插入xextern void SListInsertAfter(SListNode* pos, SLTDateType x);                          // 8.单链表在pos位置之后插入xextern void SListErase(SListNode** pplist, SListNode* pos);                           // 9.单链表删除pos位置的值extern void SListEraseAfter(SListNode* pos);                                          // 10.单链表删除pos位置之后的值extern void SListDestroy(SListNode** pplist);                                         // 11.单链表的销毁

#include"SList.h"SListNode* BuySListNode(SLTDateType x)     // 动态申请一个节点 
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){exit(-1);}else{newnode->data = x;newnode->next = NULL;}return newnode;
}void SListPrint(SListNode* plist)     // 1.单链表打印
{SListNode* cur = plist;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}void SListPushBack(SListNode** pplist, SLTDateType x)     // 2.单链表尾插
{if (*pplist == NULL)     //头插要改变指针，所以用二级指针操作{*pplist = BuySListNode(x);return;}SListNode* tail = *pplist;while (tail->next)     //找尾{tail = tail->next;}tail->next = BuySListNode(x);
}void SListPushFront(SListNode** pplist, SLTDateType x)     // 3.单链表的头插
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}void SListPopBack(SListNode** pplist)     // 4.单链表的尾删
{if (*pplist == NULL)     //考虑特殊情况1{printf("表中没有数据，尾删失败！\n");return;}if ((*pplist)->next == NULL)     //考虑特殊情况2{free(*pplist);*pplist = NULL;return;}SListNode* end = *pplist;     //使用前后指针，便于删除SListNode* prev = *pplist;while (end->next != NULL){prev = end;end = end->next;}free(end);end = NULL;prev->next = NULL;
}void SListPopFront(SListNode** pplist)     // 5.单链表头删
{if (*pplist == NULL)     //考虑特殊情况{printf("表中没有数据，头删失败！\n");return;}SListNode* begin = *pplist;*pplist = begin->next;free(begin);begin = NULL;
}SListNode* SListFind(SListNode* plist, SLTDateType x)     // 6.单链表查找
{while (plist != NULL){if (plist->data == x){return plist;}plist = plist->next;}printf("没找到！\n");return NULL;
}void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDateType x)     // 7.单链表在pos位置之前插入x
{SListNode* newnode = BuySListNode(x);if (pos == *pplist)     //考虑特殊情况{newnode->next = *pplist;*pplist = newnode;return;}SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;
}void SListInsertAfter(SListNode* pos, SLTDateType x)     // 8.单链表在pos位置之后插入x
{if (pos == NULL)     //考虑特殊情况{printf("pos位置错误，插入失败！\n");return;}SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}void SListErase(SListNode** pplist, SListNode* pos)     // 9.单链表删除pos位置的值
{if (pos == NULL)     //考虑特殊情况{printf("pos位置错误，删除失败！\n");return;}if (*pplist == NULL)     //考虑特殊情况{printf("表中没有数据，头删失败！\n");return;}if (pos == *pplist)     //考虑头删情况{(*pplist) = pos->next;free(pos);return;}SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);
}void SListEraseAfter(SListNode* pos)     // 10.单链表删除pos位置之后的值
{if ((pos == NULL) || (pos->next == NULL)){printf("pos位置错误，删除失败！\n");return;}SListNode* next = pos->next;pos->next = next->next;free(next);
}void SListDestroy(SListNode** pplist)     // 11.单链表的销毁
{SListNode* cur = *pplist;while ((*pplist) != NULL){*pplist = (*pplist)->next;free(cur);cur = *pplist;}printf("销毁成功\n");
}

#include"SList.h"void test1()     //测试1
{SListNode* plist = NULL;/*SListPopBack(&plist);SListPrint(plist);SListPushBack(&plist, 1);SListPopBack(&plist);SListPrint(plist);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPopBack(&plist);*/SListPrint(plist);SListPopFront(&plist);SListPushFront(&plist, 1);SListPopFront(&plist);SListPrint(plist);SListPushFront(&plist, 2);SListPushFront(&plist, 3);SListPopFront(&plist);SListPrint(plist);}void test2()     //测试2
{SListNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 2);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPrint(plist);SListNode* pos = SListFind(plist, 2);int i = 1;     //数字出现个数while (pos != NULL)     //找到所有指定的数字{printf("第%d次出现的地址：%p\n", i++, pos);pos = SListFind(pos->next, 2);}pos = SListFind(plist, 3);pos->data = 0;SListPrint(plist);}void test3()
{SListNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPushBack(&plist, 6);SListPushBack(&plist, 7);SListPrint(plist);/*SListNode* pos = SListFind(plist, 7);SListInsertBefore(&plist, pos, 0);SListPrint(plist);*//*SListNode* pos = SListFind(plist, 7);SListInsertAfter(pos, 0);SListPrint(plist);*//*SListNode* pos = SListFind(plist, 7);SListErase(&plist, pos);SListPrint(plist);*/SListNode* pos = SListFind(plist, 1);SListEraseAfter(pos);SListDestroy(&plist);SListPrint(plist);}void menu()     //菜单
{printf("********1.打印*****2.尾插********\n");printf("********3.头插*****4.尾删********\n");printf("********5.头删*****6.查找********\n");printf("********7.位前插***8.位后插******\n");printf("********9.位删****10.位后删******\n");printf("*******11.销毁*****0.退出********\n");
}void test()
{SListNode* plist = NULL;int input = 0;             //输入选择int x = 0;                 //输入插入的值SListNode* pos = NULL;     //地址变量enum choose{_exit,                       //0.退出_SListPrint,                 //1.单链表打印_SListPushBack,              //2.单链表的尾插_SListPushFront,             //3.单链表的头插_SListPopBack,               //4.单链表的尾删_SListPopFront,              //5.单链表头删_SListFind,                  //6.单链表查找_SListInsertBefore,          //7.单链表在pos位置之前插入x_SListInsertAfter,           //8.单链表在pos位置之后插入x_SListErase,                 //9.单链表删除pos位置的值_SListEraseAfter,            //10.单链表删除pos位置之后的值_SListDestroy                //11.单链表的销毁};do{menu();printf("请选择\n");scanf("%d", &input);switch (input){case _exit:break;case _SListPrint:SListPrint(plist);                //1.单链表打印break;case _SListPushBack:printf("请输入\n");scanf("%d", &x);SListPushBack(&plist, x);        //2.单链表的尾插break;case _SListPushFront:printf("请输入\n");scanf("%d", &x);SListPushFront(&plist, x);       //3.单链表的头插break;case _SListPopBack:SListPopBack(&plist);            //4.单链表的尾删break;case _SListPopFront:SListPopFront(&plist);           //5.单链表头删break;case _SListFind:printf("请输入\n");scanf("%d", &x);pos = SListFind(plist, x);             //6.单链表查找break;case _SListInsertBefore:printf("请输入\n");scanf("%d", &x);SListInsertBefore(&plist, pos, x);     //7.单链表在pos位置之前插入xbreak;case _SListInsertAfter:printf("请输入\n");scanf("%d", &x);SListInsertAfter(pos, x);             //8.单链表在pos位置之后插入xbreak;case _SListErase:SListErase(&plist, pos);              //9.单链表删除pos位置的值break;case _SListEraseAfter:SListEraseAfter(pos);                //10.单链表删除pos位置之后的值break;case _SListDestroy:SListDestroy(&plist);                //11.单链表的销毁break;default:printf("选项不存在，请重新输入！\n");break;}} while (input);
}int main()
{//test1();     //测试1//test2();     //测试2//test3();     //测试3test();system("pause");return 0;
}

2.练习题：

1.删除链表中等于给定值 val 的所有节点

2.反转一个单链表

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

4.输入一个链表，输出该链表中倒数第k个结点 

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

7.链表的回文结构 

8. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针

9.对链表进行插入排序 

10.​​​​​​​​​​​​​​给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝

11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

12.给定一个链表，判断链表中是否有环

13.输入两个链表，找出它们的第一个公共结点 

3.链表的优点：

1.按需申请空间不用了就释放空间，更合理的使用了空间。

2.头部中间插入删除数据，不需要挪动数据。

4.链表的缺点：

1.每一个数据都要存一个指针去链接后面的数据节点。

2.不支持随机访问。