4.带头结点的双链表

向右看齐 2022-11-22 12:52 181阅读 0赞

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

bilinkedlistwithhead.c

#include "bilinkedlistwithhead.h"
    
    
    head * creat_bilinkedlist_head(void)
    { 
    	head * h = (head *)malloc(sizeof(*h));
    
    	h->first = h->last = NULL;
    	h->num = 0;
    
    	return h;
    }
    
    void creat_order_linkedlist(head * h)
    { 
    	biNode * p = NULL; //带加入的结点的指针
    
    	int n;
    	while(1)
    	{ 
    		scanf("%d", &n);
    		if(n == 0)
    		{ 
    			break;
    		}
    
    		p = (biNode *)malloc(sizeof(*p));
    		p->data = n;
    		p->next = p->prev = NULL;
    
    		add_biNode(h, p);
    	}
    }
    
    void add_biNode(head * h, biNode * p)
    { 
    	if(h == NULL || p == NULL)
    	{ 
    		return;
    	}
    
    	if(h->first == NULL)
    	{ 
    		h->first = h->last = p;
    		h->num ++;
    		return;
    	}
    	
    	biNode * pk = h->first;
    	while(pk)
    	{ 
    		if(pk->data > p->data)
    		{ 
    			break;
    		}
    
    		pk = pk->next;
    	}
    
    	if(pk == NULL)//没找到 “尾插法”
    	{ 
    		h->last->next = p;
    		p->prev = h->last;
    
    		h->last = p;
    	}
    	else if(pk == h->first)// 找到的是第一个"头插法"
    	{ 
    		p->next = pk;
    		pk->prev = p;
    
    		h->first = p;
    	}
    	else //中间插入
    	{ 
    		pk->prev->next = p;
    		p->prev = pk->prev;
    
    		p->next = pk;
    		pk->prev = p;
    	}
    
    	h->num ++ ;
    }
    
    void delete_x(head * h, Elemtype x)
    { 
    	if(h == NULL || h->first == NULL)
    	{ 
    		return;
    	}
    
    	biNode * px = h->first;
    
    	while(px)
    	{ 	
    		if(px->data == x)
    		{ 
    			break;
    		}	
    
    		px = px->next;
    	}
    
    	if(px == NULL)//没有找到
    	{ 
    		return;
    	}
    
    	if(px == h->first)//找到的是第一个
    	{ 
    		h->first = px->next;
    
    		if(h->first)
    		{ 
    			px->next = NULL;
    			h->first->prev = NULL;
    		}
    	}
    	else if(px == h->last) //找到的是最后一个
    	{ 
    		h->last = px->prev;
    
    		px->prev = NULL;
    		h->last->next = NULL;
    	}
    	else //删除中间的结点
    	{ 
    		px->prev->next = px->next;
    		px->next->prev = px->prev;
    
    		px->next = NULL;
    		px->prev = NULL;
    	}
    	
    	free(px);
    	h->num --;
    }
    
    
    
    void delete_all_x(head * h, Elemtype x)
    { 
    	if(h == NULL || h->first == NULL)
    	{ 
    		return;
    	}
    
    	biNode * px = h->first;
    	biNode * ps = h->first;
    
    	while(1)
    	{ 
    		px = ps;
    		while(px)
    		{ 	
    			if(px->data == x)
    			{ 
    				break;
    			}	
    
    			px = px->next;
    		}
    
    		if(px == NULL)//没有找到
    		{ 
    			return;
    		}
    		ps = px->next;
    		
    		if(px == h->first)//找到的是第一个
    		{ 
    			h->first = px->next;
    
    			if(h->first)
    			{ 
    				px->next = NULL;
    				h->first->prev = NULL;
    			}
    		}
    		else if(px == h->last) //找到的是最后一个
    		{ 
    			h->last = px->prev;
    
    			px->prev = NULL;
    			h->last->next = NULL;
    		}
    		else //删除中间的结点
    		{ 
    			px->prev->next = px->next;
    			px->next->prev = px->prev;
    
    			px->next = NULL;
    			px->prev = NULL;
    		}
    		
    		free(px);
    		h->num --;
    	}
    }
    
    
    void print(head * h)
    { 
    	if(h == NULL)
    	{ 
    		printf("No linkedlist!!\n");
    		return;
    	}
    
    	if(h->first == NULL)
    	{ 
    		printf("No biNode !!\n");
    		return;
    	}
    
    	//顺序输出
    	biNode * pk = h->first;
    	while(pk)
    	{ 
    		printf("%d ", pk->data);
    		pk = pk->next;
    	}
    	printf("\n");
    
    	//逆序输出
    	biNode * pr = h->last;
    	while(pr)
    	{ 
    		printf("%d ", pr->data);
    		pr = pr->prev;
    	}
    	printf("\n--------------\n");
    
    	//打印结点的个数
    	printf("num == %d ",h->num);
    	printf("\n--------------\n");
    	
    }

bilinkedlistwithhead.h

#ifndef __BILINKEDLISTWITHHEAD_H__
    #define __BILINKEDLISTWITHHEAD_H__
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int Elemtype ;//数据元素的类型
    
    //数据结点
    typedef struct biNode 
    { 
    	struct biNode * next ;
    	struct biNode * prev;
    
    	Elemtype data;
    }biNode;
    
    //头结点的类型
    typedef struct head
    { 
    	biNode * first;
    	biNode * last;
    
    	int num;
    }head;
    
    void print(head * h);
    void add_biNode(head * h, biNode * p);
    void delete_x(head * h, Elemtype x);
    void creat_order_linkedlist(head * h);
    head * creat_bilinkedlist_head(void);
    void delete_all_x(head * h, Elemtype x);
    
    #endif

main.c

#include "bilinkedlistwithhead.h"
    
    int main()
    { 
    	head * h = creat_bilinkedlist_head();
    	creat_order_linkedlist(h);
    	print(h);
    
    	int x;
    	scanf("%d", &x);
    	delete_x(h, x);
    	print(h);
    	
    }

[2020110415455088.png_pic_center]: /images/20221120/3e5a0000235c4fe3bf58713aec5d80bc.png