单循环链表的实现

单循环链表存储结构

单循环链表结点的存储结构和单链表的存储结构一样，所不同的是：最后一个结点的 next 域指向头结点，而不是“空”。这样，由表尾很容易找到表头。但若链表较长，则由表头找到表尾较费时，因而，单循环链表往往设立尾指针而不是头指针。

单循环链表由结点类型的指针–尾指针LinkList管理链表。

typedef int ElemType;	//元素类型
typedef struct LNode{ElemType data;LNode* next;
}LNode,*LinkList;

注意：
1.单循环链表设立尾指针而不是头指针，L->next就是头指针，这样就回到了带头结点的单链表的操作。但是结束方式有区别，不是以到NULL为结束，而是以到尾指针的后一个结点即头结点为结束。
2.插入、删除时，注意如果操作的是最后一个元素时，要改变尾指针指向。
基本操作

1.初始化
建立头结点，指针域指向头结点，尾指针指向最后一个结点也就是头结点。

void InitList(LinkList& L) {L = (LinkList)malloc(sizeof(LNode));// 产生头结点，并使L指向此头结点if (!L)	exit(-1);	// 存储分配失败L->next = L;	 // 指针域指向头结点
}

2.销毁
释放所有结点，只剩一个空的尾指针。

void DestroyList(LinkList& L) {LinkList p = L->next,q;	 // p指向头结点while (p != L) {	 // 释放尾结点前所有结点q = p->next;free(p);p = q;}free(L);	//释放尾结点L = NULL;	//尾指针指向空
}

3.清空

清空后和初始化时一样，释放头结点外所有结点，只剩尾指针指向一个头结点。所以开始将尾指针指向头结点，然后释放头指针后所有结点。

void ClearList(LinkList& L) {L = L->next;	// L指向头结点LinkList p=L->next,q; // p指向首结点while (p!=L) {	// 没到表尾q = p->next;free(p);p = q;}L->next = L;  // 头结点指针域指向自身
}

4.为空

bool ListEmpty(LinkList L) {if (L->next == L)	 // 空return true;elsereturn false;
}

5.长度
p与i同步。

int ListLength(LinkList L) {LinkList p = L->next;	 // p指向头结点int i = 0; while (p != L) { // 没到表尾p = p->next;++i;}return i;
}

6.获取元素

通过ListLength函数判断i值合不合法，在遍历到i的位置。p与j同步。

bool GetElem(LinkList L, int i,ElemType &e) {if (i<1 || i>ListLength(L))	// i不合法return false;LinkList p = L->next->next;	// p指向首结点int j = 1;while (j < i) {	 // 顺指针向后查找，直到p指向第i个元素p=p->next;++j;}e = p->data;	 // 取第i个元素return true;
}

7.定位元素

返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。p与i同步。

int LocateElem(LinkList L, ElemType e, bool compare(ElemType,ElemType)) {LinkList p = L->next->next;	 // p指向首结点int i = 1;while (p != L->next) {if (compare(p->data, e))	// 满足关系return i;i++;p = p->next;}return 0;
}

8.前驱

若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；否则操作失败，pre_e无定义。从第二个结点开始找前驱，首结点无前驱。

bool PriorElem(LinkList L, ElemType cur_e, ElemType& pre_e) {LinkList p = L->next->next,q; // p指向首结点q = p->next;	//q为第二个结点,p为q的前驱while (q != L->next) // p没到表尾{if (q->data == cur_e){pre_e = p->data;return true;}p = q;q = q->next;}return false; // 操作失败
}

9.后继

若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继；否则操作失败，next_e无定义。遍历到倒数第二个结点，尾结点无后继。

bool NextElem(LinkList L, ElemType cur_e, ElemType& next_e) { LinkList p = L->next->next; // p指向首结点while (p != L) // p没到表尾{if (p->data == cur_e){next_e = p->next->data;return true;}p = p->next;}return false; // 操作失败
}

