各种线性表（单链表，双链表，循环链表）的基本运算（初始化，插入，删除，销毁，输出，按元素查找等）都有给源码

2023-12-21 06:26:09

?各种线性表（单链表，双链表，循环链表）的基本运算

1.InitList()? 初始化线性表

2.void CreateListF(LinkNode* L, ElemType a[], int n)? 头插法创建链表

3.?void CreateListR(LinkNode* L, ElemType a[], int n)? 尾插法创建链表

4.DestroyList(LinkNode* L)? 销毁线性表

5.ListEmpty(LinkNode* L)? 判断线性表L是否为空表，如果为空表返回真否则返回假

6.ListLength(LinkNode* L) 求线性表的长度，返回L中的元素个数

7.DispList(LinkNode* L)? 输出线性表

8.GetElem(LinkNode* L, int n, ElemType* e)? 按序号求线性表中的元素，用e返回L中第i个元素值

9.LocateElem(LinkNode* L, ElemType e)? 按元素查找，返回L中第一个值为e的元素序号

10.ListInsert(LinkNode* L, int n, ElemType e)? 插入元素，在L第i个位置插入e元素

11.ListDelete(LinkNode* L, int n, ElemType*t)? 删除元素，删除L的第i个元素，用e返回被删除的元素值

单链表：

单链表的基本运算：

1.InitList()? 初始化线性表

2.void CreateListF(LinkNode* L, ElemType a[], int n)? 头插法创建单链表

3.?void CreateListR(LinkNode* L, ElemType a[], int n)? 尾插法创建单链表

4.DestroyList(LinkNode* L)? 销毁线性表

5.ListEmpty(LinkNode* L)? 判断线性表L是否为空表，如果为空表返回真否则返回假

6.ListLength(LinkNode* L) 求线性表的长度，返回L中的元素个数

7.DispList(LinkNode* L)? 输出线性表

8.GetElem(LinkNode* L, int n, ElemType* e)? 按序号求线性表中的元素，用e返回L中第i个元素值

9.LocateElem(LinkNode* L, ElemType e)? 按元素查找，返回L中第一个值为e的元素序号

10.ListInsert(LinkNode* L, int n, ElemType e)? 插入元素，在L第i个位置插入e元素

11.ListDelete(LinkNode* L, int n, ElemType*t)? 删除元素，删除L的第i个元素，用e返回被删除的元素值

首先本文章将基本元素类型用int来实现（便于理解，后续改变一下即可）

用typedef 将int 用ElemType来作其别名（使代码具有通用性）

准备工作如下：

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LinkNode;
ElemType a[10] = { 1,2,3,4,12,6,7,8,11,10 };

变量名就是它的意义，大家要养成习惯

这里定义一个数组a方便大家自己拿到程序可以直接使用。

下面便是上面线性表基本运算的码源

解释基本都在代码里了

1.InitList()? 初始化线性表

LinkNode* InitList()
{
	LinkNode* L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;//创建头结点，将其next设为NULL
	return L;
}

引用malloc要用#include <stdlib.h>

创建完指针后一定要处理（养成好习惯）

InitList的用法

int main()
{
	LinkNode* L = InitList();//InitList的用法
	CreateListR(L, a, 10);
	sort(L);
	DispList(L);
	
	return 0;
}

只需看第一行即可其它代码后续会给出

2.void CreateListF(LinkNode* L, ElemType a[], int n)? 头插法创建单链表

void CreateListF(LinkNode* L, ElemType a[], int n)//头插法
{
	LinkNode* s;
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//一直在头结点处操作
		s->data = a[i];//存入数据
		s->next = L->next;//要好好理解这里和尾插法不同的地方
		L->next = s;
	}
}

头插法存入的数据与原数据相反（和后一章的stack一样）

3.?void CreateListR(LinkNode* L, ElemType a[], int n)? 尾插法创建单链表

void CreateListR(LinkNode* L, ElemType a[], int n)
{
	LinkNode* s;
	LinkNode* r;
	r = L;//始终指向尾结点
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		r->next = s;
		r = s;//指向尾结点


	}
	r->next = NULL;//最后要把链表的尾链处理不然会有野指针

}

4.DestroyList(LinkNode* L)? 销毁线性表

void DestroyList(LinkNode* L)
{
	LinkNode* pre=L, * p=L->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);

}

最后要free（pre）pre最后指向最后一个结点

5.ListEmpty(LinkNode* L)? 判断线性表L是否为空表

bool ListEmpty(LinkNode* L)
{
	return (L->next == NULL);
}

