数据结构（单链表）（C语言）

傷城~ 2022-05-17 08:07 215阅读 0赞

### C语言实现单链表的基本功能与调试： ###

*  头文件

//LinkList.h
    #ifndef _LINKLIST_H
    #define _LINKLIST_H
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    
    #define SUCCESS 10000
    #define FAILURE 10001
    #define TRUE    10002
    #define FALSE   10003
    
    typedef int Elemtype;
    
    typedef struct Node
    {
    	Elemtype data;
    	struct Node *next;
    }Node;
    
    int LinkReverse(Node *head);
    int LinkListInit(Node **head);
    int LinkInsert(Node *head, int n, Elemtype e);
    int LinkTraverse(Node *head, void(*print)(Elemtype));
    int LinkLength(Node *head);
    int LinkEmpty(Node *head);
    int LinkGetelem(Node *head, int n, Elemtype *e);
    int LocateElem(Node *head, Elemtype e, int (*p)(Elemtype, Elemtype));
    int LinkDelete(Node *head, int n, Elemtype *e);
    int LinkClear(Node *head);
    int LinkDestory(Node **head);
    
    #endif

*  功能函数
    
        //LinkList.c
        #include "LinkList.h"
        
        int LinkReverse(Node *head)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *p = head->next, *q;
        	head->next = NULL;
        	
        	while(NULL != p)
        	{
        		q = p;
        		p = p->next;
        		q->next = head->next;
        		head->next = q;
        	}
        	return SUCCESS;
        }
        
        int LinkListInit(Node **head)
        {
        	*head = (Node *)malloc(sizeof(Node));
        	if(NULL == *head)
        	{
        		return FAILURE;
        	}
        
        	(*head)->next = NULL;
        	return SUCCESS;
        }
        
        
        int LinkInsert(Node *head, int n, Elemtype e)
        {
        	int k = 1;
        	Node *p = head, *q;
        	q = (Node *)malloc(sizeof(Node));
        
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        
        	while(k < n && NULL != p)
        	{
        		p = p->next;
        		++k;
        	}
        
        	if(k > n)
        	{
        		return FAILURE;
        	}
        
        	q->data = e;
        	q->next = p->next;
        	p->next = q;
        
        	return SUCCESS;
        }
        
        /*
        **头插法
        int LinkInsert(Node *head, Elemtype e)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *p = head, *q;
        	q = (Node *)malloc(sizeof(Node));
        	
        	q->data = e;
        	q->next = p->next;
        	p->next = q;
        	
        	return SUCCESS;
        }
        **尾插法
        int LinkInsert(Node *head, Elemtype e)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *p = head, *q;
        	q = (Node *)malloc(sizeof(Node)*1);
        	
        	while(p->next != NULL)
        	{
        		p = p->next;
        	}
        	
        	q->data = e;
        	q->next = NULL;
        	p->next = q;
        	
        	return SUCCESS;
        }
        
        */
        
        
        int LinkTraverse(Node *head, void(*print)(Elemtype))
        {
        	Node *p = head;
        	if(NULL == p)
        	{
        		return FAILURE;
        	}
        
        	while(NULL != p->next)
        	{
        		p = p->next;
        		print(p->data);
        	}
        	return SUCCESS;
        }
        
        
        
        int LinkLength(Node *head)
        {
        	int count = 0;
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *p = head->next;
        
        	while(p)
        	{
        		count++;
        		p = p->next;
        	}
        
        	return count;
        }
        
        int LinkEmpty(Node *head)
        {
        	if(NULL == head ||NULL ==  head->next)
        	{
        		return TRUE;
        	}
        	return FALSE;
        }
        
        
        int LinkGetelem(Node *head, int n, Elemtype *e)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        
        	Node *p = head;
        	int i;
        
        	for(i = 0; i < n; i++)
        	{
        		p = p->next;
        	}
        	if(!p)
        	{
        		return FAILURE;
        	}
        
        	*e = p->data;
        	return SUCCESS;
        }
        
        int LocateElem(Node *head, Elemtype e, int (*p)(Elemtype, Elemtype))
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *q = head;
        	int count = 0;
        	
        	while(q->next)
        	{
        		q = q->next;
        		++count;
        		if(TRUE == p(e, q->data))
        		{
        			return count;
        		}
        	}
        	
        	return FAILURE;
        }
        
        int LinkDelete(Node *head, int n, Elemtype *e)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	int i;
        	Node *p = head, *q = head;
        	
        	for(i = 0; i < n; i++)
        	{
        		q = p;
        		p = p->next;
        		if(NULL == p)
        		{
        			return FAILURE;
        		}
        	}
        	
        	*e = p->data;
        	q->next = p->next;
        	free(p);
        	return SUCCESS;
        	
        }
        
        int LinkClear(Node *head)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	
        	Node *p = head->next;
        	while(p)
        	{
        		head->next = p->next;
        		free(p);
        		p = head->next;
        	}
        	return SUCCESS;
        }
        
        int LinkDestory(Node **head)
        {
        	if(NULL == head)
        	{
        		return FAILURE;
        	}
        	free(*head);
        	*head = NULL;
        	return SUCCESS;
        }
 *  调试
    
        //TestLinkList.c
        #include "LinkList.h"
        
        void print(Elemtype e)
        {
        	printf("%d ", e);
        }
        
        int cmp(Elemtype e1, Elemtype e2)
        {
        	return (e1 == e2) ? TRUE :FALSE;
        }
        
        
        int main()
        {
        	int ret, i;
        	Node *head = NULL;
        
        	ret = LinkListInit(&head);
        	if(SUCCESS == ret)
        	{
        		printf("Init success.\n");
        	}
        	else
        	{
        		printf("Init failure.\n");
        	}
        
        	srand(time(NULL));
        
        	for(i = 0; i < 8; i++)
        	{
        		ret = LinkInsert(head, i+1, rand()%10);
        		if(SUCCESS == ret)
        		{
        			printf("Insert success.\n");
        		}
        		else
        		{
        			printf("Insert failure.\n");
        		}
        	}
        
        	ret = LinkTraverse(head, print);
        	if(SUCCESS == ret)
        	{
        		printf("Traverse success.\n");
        	}
        	else
        	{
        		printf("Traverse failure.\n");
        	}
        	
        	ret = LinkReverse(head);
        	if(SUCCESS == ret)
        	{
        		printf("Reverse success.\n");
        	}
        	else
        	{
        		printf("Reverse failure.\n");
        	}
        	
        	ret = LinkTraverse(head, print);
        	if(SUCCESS == ret)
        	{
        		printf("Traverse success.\n");
        	}
        	else
        	{
        		printf("Traverse failure.\n");
        	}
        	 
        	ret = LinkLength(head);
        	if(FAILURE == ret)
        	{
        		printf("LinkLength failure.\n");
        	}
        	else
        	{
        		printf("Length is %d.\n", ret);
        	}
        
        	ret = LinkEmpty(head);
        	if(TRUE == ret)
        	{
        		printf("LinkList is empty.\n");
        	}
        	else
        	{
        		printf("LinkList isn't empty.\n");
        	}
        
        	int n = 4;
        	Elemtype e;
        	ret = LinkGetelem(head, n, &e);
        	if(SUCCESS == ret)
        	{
        		printf("The %dth is %d.\n", n, e);
        	}
        	else
        	{
        		printf("Get element failure.\n");
        	}
        	
        	ret = LocateElem(head, 9, cmp);
        	if(FAILURE == ret)
        	{
        		printf("9 is not exist.\n");
        	}
        	else
        	{
        		printf("9 is %dth element.\n", ret);
        	}
        	
        	ret = LinkDelete(head, n, &e);
        	if(SUCCESS == ret)
        	{
        		printf("Delete the %dth element %d.\n", n, e);
        	}
        	else
        	{
        		printf("Delete failure.\n");
        	}
        	
        	ret = LinkTraverse(head, print);
        	if(SUCCESS == ret)
        	{
        		printf("Traverse success.\n");
        	}
        	else
        	{
        		printf("Traverse failure.\n");
        	}
        	
        	ret = LinkClear(head);
        	if(SUCCESS == ret)
        	{
        		printf("Clear success.\n");
        	}
        	else
        	{
        		printf("Clear failure.\n");
        	}
        
        	ret = LinkDestory(&head);
        	if(SUCCESS == ret)
        	{
        		printf("Destory success.\n");
        	}
        	else
        	{
        		printf("Destory failure.\n");
        	}
        	
        	return 0;
        }