数据结构——双向链表（C语言）

﹏ヽ暗。殇╰゛Y 2022-08-25 08:25 232阅读 0赞

**单链表的结点中只有一个指向其后继结点的指针域next，在单链表中，想要找其前驱则只能从该链表的头指针开始，顺着各结点的next 域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)。**

**双向链表结点中存储两个指针域，即结点的直接前驱和直接后继，这样方便操作。**

**以下是链表的结构:**

![SouthEast][]

**以下是C语言源程序：**

**函数声明：**

#ifndef List_H
    #define List_H
    
    typedef int Item;
    typedef struct node *PNode;
    typedef PNode Position;
    typedef struct node
    {
    	Item data;
    	PNode previous;
    	PNode next;
    }Node;
    
    typedef struct link *DLinkList;
    typedef struct link
    {
    	PNode head;
    	PNode tail;
    	Item size;
    }DLink;
    
    /***创建有数据项结点，并返回该结点的地址***/
    Position Make_Node(Item);
    
    /***创建空的双向链表***/
    DLinkList Creat_List();
    
    /***判断是否为空链表***/
    int Is_Empty(DLinkList);
    
    /***创建存储有数据项和结点的链表***/
    DLinkList DCreat_List(DLinkList);
    
    /***释放某个结点***/
    void Free_Node(Position);
    
    /***在链表的第i个位置插入数据项***/
    void Insert_List(DLinkList,int,Item);
    
    /***计算链表的大小***/
    int Size_List(DLinkList);
    
    /***在链表的第i个位置删除数据项***/
    void Delete_List(DLinkList,int);
    
    /***摧毁链表***/
    void Destroy_List(DLinkList);
    
    /***遍历链表***/
    void Traverse_List(DLinkList);
    #endif

**函数定义：**

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include"List.h"
    /**********************
    ****函数定义***********
    **********************/
    
    /***创建有数据项结点，并返回该结点的地址***/
    Position Make_Node(Item data)
    {
    	PNode P=(PNode)malloc(sizeof(Node));
    	if(NULL!=P)
    	{
    		P->data=data;
    		P->next=NULL;
    		P->previous=NULL;
    	}
    	return P;
    }
    
    /***创建空的双向链表***/
    DLinkList Creat_List()
    {
    	DLinkList L=(DLinkList)malloc(sizeof(DLink));
    	PNode PHead=Make_Node(0);
    	if(NULL!=L && NULL!=PHead)
    	{
    			L->size=0;
    			L->head=PHead;
    			L->tail=PHead;
    	}
    	return L;
    }
    
    /***判断是否为空链表***/
    int Is_Empty(DLinkList L)
    {
    	if(0==L->size && L->head==L->tail)
    		return 1;
    	else
    		return 0;
    }
    
    /***创建存储有数据项和结点的链表***/
    DLinkList DCreat_List(DLinkList L)
    {
    	int data;
    	L=Creat_List();
    	PNode PCurrent=L->head;
    	printf("Please enter the first data:");
    	while(scanf_s("%d",&data)==1)
    	{
    		PNode temp=(PNode)malloc(sizeof(Node));
    		if(temp)
    		{
    			temp->data=data;
    			temp->next=PCurrent->next;
    			PCurrent->next=temp;
    			PCurrent=temp;
    			printf("Enter the next data:");
    			L->size++;
    		}
    	}
    	return L;
    }
    
    /***释放某个结点***/
    void Free_Node(Position P)
    {
    	free(P);
    }
    
    /***在链表的第i个位置插入数据项***/
    void Insert_List(DLinkList L,int i,Item data)
    {
    	PNode PCurrent,temp;
    	int j=0;
    	PCurrent=L->head;
    	while(NULL!=PCurrent->next && j<i-1)
    	{
    		PCurrent=PCurrent->next;
    		++j;
    	}
    	if(j!=i-1 || i<1)
    	{
    		printf("Insert the data is failed.\n");
    		return;
    	}
    	temp=(PNode)malloc(sizeof(Node));
    	temp->data=data;
    	temp->next=PCurrent->next;
    	temp->previous=PCurrent;
    	PCurrent->next=temp;
    	if(NULL!=temp->next)
    		PCurrent->next->previous=temp;
    	L->size++;
    	printf("Insert the data of %d is success: %d\n",data,data);
    }
    
    /***计算链表的大小***/
    int Size_List(DLinkList L)
    {
    	return L->size;
    }
    
    /***在链表的第i个位置删除数据项***/
    void Delete_List(DLinkList L,int i)
    {
    	PNode PCurrent,temp;
    	int j=0;
    	PCurrent=L->head;
    	while(NULL!=PCurrent->next && j<i-1)
    	{
    		PCurrent=PCurrent->next;
    		++j;
    	}
    	if(j!=i-1 || i<1)
    	{
    		printf("Delete the data is failed.\n");
    		return;
    	}
    	temp=PCurrent->next;
    	PCurrent->next=temp->next;
    	if(NULL!=temp->next)
    	temp->next->previous=PCurrent->next;
    	free(temp);
    	L->size--;
    }
    
    /***摧毁链表***/
    void Destroy_List(DLinkList L)
    {  
    	PNode  temp = L->head->next;  
        while(temp)  
        {  
            PNode tp = temp;  
            temp = temp->next;  
            free(tp);  
        }  
        free(L);  
    } 
    
    /***遍历链表***/
    void Traverse_List(DLinkList L)
    {
    	if(Is_Empty(L))
    	{
    		printf("The DList is no data.\n");
    		exit(0);
    	}
    	PNode PCurrent=L->head->next;
    	printf("The DList of data are:\n");
    	while(NULL!=PCurrent)
    	{
    		printf("%d  ",PCurrent->data);
    		PCurrent=PCurrent->next;
    	}
    	printf("\n");
    }

**测试程序：**

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include"List.h"
    
    int main()
    {
    	int size;
    	//DLinkList L=(DLinkList)malloc(sizeof(DLink));
    	DLinkList L=NULL;
    	DLinkList Link=NULL;
    	/***创建空的双向链表***/
    	Link=Creat_List();
    
    	/***判断是否为空链表***/
    	if(Is_Empty(Link))
    		printf("The list is empty.\n");
    
    	/***创建存储有数据项和结点的链表***/
    	L=DCreat_List(L);
    	size=Size_List(L);//链表的大小
    	printf("The size of list is: %d\n",size);
    	Traverse_List(L);//遍历链表
    
    	/***在链表的地第3个位置插入数据项6**/
    	Insert_List(L,3,6);
    	size=Size_List(L);
    	printf("The size of list is: %d\n",size);
    	Traverse_List(L);//遍历链表
    
    	/***删除链表第3位置的数据项***/
    	Delete_List(L,3);
    	size=Size_List(L);
    	printf("The size of list is: %d\n",size);
    	Traverse_List(L);//遍历链表
    	
    	/***摧毁链表***/
    	Destroy_List(L);
    	if(Is_Empty(L))
    		printf("The list is empty.\n");
    	else
    		printf("The list is destroied.\n");
    	return 0;
    }

[SouthEast]: /images/20220824/2aee2607545c4224ab9fe075e15d855d.png