链表 –
单链表 –
内存空间
操作函数
1.头插函数
新的结点插入到头结点和第一个有效结点之间
void list_add_head(list_t* list, int data){}
2.尾插函数
新的结点插入到最后一个有效结点和尾结点之间
void list_add_tail(list_t* list, int data){}
head—->10—>20—->30—->tail
双链表:
问题 – 可以通过tail找到30数据所在节点 – 不可以
通过前一个节点找到后一个节点
无法通过后一个节点找到前一个节点
为了克服这个问题 – 在设计链表的时候, 可以在每个节点中再设置一个指向前面结点的指针
每个结点中都包含两个指针
一个指向后面的元素
一个指向前面的元素
双向链表
声明描述一个节点的结构体
struct node{
int data;
struct node* next;//指向下一个节点的首地址
struct node* prev;//指向上一个节点的首地址
};
声明描述一个双链表的结构体
struct list{
struct node head;
struct node tail;
};
mkdir list2
vim list.h
#ifndef _LIST_H
#define _LIST_H
//包含公共的头文件
#include <stdio.h>
#include <stdlib.h>
//声明描述结点的结构体
typedef struct node{
int data;
struct node* next;//保存下一个结点首地址
struct node* prev;//保存上一个结点首地址
}node_t;
//声明描述双链表的结构体
typedef struct list{
struct node head;
struct node tail;
}list_t;
extern void list_init(list_t* list);//初始化函数
extern int list_empty(list_t* list);//判断链表是否为空的函数
#endif
vim list.c
#include "list.h"
//初始化函数
void list_init(list_t* list){
//初始化头结点
list->head.next = &list->tail;
list->head.prev = NULL;
list->head.data = 0;
//初始化尾结点
list->tail.next = NULL;
list->tail.prev = &list->head;
list->tail.data = 0;
}
//判断空函数
int list_empty(list_t* list){
//如果链表中只有头结点和尾结点
return list->head.next == &list->tail;//满足, 空; 不满足, 非空
}
//判断结点个数函数
int list_size(list_t* list){
int count = 0;//记录结点个数
for(node_t* pnode = &list->head; pnode != &list->tail; pnode = pnode->next){
//制造三个游标
node_t* pfirst = pnode;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
if(pmid != &list->tail)
count++;
}
return count;
}
//定义构造新节点的函数
static node_t* create_node(int data){
node_t* pnew = malloc(sizeof(node_t));
pnew->data = data;
pnew->next = NULL;
pnew->prev = NULL;
return pnew;
}
static void insert_node(node_t* pfirst, node_t* pmid, node_t* pnew){
pfirst->next = pnew;
pnew->prev = pfirst;
pnew->next = pmid;
pmid->prev = pnew;
}
//按照顺序插入函数
void list_add(list_t* list, int data){
node_t* pnew = create_node(data);
//head<------>10<---------->20<----->30<---->tail
// pnew(15)
// pfrist pmid
for(node_t* pnode = &list->head; pnode != &list->tail; pnode = pnode->next){
//制造三个游标
node_t* pfirst = pnode;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
if(pmid->data >= pnew->data || pmid == &list->tail){
insert_node(pfirst, pmid, pnew);
break;
}
}
}
//头插函数
void list_add_head(list_t* list, int data){
node_t* pnew = create_node(data);
//head<------------>10<---->20<----->30<---->tail
// pnew
//pfirst pmid plast
//制造游标
node_t* pfirst = &list->head;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
//将pnew结点插入到pfirst和pmid之间
insert_node(pfirst, pmid, pnew);
}
//尾插函数
void list_add_tail(list_t* list, int data){
node_t* pnew = create_node(data);
//head<---->10<---->20<----->30<--------------->tail
// pnew
// pfirst pmid plast
//制造游标
node_t* pfirst = list->tail.prev;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
//将pnew插入到pfirst和pmid之间
insert_node(pfirst, pmid, pnew);
}
//定义删除pmid指向的结点
static void del_node(node_t* pfirst, node_t* pmid, node_t* plast){
pfirst->next = plast;
plast->prev = pfirst;
free(pmid);
}
//删除指定的结点
void list_del(list_t* list, int data){
//head<------>10<---------->20<----->30<---->tail
for(node_t* pnode = &list->head; pnode != &list->tail; pnode = pnode->next){
//制造三个游标
node_t* pfirst = pnode;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
if(pmid->data == data && pmid != &list->tail){
del_node(pfirst, pmid, plast);
}
}
}
//删除第一个有效结点
void list_del_head(list_t* list){
//判断链表是否为空
if(list_empty(list)){
printf("链表为空, 无法删除\n");
return;
}
//head<------>10<---------->20<----->30<---->tail
//pfirst pmid plast
//定义游标
node_t* pfirst = &list->head;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
//删除pmid指向的结点
del_node(pfirst, pmid, plast);
}
//删除最后一个有效结点
//让pmid指向要删除的结点 - 指向最后一个有效结点
void list_del_tail(list_t* list){
//判断链表是否为空
if(list_empty(list)){
printf("链表为空, 无法删除\n");
return;
}
//head<------>10<------>20<----->30<---->tail
// pfirst pmid plast
//定义游标
node_t* plast = &list->tail;//plast指向了tail结点
node_t* pmid = plast->prev;//plast的上一个结点 - 最后一个有效结点 - pmid
node_t* pfirst = pmid->prev;//指向pmid的上一个结点
//删除pmid指向的结点
del_node(pfirst, pmid, plast);
}
//根据结点编号来获取数据的函数
//数组:
// 10 20 30 40 数据
// 0 1 2 3 数组下标
//双链表:
// 10 20 30 40 双链表数据
// 0 1 2 3 结点编号
// 根据结点编号来获取编号对应的数据
int list_get(list_t* list, int index){
int count = 0;//表示循环的次数
// head 10 20 30 40 tail 双链表数据
// 0 1 2 3 结点编号
// pfirst pmid plast
//tips:根据循环的次数, 判断pmid指向的内容
for(node_t* pnode = &list->head; pnode != &list->tail; pnode = pnode->next){
//制造三个游标
node_t* pfirst = pnode;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
if(count == index && pmid != &list->tail)
return pmid->data;
count++;
}
}
//清除链表中的所有内容
void list_deinit(list_t* list){
//head----10----20-----30----tail
//head-----tail
//head----tail
//pfirst pmid plast
while(list->head.next != &list->tail){
node_t* pfirst = &list->head;
node_t* pmid = pfirst->next;
node_t* plast = pmid->next;
del_node(pfirst, pmid, plast);//删除pmid指向的结点
}
}
vim main.c
//双链表测试
#include "list.h"
int main(void){
list_t list;
list_init(&list);//初始化
//各种插入
list_add_head(&list, 100);
list_add_head(&list, 30);
list_add_tail(&list, 70);
list_add_tail(&list, 50);
list_add(&list, 80);
list_add(&list, 20);
list_add(&list, 40);
list_add(&list, 90);
list_add(&list, 60);
list_add(&list, 10);
list_add(&list, 110);
//获取链表内容
int size = list_size(&list);
for(int i = 0; i < size; i++)
printf("%d ", list_get(&list, i));
printf("\n");
//各种删除结点
list_del(&list, 90);
list_del_head(&list);
list_del_tail(&list);
//获取链表内容
size = list_size(&list);
for(int i = 0; i < size; i++)
printf("%d ", list_get(&list, i));
printf("\n");
list_deinit(&list);//释放
return 0;
}
pmid指针
循环的次数 – 有效数据的个数 + 1
循环 – pmid != &list->tail
循环次数 == 有效数据个数
解决列表里数据动态的新增和删除
typedef struct birth{
int year;
int month;
int day;
}birth_t;
typedef struct info{
int num;
char name[32];
int num2;
char sex;
birth_t birth;
char add[40];
}info_t;
typedef struct node{
info_t info;
struct node* next;
struct node* prev;
}node_t;
