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

秒速五厘米 2022-05-17 08:07 198阅读 0赞

### C语言实现双向循环链表的基本功能与调试： ###

//DoubleCircleLinkLst.h
    #ifndef _LINKLIST_H
    #define _LINKLIST_H
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define FAILURE    10000
    #define SUCCESS    10001
    #define TRUE       10002
    #define FALSE      10003
    
    typedef int ElemType; 
    
    struct node     
    {
    	ElemType data;  
    	struct node *next; 
    	struct node *prior;
    };
    
    typedef struct node Node;
    
    int LinkInit(Node **l);
    int LinkInsert(Node *l, int n, ElemType e);
    int LinkTraverse(Node *l, void (*p)(ElemType));
    int LinkLength(Node *l);
    int LinkEmpty(Node *l);
    int GetElem(Node *l, int p, ElemType *e);
    int LocateElem(Node *l, ElemType e, int (*p)(ElemType, ElemType));
    int LinkDelete(Node *l, int p, ElemType *e);
    int LinkClear(Node *l);
    int LinkDestroy(Node **l);
    
    #endif

//DoubleCircleLinkList.c
    #include "LinkList.h"
    
    int LinkInit(Node **l)
    {
    	*l = (Node *)malloc(sizeof(Node) * 1);   
    	if (NULL == *l)
    	{
    		return FAILURE;
    	}
    
    	(*l)->next = (*l);    
    	(*l)->prior = (*l);   
    
    	return SUCCESS;
    }
    
    int LinkInsert(Node *l, int n, ElemType e)  
    {
    	Node *p = l;
    	int k = 1;   
    
    	if (NULL == l)    
    	{
    		return FAILURE;
    	}
    
    	if (n > LinkLength(l) + 1)    
    	{
    		return FAILURE;
    	}
    
    	while (k < n)     
    	{
    		p = p->next;
    		k++;
    	}
    
    
    	if (k > n)    
    	{
    		return FAILURE;
    	}
    
    	Node *q = (Node *)malloc(sizeof(Node) * 1);
    	if (NULL == q)
    	{
    		return FAILURE;
    	}
    
    
    	q->data = e;
    	q->prior = p;
    	q->next = p->next;
    	p->next = q;
    	if (l != q->next)  
    	{
    		q->next->prior = q;
    	}
    
    	return SUCCESS;
    }
    
    int LinkTraverse(Node *l, void (*p)(ElemType))
    {
    	if (NULL == l)
    	{
    		return FAILURE;
    	}
    	Node *q = l;
    
    	while (q->next != l)    
    	{
    		q = q->next;
    		p(q->data);
    	}
    
    	return SUCCESS;
    }
    
    int LinkLength(Node *l)
    {
    	if (NULL == l)
    	{
    		return FAILURE;
    	}
    
    	int len = 0;
    	Node *p = l->next;
    
    	while (p != l)   
    	{
    		len++;
    		p = p->next;
    	}
    
    	return len;
    }
    
    int LinkEmpty(Node *l)
    {
    	return (l->next == l && l->prior == l) ? TRUE : FALSE; 
    }
    
    int GetElem(Node *l, int p, ElemType *e)   
    {
    	if (NULL == l || p < 1)   
    	{
    		return FAILURE;
    	}
    
    	Node *q = l->next;  
    	int i;
    
    	for (i = 1; i < p && q != l; i++) 
    	{
    		q = q->next;
    	}
    
    	if (q == l)      
    	{
    		return FAILURE;
    	}
    
    	*e = q->data;    
    
    	return SUCCESS;
    }
    
    int LocateElem(Node *l, ElemType e, int (*p)(ElemType, ElemType))
    {
    	if (NULL == l)
    	{
    		return FAILURE;
    	}
    	
    	Node *q = l->next;
    	int len = 1;
    
    	while (q != l)   
    	{
    		if (p(e, q->data) == TRUE)
    		{
    			return len;
    		}
    		q = q->next;
    		len++;
    	}
    
    	return FAILURE;
    }
    
    int LinkDelete(Node *l, int p, ElemType *e)
    {
    	int k = 1;
    	Node *q = l;
    
    	if (l == NULL)
    	{
    		return FAILURE;
    	}
    
    	if (p > LinkLength(l) + 1)   
    	{
    		return FAILURE;
    	}
    
    	while (k < p)
    	{
    		q = q->next;
    		k++;
    	}
    
    	if (k > p)
    	{
    		return FAILURE;
    	}
    
    	Node *n = q->next;
    	*e = n->data;
    	q->next = n->next;   
    					     
    
    	n->next->prior = q;
    	free(n);
    
    	return SUCCESS;
    }
    
    int LinkClear(Node *l)
    {
    	if (NULL == l)
    	{
    		return FAILURE;
    	}
    
    	Node *p = l->next;
    
    	while (p != l) 
    	{
    		l->next = p->next;
    		//p->next->prior = l;
    		free(p);
    		p = l->next;
    	}
    
    	l->prior = l;   //**
    
    	return SUCCESS;
    }
    
    int LinkDestroy(Node **l)
    {
    	if (l == NULL)
    	{
    		return FAILURE;
    	}
    	free(*l);
    	(*l) = NULL;
    
    	return SUCCESS;
    }
    
    #if 0
    int LinkReverse(Node **l)
    {
    	if (NULL == l)
    	{
    		return FAILURE;
    	}
    
    	/*Node *p = l->next;
    	l->next = NULL;
    
    	while (p != NULL)
    	{
    		Node *q = p;
    		p = p->next;
    		q->next = l->next;
    		q->prior = l;
    		l->next = q; 
    	}*/
    
    	Node *p = (*l)->next;
    	Node *tmp;
    
    	if (p == NULL)
    	{
    		return FAILURE;
    	}
    
    	if (p->next == NULL)
    	{
    		return FAILURE;
    	}
    
    	printf("xxxxx\n");
    	while (p->next != NULL)
    	{
    		tmp = p->next;
    		p->next = p->prior;
    		p->prior = tmp;
    		p = p->next;
    	}
    	
    	printf("%d\n", p->data);
    	tmp = p->next;
    	p->next = p->prior;
    	p->prior = (*l);
    
    	(*l)->next = p;
    	
    
    	return SUCCESS;
    }
    #endif