注意要使用bool要引头文件#include <stdbool.h>

6.ListLength(LinkNode* L) 求线性表的长度

int ListLength(LinkNode* L)
{
	int n=0;
	LinkNode* p = L;
	while (p != NULL)
	{
		n++;
		p=p->next;
	}
	return n;
}

代码简单就不多说废话

7.DispList(LinkNode* L)? 输出线性表

void DispList(LinkNode* L)
{
	LinkNode* p = L->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");

}

8.GetElem(LinkNode* L, int n, ElemType* e)? 按序号求线性表中的元素

bool GetElem(LinkNode* L, int n, ElemType* e)
{
	int j = 0;
	LinkNode* p = L;
	if (n <= 0) return false;
	while (j < n && p != NULL)//找到下标为n的元素的前驱元素
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		*e = p->data;//用指针可以修改变量值
		return true;
	}

}

9.LocateElem(LinkNode* L, ElemType e)? 按元素查找

int LocateElem(LinkNode* L, ElemType e)
{
	LinkNode* p = L->next;
	int i = 1;
	while (p != NULL&&p->data!=e)//查找
	{
		p = p->next;
		i++;
	}
	if (p == NULL) return 0;
	else
	{
		return i;
	}
}

10.ListInsert(LinkNode* L, int n, ElemType e)? 插入元素

bool ListInsert(LinkNode* L, int n, ElemType e)
{
	LinkNode* p = L->next,*s=NULL;//p指向头结点
	int i = 0;
	if (n <= 0) return false;//头结点前不能插入元素
	while (p != NULL && i < n-1)//定位i-1结点
	{
		i++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));//创建结点
		s->data = e;//放结点数据
		s->next = p->next;//插入，插入前要把后面结点的地址赋给s，否则下面一步会使右面结点丢失
		p->next = s;
		return true;
	}
}

11.ListDelete(LinkNode* L, int n, ElemType*t)? 删除元素

bool ListDelete(LinkNode* L, int n, ElemType*t)
{
	LinkNode* p = L,*q;
	int j = 0;
	if (n <= 0) return false;
	while (j < n - 1 && p != NULL)//查找
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		q = p->next;//保存当前结点地址后面要free
		if (q == NULL) return false;
		*t = q->data;//将要删除结点的数据返回
		p->next = q->next;//删除结点将q的地址跳过
		free(q);//释放
		return true;

	}
}

最后附上总代码：

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
//单链表
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LinkNode;
ElemType a[10] = { 1,2,3,4,5,6,7,8,9,10 };
void CreateListF(LinkNode* L, ElemType a[], int n)//头插法
{
	LinkNode* s;
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		s->next = L->next;
		L->next = s;
	}
}
void CreateListR(LinkNode* L, ElemType a[], int n)
{
	LinkNode* s;
	LinkNode* r;
	r = L;
	for (int i = 0; i < n; i++)
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = a[i];
		r->next = s;
		r = s;


	}
	r->next = NULL;

}
LinkNode* InitList()
{
	LinkNode* L = (LinkNode*)malloc(sizeof(LinkNode));
	L->next = NULL;
	return L;
}
void DestroyList(LinkNode* L)
{
	LinkNode* pre = L, * p = L->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);

}
bool ListEmpty(LinkNode* L)
{
	return (L->next == NULL);
}
int ListLength(LinkNode* L)
{
	int n = 0;
	LinkNode* p = L;
	while (p != NULL)
	{
		n++;
		p = p->next;
	}
	return n;
}
void DispList(LinkNode* L)
{
	LinkNode* p = L->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");

}
bool GetElem(LinkNode* L, int n, ElemType* e)
{
	int j = 0;
	LinkNode* p = L;
	if (n <= 0) return false;
	while (j < n && p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		*e = p->data;
		return true;
	}

}
int LocateElem(LinkNode* L, ElemType e)
{
	LinkNode* p = L->next;
	int i = 1;
	while (p != NULL && p->data != e)
	{
		p = p->next;
		i++;
	}
	if (p == NULL) return 0;
	else
	{
		return i;
	}
}
bool ListInsert(LinkNode* L, int n, ElemType e)
{
	LinkNode* p = L->next, * s = NULL;
	int i = 0;
	if (n <= 0) return false;
	while (p != NULL && i < n - 1)
	{
		i++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		s = (LinkNode*)malloc(sizeof(LinkNode));
		s->data = e;
		s->next = p->next;
		p->next = s;
		return true;
	}
}
bool ListDelete(LinkNode* L, int n, ElemType* t)
{
	LinkNode* p = L, * q;
	int j = 0;
	if (n <= 0) return false;
	while (j < n - 1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		q = p->next;

		if (q == NULL) return false;
		*t = q->data;
		p->next = q->next;
		free(q);
		return true;

	}
}
int main()
{
	LinkNode* L = InitList();//InitList的用法
	CreateListR(L, a, 10);
	DispList(L);
	return 0;
}

