Linux下的C语言编程——双向循环链表的简单实现

超、凢脫俗 2022-07-15 06:48 164阅读 0赞

下面我先贴上我的代码

#include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
    	int num;
    	struct node *next,*prior;
    };
    
    typedef struct node Dbnode;
    typedef struct node *Dblink;
    
    void creat_link(Dblink *head) //创建链表
    {
    	*head = (Dblink)malloc(sizeof(Dbnode));
    
    	if(!(*head))
    	{
    		printf("malloc error!\n");
    		exit(-1);
    	}
    
    	(*head)->next = (*head)->prior = *head;//让头节点的前驱和后继都指向自己形成一个环
    }
    
    void creat_node(Dblink *newnode) //生成节点
    {
    	*newnode = (Dblink)malloc(sizeof(Dbnode));
    
    	if(!(*newnode))
    	{
    		printf("malloc error!\n");
    		exit(-1);
    	}
    }
    
    void insert_head(Dblink *head,Dblink newnode)//头插法实现创建链表
    {
    	newnode->next = (*head)->next;
    	newnode->prior = *head;
    	(*head)->next->prior = newnode;
    	(*head)->next = newnode;
    
    	if((*head)->prior == *head)
    	{
    		(*head)->prior = newnode;
    	}
    }
    
    void insert_tail(Dblink *head,Dblink newnode)//尾插法
    {
    	Dblink temp = *head;
    
    	while(temp->next != *head)
    	{
    		temp = temp->next;
    	}
    
    	newnode->prior = temp;
    	newnode->next = temp->next;
    	temp->next = newnode;
    	(*head)->prior = newnode;
    }
    
    void display(Dblink head)//遍历链表
    {
    	Dblink temp = head->next;
    
    	if((head)->next == head)
    	{
    		printf("empty!\n");
    		return ;
    	}
    	else
    	{
    		while(temp != head)
    		{
    			printf("sum = %d\n",temp->num);
    			temp = temp->next;
    		}
    	}
    }
    
    void delete_node(Dblink *head, int num)//删除节点
    {
    	Dblink temp;
    	temp = (*head)->next;
    
    	while(temp->num != num && temp->next != *head)
    	{
    		temp = temp->next;
    	}
    
    	if(temp->num == num)
    	{
    		temp->prior->next = temp->next;
    		temp->next->prior = temp->prior;
    		free(temp);
    	}
    	else
    	{
    		printf("no such number!\n");
    		return;
    	}
    }
    
    void clear(Dblink *head)// 将链表置空
    {
    	Dblink temp = (*head)->next;
    	Dblink p = *head;
    
    	if((*head)->next == *head)
    	{
    		printf("empty!\n");
    		return ;
    	}
    	else
    	{
    		while(temp != *head)
    		{
    			(*head)->next = temp->next;
    			free(temp);
    			temp = (*head)->next;
    		}
    		printf("success!\n");
    	}
    }
    
    void insert_mid(Dblink *head,Dblink newnode,int num)//中间插入从小到小插入
    {
    	Dblink temp = (*head)->next;
    
    	if((*head)->next == *head)
    	{
    		newnode->prior = (*head);
    		newnode->next = *head;
    		(*head)->next = newnode;
    		(*head)->prior = newnode;
    	}
    	else
    	{
    		while(temp->num < num && temp->next != *head)
    		{
    			temp = temp->next;
    		}
    
    		if(temp->next != *head)
    		{
    			newnode->prior = temp->prior;
    			newnode->next = temp;
    			temp->prior->next = newnode;
    			temp->prior = newnode;
    		}
    		else
    		{
    			if(num > temp->num)
    			{
    				newnode->next = *head;
    				newnode->prior = temp;
    				(*head)->prior = newnode;
    				temp->next = newnode;
    			}
    			else
    			{
    				newnode->prior = temp->prior;
    				newnode->next = temp;
    				temp->prior->next = newnode;
    				temp->prior = newnode;
    			}
    		}
    	}
    }
    
    
    
    int main()//主函数
    {
    	Dblink head;
    	Dblink newnode;
    
    	int i;
    	int num;
    
    	creat_link(&head);			//下面就是挨个测试函数，有些函数先注释掉，用到时候再用
    
    /*	for(i = 0; i < 10; i++)
    	{
    		creat_node(&newnode);
    		newnode->num = i;
    	//	insert_head(&head,newnode);
    		insert_tail(&head,newnode);
    	}*/
    
    //	display(head);
    
    /*	printf("input a integer!\n");
    	scanf("%d",&num);
    
    	delete_node(&head,num);*/
    
    //	clear(&head);
    	
    	for(i = 0; i < 10; i++)
    	{
    		creat_node(&newnode);
    		scanf("%d",&num);
    		newnode->num = num;
    		insert_mid(&head,newnode,newnode->num);
    	}
    
    
    	display(head);
    
        return 0;
    }