《数据结构》中双向循环链表的实现
Status.h
|
/******************************************************************
程序中要用到的 函数结果状态代码
******************************************************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; | include.h
|
/******************************************************************
程序中要用的头文件
******************************************************************/
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
/******************************************************************
自定义头文件
******************************************************************/
#include "status.h"
| dulist.h
|
#include "status.h"
typedef int ElemType;
//--------------双向链表的结构体-------------------------
struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode;
typedef struct DuLNode *DuLinkList;
//--------------双向链表的结构体-------------------------
/***********************************************************
* 函数声明 *
************************************************************/
Status InitList(DuLinkList *L);//产生空的双向循环链表L
Status DestroyList(DuLinkList *L);//销毁双向循环链表L
Status ListEmpty(DuLinkList L);//判断L是否为空，为空返回TRUE,否则返回FALSE
int ListLength(DuLinkList L);//返回L中元素的个数
Status ListInsert(DuLinkList *L, int i,ElemType e);//第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
Status ListDelete(DuLinkList *L,int i,ElemType *e);//删除第i个元素并用e返回
Status ClearList(DuLinkList *L);//将L置为空表
Status GetElem(DuLinkList L,int i,ElemType *e);//获取第i个元素 并用e返回
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType));//返回第一个与e满足compare函数的元素的位序
Status PriorElem(DuLinkList L,ElemType cur_e , ElemType *pre_e);//获取前驱函数 用pre_e，返回cur_e的前驱 成功返回TRUE
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e);//获取后继函数，用next_e返回cur_e的后继元素
void ListTraverse(DuLinkList L,void(*visit)(ElemType));//正序对L中的每个元素调用visit函数
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType));//逆序对L中的每个元素调用visit函数
| dulist.c
|
/******************************************************************************
在dulist.h中声明函数的实现
线性表单链表的基本操作有14个
******************************************************************************/
#include "include.h"
#include "dulist.h"
//-----------------------初始化函数------------------------------------------
Status InitList(DuLinkList *L)
{//产生空的双向循环链表L
(*L)=(DuLinkList)malloc(sizeof(DuLNode));
if(*L)
{
(*L)->next=(*L)->prior=(*L);
return OK;
}
else
return OVERFLOW;
}
//-----------------------销毁函数--------------------------------------------
Status DestroyList(DuLinkList *L)
{//操作结果：销毁双向循环链表L
DuLinkList q,p=(*L)->next;//p指向第一个结点
while(p!=*L)
{
q=p->next;
free(p);//释放p
p=q;
}
free(*L);
*L=NULL;
return OK;
}
//------------------------判空函数--------------------------------------------
Status ListEmpty(DuLinkList L)
{//初始条件：线性表L存在。操作结果：若L为空表则返回TRUE否则返回FALSE
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
//-------------------------计算L中元素个数------------------------------------
int ListLength(DuLinkList L)
{//初始条件：L存在。操作结果：返回L中数据元素的个数
int i=0;
DuLinkList p=L->next;//p指向第一个结点
while(p!=L) //没到表头
{
i++;
p=p->next;
}
return i;
}
//-------------------------返回第i个元素的位置指针-----------------------------
DuLinkList GetElemP(DuLinkList L,int i)
{//在双向链表L中返回第i个元素的位置指针
int j;
DuLinkList p=L;//p指向头结点
for(j=1;j<=i;j++)
p=p->next;
return p;
}
//--------------------------插入函数-------------------------------------------
Status ListInsert(DuLinkList *L, int i,ElemType e)
{//在带头结点的双向循环链表中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
DuLinkList p,s;
if(i<1||i>ListLength(*L)+1) //i值不合法
return ERROR;
p=GetElemP(*L,i-1);//将第i-1个元素的指针位置赋给p
if(!p) //p=NULL,既第i-1个元素不存在
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s) //分配失败
return OVERFLOW;
s->data=e;
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
//-----------------------------删除函数---------------------------------------
Status ListDelete(DuLinkList *L,int i,ElemType *e)
{//删除带头结点的双想循环链表L第i个元素，i的合法值为1≤i≤表长,并用e返回
DuLinkList p;
if(i<1||i>ListLength(*L))//i值不合法
return ERROR;
p=GetElemP(*L,i);//在L中确定第i个元素的位置指针p
if(!p) //p=NULL 即第i个元素不存在
return ERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
//-----------------------------置空函数---------------------------------------
Status ClearList(DuLinkList *L)
{//初始条件：L存在 。操作结果：将L置空
DuLinkList q,p=(*L)->next;//平指向第一个结点
while(p!=*L) // 没到表头
{
q=p->next;
free(p);
p=q;
}
(*L)->next=(*L)->prior=*L;//头结点的指针域均指向自身
return OK;
}
//---------------------- 获取元素函数-----------------------------------------
Status GetElem(DuLinkList L,int i,ElemType *e)
{//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=1;
DuLinkList p=L->next;//p指向第一个结点
while(p!=L&&j<i) //顺指针向后查找知道p指向第i个元素或p指向头结点
{
p=p->next;
j++;
}
if(p==L||j>i) //第i个元素不存在
return ERROR;
*e=p->data; //取第i个元素
return OK;
}
//----------------------------LocateElem函数--------------------------------------------
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始条件：L已存在，compare()是数据元素判定函数 满足compare返回TRUE,否则返回FALSE
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
int i=0;
DuLinkList p=L->next;//p指向第一个元素
while(p!=L) //遍历L知道p指向头结点
{
i++;
if(compare(p->data,e)) //找到和条件的元素
return i;
p=p->next;
}
return 0;
}
//---------------------------获取前驱函数----------------------------------------------
Status PriorElem(DuLinkList L,ElemType cur_e , ElemType *pre_e)
{// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 前驱，否则操作失败，pre_e无定义
DuLinkList p=L->next->next; // p指向第2个元素
while(p!=L) // p没到表头
{
if(p->data==cur_e)
{
*pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
//-------------------------获取后继函数------------------------------------------------
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{ // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 否则操作失败，next_e无定义
DuLinkList p=L->next->next; // p指向第2个元素
while(p!=L) // p没到表头
{
if(p->prior->data==cur_e)
{
*next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
//-----------------------------正序访问函数---------------------------------------------
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ // 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit()
DuLinkList p=L->next; // p指向头结点
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
//------------------------------逆序访问函数--------------------------------------------
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{ // 由双链循环线性表L的头结点出发,逆序对每个数据元素调用函数visit()。另加
DuLinkList p=L->prior; // p指向尾结点
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}
| main.c
|
#include "include.h"
#include "dulist.h"
Status compare(ElemType c1,ElemType c2)
{// 判断两个数是否相等 相等返回TRUE,否则返回FALSE
if(c1==c2)
return TRUE;
else
return FALSE;
}
void visit(ElemType c)
{//把C输出
printf("%d ",c);
}
void main()
{
DuLinkList L,p;
Status result; //返回状态 OK TRUE FALSE
int i;
ElemType e,pre_e,next_e;
//--------------------------初始化函数测试-------------------------------
//printf("初始化L前，L=%u\n",L);
result=InitList(&L);
if(result==OK)
printf("初始化L成功，初始化后L=%u\n",L);
//-----------------------------------------------------------------------
//---------------------------判空函数测试--------------------------------
result=ListEmpty(L);
if(result==TRUE)
printf("线性表L为空\n");
else
printf("线性表L不为空\n");
//-----------------------------------------------------------------------
//---------------------------计算元素个数测试----------------------------
i=ListLength(L);
printf("L中的元素个数为：%d\n",i);
//-----------------------------------------------------------------------
//---------------------------插入函数测试--------------------------------
printf("依次插入 1 3 5 7\n");
result=ListInsert(&L,1,1);
result=ListInsert(&L,2,3);
result=ListInsert(&L,3,5);
result=ListInsert(&L,4,7);
i=ListLength(L);
printf("插入元素后L中的元素个数为：%d\n",i);
printf("L中的元素值为：\n");
p=L->next;
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
//-----------------------------------------------------------------------
//---------------------------删除L中元素函数测试-------------------------
printf("删除L中的第3个元素并用e返回\n");
result=ListDelete(&L,3,&e);
//result=ListDelete(&L,6,&e);
if(result==OK)
printf("删除成功，删除的第3个元素值为：%d\n",e);
else
printf("删除失败，不存在此元素\n");
printf("删除后L中的元素值为：\n");
p=L->next;
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
//-----------------------------------------------------------------------
//---------------------------获取元素函数测试----------------------------
printf("获取第3个元素的值并用e返回\n");
result=GetElem(L,3,&e);
if(result==OK)
printf("第3个元素的值为：%d\n",e);
//-----------------------------------------------------------------------
//---------------------------判定函数测试--------------------------------
printf("查看L中是否有与3相等的元素\n");
i=LocateElem(L,3,compare);
if(i)
printf("第%d个元素的值与3相等\n",i);
else
printf("没有与3相等的元素\n");
printf("查看L中是否有与6相等的元素\n");
i=LocateElem(L,6,compare);
if(i)
printf("第%d个元素的值与3相等\n",i);
else
printf("没有与6相等的元素\n");
//-----------------------------------------------------------------------
//---------------------------获取前驱函数测试----------------------------
result=PriorElem(L,3,&pre_e);
if(result==TRUE)
printf("在L中3的前驱为%d\n",pre_e);
else
printf("在L中3没有前驱元素\n");
result=PriorElem(L,1,&pre_e);
if(result==TRUE)
printf("在L中1的前驱为%d\n",pre_e);
else
printf("在L中1没有前驱元素\n");
//-----------------------------------------------------------------------
//---------------------------获取后继函数测试----------------------------
result=NextElem(L,3,&next_e);
if(result==TRUE)
printf("在L中3的后继为%d\n",next_e);
else
printf("在L中3没有后继元素\n");
result=NextElem(L,7,&next_e);
if(result==TRUE)
printf("在L中7的后继为%d\n",next_e);
else
printf("在L中7没有后继元素\n");
//-----------------------------------------------------------------------
//---------------------------Traverse 函数测试---------------------------
printf("正序输出L中的元素\n");
ListTraverse(L,visit);
printf("********************************\n");
printf("逆序输出L中的元素\n");
ListTraverseBack(L,visit);
//-----------------------------------------------------------------------
//---------------------------置空函数测试--------------------------------
printf("将L置空\n");
result=ClearList(&L);
if(result==OK)
printf("置空操作成功\n");
printf("判断L是否为空\n");
result=ListEmpty(L);
if(result=TRUE)
printf("置空后L为空的\n");
//-----------------------------------------------------------------------
//---------------------------销毁函数测试--------------------------------
printf("销毁L...\n");
result=0;
result=DestroyList(&L);
if(result==OK)
printf("销毁L成功，销毁后L=%u\n",L);
else
printf("销毁失败\n");
//-----------------------------------------------------------------------
} | | | |
