3.不带头结点的双链表

淩亂°似流年 2022-11-22 12:52 184阅读 0赞

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

bilinkedlist.c

#include "bilinkedlist.h"
    
    
    biNode * create_bilinkedlist(void)
    { 
    	biNode * p = NULL; //指向带加入的那一个数据结点
    	biNode * first = 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;
    
    		first = add_biNode(first, p);
    	}
    
    	return first;
    }
    
    biNode * add_biNode(biNode * first,biNode * p)
    { 
    	if(first == NULL)
    	{ 
    		return p;
    	}
    
    	if(p == NULL)
    	{ 
    		return first;
    	}
    
    	biNode * pk = first;
    	biNode * pr = NULL;
    	while(pk)
    	{ 
    		if(pk->data > p->data)
    		{ 
    			break;
    		}
    		pr = pk;
    		pk = pk->next;
    	}
    
    	if(pk == NULL) //没有找到 “尾插法”
    	{ 
    		pr->next = p;
    		p->prev = pr;
    	}
    	else//找到了
    	{ 
    		if(pk == first) //找到的是第一个结点“头插法”
    		{ 
    			first = p;
    
    			p->next = pk;
    			pk->prev = p;
    		}
    		else //"中间插入"
    		{ 
    			pk->prev->next = p;
    			p->prev = pk->prev;
    
    			p->next = pk;
    			pk->prev = p;
    		}
    	}
    
    	return first;
    }
    
    
    biNode * delete_x(biNode * first, Elemtype x)
    { 
    	if(first == NULL)
    	{ 
    		return NULL;
    	}
    
    	biNode * px = first;
    
    	while(px)
    	{ 
    		if(px->data == x)
    		{ 
    			break;
    		}
    		px = px->next;
    	}
    
    	if(px == NULL)
    	{ 
    		return first;
    	}
    
    	if(px == first ) //第一个
    	{ 	
    		if(px->next != NULL)
    		{ 
    			first = px->next;
    			first->prev = NULL;
    			px->next = NULL;
    		}
    		else
    		{ 
    			first = NULL;
    		}
    		
    	}
    	else if(px->next == NULL)//最后一个
    	{ 
    		px->prev->next = NULL;
    		px->prev = NULL;
    	}
    	else
    	{ 
    		px->prev->next = px->next;
    		px->next->prev = px->prev;
    
    		px->next = NULL;
    		px->prev = NULL;
    	}
    
    	free(px);
    	return first;
    }
    
    
    biNode * delete_all_x(biNode * first, Elemtype x)
    { 
    	if(first == NULL)
    	{ 
    		return NULL;
    	}
    
    	biNode * px = first;
    	biNode * ps = first;
    
    	while(1)
    	{ 
    		px = ps;
    		while(px)
    		{ 
    			if(px->data == x)
    			{ 
    			
    				break;
    			}
    			px = px->next;
    		}
    
    		if(px == NULL)
    		{ 
    			return first;
    		}
    
    		ps = px->next;
    		if(px == first) //第一个
    		{ 
    			
    			if(px->next != NULL)
    			{ 
    				first = px->next;
    				first->prev = NULL;
    				px->next = NULL;
    			}
    			else
    			{ 
    				first = NULL;
    			}
    			
    		}
    		else if(px->next == NULL)//最后一个
    		{ 
    			px->prev->next = NULL;
    			px->prev = NULL;
    		}
    		else
    		{ 
    			px->prev->next = px->next;
    			px->next->prev = px->prev;
    
    			px->next = NULL;
    			px->prev = NULL;
    		}
    
    		free(px);
    	}
    	return first;
    }
    
    
    void print(biNode * f)
    { 
    	if(f == NULL)
    	{ 
    		printf("No biNode!!!\n");
    		return ;
    	}
    	biNode * pn = f;
    	biNode * pr = NULL;
    
    	while(pn)
    	{ 
    		printf("%d ", pn->data);
    		pr = pn;
    		pn = pn->next;
    	}
    	printf("\n");
    
    	while(pr)
    	{ 
    		printf("%d ", pr->data);
    		pr = pr->prev;
    	}
    	printf("\n-------------\n");
    
    	return ;
    }

bilinkedlist.h

#ifndef __BILINKEDLIST_H__
    
    #define __BILINKEDLIST_H__
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int Elemtype; //数据元素类型
    
    //数据结点
    typedef struct biNode
    { 
    	//指针域
    	struct biNode * next;
    	struct biNode * prev;
    
    	//数据域
    	Elemtype data;
    
    }biNode;
    
    biNode * create_bilinkedlist(void);
    biNode * add_biNode(biNode * first,biNode * p);
    void print(biNode * f);
    biNode * delete_x(biNode * first, Elemtype x);
    biNode * delete_all_x(biNode * first, Elemtype x);
    
    
    #endif

main.c

#include "bilinkedlist.h"
    
    
    int main()
    { 
    	biNode * f = create_bilinkedlist();
    	print(f);
    
    	Elemtype x;
    	scanf("%d", &x);
    	f = delete_all_x(f, x);
    	print(f);
    
    }

[20201104154352851.png_pic_center]: /images/20221120/45c02cc2ef29423c983bb8f0a53d76f5.png