5.带头结点的双向循环链表

墨蓝 2022-11-22 12:52 145阅读 0赞

![在这里插入图片描述][20201104154944556.png_pic_center]

Dbilinkedlist.c

#include "Dbilinkedlist.h"
    
    
    
    D_head * create_Dbilinkedlist_head(void)
    { 
    	D_head * h = malloc(sizeof(*h));
    	h->first = h->last = NULL;
    	h->num = 0;
    
    	return h;
    }
    
    
    
    void create_order_Dbilinkedlist(D_head * h)
    { 
    	DbiNode * p = NULL; //指向带加入的结点
    
    	int x;
    	while(1)
    	{ 
    		scanf("%d", &x);
    		if(x == 0)
    		{ 
    			break;
    		}	
    		p = malloc(sizeof(*p));
    		p->data = x;
    		p->next = p->prev = NULL;
    
    		add_DbiNode(h, p);
    		
    	}
    
    	
    }
    
    void add_DbiNode(D_head * h, DbiNode * p)
    { 
    	if(h == NULL || p == NULL)
    	{ 
    		return;
    	}
    
    	//头结点存在，但是没有一个数据结点
    	if(h->first == NULL)
    	{ 
    		h->first = p;
    		h->last = p;
    
    		p->next = p;
    		p->prev = p;
    
    		h->num ++;
    		return;
    	}
    
    	int flag = 0;
    	DbiNode * pk = h->first;
    	do 
    	{ 
    		if(pk->data > p->data)
    		{ 
    			flag = 1;//找到了
    			break;
    		}
    
    		pk = pk->next;
    	}
    	while(pk != h->first);
    
    	if(flag) //找到了
    	{ 
    		if(pk == h->first) //第一个结点 “头插法”
    		{ 
    			p->next = pk;
    			pk->prev = p;
    
    			h->first = p;
    
    			h->first->prev = h->last;
    			h->last->next = h->first;
    		}
    		else //“中间插入”
    		{ 
    			pk->prev->next = p;
    			p->prev = pk->prev;
    
    			p->next = pk;
    			pk->prev = p;
    		}
    	}
    	else //没有找到“尾插法”
    	{ 
    		h->last->next = p;
    		p->prev = h->last;
    
    		h->last = p;
    
    		h->first->prev = h->last;
    		h->last->next = h->first;
    	}
    
    	h->num ++;
    	
    }
    
    
    
    void delete_x(D_head * h, Elemtype x)
    { 
    	if(h == NULL || h->first == NULL)
    	{ 
    		return;
    	}
    
    	DbiNode * px = h->first;
    	int flag = 0;//表示没有找到
    	do 
    	{ 	
    		if(px->data == x)
    		{ 
    			flag = 1; //表示找到了
    			break;
    		}
    		px = px->next;
    	}
    	while(px != h->first);
    
    	if(flag == 0)
    	{ 
    		return;
    	}
    
    	//删除操作
    	if(px == h->first) //第一个
    	{ 
    		if(px->next == h->first)//只有一个数据结点
    		{ 
    			h->first = NULL;
    			h->last = NULL;
    			px->next = px->prev = NULL;
    		}
    		else
    		{ 
    			h->first = px->next;
    
    			px->next = NULL;
    			px->prev = NULL;
    
    			h->first->prev = h->last;
    			h->last->next = h->first;
    			
    		}
    		free(px);
    		h->num --;
    	}
    	else if(px == h->last)//最后一个
    	{ 
    		h->last = px->prev;
    
    		px->prev = NULL;
    		px->next = NULL;
    		free(px);
    		h->num --;
    		
    		h->last->next = h->first;
    		h->first->prev = h->last;
    	}
    	else //中间结点 
    	{ 
    		px->prev->next = px->next;
    		px->next->prev = px->prev;
    
    		px->next = NULL;
    		px->prev = NULL;
    
    		free(px);
    		h->num -- ;
    	}
    	
    }
    
    /* delete_list: 删除整个链表(链表的所有的结点 都需要free, 头结点也需要free) @h: 待删除的链表的头结点 无返回值。 */
    void delete_list(D_head * h)
    { 
    	if(h == NULL)
    	{ 
    		return;
    	}
    
    	if(h->first == NULL)
    	{ 
    		free(h);
    		return;
    	}
    
    	DbiNode * px = h->first;
    	while(px)
    	{ 
    		if(px->next == h->first)//只有一个数据结点
    		{ 
    			h->first = NULL;
    			h->last = NULL;
    			px->next = px->prev = NULL;
    		}
    		else
    		{ 
    			h->first = px->next;
    
    			px->next = NULL;
    			px->prev = NULL;
    
    			h->first->prev = h->last;
    			h->last->next = h->first;
    			
    		}
    		free(px);
    
    		px = h->first;
    	}
    
    	free(h);
    }
    
    
    void print(D_head * h)
    { 
    	if(h == NULL)
    	{ 
    		printf("No linkedlist \n");
    		return;
    	}
    
    	if(h->first == NULL)
    	{ 
    		printf("No DbiNode \n");
    		return;
    	}
    
    	DbiNode * pk = h->first;
    	DbiNode * pr = h->last;
    
    	do 
    	{ 
    		printf("%d ", pk->data);
    		pk = pk->next;
    	}
    	while(pk != h->first);
    	printf("\n");
    
    	do 
    	{ 
    		printf("%d ", pr->data);
    		pr = pr->prev;
    	}
    	while(pr != h->last);
    	printf("\n-----------\n");
    
    	printf("NUM == %d \n-----------\n", h->num);
    }

Dbilinkedlist.h

#ifndef __DBILINKEDLIST_H__
    #define __DBILINKEDLIST_H__
    
    #include <stdio.h>
    #include <stdlib.h>
    
    
    //数据元素的类型 
    typedef int Elemtype;
    
    //数据结点的类型
    typedef struct DbiNode
    { 
    	//指针域 
    	struct DbiNode * next ;
    	struct DbiNode * prev ;
    	
    	//数据域 
    	Elemtype data;
    	
    }DbiNode;
    
    //头结点的类型
    typedef struct D_head
    { 
    	DbiNode * first;
    	DbiNode * last;
    	
    	int num;
    
    }D_head;
    
    
    D_head * create_Dbilinkedlist_head(void);
    void print(D_head * h);
    void add_DbiNode(D_head * h, DbiNode * p);
    void create_order_Dbilinkedlist(D_head * h);
    void delete_x(D_head * h, Elemtype x);
    
    
    
    #endif

main.c

#include "Dbilinkedlist.h"
    
    
    int main()
    { 
    	D_head * h = create_Dbilinkedlist_head();
    	create_order_Dbilinkedlist(h);
    	print(h);
    
    	int x;
    	scanf("%d", &x);
    	delete_x(h,  x);
    	print(h);
    }

[20201104154944556.png_pic_center]: /images/20221120/49eb2529f5e64990811168078ed478ac.png