数据结构-C语言的双向链表

用到的函数库和定义的宏

#include
#include
#include

         

#define TYPE int        

创一个结构体，里面是链表的一个 节点的三个内容 前驱 数据 后继

typedef struct Node
{
	struct Node* prev;	//前驱
	TYPE data;
	struct Node* next;	//后继
}Node;                  

自定义一个函数，功能是创建一个节点，输入值是节点数据，输出值是节点的地址。

每当调用这个函数，会分配一个节点大小的内存，并且给节点的三个内容赋值。

现在只有一个节点所以这个节点的前驱连自己，后继也连自己

Node* create_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data= data;
	node->prev = node;
	node->next = node;
	return node;
}

这里定义一个依赖函数，把插入节点这个功能封装，给其他函数用的

void _add_list(Node* p,Node* n,TYPE data)//传入的是两个相邻的节点。p在左。n在右
{
	Node* node = create_node(data); //创建节点node
	node->prev = p;                 
	node->next = n;
	p->next = node;
	n->prev = node;//上四行为插入节点node，把左右节点的前驱后继连到node上
}

//头添加	
void add_head_list(Node* head,TYPE data)
{
	_add_list(head,head->next,data);
}

//尾添加
void add_tail_list(Node* head,TYPE data)
{
	_add_list(head->prev,head,data);
}

//插入
bool insert_list(Node* head,size_t index,TYPE data)//index为插入至第几个数
{
	// n 直接找要插入的index节点
	Node* n = head->next;
	for(int i = 0;inext;
		if(head == n) return false;
	}
	_add_list(n->prev,n,data);
	return true;
}

这个逻辑↓ 理清 调用就方便了

//删除节点功能
void _del_list(Node* node)//传入想删除的节点
{
	Node* p = node->prev;//定义一个指针记录节点的前驱
	Node* n = node->next;//定义一个n记录节点后继
	p->next = n;
	n->prev = p;         //让p和n相连，就是让前驱后继相连，那么中间的节点就“脱离”了
	free(node);          //释放node节点的内存，这个节点就删除了
}

下面两种删除功能都调用了删除节点功能↑

//按位置删除
bool del_index_list(Node* head,size_t index)
{
	Node* n = head->next;
	for(int i = 0;inext;
		if(head == n) return false;
	}
	_del_list(n); //直接调用删除函数
	return true;
}

//按值删除
bool del_val_list(Node* head,TYPE val)
{
	for(Node* n = head->next;n!=head;n = n->next)
	{
		if(val == n->data)
		{
			_del_list(n);//删除函数
		}
	}
	return true;
}


//遍历
void show_list(Node* head)
{
	for(Node* n = head->next; head!=n ;n=n->next )
	{
		printf("%d ",n->data);
	}
	printf("n");
}

int main (int argc,const char* argv[])
{
	Node* head = create_node(0);//这里创了头结点
	for(int i=0;i<10;i++)
	{
		add_head_list(head,i);//这里是简单头添加十个数
	}
	show_list(head);//打印整个链表
	del_val_list(head,2);//从头结点开始遍历 删除数值为2的节点
	show_list(head);
}