欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的实现

程序员文章站 2022-05-06 12:38:48
...

单链表存储结构
单链表的实现
带头结点的单链表,方面对链表统一的操作;不带头结点的链表首结点和非首结点的处理要区分。
单链表通过一个指向头结点或首结点的结点指针LinkList来管理链表。

typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

基本操作

1.初始化
单链表的实现

void InitList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode)); // 产生头结点,L指向此头结点
	if (!L) exit(-1);
	L->next = NULL;		// 指针域为空,空链表
}

2.销毁
单链表的实现
释放包括头结点在内的所有结点,只剩一个空指针LinkList。

void DestroyList(LinkList& L) {
	LinkList p=L;
	while (L) {
		p=L->next;
		free(L);
		L = p;
	}
}

3.清空
单链表的实现
释放头结点外所有结点,保留头结点。

void ClearList(LinkList& L) {
	LinkList p = L->next;
	while (p) {
		LinkList q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;
}

4.为空
头结点后为空。

bool ListEmpty(LinkList L) {
	if (L->next)
		return false;
	else
		return true;
}

5.长度

int ListLength(LinkList L) {
	int n = 0;
	LinkList p = L->next;	//首结点
	while (p) {
		++n;
		p = p->next;
	}
	return n;
}

6.获取元素

当第i个元素存在时,其值赋给e;

bool GetElem(LinkList L, int i, ElemType& e) 
{ 
	int j = 1;  // j为计数器
	LinkList p = L->next;	 // p指向首结点
	while (p && j < i)	// 向后查找,直到p指向第i个元素或p为空
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)	 // 第i个元素不存在
		return false;
	e = p->data;	 // 取第i个元素
	return true;
}

7.定位元素

compare()是数据元素判定函数(满足为1,否则为0),返回L中第1个与e满足关系compare()的数据元素的位序;若这样的数据元素不存在,则返回值为0

int LocateElem(LinkList L, ElemType e, bool(*compare)(ElemType, ElemType))
{ 
	int i = 0;
	LinkList p = L->next;	//首结点
	while (p)
	{
		i++;
		if (compare(p->data, e)) // 找到这样的数据元素
			return i;
		p = p->next;
	}
	return 0;
}

8.前驱

若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,返回true;否则操作失败,pre_e无定义,返回false

bool PriorElem(LinkList L, ElemType cur_e, ElemType& pre_e)
{ 
	LinkList q, p = L->next;	 // p指向首结点
	while (p->next)	// p所指结点有后继
	{
		q = p->next;	// q为p的后继
		if (q->data == cur_e)	//如果q的元素满足则返回前驱元素
		{
			pre_e = p->data;
			return true;
		}
		p = q;	// p向后移
	}
	return false;
}

9.后继

若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,返回true;否则操作失败,next_e无定义,返回false

bool NextElem(LinkList L, ElemType cur_e, ElemType& next_e)
{ 
	LinkList p = L->next;	// p指向首结点
	while (p->next)	 // p所指结点有后继
	{
		if (p->data == cur_e)	//p元素满足则返回后继元素
		{
			next_e = p->next->data;
			return true;
		}
		p = p->next;
	}
	return false;
}

10.插入

第i个位置之前插入元素e

bool ListInsert(LinkList& L, int i, ElemType val) {
	LinkList p = L;
	int j = 0;
	while (j < i-1 && p) {	// 寻找第i-1个结点
		++j;
		p = p->next;
	}
	if (!p || j > i-1)	// i小于1或者大于表长
		return false;
	LinkList tmp = (LinkList)malloc(sizeof(LNode));	 // 生成新结点
	if (!tmp)	exit(-1);
	tmp->data = val;
	tmp->next = p->next;
	p->next = tmp;
	return true;
}

11.删除

删除第i个元素,并由e返回其值

bool ListDelete(LinkList L, int i, ElemType& val) {
	LinkList p = L;
	int j = 0;
	while (p->next && j < i-1) {	  // 寻找第i个结点,并令p指向其前驱
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)	return false;	 // 删除位置不合理
	LinkList tmp = p->next;		// 删除并释放结点
	val = tmp->data;
	p->next = tmp->next;
	free(tmp);
	return true;
}

12.遍历

void ListTraverse(LinkList L, void(*vi)(ElemType)) {
	LinkList p = L->next;
	while (p) {
		vi(p->data);
		p = p->next;
	}
	printf("\n");
}

测试函数

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);
	else
		printf("没有第5个元素\n");
	if (GetElem(L, 13, e))
		printf("第13个元素的值为%d\n", e);
	else
		printf("没有第13个元素\n");


	if (e = LocateElem(L, 8, compare))	//定位元素
		printf("元素8的位置为%d\n", e);
	else
		printf("没有值为8的元素\n");
	if (e = LocateElem(L, 11, compare))
		printf("元素11的位置为%d\n", e);
	else
		printf("没有值为11的元素\n");
	
	if (PriorElem(L, 10, e))	//前驱
		printf("元素10的前驱为%d\n", e);
	else
		printf("元素10无前驱\n");
	if (NextElem(L, 10, e))
		printf("元素10的后继为%d\n", e);
	else
		printf("元素10无后继\n");

	if (PriorElem(L, 1, e))		//后继
		printf("元素1的前驱为%d\n", e);
	else
		printf("元素1无前驱\n");
	if (NextElem(L, 1, e))
		printf("元素1的后继为%d\n", e);
	else
		printf("元素1无后继\n");

	ListTraverse(L, visit);
	printf("表长为%d\n", ListLength(L));
	if (ListDelete(L, 3, e))	//删除
		printf("删除第3个元素成功,其值为%d\n", e);
	else
		printf("删除第3个元素失败\n");

	printf("依次输出L的元素:");
	ListTraverse(L, visit);
	DestroyList(L);
	printf("销毁L后:L=%u\n", L);
	return 0;
}

测试结果
单链表的实现