链表的创建、查找、插入、删除和逆置源码实例

Source

链表的创建、查找、插入、删除和逆置源码实例

本程序结合自身理解编写,主要是通过一串简单的整数来验证单链表的相关算法,比较全面且富含详细注释,对初学者更加和蔼,清晰易懂,让抽象算法在实际例子中运行的代码,能够更好地研究数据结构单链表相关算法,希望对各位新入手的同学有所帮助。在此,若发现错误之处,欢迎指正批评!

程序源码

#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100

typedef int ElemType;
typedef int Status;
typedef struct LNode
{
    
      
	ElemType data;//数据域
	struct LNode* next;//指针域
}LNode,*LinkList;

/*链表的初始化*/
Status InitList_L(LinkList& L)
{
    
      
	L = new LNode;//生成一个新结点,用头指针指向
	L->next = NULL;
	printf("====链表初始化成功!====\n\n");
	return OK;
}                  

/*链表的前插法*/
void CreatList_L1(LinkList& L, int n)
{
    
      
	L = new LNode;//创建一个空结点
	L->next = NULL;//新结点指针域指向空

	for (int i = n;i > 0;--i)//循环n次插入每个节点
	{
    
      
		LinkList p;
		p = new LNode;//生成一个新结点
		printf("第%d个元素为:",i);
		scanf_s("%d", &p->data);//将数据存入data中
		p->next = L->next;//修改指针位置
		L->next = p;
	}
	printf("链表数据创建成功!\n");
}

/*链表的尾插法*/
void CreatList_L2(LinkList& L, int n)
{
    
      
	LinkList r;//声明尾指针r
	L = new LNode;//创建一个新结点
	L->next = NULL;//新结点指针域指向空
	r = L;//刚开始尾指针指向L

	for (int i = 0;i < n;i++)//循环n次插入n个结点
	{
    
      
		LinkList p;
		p = new LNode;//生成一个新结点P
		printf("请输入第%d个元素:", i + 1);
			scanf_s("%d", &p->data);//将数据存入到结点的数据域data中
			p->next = NULL;//最后一个结点的指针域指向空
			r->next = p;//将新结点p与前面的结点连接起来
			r = p;//更改尾结点的位置
	}
	printf("链表创建成功!\n");
}

/*单链表的查找(按序号查找)*/
Status GetElem_L1(LinkList L,int i, ElemType& e)
{
    
      
	LinkList p;//生成新结点p
	p = L->next;//p指向第一个结点
	int j = 1;
	while (p  && j < i)
	{
    
      
		p = p->next;//结点向后扫描
		++j;
	}
	if (!p || j > i) return ERROR;
	e = p->data;
	return OK;
}

/*单链表的查找(按值查找)*/
Status GetElem_L2(LinkList L, ElemType e)
{
    
      
	LinkList p;//声明一个新结点
	int i = 1;
	p = L->next;//新结点指向第一个结点
	while (p && p->data != e)//链表不为空,没找到e
	{
    
      
		p = p->next;//依次向后查找
		++i;//计数器+1
	}
	if (p==NULL) return ERROR;
	return i;
}

/*单链表的逆置*/
LinkList Reverse(LinkList& L)
{
    
      
	LinkList p, r;
	p = L->next;
	L->next = NULL;//断链

	while (p)
	{
    
      
		r = p->next;
		p->next = L->next;//头插法原理
		L->next = p;
		p = r;
	}
	return L;
}

/*单链表的插入*/
Status ListInsert_L(LinkList& L, int i, ElemType e)
{
    
      
	LinkList p,s;
	int j = 0;
	p = L;
	while (p && j < i - 1)//寻找第i-1个结点
	{
    
      
		p = p->next;//依次向后寻找
		++j;
	}
	if (!p || j > i - 1) return ERROR;//不合法
	s = new LNode;//生成一个新结点s
	s->data = e;//将数据e存入到新结点的数据域
	s->next = p->next;//将新结点与后链连接起来
	p->next = s;//将新结点与前链连接起来
	return OK;
}

/*单链表的删除*/
Status ListDelete_L(LinkList& L, int i, ElemType& e)
{
    
      
	LinkList p,q;
	int j = 0;
	p = L;
	while (p && j < i - 1)//寻找第i-1个结点
	{
    
      
		p = p->next;//依次向后寻找
		++j;
	}
	if (!p || j > i - 1) return ERROR;//i大于表长+1或者小于1
	q = p->next;//新结点保存待删除的结点
	p->next = q->next;//改变删除结点前驱结点的指针域
	e = q->data;//保存删除结点的数据域
	delete q;//回收删除结点的空间
	return OK;
}


/*单链表的输出打印*/
Status PrintList_L(LinkList L) 
{
    
      
	printf("操作成功,即将打印链表......\n");
	LinkList p; 
	p = L->next;//生成一个结点指向头结点
	if (!p) return ERROR;//如果链表为空,返回错误
	while (p)
	{
    
      
		printf("%d\n", p->data);//输出结点的数据域
		p = p->next;//修改指针位置
	}
	printf("\n");
	return OK;//打印成功
}

int main()
{
    
      
	LinkList L;//声明链表
	ElemType e1,e2;
	int e,n,i,x,m,f,number;

	InitList_L(L);//调用初始化链表函数

		printf("********相应的功能菜单*****\n");
		printf("*****功能1:头插法创建链表*\n");
		printf("*****功能2:尾插法创建链表*\n");
		printf("*****功能3:按序号查找*****\n");
		printf("*****功能4:按值查找*******\n");
		printf("*****功能5:单链表的逆置***\n");
		printf("*****功能6: 插入元素*******\n");
		printf("*****功能7:删除元素*******\n\n");

	do {
    
      
		printf("请输入相应功能的序号:");
		scanf_s("%d", &number);
		switch (number)
		{
    
      
		case 1:
			printf("请输入链表元素个数:");
			scanf_s("%d", &n);
			CreatList_L1(L, n);//调用头插法函数创建链表函数
			PrintList_L(L);//调用输出函数
			break;

		case 2:
			printf("请输入链表元素个数:");
			scanf_s("%d", &n);
			CreatList_L2(L, n);//调用尾插法创建链表函数
			PrintList_L(L);//调用输出函数
			break;

		case 3:
			printf("请输入要查找元素的位置:");
			scanf_s("%d", &e1);
			GetElem_L1(L, e1, f);//调用按序号查找函数
			printf("你所查找元素在链表的值为:%d\n\n", f);
			break;

		case 4:
			printf("请输入要查找元素的值:");
			scanf_s("%d", &e);//调用按值查找函数
			printf("你查找元素在链表中的位置为:%d\n\n", GetElem_L2(L, e));
			break;

		case 5:
			Reverse(L);
			PrintList_L(L);//调用输出函数
			break;

		case 6:
			printf("请输入要插入元素的位置i:");
			scanf_s("%d", &i);
			printf("请输入要插入的元素e2:");
			scanf_s("%d", &e2);
			if (ListInsert_L(L, i, e2))//调用插入函数
				PrintList_L(L);//调用输出函数
			break;

		case 7:
			printf("请输入要删除元素所在的位置x:");
			scanf_s("%d", &x);
			if (ListDelete_L(L, x, m))//调用删除函数
				PrintList_L(L);//调用输出函数
			printf("所删除位置的元素为%d:\n", m);
			break;

		default: printf("输入错误,请重新输入\n");
		}
	} while (number != 8);
	return 0;
}

运行结果展示:
在这里插入图片描述

在这里插入图片描述