(C语言)双向链表实现案例(数据结构六)

客官°小女子只卖身不卖艺 2022-09-17 10:23 202阅读 0赞

1.数据类型定义

在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：

//定义数据结构中要用到的一些变量和类型
    #ifndef HEAD_H
    #define HEAD_H
    
    #include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    #define TRUE  1
    #define FALSE 0
    #define OK    1
    #define ERROR  0
    #define INFEASIBLE -1
    #define OVERFLOW   -2    //分配内存出错
    
    typedef int  Status;     //函数返回值类型
    typedef int  ElemType;   //用户定义的数据类型
    
    #endif

2.双链表数据结构实现

typedef struct LNode{
    	ElemType data;
    	struct LNode *pre;
    	struct LNode *next;
    }LNode,*Link;
    
    typedef struct DLink{
    	Link head;
    	Link tail;
    	int  len;
    }DLink,*DLinkList;

3.双链表代码实现

DLinkList.h文件如下:

#ifndef DLINKLIST_H
    #define DLINKLIST_H
    #include "head.h"
    
    
    typedef struct LNode{
    	ElemType data;
    	struct LNode *pre;
    	struct LNode *next;
    }LNode,*Link;
    
    typedef struct DLink{
    	Link head;
    	Link tail;
    	int  len;
    }DLink,*DLinkList;
    
    
    Status MakeNode(Link &p,ElemType e){
    	p=(Link)malloc(sizeof(LNode));
    	if(!p) return OVERFLOW;
    	p->data=e;
    	return OK;
    }
    
    Status FreeNode(Link &p){
    	free(p);
    	p=NULL;
    	return OK;
    }
    Status InitList(DLinkList &L){
    	Link head=(Link)malloc(sizeof(LNode));
    	if(!head) return OVERFLOW;
    	Link tail=(Link)malloc(sizeof(LNode));
    	if(!tail) return OVERFLOW;
    	head->data=-99999;
    	tail->data=9999;
    	head->next=tail;
    	tail->next=head;
    	head->pre=tail;
    	tail->pre=head;
    
    	L=(DLinkList)malloc(sizeof(DLink));
    	if(!L) return OVERFLOW;
    	L->head=head;
    	L->tail=tail;
    	L->len=0;
    	return OK;
    }
    Link getPreLink(DLinkList L,int i){
    	Link p=L->head;
    	for (int n=1;n<i;n++)
    	{
    		p=p->next;
    	}
    	return p;
    }
    Link getNextLink(DLinkList L,int i){
    	Link p=L->head;
    	for (int n=0;n<i;n++)
    	{
    		p=p->next;
    	}
    	return p;
    }
    Status DListInsert(DLinkList &L,int i,ElemType e){
    	if(i<1 ||i>L->len+1) return ERROR;
    	Link p=getPreLink(L,i);
    	Link n=getNextLink(L,i);
    	Link link;
    	MakeNode(link,e);
    	p->next=link;
    	link->next=n;
    	n->pre=link;
    	link->pre=p;
    	L->len++;
    	return OK;
    }
    Status DLinkDelete(DLinkList &L,int i,ElemType &e){
    	if(i<1 ||i>L->len) return ERROR;
    	Link p=getPreLink(L,i);
    	Link n=getNextLink(L,i+1);
    	Link link=p->next;
    	p->next=link->next;
    	n->pre=link->pre;
    	e=link->data;
    	FreeNode(link);
    	link=NULL;
    	return OK;
    }
    Status printDLinkHead(DLinkList L){
    	Link Ln=L->head->next;
    	printf("head->");
    	while(Ln!=L->tail){
    		printf("%d->",Ln->data);
    		Ln=Ln->next;
    	}
    	printf("tail");
    	return true;
    }
    Status printDLinkTail(DLinkList L){
    	Link Ln=L->tail->pre;
    	printf("tail->");
    	while(Ln!=L->head){
    		printf("%d->",Ln->data);
    		Ln=Ln->pre;
    	}
    	printf("head");
    	return true;
    }
    
    
    #endif

4.双链表测试

#include "DLinkList.h"
    
    void main(){
    	DLinkList L;
    	InitList(L);
    	for(int i=1;i<10;i++)
    		DListInsert(L,i,i);
    
    	printf("\n从头遍历：");
    	printDLinkHead(L);
    	printf("\n从尾遍历：");
    	printDLinkTail(L);
    
    	DListInsert(L,5,55);
    
    	printf("\n第5位置插入55后从头遍历：");
    	printDLinkHead(L);
    	printf("\n第5位置插入55后从尾遍历：");
    	printDLinkTail(L);
    
    	ElemType e;
    	DLinkDelete(L,6,e);
    	printf("\n删除第6位置后从头遍历：");
    	printDLinkHead(L);
    	printf("\n删除第6位置后从尾遍历：");
    	printDLinkTail(L);
    }

5.测试结果

从头遍历：head->1->2->3->4->5->6->7->8->9->tail
    从尾遍历：tail->9->8->7->6->5->4->3->2->1->head
    第5位置插入55后从头遍历：head->1->2->3->4->55->5->6->7->8->9->tail
    第5位置插入55后从尾遍历：tail->9->8->7->6->5->55->4->3->2->1->head
    删除第6位置后从头遍历：head->1->2->3->4->55->6->7->8->9->tail
    删除第6位置后从尾遍历：tail->9->8->7->6->55->4->3->2->1->head