[数据结构与算法]实现双链表的各基本算法

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> 

typedef char ElemType;
typedef struct DNode
{
	ElemType data;
	struct DNode *prior;
	struct DNode *next;
}DLinkNode;


int CreateList(DLinkNode *L, ElemType a[], int n )
{
	DLinkNode * s , * r;
	L = (DLinkNode *)malloc(sizeof(DLinkNode));    //创建头结点
	r = L;
	for(int i = 0; i < n; i++)
	{
		s = (DLinkNode *)malloc(sizeof(DLinkNode));
		s -> data = a[i];
		r -> next = s;
		s -> prior = r;
		r = s; 
	} 
	r -> next = NULL;
	
}  //尾插法创建双链表

int InitList(DLinkNode *L)
{
	L -> next = NULL;
	L -> prior = NULL;
} 
	//初始化
	
int ListInsert(DLinkNode *L, int i, ElemType e)
{
	DLinkNode *p = L, *s;
	int j = 0;
	while(j < i - 1)
	{
		j++;
		p = p -> next;
	}
	s = (DLinkNode *)malloc(sizeof(DLinkNode));
	s -> data = e;
	s -> next = p -> next;
	if (p -> next != NULL)
		p -> next -> prior = s;
	s -> prior = p;
	p -> next = s;
}
	//在链表的第i个位置插入元素e 
	
int DispList(DLinkNode *L)
{
	DLinkNode *p = L -> next;
	while (p != NULL) 
	{
		printf("%c ",p -> data);
		p = p -> next;
	}
	printf("\n\n");
}
	 //打印链表
	 
	
int ListLength(DLinkNode *L)
{
	int n = 0;
	DLinkNode *p = L;
	while(p -> next != NULL)
	{
		n++;
		p = p -> next;
	}
	printf("此表的长度为：%d\n\n",n);
} 
//输出表的长度


int ListEmpty(DLinkNode *L) 
	  {
	  	if(L -> next == NULL)
	  		printf("此表为空表\n\n");
	  	else
	  		printf("此表不是空表\n\n");	
	  }
	  
	  
int GetElem(DLinkNode *L, int i)
{
	DLinkNode *p = L;
	for(int j = 0 ; j < i ; j++)
		p = p -> next;
	ElemType e = p -> data;
	printf("第%d个元素是：%c\n\n",i,e );
} 
	 //输出第i个元素 
	 
int LocateElem(DLinkNode *L, ElemType e)
{
	DLinkNode *p = L -> next;
	int j = 1; 
	while(p -> data != e)
	{
		j++;
		p = p -> next;
	}
	printf("元素%c的序号是：%d\n\n", e, j);
}   //输出元素e的位置 


int ListDelete(DLinkNode *L , int i)
{
	DLinkNode *p = L , *s;
	int j = 0;
	while(j < i-1)
	{
		p = p -> next;
		j++;
	}	
	s = p -> next;
	p -> next = s -> next;
	s -> next -> prior = p;
	free(s); 
		 
}  //删除第i个元素 

int DestroyList(DLinkNode *L)
{
	DLinkNode *p = L, *q = L -> next;
	while(q != NULL)
		{
			free(p);
			p = q;
			q = p -> next;
		}
} 
	  
int main( ) {
	
	DLinkNode L; //建表 
	
	InitList(&L); //初始化 
	
	printf("依次采用尾插法插入a、b、c、d、e元素\n");
	ListInsert(&L , 1 , 'a');
	ListInsert(&L , 2 , 'b');
	ListInsert(&L , 3 , 'c');
	ListInsert(&L , 4 , 'd');
	ListInsert(&L , 5 , 'e');
	
	DispList(&L);  //打印链表 
	
	ListLength(&L);  //输出表的长度
	
	ListEmpty(&L);  //判断此表是不是空表 
	
	GetElem(&L, 3);  //打印表的第i个元素 
	
	LocateElem(&L, 'a');   //打印元素e的位置 
	
	ListInsert(&L , 4 , 'f');
	DispList(&L);  
	
	ListDelete(&L , 3);   //删除第i个元素 
	DispList(&L); 
	
	DestroyList(&L);
	return 0;
}

在单链表的基础上添加前驱节点prior使得链表成为一个双链表

李春葆数据结构第二章实验操作