链表的结构体描述
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct Node
{
int data; //数据域
struct Node* next; //指针域
}LIST,*LPLIST,*LPNODE; //链表 节点
?创建链表 |?节点--->创建一个结构体变量
LPLIST createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(LIST));
assert(newNode);
//给数据初始化
newNode->data = data;
newNode->next = NULL;
return newNode;
}
?头插法
-
需要传入二级指针，会修改表头的指向 -
注意LPLIST*是别名，原本应该有两个*
//要插入的链表 要插入的数据
void push_front(LPLIST* headNode, int data)
{
LPNODE newNode = createNode(data); //创建新节点
newNode->next = *headNode; //新节点的next指针指向NULL
*headNode = newNode; //把新节点移到newNode的位置
}
//测试代码
//LPLIST list = createNode(1); //3 2 1 1
LPLIST list = NULL;
LPLIST test = NULL;
push_front(&list, 1);
push_front(&list, 2);
push_front(&list, 3);
printList(list); //3 2 1
return 0;
?打印链表?
void printList(LPLIST list)
{
LPLIST pmove = list;
while (pmove != NULL)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
?尾插法
void push_back(LPLIST* headNode, int data)
{
LPNODE newNode = createNode(data); //创建新节点
//定义一个移动的节点 == 第一个节点
LPNODE pmove = *headNode;
while (pmove != NULL && pmove->next != NULL)
{
pmove = pmove->next; //往下走
}
if (pmove == NULL) //没有节点表头成为新节点 改变表头
{
*headNode = newNode;
}
else //有节点
{
pmove->next = newNode;
}
}
//测试代码
push_back(&test, 1);
push_back(&test, 2);
push_back(&test, 3); //1 2 3
printList(test);
?指定位置插入?
void push_appoin(LPLIST* headNode, int posData, int data)
{
LPNODE preNode = *headNode; //前驱节点
LPNODE curNode = *headNode; //当前节点做移动
while (curNode != NULL && curNode->data != posData) //数据!=指定数据
{
preNode = curNode; //并排往下走
curNode = preNode->next;
}
if (curNode == NULL)
{
printf("未找到指定位置无法插入!\n");
}
else //找到了
{
if (curNode == *headNode)
{
push_front(headNode, data); //头插法
}
else
{
//创建新节点
LPNODE newNode = createNode(data);
//连接
preNode->next = newNode; //前一个节点的next指向新节点
newNode->next = curNode; //新节点的next指向当前节点
}
}
}
//测试代码
push_appoin(&test, 1, 999); //999 1 666 2 3
push_appoin(&test, 2, 666);
printList(test);
?头删法?
void pop_front(LPLIST* headNode)
{
if (*headNode == NULL) //为空无法做删除
return;
LPLIST nextNode = (*headNode)->next; //把表头的下一个保存起来
free(*headNode); //释放表头
*headNode = nextNode; //把表头置为下一个节点
}
//测试代码
pop_front(&test); //999 1 666 2 3
printList(test); //1 666 2 3
?尾删法
void pop_back(LPLIST* headNode)
{
if (*headNode == NULL) //为空无法做删除
return;
if ((*headNode)->next == NULL) //第一个节点的next指针为空--->头删法
pop_front(headNode);
else //其他情况需要找表尾和表尾前面的节点
{
LPNODE preNode = *headNode;
LPNODE curNode = *headNode;
while (curNode->next != NULL) //并排往下走
{
preNode = curNode; //前驱节点走到当前节点的位置
curNode = preNode->next; //当前节点走到原来节点的下一个
}
free(curNode); //释放当前节点
curNode = NULL; //当前节点置空
preNode->next = NULL; //前驱节点的next指针置空
}
}
//测试代码
pop_back(&test); //1 666 2 3
printList(test); //1 666 2
?指定位置删除
//要删除的链表 指定位置:按数据做删除
void pop_appoin(LPLIST* headNode, int posData)
{
if (*headNode == NULL)
return;
if ((*headNode)->data == posData) //头节点的数据==posData
{
pop_front(headNode); //头删法
}
else
{
LPNODE preNode = *headNode; //前驱节点
LPNODE curNode = *headNode; //移动的节点--->当前节点
while (curNode != NULL && curNode->data != posData)
{
preNode = curNode; //并排往下走
curNode = preNode->next;
}
if (curNode == NULL) //没找到
return;
else //找到了
{
preNode->next = curNode->next; //指向当前节点的下一个
free(curNode); //释放当前节点后置空
curNode = NULL;
}
}
}
//测试代码
pop_appoin(&test, 666); //1 666 2
printList(test); //1 2
|