链表的常用操作实现及测试

功能模块设计

基于C语言实现的顺序表，包含以下功能模块：

• 创建并初始化单链表

• 节点插入

• 节点删除

• 节点查询

• 节点修改

• 链表排序

• 链表的遍历

• 反转链表

• 合并两个有序链表，使新链表仍保持有序

• 删除单链表中的重复元素

完整代码

//带头节点的单链表的常用操作实现及测试
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

//数据结构
//定义元素类型为int
typedef int ElemType;
//线性表的链式存储结构定义
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
} LNode, * LinkList;

//函数声明
LinkList Create_LinkList(int n);                      //1  创建及初始化
void Print_LinkList(LinkList L);                      //2  遍历及输出
int Insert_LinkList(LinkList L, int i, ElemType e);   //3  节点插入
int Delete_LinkList(LinkList L, int i, ElemType* e);  //4  节点删除
int Locate_LinkList(LinkList L, ElemType e);          //5  节点按值查询
int Modify_LinkList(LinkList L, int i, ElemType e);   //6  节点按位置修改
int GetPosition_LinkList(LinkList L, ElemType e);     //7  获取正确的有序插入位置
void DuplicateRemoveLinkList(LinkList L);             //8  链表去重
LinkList ReverseLinkList(LinkList L);                 //9  反转链表
void BubbleSort_LinkList(LinkList L);                 //10 链表排序--冒泡排序
void SelectSort_LinkList(LinkList L);                 //11 链表排序--直接选择排序
LNode* Merge(LNode* head1, LNode* head2);             //12 链表有序归并
LinkList MergeSort_LinkList(LinkList L);              //13 链表排序--自底向上归并排序
int Count_LinkList(LinkList L, ElemType x);           //14 计算单链表L中数据域值为一个指定值x的节点个数
void Test1();                                         //15 测试1 检验单链表的基本操作
void Test2();                                         //16 测试2 检验链表的有序归并
void Test3();                                         //17 测试3 检验链表去重
void menu();                                          //18 主菜单

//主函数
int main(void)
{
	menu();
	return 0;
}

//函数实现
//功能1 单链表的创建及初始化
//尾插法建立带头节点的单链表L，输入n个元素的值
LinkList Create_LinkList(int n)
{
	LNode* p, * q;
	int i = 0;
	LNode* L = (LNode*)malloc(sizeof(LNode));
	//先建立一个带头节点的单链表
	L->next = NULL;
	//q的初始值指向头节点
	q = L;
	printf("输入单链表各元素的值：");
	for (i = 0; i < n; i++)
	{
		//生成新节点
		p = (LNode*)malloc(sizeof(LNode));
		//输入元素值
		scanf("%d", &p->data);
		//将该节点插入到表尾
		p->next = NULL;
		q->next = p;
		q = p;
	}
	return L;
}

//功能2 单链表的遍历及输出
//打印单链表L中各元素的值
void Print_LinkList(LinkList L)
{
	LNode* p;
	p = L->next;
	printf("\n输出单链表中各元素的值：");
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}

