[数据结构与算法]数据结构--单链表的基本操作 (C/C++)第二版

?实现单链表的创建、插入、删除、查找、取值五种操作

typedef  int Status;
typedef  int ElemType;

解释1.：
定义不同的数据类型名称是为了程序的可读性.
而且一旦你需要将类型变换比如使用double型的了,只要写:
typedef double elemtype;
一下子就全改了,如果没有定义的话就要一个个的把int改成double
解释2：
typedef int status;是个自定义类型的语句
typedef用来定义类型的别名
status i;=>>int i;
status的英文是状态，用int值表示一个状态，所以自定义一个类型。
这样status i;一看就知道变量i表示一个状态变量。
而int i;就不能传达给读者这样一个意思。
但是本质上是一样的，这样写就是为了传达编程的信息，方便以后维护、可读性。

typedef struct LNode
{
	ElemType data;//整型数据元素
	struct LNode* next;
}LNode, * LinkList;

typedef是一种在计算机编程语言中用来声明<自定义数据类型>
LNode, * LinkList;表示定义LinkList为LNode指针类型，用逗号进行分隔可以定义多个类型。
LNode,*LinkList均为LNode的别名，只不过是一个主要指代结点一个指代链表。
这个类型是一个结构体的指针

1.初始化操作

Status InitList(LinkList& L)/*添加&;修改值或者将运行结果返回主函数*/
{
	L = (LinkList)malloc(sizeof(LNode));//为单链表分配空间
	L = new LNode;//定义头结点
	L->next = NULL;//尾指针为空
	return OK;
}

2.创建操作(采用后插法创建单链表)

Status CreateList_R(LinkList& L)
{//Linklist *L 用头指针表示链表类，即实质是该链表的头指针类型
	printf("初始化链表\n");
	InitList(L);//创建单链表的前提是初始化单链表，调用初始化函数
	LinkList r, p;//r为指针，p为结点，L为带头结点的空链表
	/*
	Linklist L
    定义一个单链表类型的单链表L;
	L可以作为指向定义的node结构体的指针;
	*/
	r = L;//尾指针指向头结点
	int n;
	printf("请输入链表元素个数：");
	scanf_s("%d", &n);
	printf("请输入元素值：");
	for (int i = 0; i < n; i++)
	{
		p = new LNode;//定义新的结点
		cin >> p->data;//输入数据域的值
		p->next = NULL;//尾指针为空
		r->next = p;//与p结点建立连接
		r = p;//r指向新的尾结点
	}
	return OK;
}

3.遍历操作

其一；常规

