#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态码
typedef int Status;
typedef int ElemType; //顺序表存储元素类型， 考虑到可移植性， 若改变存储类型， 只需修改这一处，比较方便
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList;
Status InitList(DuLinkList *L);
Status ListInsert(DuLinkList L, int i, ElemType e);
int ListLength(DuLinkList L);
void Traverse(DuLinkList L);
DuLinkList GetElemP(DuLinkList L, int i);
void ClearList(DuLinkList L);
Status Destroy(DuLinkList *L);
void vd(ElemType c) ;
void ListTraverse(DuLinkList L,void(*visit)(ElemType)) ;
void Re_Traverse(DuLinkList L);
void main()
{
DuLinkList L;
int i;
InitList(&L);
for(i=1; i<=4; i++)
ListInsert(L,i, i); //在第i个结点之前插入i
printf("正序输出链表：\n");
Traverse(L);
printf("L = %d\n", ListLength(L));
printf("逆序输出链表：\n");
Re_Traverse(L);
Destroy(&L);
}
//初始化一个空的双链表
Status InitList(DuLinkList *L)
{
(*L) = (DuLinkList)malloc(sizeof(DuLNode));
if(L == NULL)
{
printf("内存分配失败!\n");
return FALSE;
}
(*L)->prior = (*L)->next = (*L); //使头结点的两个指针域指向本身
return OK;
}
//在带头结点的双向循环链表L中第i个位置之前插入元素e，
// 1 < i < 表长+1
Status ListInsert(DuLinkList L, int i, ElemType e)
{
DuLinkList s;
DuLinkList p;
if(i < 1 || i > ListLength(L)+1)
return ERROR;
p = GetElemP(L, i - 1); //使p指向第i个元素的位置
if(!p)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode)); //s为存储新插入元素的结点
if(!s)
exit(OVERFLOW);
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
//返回双向链表的长度
int ListLength(DuLinkList L)
{
DuLinkList p;
int i;
p = L->next; //使p指向头结点
i = 0;
while(p != L)
{
i++;
p = p->next;
}
return i;
}
//返回指向第i个结点的指针
DuLinkList GetElemP(DuLinkList L, int i)
{
DuLinkList p;
int j;
p = L;
for(j = 1; j <= i; j++)
p = p->next;
return p;
}
//遍历结点正序输出
void Traverse(DuLinkList L)
{
DuLinkList p;
int i;
i = 0;
p = L->next;
while(p != L)
{
i++;
printf("第%d个结点的数据是：%d\n", i, p->data);
p = p->next;
}
}
//遍历结点逆序输出
void Re_Traverse(DuLinkList L)
{
DuLinkList p;
int i;
i = ListLength(L);
p = L->prior;
while(p != L)
{
printf("第%d个结点的元素是：%d\n", i, p->data);
i--;
p = p->prior;
}
}
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{
//操作结果：由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit()
DuLinkList p = L->next;
while(p!=L)
{
visit(p->data);
p = p->next;
}
printf("\n");
}
void vd(ElemType c)
{
printf("%d ",c);
}
//将双向链表L重置为空表
void ClearList(DuLinkList L)
{
DuLinkList p, q;
p = L->next;
while(p != L)
{
q = p->next;
free(p);
p = q;
}
L->prior = L->next = L; //使头结点的两个指针域都指向自己
}
//销毁双向链表L
Status Destroy(DuLinkList *L)
{
DuLinkList p, q;
p = (*L)->next;
while(p != (*L))
{
q = p->next;
free(p);
p = q;
}
free((*L));
(*L) = NULL;
return OK;
}