//功能3 单链表的节点插入
//在带头节点的单链表L中第i个位置之前插入元素e，成功返回1，失败返回0
int Insert_LinkList(LinkList L, int i, ElemType e)
{
	LNode* p = L;
	int  j = 1;
	//寻找第i个节点
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	//i值不合法，返回0
	if (!p || j > i)  return 0;
	//生成新节点
	LNode* s = (LNode*)malloc(sizeof(LNode));
	//生成新节点
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

//功能4 单链表的节点删除
//在带头节点的单链表L中删除第i个元素，并由e返回其值，成功返回1，失败返回0
int Delete_LinkList(LinkList L, int i, ElemType* e)
{
	int j = 1;
	LNode* p = L;
	//该循环执行i-1次，循环结束p指向第i-1个元素
	//寻找第i个节点，并令p指向其前趋
	while (p->next && j < i)
	{
		p = p->next;
		j++;
	}
	//删除位置不合理
	if (!(p->next) || j > i)  return 0;
	LNode* q = p->next;
	//用e返回被删节点数据域的值
	*e = q->data;
	p->next = q->next;
	//删除并释放节点
	free(q);
	return 1;
}

//功能5 单链表的节点按值查询
//在带头节点的单链表L中按值查询指定元素的位置，查询成功，则返回位置i，否则返回0
int Locate_LinkList(LinkList L, ElemType e)
{
	int i = 0;
	LNode* p = L;
	while (p && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (!p)  return 0;
	else  return i;
}

//功能6 单链表的节点按位置修改
//在带头节点的单链表L中修改第i个位置元素的值
int Modify_LinkList(LinkList L, int i, ElemType e)
{
	LNode* p = L;
	int j = 0;
	while (j++ < i && p)
	{
		p = p->next;
	}
	//i值不合法，修改失败，返回0
	if (i < 1 || p == NULL) return 0;
	p->data = e;
	return 1;
}

//功能7 获取单链表有序插入节点的正确位置
//已知节点数据e，将其插入到有序单链表L中，并使其仍保持有序，获取插入位置
int GetPosition_LinkList(LinkList L, ElemType e)
{
	LNode* p = L;
	int t = 0;
	while (p->next != NULL)
	{
		t++;
		if (e <= (p->next->data)) return t;
		p = p->next;
	}
	//如果e比链表最后一个元素都大，那么返回的位置是t+1
	return t + 1;
}

//功能8 去除单链表L中的重复元素
//将单链表L中的重复元素删除，相同元素保留靠左边的
void DuplicateRemoveLinkList(LinkList L)
{
	LNode* p, * q;
	p = L->next;
	while (p != NULL)
	{
		q = p;
		while (q->next != NULL)
		{
			//删除q这个节点
			if (p->data == q->next->data)
			{
				LNode* tem = q->next;
				//删除q->next这个节点
				q->next = q->next->next;
				free(tem);
			}
			else
			{
				q = q->next;
			}
		}
		p = p->next;
	}
}

//功能9 反转单链表L的各个元素
//反转带头节点的单链表L的各个元素，如 head->1->2->3->NULL 变为 NULL<-1<-2<-3<-head
LinkList ReverseLinkList(LinkList L)
{
	LNode* head = L->next;
	LNode* prev = NULL;
	LNode* curr = head;
	while (curr)
	{
		LNode* next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	L->next = prev;
	return L;
}

//功能10 链表递增排序--冒泡排序
void BubbleSort_LinkList(LinkList L)
{
	if (L == NULL || L->next == NULL) return;
	LNode* p = NULL, * q = NULL;
	for (p = L->next; p->next != NULL; p = p->next)
	{
		int flag = 0;
		for (q = L->next; q->next != NULL; q = q->next)
		{
			if (q->data > q->next->data)
			{
				ElemType temp = q->data;
				q->data = q->next->data;
				q->next->data = temp;
				flag = 1;
			}
		}
		if (flag == 0) return;
	}
}

//功能11 链表递增排序--直接选择排序
void SelectSort_LinkList(LinkList L)
{
	if (L == NULL || L->next == NULL) return;
	LNode* p = NULL, * q = NULL;
	for (p = L->next; p->next != NULL; p = p->next)
	{
		for (q = p->next; q != NULL; q = q->next)
		{
			if (p->data > q->data)
			{
				ElemType temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
		}
	}
}

//功能12 合并两个有序链表，并使新链表仍保持有序
//归并排序中会调用该函数
LNode* Merge(LNode* head1, LNode* head2)
{
	LNode* dummyHead = (LNode*)malloc(sizeof(LNode));
	dummyHead->data = 0;
	LNode* temp = dummyHead, * temp1 = head1, * temp2 = head2;
	while (temp1 != NULL && temp2 != NULL)
	{
		if (temp1->data <= temp2->data)
		{
			temp->next = temp1;
			temp1 = temp1->next;
		}
		else
		{
			temp->next = temp2;
			temp2 = temp2->next;
		}
		temp = temp->next;
	}
	if (temp1 != NULL)
	{
		temp->next = temp1;
	}
	else if (temp2 != NULL)
	{
		temp->next = temp2;
	}
	return dummyHead->next;
}

//功能13 链表递增排序--自底向上归并排序
LinkList MergeSort_LinkList(LinkList L)
{
	//head是首元节点
	LNode* head = L->next;
	if (head == NULL)
	{
		return head;
	}
	int length = 0;
	LNode* node = head;
	//计算表长
	while (node != NULL)
	{
		length++;
		node = node->next;
	}
	LNode* dummyHead = (LNode*)malloc(sizeof(LNode));
	dummyHead->next = head;
	for (int subLength = 1; subLength < length; subLength <<= 1)
	{
		//subLength <<= 1等价于subLength *=2
		LNode* prev = dummyHead, * curr = dummyHead->next;
		while (curr != NULL)
		{
			LNode* head1 = curr;
			for (int i = 1; i < subLength && curr->next != NULL; i++)
			{
				curr = curr->next;
			}
			LNode* head2 = curr->next;
			curr->next = NULL;
			curr = head2;
			for (int i = 1; i < subLength && curr != NULL && curr->next != NULL; i++)
			{
				curr = curr->next;
			}
			LNode* next = NULL;
			if (curr != NULL)
			{
				next = curr->next;
				curr->next = NULL;
			}
			LNode* merged = Merge(head1, head2);
			prev->next = merged;
			while (prev->next != NULL)
			{
				prev = prev->next;
			}
			curr = next;
		}
	}
	return dummyHead;
}

//功能14 计算单链表L中数据域值为一个指定值x的节点个数
int Count_LinkList(LinkList L, ElemType x)
{
	LNode* p;
	int cnt = 0;
	p = L->next;
	while (p)
	{
		if (p->data == x) cnt++;
		p = p->next;
	}
	//返回数据域为指定值x的节点个数
	return cnt;
}

//测试1 检验单链表L的基本操作
//包括：创建及初始化、节点插入、节点删除、节点查询、节点修改、链表排序、链表遍历并输出、反转链表等功能
void Test1()
{
	//定义一个头指针，以指示一个单链表
	LinkList L;
	int n = 0, status = 0, i = 0;
	ElemType e = 0, x = 0;
	printf("请输入单链表的长度：n=");
	scanf("%d", &n);
	//建立一个含n个元素的单链表
	L = Create_LinkList(n);
	//依次输出线性表各元素的值
	Print_LinkList(L);
	printf("\n\n1 测试插入功能\n输入待插入的元素的值：");
	scanf("%d", &e);
	printf("输入待插入的位置：");
	scanf("%d", &i);
	//在第i个元素之前插入e
	status = Insert_LinkList(L, i, e);
	if (status)
	{
		printf("插入成功！");
		Print_LinkList(L);
	}
	else printf("插入失败！");
	printf("\n\n2 测试删除功能\n输入待删除元素的位置：");
	scanf("%d", &i);
	status = Delete_LinkList(L, i, &e);
	printf("待删除元素的值为：%d\n", e);
	if (status)
	{
		printf("删除成功！");
		Print_LinkList(L);
	}
	else printf("删除失败！");
	printf("\n\n3 测试查询功能\n输入待查询的元素的值：");
	scanf("%d", &e);
	int position = Locate_LinkList(L, e);
	if (position) printf("该元素在链表中的位置为：第%d个元素", position);
	else printf("未查询到该元素！");
	printf("\n\n4 测试修改功能\n输入待修改元素的位置：");
	scanf("%d", &i);
	printf("输入修改后的值：");
	scanf("%d", &e);
	status = Modify_LinkList(L, i, e);
	if (status)
	{
		printf("修改成功！");
		Print_LinkList(L);
	}
	else printf("输入的位置不合法，修改失败！");
	printf("\n\n5 测试排序功能");
	L = MergeSort_LinkList(L);
	printf("\n归并排序结束！");
	Print_LinkList(L);
	printf("\n\n6 将元素e插入至有序单链表L中，并使L仍保持有序：\n");
	printf("输入元素e的值：");
	scanf("%d", &e);
	position = GetPosition_LinkList(L, e);
	//在第position个元素之前插入e
	status = Insert_LinkList(L, position, e);
	if (status)
	{
		printf("插入成功！");
		Print_LinkList(L);
	}
	else printf("插入失败！");
	printf("\n\n7 测试反转链表功能\n反转链表后");

	L = ReverseLinkList(L);
	Print_LinkList(L);

	printf("\n\n8 计算单链表L中数据域值为x的节点个数：\n");
	printf("输入x的值：");
	scanf("%d", &x);
	int cnt = Count_LinkList(L, x);
	printf("单链表L中数据域值为%d的个数为：%d个\n\n", x, cnt);
	system("pause");
}

//测试2 检验两个有序单链表的有序归并
//将两个有序单链表合并为一个新的有序单链表
void Test2()
{
	int lenA = 0, lenB = 0;
	//定义一个头指针，以指示单链表LA
	LinkList LA;
	//定义一个头指针，以指示单链表LB
	LinkList LB;
	printf("创建单链表LA，输入其长度：");
	scanf("%d", &lenA);
	//建立一个含lenA个元素的单链表
	LA = Create_LinkList(lenA);
	printf("对单链表LA进行冒泡排序：");
	BubbleSort_LinkList(LA);
	Print_LinkList(LA);
	printf("\n\n创建单链表LB，输入其长度：");
	scanf("%d", &lenB);
	//建立一个含lenB个元素的单链表
	LB = Create_LinkList(lenB);
	printf("对单链表LB进行直接选择排序：");
	SelectSort_LinkList(LB);
	Print_LinkList(LB);
	printf("\n\n合并单链表LA和LB，使新链表仍保持有序！\n合并成功！");
	LinkList LC = (LNode*)malloc(sizeof(LNode));
	LC->next = Merge(LA->next, LB->next);
	Print_LinkList(LC);
	printf("\n\n");
	system("pause");
}

//测试3 检验链表的去重
//删除单链表L中的重复元素
void Test3()
{
	//定义一个头指针，以指示一个单链表
	LinkList L;
	int n = 0;
	printf("请输入单链表的长度：n=");
	scanf("%d", &n);
	//建立一个含n个元素的单链表
	L = Create_LinkList(n);
	Print_LinkList(L);
	DuplicateRemoveLinkList(L);
	printf("\n去重后：");
	Print_LinkList(L);
	printf("\n\n");
	system("pause");
}

void menu()
{
	system("cls");
	int sel = 0;
	printf("1 测试单链表的创建及初始化、节点插入、节点删除、节点查询、节点修改、链表排序、链表遍历并输出、反转链表等功能\n");
	printf("2 合并两个有序链表，使新链表仍保持有序\n");
	printf("3 删除单链表L中的重复元素\n");
	printf("4 退出\n");
	printf("输入你的选择：");
	scanf("%d", &sel);
	while (sel < 1 || sel > 4)
	{
		printf("输入有误，重新输入：");
		scanf("%d", &sel);
	}
	switch (sel)
	{
		case 1:
			Test1();
			menu();
			break;
		case 2:
			Test2();
			menu();
			break;
		case 3:
			Test3();
			menu();
			break;
		case 4:
			exit(0);
		default:
			menu();
			break;
	}
}

运行方法

1. 新建一个cpp文件，命名为”main.cpp”。
2. 将完整代码复制粘贴至”main.cpp”中。
3. 利用Dev C++运行”main.cpp”即可。

运行结果

• 测试1

• 测试2

• 测试3