目录

前言

一、链表的定义

二、链表的 C 语言描述

三、链表中基本操作的实现

3.1构造一个带头结点的空链表

3.2取第i个数据元素

3.3在链表中查找值为e的元素

3.3.1返回值类型是节点的地址

3.3.2返回值类型是节点的位置(序号)

3.4在第i位插入数据元素

 3.5删除第i个数据元素

 3.6 前插建立具有n的元素链表

3.7尾插建立具有n的元素链表

3.8线性表置空

3.9销毁链表

3.10判断链表是否为空

 3.11求链表的表长

四、链表代码实现

五、测试结果 

六、总结

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一、链表的定义

用一组地址任意的存储单元存放线性表中的数据元素。

结点 = 数据元素+指针(指后继元素存储位置)

二、链表的 C 语言描述

代码如下（示例）：

//带头结点的单链表
typedef struct LNode {
    int data;
    struct LNode* next;
}Lnode,*LinkList;

三、链表中基本操作的实现

3.1构造一个带头结点的空链表

c++中用new来动态的开辟空间，而c中则是用malloc来开辟空间

我使用new来动态开辟空间

注意:参数是引用型的

代码如下(示例): 

void InitList(LinkList& L)
{
	L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
	L->next = NULL;
}

3.2取第i个数据元素

结束条件：链表走到空或者i的大小不对，比1小

则while语句判断条件为：while(p&&j

当此时p为空或者j>i，则返回0，表示未找到

否则把此时节点的data传给引用型参数data，并返回1

代码如下(示例): 

int GetElem_L(LinkList L, int i, int& data)
{
	int j = 1;
	Lnode* p;
	p = L->next;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)	return 0;
	data = p->data;
	return 1;
}

3.3在链表中查找值为e的元素

时间效率分析：查找次数与位置有关，O(n)

注意，可以按照具体情况来写函数的返回值类型

比如，返回值类型可以是节点的地址，也可以是节点的位置

3.3.1返回值类型是节点的地址

代码如下(示例):

Lnode* LocationElem(LinkList L, int e)
{
	Lnode* p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}

3.3.2返回值类型是节点的位置(序号)

代码如下(示例):

int LocateElem_L(LinkList L, int e)
{
	int j = 1;
	Lnode* p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)	return j;
	else return 0;
}

3.4在第i位插入数据元素

修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)

代码如下(示例): 

void ListInsert_L(LinkList& L, int i, int e)
{
	int j = 0;
	Lnode* p = L;
	while (p && j < i - 1)//即找到i-1的位置
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		printf("i值错误,i小于1或大于表长n");
		return;
	}
	Lnode* s = new Lnode;
	s->data = e;
	s->next = NULL;
	s->next = p->next;
	p->next = s;//注意两行不能调换位置，否则s指向自己，错误
	printf("插入成功n");
}

 3.5删除第i个数据元素

修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)

代码如下(示例): 

void ListDelete(LinkList& L, int i, int& e)
{
	Lnode* p = L,*q;
	int j = 0;
	while (p->next && j < i - 1)//找到i-1的节点
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		printf("未找到要删除的节点n");
		return;
	}
	q = p->next;
	e = q->data;
	p->next = q->next;
	delete q;//释放空间
	printf("成功删除n");
}

 3.6 前插建立具有n的元素链表

时间复杂度：O(n)  

逆序输入

确保结果与想要的是一致的（与尾插结果一致）

代码如下(示例): 

void CreateList_F(LinkList& L, int t[],int n)
{
	//创建n个节点
	L = new Lnode;
	L->next = NULL;
	for(int i=n-1;i>=0;i--)
	{
		Lnode* p =new Lnode;
		p->data=t[i];
		p->next = L->next;
		L->next = p;
	}
}

3.7尾插建立具有n的元素链表

正序输入

时间复杂度：O(n)

代码如下(示例):

void CreateList_L(LinkList& L,int a[],int n)
{
	//尾指针指向尾节点
	L = new Lnode;
	L->next = NULL;
	Lnode* r = L;//尾指针，开始也指向头节点
	for (int i = 0; i < n; i++)
	{
		Lnode* p = new Lnode;
		p->data=a[i];
		p->next = NULL;
		r->next = p;
		r = p;//把尾指针更新到新节点的位置
	}
}

3.8线性表置空

从首元节点开始删除，保存了头指针和头节点

头节点的next赋值为空

 代码如下(示例):

void CleanList(LinkList& L)
{
	Lnode* p = L->next;
	Lnode* q;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;
}

3.9销毁链表

所有节点，包括头节点也删掉

 代码如下(示例): 

void DestoryList(LinkList& L)
{
	Lnode* p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
}

3.10判断链表是否为空

头节点和头指针还在算空表，返回1

当头节点的next值不为空，即起码有个首元节点，则不算空表，返回0

 代码如下(示例):  

int isEmpty(LinkList L)
{
	if (L->next == NULL)
		return 1;
	return 0;
}

 3.11求链表的表长

用一个int型的length来计算，在循环中，当tmp未走到空的时候，每次都加1

 代码如下(示例):  

int ListLength(LinkList L)
{
	Lnode* tmp = L->next;
	int length = 0;
	while (tmp != NULL)
	{
		length++;
		tmp = tmp->next;
	}
	return length;
}

 3.12遍历链表

当链表未走到空的时候，依次把所有节点的数据都输出

代码如下(示例):  

void ListTraverse(LinkList L)
{
	Lnode *tmp=L->next;
	int i=0;
	while(tmp!=NULL)
	{
		cout<<"第"<data<next;
	}
}

