[数据结构与算法]C++实现单链表

list.h

#pragma once
#define OK 		1
#define ERROR 	0
#define TRUE 	1
#define FALSE 	0

typedef int Status;
typedef int ElemType;

typedef struct LNode
{
	ElemType data;				//数据域
	struct LNode *next;			//指针域
}LNode, *LinkList;				//结点和指向结点的指针

Status InitList(LinkList &L);								//链表初始化
Status CreatList(LinkList &L);								//尾插法创建链表，包含初始化功能
Status ListInsert(LinkList &L, int i, ElemType e);			//单链表的按位置插入
LNode* GetElem(LinkList L, int i);							//查找链表指定位置节点，返回的是结点
Status InsertNextNode(LNode *p, ElemType e);				//结点p之后插入元素e
void ListTraverse(const LinkList &L);						//链表的遍历
Status LocateElem(const LinkList &L, int &i, ElemType e);	//查找指定元素的位置
Status ListDelete(LinkList &L, int i, ElemType &e);			//指定位置删除元素
Status DeleteNextNode(LNode *p, ElemType &e);				//结点p之后插入元素e
int Getlength(const LinkList &L);							//获取单链表中的元素数量
void Clearlist(LinkList &L);								//单链表的删除

oper_func.cpp

#include <iostream>
#include"list.h"

Status InitList(LinkList &L)
{
	//构建空的单链表，作为单链表的头结点，数据域为空
	L = new LNode;
	L->next = NULL;
	if (L == NULL)						//内存不够
		return ERROR;
	else
		return OK;
}

Status CreatList(LinkList &L)
{
	using std::cin;
	using std::cout;
	using std::endl;
	if (InitList(L))					//首先初始化链表
	{
		LNode *p, *r = L;				//其中p为新建的结点，用来存储数据，而r为尾指针，始终指向尾部节点
		int num;
		cout << "输入你需要创建的单链表的个数：";
		cin >> num;
		for (int i = 0; i < num; i++)	//尾插法建立单链表
		{
			p = new LNode;				//创建新结点
			cout << "输入第" << i + 1 << "个元素：";
			cin >> p->data;				//输入数据
			p->next = NULL;
			r->next = p;				//将创建的结点放在最后一个结点的后面
			r = p;						//尾指针指向新的尾结点
		}
		return OK;
	}
	else
	{
		cout << "内存不够，单链表创建失败！" << endl;
		return ERROR;
	}
}

Status ListInsert(LinkList &L, int i, ElemType e)
{
	if (i < 1)
		return FALSE;
	//寻找第i-1个结点
	LNode *p = GetElem(L,i-1);
	//直接在i-1结点的后面插入元素即可
	return InsertNextNode(p,e);
}

LNode* GetElem(LinkList L, int i)
{
	LNode *p = L;
	int j = 0;				//表示p指向的当前结点的位置，此时为头结点
	while (p != NULL && j < i)
	{
		p = p->next;		//指向下一个结点
		j++;
	}
	return p;
}

Status InsertNextNode(LNode *p, ElemType e)
{
	if (p == NULL)				//当越界时，p指向NULL
		return FALSE;
	LNode *s = new LNode;		//创建新结点
	if(s == NULL)
		return FALSE;			//内存分配失败
	s->next = p->next;
	s->data = e;
	p->next = s;
	return OK;
}

void ListTraverse(const LinkList &L)
{
	using std::cout;
	using std::endl;
	int i = 1;
	LNode *p = L->next;					//指向第一个元素
	if (p == NULL)
	{
		cout << "单链表为空，无法输出元素！" << endl;
		return;
	}
	while (p)
	{
		cout << "第" << i++ << "个元素为：" << p->data << endl;
		p = p->next;
	}
}

Status LocateElem(const LinkList &L, int &i, ElemType e)
{
	LNode *s = L->next;
	int j = 1;						//表示当前指针的指向位置，为第一个节点
	while (s && (s->data != e))
	{
		s = s->next;
		j++;
	}
	if (s == NULL)							//为空表示查找到表尾还没有找到此元素
		return FALSE;
	else
	{
		i = j;
		return OK;
	}
}

Status ListDelete(LinkList &L, int i, ElemType &e)
{
	if (i < 1)
		return FALSE;
	//寻找第i-1个结点
	LNode *p = GetElem(L, i - 1);
	//直接在i-1结点的后面接上i+1结点即可
	return DeleteNextNode(p, e);
}