10.插入

在L的第i个位置之前插入元素e，注意i的取值范围1<=i<=length+1，p与j同步。注意如果在表尾插入需要改变尾指针指向。

bool ListInsert(LinkList& L, int i, ElemType e) { if (i < 1 || i > ListLength(L) + 1) // i不合法return false;LinkList p = L->next;  // p指向头结点int j = 0;while (j < i - 1){	 // 寻找第i-1个结点p = p->next;j++;}LinkList s = (LinkList)malloc(sizeof(LNode)); // 生成新结点s->data = e;		// 插入L中s->next = p->next;p->next = s;if (p == L)		// 注意在表尾插入要改变尾指针指向L = s;return true;
}

11.删除

删除L的第i个元素，并由e返回其值。注意i的范围为1<=i<=length，j与p同步。注意如果要删除尾结点，需要改变尾指针指向。

bool ListDelete(LinkList& L, int i, ElemType& e) {if (i < 1 || i > ListLength(L)) // i不合法return false; LinkList p = L->next; // p指向头结点int j = 0;while (j < i - 1) // 寻找第i-1个结点{p = p->next;j++;}LinkList q = p->next; // q指向待删除结点p->next = q->next;e = q->data;if (L == q) // 注意删除表尾时要修改尾指针指向L = p;free(q); // 释放待删除结点return true;
}

12.遍历

void ListTraverse(LinkList L, void(*vi)(ElemType))
{ LinkList p = L->next->next; // p指向首结点while (p != L->next) // p不指向头结点{vi(p->data);p = p->next;}printf("\n");
}

测试函数

#include 
#include 
#include void visit(ElemType e) {printf("%d ", e);
}bool compare(ElemType e1, ElemType e2) {if (e1 == e2)return true;elsereturn false;
}int main() {ElemType e;LinkList L;InitList(L);	//初始化for (int j = 1; j <= 5; j++)ListInsert(L, 1, j);	//插入printf("在L的表头依次插入1～5后：L=");ListTraverse(L, visit);printf("L是否空：i=%d(1:是 0:否)\n", ListEmpty(L));ClearList(L);printf("清空L后：L=");ListTraverse(L, visit);printf("L是否空：i=%d(1:是 0:否)\n", ListEmpty(L));for (int j = 1; j <= 10; j++)	//插入ListInsert(L, j, j);printf("在L的表尾依次插入1～10后：L=");ListTraverse(L, visit);if (GetElem(L, 5, e))	//获取元素printf("第5个元素的值为%d\n", e);elseprintf("没有第5个元素\n");if (GetElem(L, 13, e))printf("第13个元素的值为%d\n", e);elseprintf("没有第13个元素\n");if (e = LocateElem(L, 8, compare))	//定位元素printf("元素8的位置为%d\n", e);elseprintf("没有值为8的元素\n");if (e = LocateElem(L, 11, compare))printf("元素11的位置为%d\n", e);elseprintf("没有值为11的元素\n");if (PriorElem(L, 10, e))	//前驱printf("元素10的前驱为%d\n", e);elseprintf("元素10无前驱\n");if (NextElem(L, 10, e))printf("元素10的后继为%d\n", e);elseprintf("元素10无后继\n");if (PriorElem(L, 1, e))		//后继printf("元素1的前驱为%d\n", e);elseprintf("元素1无前驱\n");if (NextElem(L, 1, e))printf("元素1的后继为%d\n", e);elseprintf("元素1无后继\n");ListTraverse(L, visit);printf("表长为%d\n", ListLength(L));if (ListDelete(L, 3, e))	//删除printf("删除第3个元素成功，其值为%d\n", e);elseprintf("删除第3个元素失败\n");printf("依次输出L的元素：");ListTraverse(L, visit);DestroyList(L);printf("销毁L后：L=%u\n", L);return 0;
}

测试结果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！