Status DisplayList(LinkList L)
{
	if (L->next == NULL)
	{
		printf("空表\n");
		return ERROR;
	}
	LinkList p = L->next;
	while (p != NULL)
	{
		printf("%4d", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

其二；递归

Status DisplayList(LinkList L)
{
	LinkList p;
	p = L->next;
	if (p)
	{
		cout << p->data << endl;
		DisplayList(L->next);
	}
	return OK;
}

4.插入单链表

Status ListInsert(LinkList& L)
{
	int j = 0,  i;
	LinkList p, s;
	ElemType  e;
	printf("请输入要插入的元素的位置和值：");
	scanf_s("%d%d", &i, &e);
	p = L;
	while (p && (j < i - 1))
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
	{
		printf("插入位置不合法\n");
		return ERROR;
	}
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

5.删除单链表

Status DeleteList(LinkList& L)
{
	int j = 0, i;
	LinkList p, q;
	printf("请输入要删除元素的位置：");
	scanf_s("%d", &i);
	p = L;
	while (p && (j < i - 1))
	{
		p = p->next;
		++j;
	}
	if (!p || (j > i - 1))
	{
		printf("删除位置不合法！\n");
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	printf("删除元素为：%d\n", q->data);
	delete q;
	return OK;
}

6.查找操作(查找指定元素的值并输出该元素位序)

Status LocateElem(LinkList& L)
{
	LinkList p;
	int i = 1;
	ElemType e;
	p = L->next;
	printf("请输入要查找元素的值：");
	scanf_s("%d", &e);
	while (p) {
		if (p->data == e) {
			printf("该元素的位序为：%d\n", i);
			return 0;
		}
		else {
			p = p->next;
			i++;
		}
		if (!p) {
			printf("未找到该元素！\n");
			return 0;
		}
	}
}

7.单链表取值

Status GetELem(LinkList& L)
{
	int j = 1, i;
	LinkList p;
	p = L->next;
	printf("请输入要查找元素的位序：");
	scanf_s("%d", &i);
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		printf("请输入正确的位置\n");
	}
	else
	{
		printf("第%d个位置的值为：%d", i, p->data);
	}
	return OK;
}

8.建立菜单(外加while循环体)

printf("----------------栈的基本操作---------------\n");
		printf("\t\t1.创建操作\n");
		printf("\t\t2.插入操作\n");
		printf("\t\t3.删除操作\n");
		printf("\t\t4.查找操作\n");
		printf("\t\t5.取值操作\n");
		int i = 0;
		printf("请输入将要进行操作的序号：\n");
		cin >> ("%d", i);
		LinkList H;
		switch (i) {
			//LinkList H;
		case 1:
			CreateList_R(H);
			DisplayList(H);
			break;
		case 2:
			ListInsert(H);
			DisplayList(H);
			break;
		case 3:
			DeleteList(H);
			DisplayList(H);
			break;
		case 4:
			LocateElem(H);
			break;
		case 5:
			GetELem(H);
			break;
		default:printf("输入的数字有误，请重新输入\n");
		}
		system("pause");
		system("cls");

完整代码如下，如需copy，请留言

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream"//用到cin
using namespace std;

#define OK 1
#define ERROR 0
//#define OVERFLOW -2
typedef  int Status;
typedef  int ElemType;//整型

typedef struct LNode
{
	ElemType data;//整型数据元素
	struct LNode* next;
}LNode, * LinkList;

//初始化操作单链表
Status InitList(LinkList& L)/*添加&;修改值或者将运行结果返回主函数*/
{
	L = (LinkList)malloc(sizeof(LNode));//为单链表分配空间
	L = new LNode;//定义头结点
	L->next = NULL;//尾指针为空
	return OK;
}

//后插法创建单链表
Status CreateList_R(LinkList& L)
{//Linklist *L 用头指针表示链表类，即实质是该链表的头指针类型
	printf("初始化链表\n");
	InitList(L);//创建单链表的前提是初始化单链表，调用初始化函数
	LinkList r, p;//r为指针，p为结点，L为带头结点的空链表
	/*
	Linklist L
    定义一个单链表类型的单链表L;
	L可以作为指向定义的node结构体的指针;
	*/
	r = L;//尾指针指向头结点
	int n;
	printf("请输入链表元素个数：");
	scanf_s("%d", &n);
	printf("请输入元素值：");
	for (int i = 0; i < n; i++)
	{
		p = new LNode;//定义新的结点
		cin >> p->data;//输入数据域的值
		p->next = NULL;//尾指针为空
		r->next = p;//与p结点建立连接
		r = p;//r指向新的尾结点
	}
	return OK;
}

//遍历  
Status DisplayList(LinkList L)
{
	if (L->next == NULL)
	{
		printf("空表\n");
		return ERROR;
	}
	LinkList p = L->next;
	while (p != NULL)
	{
		printf("%4d", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}
/*//递归遍历
Status DisplayList(LinkList L)
{
	LinkList p;
	p = L->next;
	if (p)
	{
		cout << p->data << endl;
		DisplayList(L->next);
	}
	return OK;
}*/

//插入单链表
Status ListInsert(LinkList& L)
{
	int j = 0,  i;
	LinkList p, s;
	ElemType  e;
	printf("请输入要插入的元素的位置和值：");
	scanf_s("%d%d", &i, &e);
	p = L;
	while (p && (j < i - 1))
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
	{
		printf("插入位置不合法\n");
		return ERROR;
	}
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}


//删除单链表
Status DeleteList(LinkList& L)
{
	int j = 0, i;
	LinkList p, q;
	printf("请输入要删除元素的位置：");
	scanf_s("%d", &i);
	p = L;
	while (p && (j < i - 1))
	{
		p = p->next;
		++j;
	}
	if (!p || (j > i - 1))
	{
		printf("删除位置不合法！\n");
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	printf("删除元素为：%d\n", q->data);
	delete q;
	return OK;
}

//查找指定元素的值并输出该元素位序
Status LocateElem(LinkList& L)
{
	LinkList p;
	int i = 1;
	ElemType e;
	p = L->next;
	printf("请输入要查找元素的值：");
	scanf_s("%d", &e);
	while (p) {
		if (p->data == e) {
			printf("该元素的位序为：%d\n", i);
			return 0;
		}
		else {
			p = p->next;
			i++;
		}
		if (!p) {
			printf("未找到该元素！\n");
			return 0;
		}
	}
}

//单链表取值操作
Status GetELem(LinkList& L)
{
	int j = 1, i;
	LinkList p;
	p = L->next;
	printf("请输入要查找元素的位序：");
	scanf_s("%d", &i);
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		printf("请输入正确的位置\n");
	}
	else
	{
		printf("第%d个位置的值为：%d", i, p->data);
	}
	return OK;
}
int main()
{	
	while (1)
	{
		printf("----------------栈的基本操作---------------\n");
		printf("\t\t1.创建操作\n");
		printf("\t\t2.插入操作\n");
		printf("\t\t3.删除操作\n");
		printf("\t\t4.查找操作\n");
		printf("\t\t5.取值操作\n");
		int i = 0;
		printf("请输入将要进行操作的序号：\n");
		cin >> ("%d", i);
		LinkList H;
		switch (i) {
			//LinkList H;
		case 1:
			CreateList_R(H);
			DisplayList(H);
			break;
		case 2:
			ListInsert(H);
			DisplayList(H);
			break;
		case 3:
			DeleteList(H);
			DisplayList(H);
			break;
		case 4:
			LocateElem(H);
			break;
		case 5:
			GetELem(H);
			break;
		default:printf("输入的数字有误，请重新输入\n");
		}
		system("pause");
		system("cls");
	}
}