单链表之无头链表
1. 定义节点结构
- NODE为 节点类型
- LPNODE 为节点指针类型
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//定义节点结构
typedef struct Node_tlg{
int data; //数据域
struct Node_tlg* next; //指针域
}NODE,*LPNODE;
2. 定义链表结构
- size 当前节点个数
- frontNode 首元节点指针
- tailNode 尾节点指针
- List 链表数据类型
//定义链表结构
typedef struct List_tlg{
int size; //当前节点个数
NODE* frontNode; //首元节点(头节点)指针
//LPNODE frontNode; 也可
NODE* tailNode; //尾节点指针
}List;
3. 创建链表
//创建链表
List* createList()
{
List* list = (List*)malloc(sizeof(List));
if (NULL == list)
{
printf("链表空间申请失败!\n");
return NULL;
}
//初始化链表数据
list->size = 0;
list->frontNode = NULL;
list->tailNode = NULL;
return list;
}
4. 创建节点
//创建节点
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
if (NULL == newNode)
{
printf("节点空间申请失败!\n");
return NULL;
}
//初始化节点数据
newNode->data = data;
newNode->next = NULL;
return newNode;
}
5. 求链表长度
//求链表长度大小
int listSize(List* list)
{
return list->size;
}
6. 判断链表是否为空
//求链表是否为空
int empty(List* list)
{
return list->size == 0;
}
7. 头插法插入数据
为空直接插入即可
1. 头节点指针(frontNode),尾节点指针(tailNode)均指向新节点不为空头插法插入数据
1. 新节点(newNode)指针域指向首元节点 2. frontNode(链表首元节点)指针移动到新节点(newNode)
//头部插入
void insertFront(List* list, int data)
{
//创建一个节点
LPNODE newNode = createNode(data);
//表为空直接插入
if (empty(list))
{
//头指针尾指针均指向创建的新节点
list->frontNode = newNode;
list->tailNode = newNode;
}
//头插,移动头节点指针
else{
newNode->next = list->frontNode;
list->frontNode = newNode;
}
list->size++;
}
8. 尾插法插入数据
为空直接插入即可
1. 头节点指针,尾节点指针均指向新节点不为空头插法插入数据
1. 尾节点(tailNode)的next域指向新节点(newNode) 2. tailNode(链表尾节点)指针移动到新节点(newNode)
//尾部插入
void insertTail(List* list, int data)
{
//创建一个节点
LPNODE newNode = createNode(data);
//为空直接插入
if (empty(list))
{
list->frontNode = newNode;
list->tailNode = newNode;
}
//插入节点到尾部,移动尾指针
else{
list->tailNode->next = newNode;
list->tailNode = newNode;
}
list->size++;
}
9. 自定义位置插入数据
//自定义位置插入
void insertAppoint(List* list, int data, int pos)
{
//创建一个节点
LPNODE newNode = createNode(data);
LPNODE curNode = list->frontNode;
LPNODE beforeNode = NULL;
if (pos > list->size || pos <= 0)
{
printf("插入的位置有误!\n");
return;
}
if (pos == 1) //头插
{
insertFront(list, data);
return;
}
while (--pos && curNode->next!=NULL)
{
beforeNode = curNode;
curNode = curNode->next;
}
newNode->next = curNode;
beforeNode->next = newNode;
list->size++;
}
10. 头删法删除数据
只有一个节点
1. 直接删除 2. 将首元节点指针(frontNode),尾节点指针(tailNode)置空即可头删法删除
1. 保存要删除的节点(定义一个节点保存首元节点) 2. 首元节点指针(frontNode)指向首元节点(或要删除节点)下一个节点 3. 删除保存的节点
//头部删除
void deleteFront(List* list)
{
if (empty(list))
{
printf("表为空,无元素可删!\n");
return;
}
if (listSize(list) == 1)
{
LPNODE delNode = list->frontNode;
free(delNode);
delNode = NULL;
list->frontNode = NULL;
list->tailNode = NULL;
}
else{
LPNODE delNode = list->frontNode;
list->frontNode = delNode->next;
free(delNode);
delNode = NULL;
}
list->size--;
}
11. 尾删法删除数据
只有一个节点
1. 直接删除 2. 将首元节点指针(frontNode),尾节点指针(tailNode)置空即可尾删法删除
1. 保存要删除的节点(定义一个节点保存最后一个节点delNode) 2. 定义一个节点去保存需要删除节点的前一个节点(curNode) 3. 尾节点指针(tailNode)指向curNode节点 4. 删除保存的节点(delNode)
//尾部删除
void deleteTail(List* list)
{
if (empty(list))
{
printf("表为空,无元素可删!\n");
return;
}
if (listSize(list) == 1)
{
LPNODE delNode = list->tailNode;
free(delNode);
delNode = NULL;
list->frontNode = NULL;
list->tailNode = NULL;
}
else
{
LPNODE delNode = list->tailNode;
LPNODE curNode = list->frontNode; //保存删除节点的前一个节点
while (curNode->next->next != NULL)
{
curNode = curNode->next;
}
list->tailNode = curNode;
free(delNode);
delNode = NULL;
curNode->next = NULL;
}
list->size--;
}
12. 自定义位置删除数据
//自定义位置删除
void deleteAppoint(List* list, int pos)
{
if (empty(list))
{
printf("表为空,无元素可删!\n");
return;
}
LPNODE delNode = list->frontNode;
LPNODE curNode = NULL;
if (pos == 1) //pos为1直接头删
{
deleteFront(list);
return;
}
while (--pos > 0 && delNode->next != NULL)
{
curNode = delNode;
delNode = delNode->next;
}
if (curNode == NULL)
{
printf("节点删除失败!可能位置有误哦!\n");
return;
}
curNode->next = delNode->next;
free(delNode);
delNode = NULL;
list->size--;
}
13. 删除指定数据
//指定数据删除
void deleteByData(List* list, int data)
{
//判断链表中是否有用户想要删除的数据的标志
bool flag = false;
if (empty(list))
{
printf("表为空,无元素可删!\n");
return;
}
LPNODE delNode = list->frontNode;
LPNODE curNode = NULL;
while (delNode->next!=NULL)
{
curNode = delNode;
delNode = delNode->next;
if (delNode->data == data)
{
//找到数据,标志置为true,退出循环
flag = true;
break;
}
}
//节点删除
if (flag){
curNode->next = delNode->next;
free(delNode);
delNode = NULL;
list->size--;
}
else
{
printf("表中没有你想要删除的数据!\n");
return;
}
}
14. 清空链表
//清空链表
void clearList(List* list)
{
int n = listSize(list);
while (n--)
{
//头删删除链表中的节点
deleteFront(list);
}
if (list->size == 0)
{
printf("链表已清空!\n");
return;
}
else{
printf("链表未清空!\n");
clearList(list);
}
}
15. 销毁链表
//销毁链表
//注意改变指针指向需要传入二级指针
void destoryList(List** plist)
{
if ((*plist)->size >= 0)
{
clearList(*plist);
}
free(*plist);
*plist = NULL;
printf("链表已经销毁!\n");
}
16. 打印链表
//打印链表
void showList(List* list,char* str)
{
printf("%s\n", str);
if (listSize(list) == 0 || list == NULL)
{
printf("链表为空,无法打印!\n");
return;
}
LPNODE curNode = list->frontNode;
while (curNode != NULL)
{
printf("%d\t", curNode->data);
curNode = curNode->next;
}
//打印当前链表长度
printf("\n当前链表长度: %d", list->size);
putchar('\n');
putchar('\n');
}
17.链表功能测试
int main()
{
system("color 0B");
//创建无头链表
List* mylist = createList();
//头插
for (int i = 0; i < 10; i++)
{
insertFront(mylist, 520 + i);
}
showList(mylist,"头插: ");
//尾插
for (int i = 0; i < 5; i++)
{
insertTail(mylist, 580 + i);
}
showList(mylist,"尾插: ");
//头删
deleteFront(mylist);
showList(mylist,"头删: ");
//尾删
deleteTail(mylist);
showList(mylist,"尾删: ");
//自定义位置插入
insertAppoint(mylist,1314,2);
showList(mylist,"自定义位置插入: ");
//自定义位置删除
deleteAppoint(mylist, 2);
showList(mylist,"自定义位置删除: ");
//指定数据删除
deleteByData(mylist, 1000);
showList(mylist, "指定数据删除: ");
//清空链表
clearList(mylist);
//销毁链表
destoryList(&mylist); //二级指针传入改变指针指向
system("pause");
return 0;
}
