带头节点的双向链表的基本操作

双向链表的一些基本操作
头插法 头删法
尾插法 尾删法
按照位置前后进行插入、删除
合并两个无序的双向链表
将双向链表进行按位置反转
比如A->B->C->D->E->F 以 C 点 为转换
转换之后就是C->D->E->F->A->B

#include "3.h"

Linklist createlist() //创建一个带头节点的双向链表
{
	Linklist head = (Linklist)malloc(sizeof(Node));
	assert(head != NULL);
	head->next = NULL;
	head->prev = NULL;
	return head;
}
Linklist push_back_list(Linklist head,int val) //尾插法进行插入
{
	assert(head);
	Linklist end = head;
	while(end->next != NULL)
	{
		end = end->next;
	}
	Linklist newnode = createlist();
	end->next = newnode;
	newnode->prev = end;
	newnode->data = val;
	return newnode;
}
void pop_back_list(Linklist h) //尾删法进行删除
{
	assert(h);
	Linklist temp = h->next;
	if(temp == NULL)
	{
		return;
	}
	else if(temp->next == NULL)
	{
		free(temp);
		h->next = NULL;
		return;
	}
	while(temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->prev->next = NULL;
	free(temp);
	temp = NULL;
}
void push_front_list(Linklist h,int val)//头插法进行插入
{
	assert(h);
	Linklist temp = h;
	Linklist newnode = createlist();
	newnode->data = val;
	if(temp->next == NULL)
	{
		temp->next = newnode;
		newnode->prev = temp;
		return;
	}
	newnode->next = temp->next;
	temp->next->prev = newnode;
	temp->next = newnode;
	newnode->prev = temp;
}
void pop_front_list(Linklist h)//头删法进行删除
{
	assert(h);
	Linklist temp = h->next;
	if(temp == NULL)
	{
		return;
	}
	temp->next->prev = temp->prev;
	temp->prev->next = temp->next;
	free(temp);
	temp = NULL;
}
void push_pos_back(Linklist h,int pos,int val)//在指定位置后插入
{
	assert(h);
	Linklist temp = h;
	while(pos--)
	{
		temp = temp->next;
	}
	Linklist newnode = createlist();
	newnode->next = temp->next;
	temp->next->prev = newnode;
	temp->next = newnode;
	newnode->prev = temp;
	newnode->data = val;
}
void push_pos_front(Linklist h,int pos,int val)//在指定位置前插入
{
	assert(h);
	Linklist temp = h;
	while(--pos)
	{
		temp = temp->next;
	}
	Linklist newnode = createlist();
	newnode->next = temp->next;
	temp->next->prev = newnode;
	temp->next = newnode;
	newnode->prev = temp;
	newnode->data = val;
}
void pop_pos_list(Linklist h,int pos)//按照位置删除
{
	assert(h);
	Linklist temp = h;
	while(pos--)
	{
		temp = temp->next;
	}
	temp->next->prev = temp->prev;
	temp->prev->next = temp->next;
	free(temp);
	temp = NULL;
}
//根据指定的位置进行转换链表，如A->B->C->D->E->F  以 C 点 为转换 C->D->E->F->A->B
Linklist change_list(Linklist head ,int value)
{
	assert(head);
    Linklist temp = head->next;
	Linklist tail = head->next;
	Linklist newhead = head->next;
	//如果只有一个节点直接返回
	if(tail->next==NULL)
    return head;
    //找到尾节点
    while(tail->next)
    {
        tail = tail->next;
    }
    while(temp)
    {
        if(temp->data == value)//说明节点存在
        {
            //1.翻转节点为头节点
            //A->B->C->D->E->F 不变
            if(temp->prev->prev == NULL)
            {
                //无需操作
                break;
            }
            //2.翻转节点为尾节点
            //F->A->B->C->D->E
            else if(temp->next == NULL)
            {
                temp->prev->next = NULL;//变成尾节点
				temp->next = newhead;    //让尾结点和第一个节点相连
				newhead->prev = temp;
				head->next = temp;      //让头结点和尾结点相连
				temp->prev = head;
                break;

            }
            //3.翻转节点为中间位置
            //C->D->E->F->A->B
            else
            {
                temp->prev->next = NULL;//翻转前一个节点变成尾节点
				tail->next = newhead;   //让尾结点与第一个节点相连
				newhead->prev = tail;
				head->next = temp;       //让头结点与断开的节点相连
				temp->prev = head;
                break;

            }
        }
        temp = temp->next;
    }
    return head;
}
Linklist reverse_list(Linklist head)//反转链表
{
	assert(head);
	Linklist temp = NULL;
	Linklist current = head->next;
	if(current->next == NULL)
	{
		return head;
	}
 
	//交换每个节点的后向指针和前向指针
	// 1-->2-->3, 假设2为current.
	while (current != NULL)
	{
		temp=current->prev;
        current->prev=current->next;
        current->next=temp;
        //flag=current;
        if(current->prev==NULL)break;//此处也可以用预先定义的一个DNode *flag，记录current=current->pre操作之前的原始current值，结束时将h->next=flag
        else current=current->prev;
	}
	//总结：先处理前向指针，然后处理后向指针。这些操作都只对当前节点(current),不涉及其它节点。
	//1.缓存前向指针
	//2.将后向指针赋值给前向指针
	//3.将缓存的前者指针，赋值给后向指针
	//4.当前节点指针移动到下一个待处理节点
 
	//修改头指针之前，先检测链表是否为空链表，或者只有一个节点的情况
	if (temp != NULL)
	{
		head ->next->next = NULL;
		head->next = current;
	}
	return head;
}
Linklist connect_list(Linklist L1,Linklist L2)//合并两个双向链表（无序）
{
	assert(L1);
	assert(L2);
	Linklist tail = L1->next;
	Linklist head = L2->next;
	while(tail->next)
	{
		tail = tail->next;
	}
	tail->next = head;
	head->prev = tail;
	free(L2);
	L2 = NULL;
	return L1;
}

void printf_list(Linklist h) //打印双向链表
{
	assert(h != NULL);
	Linklist temp = h->next;
	while(temp != NULL)
	{
		cout<<temp->data<<" ";
		temp = temp->next;
	}
	cout<<endl;
}
int main()
{
	Linklist h = createlist();
	Linklist L = createlist();
	Linklist L1 = createlist();
	for(int i= 0;i<8;i++)
	{
		//push_back_list(h,i+1);
		push_front_list(h,i+1);
		push_back_list(L,i+1);
		push_front_list(L1,i+1);
	}
	printf_list(h);
	cout<<"尾删后:"<<endl;
	pop_back_list(h);
	printf_list(h);
	cout<<"头插后:"<<endl;
	push_front_list(h,6);
	printf_list(h);
	cout<<"头删后:"<<endl;
	pop_front_list(h);
	printf_list(h);
	cout<<"按位置后插入后："<<endl;
	push_pos_back(h,2,11);
	printf_list(h);
	cout<<"按位置前插入后："<<endl;
	push_pos_front(h,4,12);
	printf_list(h);
	cout<<"按照位置删除后:"<<endl;
	pop_pos_list(h,5);
	printf_list(h);
	cout<<"按照位置转换后的链表："<<endl;
	change_list(h,12);
	printf_list(h);
	cout<<"反转后的链表："<<endl;
	reverse_list(h);
	printf_list(h);
	cout<<"L链表："<<endl;
	printf_list(L);
	cout<<"合并后:"<<endl;
	connect_list(h,L);
	printf_list(h);

}

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

typedef struct node{
	int data;
	struct node* next;
	struct node* prev;
}Node;

typedef struct node * Linklist;

Linklist createlist(); //创建一个带头节点的双向链表
Linklist push_back_list(Linklist head,int val); //尾插法进行插入
void pop_back_list(Linklist h); //尾删法进行删除
void push_front_list(Linklist h,int val);//头插法进行插入
void pop_front_list(Linklist h);//头删法进行删除
void push_pos_back(Linklist h,int pos,int val);//在指定位置后插入
void push_pos_front(Linklist h,int pos,int val);//在指定位置前插入
void pop_pos_list(Linklist h,int pos);//按照位置删除
Linklist change_list(Linklist head ,int value);//根据指定的位置进行转换链表，如A->B->C->D->E->F  以 C 点 为转换 C->D->E->F->A->B
Linklist connect_list(Linklist L1,Linklist L2);//合并两个链表（无序）
void printf_list(Linklist h); //打印双向链表