//TestDoubleCircleLinkList.c
    #include "LinkList.h"
    
    void print(ElemType e)
    {
    	printf("%d ", e);
    }
    
    int equal(ElemType e1, ElemType e2)
    {
    	return (e1 == e2) ? TRUE : FALSE;
    }
    	
    
    int main()
    {
    	int ret, i;
    	Node *first = NULL;
    
    	srand(time(NULL));
    
    	ret = LinkInit(&first);
    	if (ret == FAILURE)
    	{
    		printf("Init Failure!\n");
    	}
    	else
    	{
    		printf("Init Success!\n");
    	}
    
    	for (i = 0; i < 10; i++)
    	{
    		ret = LinkInsert(first, i + 1, rand() % 20);
    		if (ret == FAILURE)
    		{
    			printf("Insert Failure!\n");
    		}
    		else
    		{
    			printf("Insert Success!\n");
    		}
    	}
    
    	ret = LinkTraverse(first, print);
    	if (ret == FAILURE)
    	{
    		printf("\nTraverse Falure!\n");
    	}
    	else
    	{
    		printf("\nTraverse Success!\n");
    	}
    
    	/*ret = LinkReverse(&first);
    	if (ret == SUCCESS)
    	{
    		printf("Reverse Success!\n");
    	}
    	else
    	{
    		printf("Reverse Failure!\n");
    	}
    
    	ret = LinkTraverse(first, print);
    	if (ret == FAILURE)
    	{
    		printf("\nTraverse Falure!\n");
    	}
    	else
    	{
    		printf("\nTraverse Success!\n");
    	}*/
    
    
    	ret = LinkLength(first);
    	if (ret == FAILURE)
    	{
    		printf("Get Length Failure!\n");
    	}
    	else
    	{
    		printf("length %d\n", ret);
    	}
    
    	ret = LinkEmpty(first);
    	if (ret == TRUE)
    	{
    		printf("List is empty!\n");
    	}
    	else if (ret == FALSE)
    	{
    		printf("List is not empty!\n");
    	}
    
    	int p = 10;
    	ElemType e;
    	ret = GetElem(first, p, &e);
    	if (ret == FAILURE)
    	{
    		printf("Get element failure!\n");
    	}
    	else
    	{
    		printf("The %dth element is %d\n", p, e);
    	}
    
    	e = 10;
    	ret = LocateElem(first, e, equal);
    	if (FAILURE == ret)
    	{
    		printf("%d not exist!\n", e);
    	}
    	else
    	{
    		printf("%d is %dth element!\n", e, ret);
    	}
    
    	p = 1;
    	ret = LinkDelete(first, p, &e);
    	if (ret == FAILURE)
    	{
    		printf("Delete Failure!\n");
    	}
    	else
    	{
    		printf("Delete %d Success!\n", e);
    	}
    
    	ret = LinkTraverse(first, print);
    	if (ret == FAILURE)
    	{
    		printf("\nTraverse Falure!\n");
    	}
    	else
    	{
    		printf("\nTraverse Success!\n");
    	}
    
    	ret = LinkClear(first);
    	if (ret == SUCCESS)
    	{
    		printf("Clear Success!\n");
    	}
    	else
    	{
    		printf("Clear Failure!\n");
    	}
    
    	ret = LinkEmpty(first);
    	if (ret == TRUE)
    	{
    		printf("List is empty!\n");
    	}
    	else if (ret == FALSE)
    	{
    		printf("List is not empty!\n");
    	}
    
    	ret = LinkDestroy(&first);
    	if (ret == SUCCESS)
    	{
    		printf("Destroy Success!\n");
    	}
    	else
    	{
    		printf("Destroy Failure!\n");
    	}
    
    	for (i = 0; i < 10; i++)
    	{
    		ret = LinkInsert(first, i + 1, rand() % 20);
    		if (ret == FAILURE)
    		{
    			printf("Insert Failure!\n");
    		}
    		else
    		{
    			printf("Insert Success!\n");
    		}
    	}
    
    	return 0;
    }