单链表
一、单链表定义
?单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
?根据第一个节点是否存放数据：分为带头节点(带哨兵位)的单链表与不带头节点（不带哨兵位）的单链表两种
二、不带头节点的单链表
2.1 单链表结构及接口定义
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}ListNode;
ListNode* CreateNode(); // 创建一个单链表节点
void SinListHeadInsert(ListNode **ppHead, ElemType elem); // 头部插入元素
void SinListHeadDelete(ListNode** ppHead); // 头部删除元素
void SinListTailInsert(ListNode** ppHead, ElemType elem); //尾部插入元素
void SinListTailDelete(ListNode** ppHead); //尾部删除元素
void SinListInsert(ListNode** ppHead, int pos, ElemType elem); //插入元素到pos位置,位置从1开始
void SinListDelete(ListNode** ppHead, int pos); //删除pos位置元素,位置从1开始
void SinListPrint(ListNode* pHead); //打印单链表
int SinListFind(ListNode* pHead, ElemType value); //查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1
void Destory(ListNode** ppHead); // 销毁单链表
2.2 创建节点
ListNode* CreateNode(ElemType elem)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) // 开辟空间失败，终止程序
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = elem;
newNode->next = NULL;
return newNode;
}
2.3 头插元素
void SinListHeadInsert(ListNode** ppHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
newNode->next = *ppHead;
*ppHead = newNode; // 头指针指向新节点
}
2.4 头删元素
void SinListHeadDelete(ListNode** ppHead)
{
if (*ppHead == NULL) // 单链表为空
{
printf("单链表为空，头删失败\n");
}
else
{
ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
free(*ppHead); // 释放第一个节点空间
*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
}
}
2.5 尾插元素
void SinListTailInsert(ListNode** ppHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
if (*ppHead == NULL) // 单链表为空
{
*ppHead = newNode;
}
else
{
ListNode* tail = *ppHead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
2.6 尾删元素
void SinListTailDelete(ListNode** ppHead)
{
if (*ppHead == NULL) // 单链表为空
{
printf("单链表为空，尾删失败\n");
}
else //单链表至少有一个节点以上
{
if ((*ppHead)->next == NULL) // 单链表只有1个节点
{
free(*ppHead);
*ppHead = NULL;
}
else // 单链表有2个及以上节点
{
ListNode* prev = NULL;
ListNode* tail = *ppHead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL; // 将原单链表倒数第二个节点的next置为NULL，作为新链表的尾节点
}
}
}
2.7 指定位置插入元素
位序（位置）从1开始，即第一个节点位序为1
void SinListInsert(ListNode** ppHead, int pos, ElemType elem)
{
if (pos <= 0)
{
printf("位置不合法，插入失败\n");
}
else if (pos == 1) // 头部插入
{
ListNode* newNode = CreateNode(elem);
newNode->next = *ppHead;
*ppHead = newNode; // 头指针指向新节点
}
else
{
int i = 1;
ListNode* prev = NULL;
ListNode* cur = *ppHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (i == pos)
{
ListNode* newNode = CreateNode(elem);
newNode->next = cur;
prev->next = newNode;
}
else
{
printf("位置不合法，插入失败\n");
}
}
}
2.7 指定位置删除元素
void SinListDelete(ListNode** ppHead, int pos)
{
if (pos <= 0)
{
printf("位置不合法，删除失败\n");
}
else if (*ppHead == NULL)
{
printf("单链表为空，删除失败\n");
}
else if(pos == 1)
{
ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
free(*ppHead); // 释放头节点
*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
}
else
{
int i = 1;
ListNode* prev = NULL;
ListNode* cur = *ppHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (cur == NULL)
{
printf("位置不合法，删除失败\n");
}
else
{
prev->next = cur->next;
free(cur);
}
}
}
2.8 打印单链表
void SinListPrint(ListNode* pHead)
{
if (pHead == NULL)
{
printf("单链表为空\n");
}
else
{
ListNode* cur = pHead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
}
2.9 查找指定元素位置
查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1
int SinListFind(ListNode* pHead, ElemType value)
{
ListNode* cur = pHead;
int i = 1;
while (cur != NULL)
{
if (cur->data == value)
{
return i;
}
cur = cur->next;
i++;
}
return -1;
}
2.10 销毁单链表
void Destory(ListNode** ppHead)
{
ListNode* cur = *ppHead;
ListNode* next = NULL;
while (cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
*ppHead = NULL;
}
2.11 源代码
头文件SinList.h内容：
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}ListNode;
ListNode* CreateNode(); // 创建一个单链表节点
void SinListHeadInsert(ListNode **ppHead, ElemType elem); // 头部插入元素
void SinListHeadDelete(ListNode** ppHead); // 头部删除元素
void SinListTailInsert(ListNode** ppHead, ElemType elem); //尾部插入元素
void SinListTailDelete(ListNode** ppHead); //尾部删除元素
void SinListInsert(ListNode** ppHead, int pos, ElemType elem); //插入元素到pos位置,位置从1开始
void SinListDelete(ListNode** ppHead, int pos); //删除pos位置元素,位置从1开始
void SinListPrint(ListNode* pHead); //打印单链表
int SinListFind(ListNode* pHead, ElemType value); //查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1
void Destory(ListNode** ppHead); // 销毁单链表
源文件SinList.c内容：
#include "SinList.h"
ListNode* CreateNode(ElemType elem)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) // 开辟空间失败，终止程序
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = elem;
newNode->next = NULL;
return newNode;
}
void SinListHeadInsert(ListNode** ppHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
newNode->next = *ppHead;
*ppHead = newNode; // 头指针指向新节点
}
void SinListHeadDelete(ListNode** ppHead)
{
if (*ppHead == NULL) // 单链表为空
{
printf("单链表为空，头删失败\n");
}
else
{
ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
free(*ppHead); // 释放第一个节点空间
*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
}
}
void SinListTailInsert(ListNode** ppHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
if (*ppHead == NULL) // 单链表为空
{
*ppHead = newNode;
}
else
{
ListNode* tail = *ppHead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}
void SinListTailDelete(ListNode** ppHead)
{
if (*ppHead == NULL) // 单链表为空
{
printf("单链表为空，尾删失败\n");
}
else //单链表至少有一个节点以上
{
if ((*ppHead)->next == NULL) // 单链表只有1个节点
{
free(*ppHead);
*ppHead = NULL;
}
else // 单链表有2个及以上节点
{
ListNode* prev = NULL;
ListNode* tail = *ppHead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL; // 将原单链表倒数第二个节点的next置为NULL，作为新链表的尾节点
}
}
}
void SinListInsert(ListNode** ppHead, int pos, ElemType elem)
{
if (pos <= 0)
{
printf("位置不合法，插入失败\n");
}
else if (pos == 1) // 头部插入
{
ListNode* newNode = CreateNode(elem);
newNode->next = *ppHead;
*ppHead = newNode; // 头指针指向新节点
}
else
{
int i = 1;
ListNode* prev = NULL;
ListNode* cur = *ppHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (i == pos)
{
ListNode* newNode = CreateNode(elem);
newNode->next = cur;
prev->next = newNode;
}
else
{
printf("位置不合法，插入失败\n");
}
}
}
void SinListDelete(ListNode** ppHead, int pos)
{
if (pos <= 0)
{
printf("位置不合法，删除失败\n");
}
else if (*ppHead == NULL)
{
printf("单链表为空，删除失败\n");
}
else if(pos == 1)
{
ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
free(*ppHead); // 释放头节点
*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
}
else
{
int i = 1;
ListNode* prev = NULL;
ListNode* cur = *ppHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (cur == NULL)
{
printf("位置不合法，删除失败\n");
}
else
{
prev->next = cur->next;
free(cur);
}
}
}
void SinListPrint(ListNode* pHead)
{
if (pHead == NULL)
{
printf("单链表为空\n");
}
else
{
ListNode* cur = pHead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
}
int SinListFind(ListNode* pHead, ElemType value)
{
ListNode* cur = pHead;
int i = 1;
while (cur != NULL)
{
if (cur->data == value)
{
return i;
}
cur = cur->next;
i++;
}
return -1;
}
void Destory(ListNode** ppHead)
{
ListNode* cur = *ppHead;
ListNode* next = NULL;
while (cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
*ppHead = NULL;
}
源文件main.c内容：
#include "SinList.h"
void menu()
{
printf("------------------------------\n");
printf("-- H. 头插元素 h. 头删元素 --\n");
printf("-- T. 尾插元素 t. 尾删元素 --\n");
printf("-- I. 插入元素 D. 删除元素 --\n");
printf("-- F. 查找元素 P. 打印元素 --\n");
printf("--------- Q. 退出 --------\n");
printf("------------------------------\n\n");
}
int main()
{
ListNode* pHead = NULL;
char choose = 'Q';
do
{
menu();
printf("请选择：");
choose = getchar(); //接接收用户选择
ElemType elem; //待插入（或查找）元素值
int position = -1; //待插入（删除、查找）元素位序，位序从1开始
getchar(); //从输入缓冲区读取回车符，避免影响下次输入
switch (choose)
{
case 'H':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SinListHeadInsert(&pHead, elem);
getchar();
break;
case 'h':
SinListHeadDelete(&pHead);
break;
case 'T':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SinListTailInsert(&pHead,elem);
getchar();
break;
case 't':
SinListTailDelete(&pHead);
break;
case 'I':
printf("请输入待插入元素位序及值,例：2 5 >"); //位序：单链表的第几个元素，从1开始
scanf("%d %d", &position, &elem);
SinListInsert(&pHead, position, elem);
getchar();
break;
case 'D':
printf("请输入待删除元素位序：");
scanf("%d", &position);
SinListDelete(&pHead, position);
getchar();
break;
case 'F':
printf("请输入待查找元素的值：");
scanf("%d", &elem);
position = SinListFind(pHead, elem);
getchar();
if (position == -1)
{
printf("元素：%d 不在单链表中\n", elem);
}
else
{
printf("元素：%d 的位序为：%d\n", elem, position);
}
break;
case 'P':
SinListPrint(pHead);
break;
case 'Q':
Destory(&pHead);
printf("退出成功\n");
break;
default:
printf("选择错误，请重新选择!!!\n");
break;
}
} while (choose != 'Q');
return 0;
}
三、带头节点的单链表
3.1 单链表结构及接口定义
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}ListNode;
ListNode* CreateNode(); // 创建一个节点
void SinListHeadInsert(ListNode *pHead, ElemType elem); // 头部插入元素
void SinListHeadDelete(ListNode *pHead); // 头部删除元素
void SinListTailInsert(ListNode *pHead, ElemType elem); //尾部插入元素
void SinListTailDelete(ListNode *pHead); //尾部删除元素
void SinListInsert(ListNode *pHead, int pos, ElemType elem); // 插入元素到pos位置,位置从1开始
void SinListDelete(ListNode *pHead, int pos); // 删除pos位置元素,位置从1开始
void SinListPrint(ListNode *pHead); // 打印单链表
int SinListFind(ListNode *pHead, ElemType value); // 查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1
ListNode* Destory(ListNode* pHead); // 销毁单链表
3.2 创建节点
ListNode* CreateNode(ElemType elem)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) // 开辟空间失败，终止程序
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = elem;
newNode->next = NULL;
return newNode;
}
3.3 头插元素
void SinListHeadInsert(ListNode* pHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
newNode->next = pHead->next;
pHead->next = newNode;
}
3.3 头删元素
void SinListHeadDelete(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空，头删失败\n");
}
else
{
ListNode* Node = pHead->next;
pHead->next = pHead->next->next;
free(Node);
}
}
3.4 尾插元素
void SinListTailInsert(ListNode* pHead, ElemType elem)
{
ListNode* tail = pHead;
while (tail->next != NULL)
{
tail = tail->next;
}
ListNode* newNode = CreateNode(elem);
tail->next = newNode;
}
3.5 尾删元素
void SinListTailDelete(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空，尾删失败\n");
}
else
{
ListNode* prev = NULL;
ListNode* tail = pHead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
3.6 指定位置插入元素
void SinListInsert(ListNode* pHead, int pos, ElemType elem)
{
if (pos <= 0)
{
printf("位置不合法，插入失败\n");
}
else
{
int i = 0;
ListNode* prev = NULL;
ListNode* cur = pHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (i == pos)
{
ListNode* newNode = CreateNode(elem);
newNode->next = cur;
prev->next = newNode;
}
else
{
printf("位置不合法，插入失败\n");
}
}
}
3.7 指定位置删除元素
void SinListDelete(ListNode* pHead, int pos)
{
if (pos <= 0)
{
printf("位置不合法，删除失败\n");
}
else if(pHead->next == NULL)
{
printf("单链表为空，删除失败\n");
}
else
{
int i = 0;
ListNode* prev = NULL;
ListNode* cur = pHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (cur == NULL)
{
printf("位置不合法，删除失败\n");
}
else
{
prev->next = cur->next;
free(cur);
}
}
}
3.8 打印单链表
void SinListPrint(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空\n");
}
else
{
ListNode* cur = pHead->next;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
}
3.9 查找指定元素位置
int SinListFind(ListNode* pHead, ElemType value)
{
ListNode* cur = pHead->next;
int i = 1;
while (cur != NULL)
{
if (cur->data == value)
{
return i;
}
cur = cur->next;
i++;
}
return -1;
}
3.10 销毁单链表
ListNode* Destory(ListNode* pHead)
{
ListNode* cur = pHead;
ListNode* next = NULL;
while (cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
return NULL;
}
3.11 源代码
头文件SinList.h内容：
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}ListNode;
ListNode* CreateNode(); // 创建一个节点
void SinListHeadInsert(ListNode *pHead, ElemType elem); // 头部插入元素
void SinListHeadDelete(ListNode *pHead); // 头部删除元素
void SinListTailInsert(ListNode *pHead, ElemType elem); //尾部插入元素
void SinListTailDelete(ListNode *pHead); //尾部删除元素
void SinListInsert(ListNode *pHead, int pos, ElemType elem); // 插入元素到pos位置,位置从1开始
void SinListDelete(ListNode *pHead, int pos); // 删除pos位置元素,位置从1开始
void SinListPrint(ListNode *pHead); // 打印单链表
int SinListFind(ListNode *pHead, ElemType value); // 查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1
ListNode* Destory(ListNode* pHead); // 销毁单链表
源文件SinList.c内容：
#include "SinList.h"
ListNode* CreateNode(ElemType elem)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) // 开辟空间失败，终止程序
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = elem;
newNode->next = NULL;
return newNode;
}
void SinListHeadInsert(ListNode* pHead, ElemType elem)
{
ListNode* newNode = CreateNode(elem);
newNode->next = pHead->next;
pHead->next = newNode;
}
void SinListHeadDelete(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空，头删失败\n");
}
else
{
ListNode* Node = pHead->next;
pHead->next = pHead->next->next;
free(Node);
}
}
void SinListTailInsert(ListNode* pHead, ElemType elem)
{
ListNode* tail = pHead;
while (tail->next != NULL)
{
tail = tail->next;
}
ListNode* newNode = CreateNode(elem);
tail->next = newNode;
}
void SinListTailDelete(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空，尾删失败\n");
}
else
{
ListNode* prev = NULL;
ListNode* tail = pHead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SinListInsert(ListNode* pHead, int pos, ElemType elem)
{
if (pos <= 0)
{
printf("位置不合法，插入失败\n");
}
else
{
int i = 0;
ListNode* prev = NULL;
ListNode* cur = pHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (i == pos)
{
ListNode* newNode = CreateNode(elem);
newNode->next = cur;
prev->next = newNode;
}
else
{
printf("位置不合法，插入失败\n");
}
}
}
void SinListDelete(ListNode* pHead, int pos)
{
if (pos <= 0)
{
printf("位置不合法，删除失败\n");
}
else if(pHead->next == NULL)
{
printf("单链表为空，删除失败\n");
}
else
{
int i = 0;
ListNode* prev = NULL;
ListNode* cur = pHead;
while (cur != NULL && i < pos)
{
prev = cur;
cur = cur->next;
i++;
}
if (cur == NULL)
{
printf("位置不合法，删除失败\n");
}
else
{
prev->next = cur->next;
free(cur);
}
}
}
void SinListPrint(ListNode* pHead)
{
if (pHead->next == NULL)
{
printf("单链表为空\n");
}
else
{
ListNode* cur = pHead->next;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
}
int SinListFind(ListNode* pHead, ElemType value)
{
ListNode* cur = pHead->next;
int i = 1;
while (cur != NULL)
{
if (cur->data == value)
{
return i;
}
cur = cur->next;
i++;
}
return -1;
}
ListNode* Destory(ListNode* pHead)
{
ListNode* cur = pHead;
ListNode* next = NULL;
while (cur != NULL)
{
next = cur->next;
free(cur);
cur = next;
}
return NULL;
}
源文件main.c内容：
#include "SinList.h"
void menu()
{
printf("------------------------------\n");
printf("-- H. 头插元素 h. 头删元素 --\n");
printf("-- T. 尾插元素 t. 尾删元素 --\n");
printf("-- I. 插入元素 D. 删除元素 --\n");
printf("-- F. 查找元素 P. 打印元素 --\n");
printf("--------- Q. 退出 --------\n");
printf("------------------------------\n\n");
}
int main()
{
ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
pHead->next = NULL;
char choose = 'Q';
do
{
menu();
printf("请选择：");
choose = getchar(); //接接收用户选择
ElemType elem; //待插入（或查找）元素值
int position = -1; //待插入（删除、查找）元素位序，位序从1开始
getchar(); //从输入缓冲区读取回车符，避免影响下次输入
switch (choose)
{
case 'H':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SinListHeadInsert(pHead, elem);
getchar();
break;
case 'h':
SinListHeadDelete(pHead);
break;
case 'T':
printf("请输入待插入元素值：");
scanf("%d", &elem);
SinListTailInsert(pHead,elem);
getchar();
break;
case 't':
SinListTailDelete(pHead);
break;
case 'I':
printf("请输入待插入元素位序及值,例：2 5 >"); //位序：单链表的第几个元素，从1开始
scanf("%d %d", &position, &elem);
SinListInsert(pHead, position, elem);
getchar();
break;
case 'D':
printf("请输入待删除元素位序：");
scanf("%d", &position);
SinListDelete(pHead, position);
getchar();
break;
case 'F':
printf("请输入待查找元素的值：");
scanf("%d", &elem);
position = SinListFind(pHead, elem);
getchar();
if (position == -1)
{
printf("元素：%d 不在单链表中\n", elem);
}
else
{
printf("元素：%d 的位序为：%d\n", elem, position);
}
break;
case 'P':
SinListPrint(pHead);
break;
case 'Q':
pHead = Destory(pHead);
printf("退出成功\n");
break;
default:
printf("选择错误，请重新选择!!!\n");
break;
}
} while (choose != 'Q');
return 0;
}