四、链表代码实现

代码如下(示例):  

#include 
using namespace std;
const int N=101;
//带头结点的单链表
typedef struct LNode {
	int data;
	struct LNode* next;
}Lnode,*LinkList;
//链表初始化
//构造一个带头结点的空链表
void InitList(LinkList& L)
{
	L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
	L->next = NULL;
}
//判断链表是否为空
//头节点和头指针还在（空表）
int isEmpty(LinkList L)
{
	if (L->next == NULL)
		return 1;
	return 0;
}
//销毁链表
//所有节点，包括头节点也删掉
void DestoryList(LinkList& L)
{
	Lnode* p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
}
//清空单链表
//清空元素,从首元节点开始删除
void CleanList(LinkList& L)
{
	Lnode* p = L->next;
	Lnode* q;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;
}
//求链表的表长
int ListLength(LinkList L)
{
	Lnode* tmp = L->next;
	int length = 0;
	while (tmp != NULL)
	{
		length++;
		tmp = tmp->next;
	}
	return length;
}
//求第i个元素的值
int GetElem_L(LinkList L, int i, int& data)
{
	int j = 1;
	Lnode* p;
	p = L->next;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)	return 0;
	data = p->data;
	return 1;
}
//按值查找  返回地址
//时间效率分析：查找次数与位置有关，O(n)
Lnode* LocationElem(LinkList L, int e)
{
	Lnode* p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}
//按值查找，返回位置序号
int LocateElem_L(LinkList L, int e)
{
	int j = 1;
	Lnode* p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)	return j;
	else return 0;
}
//在第i个元素之前插入值为e的节点
//修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)
void ListInsert_L(LinkList& L, int i, int e)
{
	int j = 0;
	Lnode* p = L;
	while (p && j < i - 1)//即找到i-1的位置
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		printf("i值错误,i小于1或大于表长n");
		return;
	}
	Lnode* s = new Lnode;
	s->data = e;
	s->next = NULL;
	s->next = p->next;
	p->next = s;//注意两行不能调换位置，否则s指向自己，错误
	printf("插入成功n");
}
//删除  删除第i个节点
//修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)
void ListDelete(LinkList& L, int i, int& e)
{
	Lnode* p = L,*q;
	int j = 0;
	while (p->next && j < i - 1)//找到i-1的节点
	{
		p = p->next;
		j++;
	}
	if (!(p->next) || j > i - 1)
	{
		printf("未找到要删除的节点n");
		return;
	}
	q = p->next;
	e = q->data;
	p->next = q->next;
	delete q;//释放空间
	printf("成功删除n");
}
//头插法建立单链表   时间复杂度：O(n)  逆序输入
void CreateList_F(LinkList& L, int t[],int n)
{
	//创建n个节点
	L = new Lnode;
	L->next = NULL;
	for(int i=n-1;i>=0;i--)
	{
		Lnode* p =new Lnode;
		p->data=t[i];
		p->next = L->next;
		L->next = p;
	}
}
//尾插法  正序输入 时间复杂度：O(n)
void CreateList_L(LinkList& L,int a[],int n)
{
	//尾指针指向尾节点
	L = new Lnode;
	L->next = NULL;
	Lnode* r = L;//尾指针，开始也指向头节点
	for (int i = 0; i < n; i++)
	{
		Lnode* p = new Lnode;
		p->data=a[i];
		p->next = NULL;
		r->next = p;
		r = p;//把尾指针更新到新节点的位置
	}
}
//遍历 
void ListTraverse(LinkList L)
{
	Lnode *tmp=L->next;
	int i=0;
	while(tmp!=NULL)
	{
		cout<<"第"<data<next;
	}
}
void menu()
{
	cout<<"*******************************************"<>choice;
		switch(choice)
		{
			case 1:
				InitList(L);
				cout<<"成功初始化"<>t;
				if(t==1)
				{
					int a1[N];
					cout<<"请输入需要多少个节点"<>n;
					for(int i=0;i>a1[i];	
					} 
					CreateList_F(L,a1,n);
				}
				else
				{
					int a2[N];
					cout<<"请输入需要多少个节点"<>n;
					for(int i=0;i>a2[i];	
					} 
					CreateList_L(L,a2,n);
				}
				break;
			case 3:	
				cout<<"输入要查找的位置"<>x; 
				GetElem_L(L,x,data);
				cout<<"第"<>e;
				x1=LocateElem_L(L,e);
				cout<<"位置为："<>i1>>e1;
				ListInsert_L(L,i1,e1);
				break;
			case 6:
				cout<<"请输入要删除哪个节点"<>i2;
				ListDelete(L,i2,e2);
				cout<<"删除成功，原来的节点的数据为"< 
五、测试结果  
 
 
测试样例：创建4个节点    数据分别为1、2、3、4        其余测试基于以上4个节点
 
 
 
 图一
 
 
图二
 
 
 
图三
 
 
图四
 
 
 
图五
 
 
图六
 
 
图七
 
 
 
图八
 
 
 
 图九
 
 
图十
 
 
 
图11
 
 
图十二 
 
六、总结 
        链表是一种动态分配空间的存储结构，能更有效地利用存储空间，通过对单链表基本操作的代码实现，我深刻领悟到以“指针”指示元素的后继，在插入或删除元素时不需要移动元素。但是与此同时，由于链表是“顺序存取”的结构，给随机存取元素和在表尾插入等操作带来不便。，所以接下来我将学习尾指针表示的单链表，双向链表以及循环链表等。