list1单链表
//list.h:单链表的声明
#ifndef __LIST_H
#define __LIST_H
//包含公共的头文件
#include
#include
//声明描述节点信息的结构体类型
typedef struct node {
int data;
//节点数据
struct node *next; //保存下一个节点的首地址
}node_t;
//声明描述整个单链表信息的结构体类型
typedef struct list {
struct node *head;
//保存头节点内存的首地址
struct node *tail;
//保存尾节点内存的首地址
}list_t;
//struct list 等价于 list_t 类比成 int类型
//声明单链表的操作函数
extern void list_init(list_t *list);
//初始化
extern void list_deinit(list_t *list);
//释放所有节点内存
extern void list_travel(list_t *list);
//遍历
extern void list_add(list_t *list, int data);
//顺序插
extern void list_add_first(list_t *list, int data); //前插
extern void list_add_last(list_t *list, int data);
//后插
extern void list_del(list_t *list, int data);
//删除data所在的节点
#endif
//list.c:单链表的各种定义
#include "list.h"
//包含自己对应的头文件
//定义分配新节点内存并且初始化新节点的函数//指针函数本质就是一个函数,返回一个地址而已
//函数指针本质就是自定义的一种数据类型而已,将来定义的变量保存一个函数的首地址而已
static node_t *create_node(int data) {
//1.分配新节点内存
node_t *pnew = malloc(sizeof(node_t));
//2.初始化新节点内存
pnew->data = data;
pnew->next = NULL;
//3.返回新节点内存的首地址
return pnew;
//pnew目前保存这新节点的首地址,所以return返回的也是新节点的首地址(编号嘛)
}
//定义初始化函数
void list_init(list_t *list) {
//1.给头节点分配内存
list->head = create_node(0);
//2.给尾节点分配内存
list->tail = create_node(0);
//3.首尾相连
list->head->next = list->tail;
list->tail->next = NULL;
}
//定义遍历函数
void list_travel(list_t *list) {
for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
//1.定义三个游标
node_t *pfirst = pnode;
node_t *pmid = pfirst->next;
node_t *plast = pmid->next;
//2.只要pmid不指向尾节点那么pmid就是指向有效节点
if(pmid != list->tail)
printf("%d ", pmid->data);
}
printf("\n");
}
//定义顺序插函数
void list_add(list_t *list, int data) {
//1.创建要插入的新节点
node_t *pnew = create_node(data);
//2.遍历找到要插入的位置,让pfirst指向前一个节点,pmid指向后一个节点
//那么新节点pnew就插入到pfirst和pmid中间即可
for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
//3.定义三个游标
node_t *pfirst = pnode;
node_t *pmid = pfirst->next;
node_t *plast = pmid->next;
//4.找到要插入的位置,让pfirst指向前一个节点,pmid指向后一个节点
//那么新节点pnew就插入到pfirst和pmid中间即可
if(pmid->data >= pnew->data || pmid == list->tail/*新节点比前面都大*/) {
pfirst->next = pnew;
pnew->next = pmid;
break;
}
}
}
//定义前插函数
void list_add_first(list_t *list, int data) {
//1.创建新节点
node_t *pnew = create_node(data);
//2.临时备份原先第一个节点
node_t *ptmp = list->head->next;
//2.将新节点插入到头文件和原先第一个节点之间
list->head->next = pnew;
pnew->next = ptmp;
}
//定义后插函数
void list_add_last(list_t *list, int data) {
//1.创建新节点
node_t *pnew = create_node(data);
//2.遍历找到原先的最后一个节点并且让pfirst指向它,自然的让pmid指向尾节点
//新节点pnew就插入到pfirst和pmid中间即可,也就是插入到原先最后一个节点和尾节点中间
for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
//3.定义三个游标
node_t *pfirst = pnode; node_t *pmid = pfirst->next; node_t *plast = pmid->next;
//4.pmid一旦指向尾节点,那么pfirst肯定指向原先最后一个节点
if(pmid == list->tail) {
pfirst->next = pnew;
pnew->next = pmid;
break;
}
}
}
//定义删除指定数字所在的节点函数
void list_del(list_t *list, int data) {
//1.遍历找到要删除的节点,并且让pmid指向要删除的节点
//自然而然pfirst指向前一个节点,plast指向后一个节点
//然后让pfirst的next指向plast即可,也就是让前一个节点指向后一个节点
for(node_t *pnode = list->head; pnode != list->tail; pnode = pnode->next) {
//2.定义三个游标
node_t *pfirst = pnode;
node_t *pmid = pfirst->next;
node_t *plast = pmid->next;
if(data == pmid->data && pmid != list->tail/*不能删除尾节点*/) {
pfirst->next = plast;
//连接前一个节点和后一个节点
free(pmid);
//释放要删除的节点内存
break;
}
}
}
//定义释放链表所有节点的函数
void list_deinit(list_t *list) {
node_t *pnode = list->head;
while(pnode) {
//只要pnode不为空,不为NULL,说明pnode指向一个节点
node_t *ptmp = pnode->next;
//临时备份下一个要释放的节点
free(pnode);
//释放当前的节点内存
pnode = ptmp;
//准备释放下一个节点
}
}
//main.c:单链表测试
#include "list.h"
//各种声明
int main(void) {
//1.创建单链表
list_t list;
//2.初始化单链表
list_init(&list);
//2.初始化单链表
//3.各种插入和遍历
list_add(&list, 10);
list_add(&list, 20);
list_add(&list, 30);
list_travel(&list);
list_add_first(&list, 5);
list_add_first(&list, 3);
list_travel(&list);
list_add_last(&list, 40);
list_add_last(&list, 50);
list_travel(&list);
//4.删除节点
list_del(&list, 20);
list_travel(&list);
//5.释放整个链表
list_deinit(&list);
return 0;
}