双链表：

双链表算法实现和单链表的实现基本一样我就不解释直接上代码

#define  _CRT_SECURE_NO_WARNINGS 1
//双链表
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
typedef int ElemType;
typedef struct DLinkNode
{
	ElemType data;
	struct DLinkNode* prior;
	struct DLinkNode* next;
}DLinkNode;
DLinkNode* InitList()
{
	DLinkNode* L = (DLinkNode*)malloc(sizeof(DLinkNode));
	L->next = NULL;
	L->prior = NULL;
	return L;
}
void CreateList(DLinkNode* L, ElemType a[], int n)//尾插法，头插上面给过就由读者自行实现（不难的）
{
	DLinkNode* s,*r;
	r = L;
	for (int i = 0; i < n; i++)
	{
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = a[i];
		r->next = s;
		s->prior = r;
		r = s;
	}
	r->next = NULL;
}
void DispList(DLinkNode* L)
{
	DLinkNode* p = L->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
void DestroyList(DLinkNode* L)
{
	DLinkNode* pre=L, * p = L->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}
bool ListEmpty(DLinkNode* L)
{
	return (L->next == NULL);
}
int Listlength(DLinkNode* L)
{
	int n=0;
	DLinkNode* p = L;
	while (p != NULL)
	{
		n++;
		p->next;
	}
	return n;
}
bool GetElem(DLinkNode* L,int n,ElemType* e)
{
	if (n <= 0) return false;
	DLinkNode* p = L;
	int i=0;
	while (i < n  && p!= NULL)
	{
		i++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		*e = p->data;
		return true;
	}

}
int LocateList(DLinkNode* L, ElemType e)
{
	DLinkNode* p = L;
	int i=0;
	while (p->data != e&&p!=NULL)
	{
		i++;
		p = p->next;
	}
	if (p == NULL) return 0;
	else return i;
}
bool ListInsert(DLinkNode* L, int i, ElemType e)
{
	DLinkNode* s;
	if (i <= 0) return false;
	int j = 0;
	DLinkNode* p = L;
	while (j <i-1 && p != NULL)
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false;
	else
	{
		s = (DLinkNode*)malloc(sizeof(DLinkNode));
		s->data = e;
		s->next = p->next;
		if(p->next!=NULL) p->next->prior = s;
		p->next = s;
		s->prior = p;
		return true;	
	}
}
bool ListDelete(DLinkNode* L, int i, ElemType* e)
{
	if (i <= 0) return false;
	int j = 0;
	DLinkNode* p = L, * pre;
	while (j < i - 1 && p != NULL)
	{
		if (p->next == NULL) return false;
		pre = p->next;
		p->next = pre->next;
		pre->next->prior = p;
		free(pre);
		return true;
	}

}
int main()
{
	ElemType a[10] = { 1,2,3,4,5,6,7,8,9,10 };
	DLinkNode* L = InitList();
	CreateList(L, a, 10);
	ElemType b = 0;
	ElemType* c = &b;
	ListDelete(L, 3, c);
	
	DispList(L);
	//DispList(L);
	return 0;
}

循环链表:

一样也有单双循环链表，但理解单链表双链表也差不多了

下面描述均在单链表上实现

循环链表就是把它的尾结点的next指针域由原来的空改为指向头结点，整个单链表形成一个环。

基本运算和上面基本一样就不多说。

最后第二章的小结：

1.理解线性表的逻辑结构

2.掌握线性表的两种存储结构（1）顺序表（用数组实现直接开辟一大块连续空间，简单故本文章不描述）（2）链表

3.掌握链表的基本运算

给出题目供大家练手

如果不会的话看官方题解

LeetCode67

LeetCode27

LeetCode26

LeetCode80

LeetCode88

作家文章的生命在于读者。只要你还在读我的文章，我就在你眼底，你就在我心中。

如果文章对你有帮助的话点个赞啦！

文章来源:https://blog.csdn.net/2301_80035594/article/details/135095965
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

各种线性表（单链表，双链表，循环链表）的基本运算（初始化，插入，删除，销毁，输出，按元素查找等） 都有给源码