Status DeleteNextNode(LNode *p, ElemType &e)
{
	if(p == NULL)		//当越界时，p指向NULL
		return FALSE;
	if (p->next == NULL)
		return FALSE;	//在i-1结点之后无其他结点，也是无法删除
	LNode *s = p->next;
	e = s->data;
	p->next = s->next;
	delete s;
	return OK;
}

int Getlength(const LinkList &L)
{
	int length = 0;
	LNode*p = L;
	while (p)
	{
		p = p->next;
		length++;
	}
	return length-1;
}

void Clearlist(LinkList &L)
{
	using std::cin;
	using std::cout;
	using std::endl;
	int l = Getlength(L);		//先计算单链表的元素个数
	ElemType elem;
	while (l--)
	{
		ListDelete(L,l+1, elem);
		cout << "单链表中的" << l+1 << "位置元素：" << elem << "被删除" << endl;
	}
}

main.cpp

/*单链表---包含头结点
typedef struct LNode
{
	ElemType data;				//数据域
	struct LNode *next;			//指针域
}LNode,*LinkList;				//结点和指向结点的指针

1、按位序插入（要判断在表头插入，中间插入，末尾插入和位置不合法处插入的情况）
2、按位序删除（找到i-1的结点）
3、指定结点的删除（无法删除最后一个结点）
4、按位查找
5、按值查找
6、求链表的长度
7、单链表的创建：头插入和尾插法（设计一个表尾指针）

单独封装的函数：
1、找i-1的结点
2、在一个结点之后插入元素
*/
#include <iostream>
#include"list.h"

void showMenu()
{
	using std::cout;
	using std::cin;
	using std::endl;
	cout << "*********************************************************" << endl;
	cout << "*** 1.指定位置插入元素			2.查找指定位置元素 ***" << endl;
	cout << "*** 3.查找指定元素，返回位置		4.删除指定位置元素 ***" << endl;
	cout << "*** 5.遍历单链表			6.清空单链表 ***" << endl;
	cout << "*** 7.单链表的长度			0.退出单链表 ***" << endl;
	cout << "*********************************************************" << endl;
}

int main()
{
	using std::cout;
	using std::cin;
	using std::endl;
	int select = 0, flag = -1;			//输入的选择
	LinkList L;				//L表示头指针，始终指向表头
	
	if (CreatList(L))		//尾插法创建单链表
	{
		cout << "单链表创建成功！" << endl;
	}
	else
		cout << "单链表创建失败！" << endl;

	while (true)
	{
		showMenu();
		cout << "输入你的选择：";
		cin >> select;
		switch (select)
		{
		case 1: {		//指定位置插入元素
			int position = 0, elem = 0;
			cout << "输入插入的位置和元素:";
			cin >> position >> elem;
			if (ListInsert(L, position,elem))
				cout << "指定位置插入元素成功！" << endl;
			else
				cout << "内存分配失败或者插入位置越界，插入失败！" << endl;
		}
		break;
		case 2: {		//查找指定位置元素
			int position = 0;
			LNode *p;
			cout << "输入指定位置:";
			cin >> position;
			if((p = GetElem(L, position)) == NULL)
				cout << "查找位置越界，查找失败！" << endl;
			else
				cout << "查找指定位置元素成功！，元素为：" << p->data << endl;
		}
			break;
		case 3: {		//查找指定元素，返回位置
			int position = 0, elem = 0;
			cout << "输入指定元素:";
			cin >> elem;
			if (LocateElem(L, position, elem))
			{
				cout << "查找指定元素成功！位置为：" << position << endl;
			}
			else
			{
				cout << "单链表不存在此元素！" << endl;
			}
		}
			break;
		case 4: {	//删除指定位置节点
			int position = 0, elem = 0;
			cout << "输入指定位置:";
			cin >> position;
			if (ListDelete(L, position, elem))
			{
				cout << "删除指定位置元素成功！元素为：" << elem << endl;
			}
			else
			{
				cout << "单链表为空或者删除位置不合理！" << endl;
			}
		}
			break;
		case 5: {
			ListTraverse(L);
		}
			break;
		case 6: {
			Clearlist(L);
			flag++;
		}
			break;
		case 7: {	//求取单链表的长度
			cout << "单链表中元素个数为：" << Getlength(L) << "个" << endl;
		}
			break;
		case 0: {
			cout << "退出单链表!" << endl;
			if (flag == -1)
			{
				Clearlist(L);
			}
			system("pause");
			return 0;
		}
			break;
		}
	}

	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