双向链表（C实现）

布满荆棘的人生 2022-08-14 04:54 218阅读 0赞

list.h

#ifndef _LIST_H
    #define _LIST_H
    
    typedef struct _node
    {
    	void *data;
    	struct _node *piror;
    	struct _node *next;
    }NODE;
    
    typedef struct
    {
    	NODE *head;
    	NODE *last;
    	int length;
    }LIST;
    
    LIST *InitList();
    
    int InsertNode(LIST *l,void *data,int size);
    
    int DeleteNode(LIST *l,int n);
    void PrintList(LIST *l,int page,int perpage,void(*printNode)(void *));
    void ClearList(LIST *l);
    void DestroyList(LIST **l);
    
    #endif

list.c

#include "list.h"
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h> 
    LIST *InitList()
    {
    	LIST *l=(LIST *)malloc(sizeof(LIST));
    	if(l==NULL) exit(0);
    	l->head=(NODE *)malloc(sizeof(NODE));
    	if(l->head==NULL) exit(0);
    	memset(l->head,0,sizeof(NODE));//all member set to 0
    	l->last=(NODE *)malloc(sizeof(NODE));
    	if(l->last==NULL) exit(0);
    	memset(l->last,0,sizeof(NODE));
    
    //	l->head->piror=NULL;
    	l->head->next=l->last;
    	l->last->piror=l->head;
    	l->length=0;
    	return l;
    }
    //有效数据的尾部插入
    int InsertNode(LIST *l,void *data,int size)
    {
    	NODE *n=NULL;
    	if(l==NULL || data==NULL ||size==0)
    		return 0;
    	n=(NODE *)malloc(sizeof(NODE));
    	if(n==NULL) return 0;
    	n->data=malloc(size);
    	if(n->data==NULL)
    	{
    		free(n);
    		return 0;
    	}
    	memcpy(n->data,data,size);
    	n->next=l->last;
    	n->piror=l->last->piror;
    
    	l->last->piror->next=n;
    	l->last->piror=n;
    	l->length++;
    	return 1;
    }
    
    int DeleteNode(LIST *l,int n)
    {
    	NODE *p=NULL;
    	int i=0;
    	if(l==NULL || n<1 || n>l->length)
    		return 0;
    	p=l->head->next;
        while(i<l->length)
    	{
    		i++;
    		if(i==n)
    			break;
    		p=p->next;
    	}//end while--p points to the node to be deleted
    
    	p->piror->next=p->next;//把删除的结点从链表中断开
    	p->next->piror=p->piror;//重新建立两个连接即可
    	free(p->data);
    	free(p);
    	l->length--;
    	return 1;
    }
    //实现分页打印
    //传递过来的函数指针告诉我们怎么打印数据
    void PrintList(LIST *l,int page,int perpage,void(*printNode)(void *))
    {
    	int start,end,i;
    	NODE *p=NULL;
        if(l==NULL || printNode==NULL)
    		return;
    	start=(page-1)*perpage+1;
    	end=page*perpage;
    	p=l->head->next;
    	i=0;
    	while(i<l->length && p->next!=NULL)
    	{
    		i++;
    		if(i==start) break;
    		p=p->next;
    	}
    	for(;i<=end&&p->next!=NULL;i++)
    	{
    		printNode(p->data);
    		p=p->next;
    	}
    }
    
    void ClearList(LIST *l)
    {
    	if(l==NULL)
    		return;
    	
    	while(l->length)
    	{
    		DeleteNode(l,1);
    	}
    }
    
    void DestroyList(LIST **l)
    {
    	LIST *p=*l;
    	if(p==NULL)
    		return;
    	ClearList(p);
    	free(p->head);
    	free(p->last);
    	free(p);
    	*l=NULL;
    }

main.c

#include <stdio.h>
    #include "list.h"
    
    double d[5]={10.23,34.23,54.65,12.12,13.13};
    //结点数据是无类型的，应用层这边知道是什么类型的，所以传递一个函数指针
    void PrintData(void *data)
    {
    	double *d=(double *)data;
    	printf("d=%lf\n",*d);
    }
    
    void main()
    {
    	int i;
    	LIST *list =InitList();
    	for(i=0;i<5;i++)
    		InsertNode(list,&d[i],sizeof(d[i]));
        
    	PrintList(list,2,3,PrintData);
    	DestroyList(&list);
    	if(list==NULL)
    		printf("list is NULL\n");
    	else
    		printf("list is not NULL\n");
    
    }

VC6运行效果图

![20151122015300545][]

[20151122015300545]: /images/20220731/0a7bb394454a44c5ac5e565f363c987f.png