《数据结构》-双向链表的表示及实现
#include
#include
#include
#include // 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1typedef int Status;
// Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean;
// Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;
// bo2-5.cpp 带头结点的双向循环链表(存储结构由c2-4.h定义)的基本操作(14个),包括算法2.18,2.19
void InitList(DuLinkList *L)
{ // 产生空的双向循环链表L
*L = (DuLinkList)malloc(sizeof(DuLNode));
if (*L)
(*L)->next = (*L)->prior = *L;
else
exit(-1);
}void DestroyList(DuLinkList *L)
{// 操作结果：销毁双向循环链表L
DuLinkList q, p = (*L)->next;
// p指向第一个结点
while (p != *L)// p没到表头
{
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
}void ClearList(DuLinkList L)// 不改变L
{// 初始条件：L已存在。操作结果：将L重置为空表
DuLinkList q, p = L->next;
// p指向第一个结点
while (p != L)// p没到表头
{
q = p->next;
free(p);
p = q;
}
L->next = L->prior = L;
// 头结点的两个指针域均指向自身
}Status ListEmpty(DuLinkList L)
{ // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if (L->next == L && L->prior == L)
return TRUE;
else
return FALSE;
}int ListLength(DuLinkList L)
{ // 初始条件：L已存在。操作结果：返回L中数据元素个数
int i = 0;
DuLinkList p = L->next;
// p指向第一个结点
while (p != L)// p没到表头
{
i++;
p = p->next;
}
return i;
}Status GetElem(DuLinkList L, int i, ElemType *e)
{// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j = 1;
// j为计数器
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;
}int LocateElem(DuLinkList L, ElemType e, Status (*compare)(ElemType, ElemType))
{ // 初始条件：L已存在，compare()是数据元素判定函数
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
//若这样的数据元素不存在，则返回值为0
int i = 0;
DuLinkList p = L->next;
// p指向第1个元素
while (p != L)
{
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 =https://www.it610.com/article/= 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 =https://www.it610.com/article/= cur_e)
{
*next_e = p->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}DuLinkList GetElemP(DuLinkList L, int i) // 另加
{// 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，
// 返回NULL(算法2.18、2.19要调用的函数)
int j;
DuLinkList p = L;
// p指向头结点
if (i < 0 || i > ListLength(L)) // i值不合法
return NULL;
for (j = 1;
j <= i;
j++)
p = p->next;
return p;
}Status ListInsert(DuLinkList L, int i, ElemType e)
{ // 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
// 改进算法2.18，否则无法在第表长+1个结点之前插入元素
DuLinkList p, s;
if (i < 1 || i > ListLength(L) + 1) // i值不合法
return ERROR;
p = GetElemP(L, i - 1);
// 在L中确定第i个元素前驱的位置指针p
if (!p)// p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s)
return -1;
s->data = https://www.it610.com/article/e;
s->prior = p;
// 在第i-1个元素之后插入
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}Status ListDelete(DuLinkList L, int i, ElemType *e) // 算法2.19
{// 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
DuLinkList p;
if (i < 1) // 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;
}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");
}
void print(ElemType c)
{
printf("%d ", c);
}
Status equal(ElemType c1, ElemType c2)
{ // 判断是否相等的函数
if (c1 == c2)
return TRUE;
else
return FALSE;
}
void main(int argc, char *argv[])
{
DuLinkList L;
int i, n;
Status j;
ElemType e;
InitList(&L);
for (i = 1;
i <= 5;
i++)
ListInsert(L, i, i);
// 在第i个结点之前插入i
printf("ListTraverse list is:");
ListTraverse(L, print);
// 正序输出
printf("ListTraverseBack list is:");
ListTraverseBack(L, print);
// 逆序输出
n = 2;
ListDelete(L, n, &e);
// 删除并释放第n个结点
printf("delete %d node, value is %d, other node is:", n, e);
ListTraverse(L, print);
// 正序输出
printf("list value num is:%d\n", ListLength(L));
printf("list is empty:%d(1:yes 0:no)\n", ListEmpty(L));
ClearList(L);
// 清空链表
printf("after clear, list is empty:%d(1:yes 0:no)\n", ListEmpty(L));
for (i = 1;
i <= 5;
i++)
ListInsert(L, i, i);
// 重新插入5个结点
ListTraverse(L, print);
// 正序输出
n = 3;
j = GetElem(L, n, &e);
// 将链表的第n个元素赋值给e
if (j)
printf("list %d value%d\n", n, e);
else
printf("no %d value\n", n);
n = 4;
i = LocateElem(L, n, equal);
if (i)
printf("equal %d num is %d\n", n, i);
else
printf("no equal %d value\n", n);
j = PriorElem(L, n, &e);
if (j)
printf("%d pri is %d\n", n, e);
else
printf("no %d pri \n", n);
j = NextElem(L, n, &e);
if (j)
printf("%d next is %d\n", n, e);
else
printf("no %d next\n", n);
DestroyList(&L);
while (1)
;
}
/* output
ListTraverse list is:1 2 3 4 5
ListTraverseBack list is:5 4 3 2 1
delete 2 node, value is 2, other node is:1 3 4 5
list value num is:4
list is empty:0(1:yes 0:no)
after clear, list is empty:1(1:yes 0:no)
1 2 3 4 5
list 3 value3
equal 4 num is 4
4 pri is 3
4 next is 5
*/ 【《数据结构》-双向链表的表示及实现】
推荐阅读
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 《跨界歌手》:亲情永远比爱情更有泪点
- 诗歌:|诗歌: 《让我们举起世界杯，干了！》
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- 人间词话的智慧
- 《一代诗人》37期，生活，江南j，拨动心潭的一泓秋水
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术
- 书评——《小行星》