单链表的相关操作

一、闵版（char类型）
- 1.完整代码
- 2.运行效果
二、钦版（int 类型）
- 0.链表的概念
- 1.链表结构体创建
- 2.初始化
- 3.头插法
- 4.尾插法
- 5.指定位置插入
- 6.指定值插入（多个同样元素取首个元素插入）
- 7.指定位置获取数据
- 8.按值获取元素位置
- 9.删除结点
- 10.打印链表
- 11.摧毁链表
- 12.完整代码
三、总结

提示：以下是本篇文章正文内容，下面案例可供参考

一、闵版（char类型） 1.完整代码

#include 
#include 

using namespace std;

typedef struct LinkNode
{
	char data;
	struct LinkNode *next;
}LNode,*LinkList,*NodePtr;


LinkList initLinkList()
{
	NodePtr tempHeader = new LNode;

	if(!tempHeader)
		return NULL;

	tempHeader->data = '';
	tempHeader->next = NULL;

	return tempHeader;
}

//尾插法插入元素
void appendElement(NodePtr paraHeader,char paraChar)
{
	NodePtr p,q;

	// Step 1. Construct a new node.
	q = new LNode;
	q->data = paraChar;
	q->next = NULL;

	// Step 2. Search to the tail.
	p = paraHeader;

	while(p->next)
	{
		p = p->next;
	}

	// Step 3. Now add/link.
	p->next = q;
}

//任意位置插入元素
void insertElement(NodePtr paraHeader, char paraChar, int paraPosition)
{
	NodePtr p, q;

	// Step 1. Search to the position.
	p = paraHeader;
	int pos = 0;

	while(p!= NULL && pos
		p = p->next;
		pos++;
	}

	if(!p || pos>paraPosition)
	{
		cout<data = paraChar;

	// Step 3. Now link.
	cout<<"linking"<next = p->next;
	p->next = q;
}


void deleteElement(NodePtr paraHeader, char paraChar)
{
	NodePtr p,q;

	p = paraHeader;

	while((p->next != NULL) && (p->data != paraChar))
	{
		p = p->next;//找到目标节点的前一个节点
	}

	if(!p->next)//目标节点为空
	{
		cout<next;
	p->next = q->next;

	delete q;
}

void printList(NodePtr paraHeader){
	NodePtr p = paraHeader->next;
	while (p != NULL) {
		cout<data<<" ";
		p = p->next;
	}
	printf("n");
}// Of printList

void appendInsertDeleteTest(){
	// Step 1. Initialize an empty list.
	LinkList tempList = initLinkList();
	printList(tempList);

	// Step 2. Add some characters.
	appendElement(tempList, 'H');
	appendElement(tempList, 'e');
	appendElement(tempList, 'l');
	appendElement(tempList, 'l');
	appendElement(tempList, 'o');
	appendElement(tempList, '!');
	printList(tempList);

	// Step 3. Delete some characters (the first occurrence).
	deleteElement(tempList, 'e');
	deleteElement(tempList, 'a');
	deleteElement(tempList, 'o');
	printList(tempList);

	
	insertElement(tempList, 'o', 1);
	printList(tempList);
}
int main(){
	appendInsertDeleteTest();
	
	system("pause");
	return 0;
}

2.运行效果

二、钦版（int 类型） 0.链表的概念

简单来说，就是一条线性数据链。

1.链表结构体创建

typedef struct _LinkNode
{
	int data;
	struct _LinkNode *next;
}LinkNode,LinkList;

上面采用char 类型，这里采用int 类型。

2.初始化

bool InitList(LinkList* &L)
{
	L = new LinkNode;
	
	if(!L)
		return false;
	
	L->next = NULL;
	
	return true;
}

注：
（1）LinkList* &L ：结构体指针的引用，相当于就是给main函数里面的结构体指针取了个别名“L”。
（2）new: 动态内存申请，后面直接给数据类型就可以了，不用强制性转换。
（3）记住这里申请了动态内存，后面一定要记得用完了，自己释放！

3.头插法

//头插法 
bool ListInsertByHead(LinkList* &L,LinkNode *node)
{
	if(!L||!node)//防御性编程
		return false;
		
	node->next = L->next;//新结点指向头结点曾经指向的结点 
	L->next = node;     //头结点指向新结点 
	
	return true; 
}

注：
（1）传入的结点，可能是空结点，此时建议加上防御性编程

4.尾插法

//尾插法
bool LinkInsertByTail(LinkList* &L,LinkNode *node)
{
	LinkNode *last = NULL;
	
	if(!L||!node)
		return false;
	
	last = L;
	
	while(last->next != NULL)
	{
		last = last->next;//循环直至保存倒数第二个节点位置 
	}	
	
	node->next = NULL;//先把新节点指向空 
	last->next = node;//曾经的最后一个节点指向新插入的节点 
	
	return true; 
}

尾插法比头插法多了一个循环移动，关键是最后的指针的指向，根据注释和图解，加以理解。

5.指定位置插入

//指定位置插入
bool LinkInsertByApoint(LinkList* &L,int i,int &e)//链表名，插入的位置，插入的数据
{
	if(!L||!e)
		return false;
	
	int pos = 0;
	
	LinkList *p,*s;
	
	p=L;
	
	while(p!=NULL && pos
		p = p->next;
		pos++; 
	}
	
	if(!p || pos>i-1) // 在两个空位置间插入数据  or  想在下标为负的位置插入数据 
	{
		cout<<"n非法插入！";
	 	return false;
	}

	s = new LinkNode;
	s->data = e;
	
	s->next = p->next;//新结点指向第i个结点 
	p->next = s;     //新结点被第i-1个结点所指向 
	
	return true;	
	
}

我这里说的位置，不是下标位置，就是普通的物理位置。

6.指定值插入（多个同样元素取首个元素插入）

bool inserElementByValue(LinkList* &L,int i,int &Value)
{
	if(!L)
		return false;

	LinkList *p = NULL,*q = NULL;

	p = L->next;

	while(p->next && p->next->data != i)
	{
		p = p->next;
	}
	
	q = new LinkNode;

	q->data = Value;
	q->next = p->next;//新结点指向目标结点 
	p->next = q;     //新结点被目标结点的前一个结点指向 

	return true;

}

7.指定位置获取数据

//指定位置获取数据
bool LinkGetsDataByPos(LinkNode* &L,int i,int &e)
// i-->位置 ， e -- >要返回的数据 
{
	int index = 1;
	LinkList *p = L->next;
	
	if(!L || !L->next)
	{
		cout<<"空玩意儿！";
		return false;
	}
	
	while(p && index 
		p=p->next;
		index++;//计数器 
	}
	
	if(!p || index>i)
	{
		return false;//i值 不合法 :i>n 或 i<=0 
	} 
	
	e = p->data;
	
	return true;
}

注：
（1）引用可以把 e 带出去，所以采用了习惯的bool返回方式。
（2）采用引用带出数据是C++的代码风格，不习惯的小伙伴可以采用int 等的返回类型return e;即可

8.按值获取元素位置

//按值获取元素
bool LinkGetsDataByData(LinkNode* &L,int e,int &index) 
{
	LinkList *p = L->next; //p 当前结点 
	index = 1;
	
	if(!L || !L->next)
	{
		return false;
	}
	
	while(p && p->data != e)
	{
		index++;
		p=p->next;//p->next 是下一个结点 
	}
	
	if(!p)
	{
		return false;
	}
	
	return true;
}

9.删除结点

//按位置删除
bool LinkDeleteByPos(LinkList* &L,int i)
{
	LinkList *p = L,*q;//要删除的前面一个结点 
	
	int index = 0;
	
	if(!L || !L->next)
	{
		return false;
	}
	
	while((p->next) && (indexnext 指的是当前的结点 
	{
		p = p->next;//找到要删除的节点的前一个结点 
		index++;
	}
	
	if((!p->next) || (index>i-1))// 当 i>n  或 i < 1 时不合理 
	{
		return false; 
	}
	
	q = p->next; //临时保存被删除的结点的地址，以备释放空间 
	p->next = q->next; //使得被删除的结点的前一个结点，指向被删除结点的下一个结点 
	
	delete q; //把被删除的结点的内存释放掉 
	
	return true;
}

注：
（1）C++里new 对应delete

10.打印链表

//打印链表 
void PrintLink(LinkList* &L)
{
	LinkNode *pMove = NULL;
	
	if(!L)
	{
		cout<<"链表为空链表！！！";
		return ;
	}
	
	pMove = L->next;//指向头结点了
	
	while(pMove!=NULL)
	{
		cout<data<<" ";
		
		pMove=pMove->next;
	}
	cout< 
pMove ：循环指针 
11.摧毁链表 
//销毁链表
bool LinkDestroy(LinkList* &L)
{
	LinkList *p = L;

	while(p)
	{
		L= L->next;//指向下一个结点 
		delete p;  //释放当前结点 
		
		p = L;    //赋给p，让p去循环执行释放的工作 
	}
	
	cout<<"n销毁链表！！！" < 
12.完整代码 
#include 
#include 
#include 

using namespace std;

typedef struct _LinkNode
{
	int data;
	struct _LinkNode *next;
}LinkNode,LinkList;

bool InitList(LinkList* &L)
{
	L = new LinkNode;
	
	if(!L)
		return false;
	
	L->next = NULL;
	
	return true;
}

//头插法 
bool ListInsertByHead(LinkList* L,LinkNode *node)//引用写不写问题不大，由于是指针可以直接访问地址 
{
	if(!L||!node)
		return false;
	node->next = L->next;//新结点指向头结点曾经指向的结点 
	L->next = node;     //头结点指向新结点 
	
	return true; 
} 
//尾插法
bool LinkInsertByTail(LinkList* &L,LinkNode *node)
{
	LinkNode *last = NULL;
	
	if(!L||!node)
		return false;
	
	last = L;
	
	while(last->next != NULL)
	{
		last = last->next;//循环直至保存倒数第二个节点位置 
	}	
	
	node->next = NULL;//先把新节点指向空 
	last->next = node;//曾经的最后一个节点指向新插入的节点 
	
	return true; 
} 

//指定位置插入
bool LinkInsertByApoint(LinkList* &L,int i,int &e)//链表名，插入的位置，插入的数据
{
	if(!L||!e)
		return false;
	
	int pos = 0;
	
	LinkList *p,*s;
	
	p=L;
	
	while(p!=NULL && pos
		p = p->next;
		pos++; 
	}
	
	if(!p || pos>i-1) // 在两个空位置间插入数据  or  想在下标为负的位置插入数据 
	{
		cout<<"n非法插入！";
	 	return false;
	}

	s = new LinkNode;
	s->data = e;
	
	s->next = p->next;//新结点指向第i个结点 
	p->next = s;     //新结点被第i-1个结点所指向 
	
	return true;	
	
} 


bool inserElementByValue(LinkList* &L,int i,int &Value)
{
	if(!L)
		return false;

	LinkList *p = NULL,*q = NULL;

	p = L->next;

	while(p->next && p->next->data != i)
	{
		p = p->next;
	}
	
	q = new LinkNode;

	q->data = Value;
	q->next = p->next;
	p->next = q;

	return true;

}
//指定位置获取数据
bool LinkGetsDataByPos(LinkNode* &L,int i,int &e)
{
	int index = 1;
	LinkList *p = L->next;
	
	if(!L || !L->next)
	{
		cout<<"空玩意儿！";
		return false;
	}
	
	while(p && index 
		p=p->next;
		index++;//计数器 
	}
	
	if(!p || index>i)
	{
		return false;//i值 不合法 :i>n 或 i<=0 
	} 
	
	e = p->data;
	
	return true;
}

//按值获取元素
bool LinkGetsDataByData(LinkNode* &L,int e,int &index) 
{
	LinkList *p = L->next; //p 当前结点 
	index = 1;
	
	if(!L || !L->next)
	{
		return false;
	}
	
	while(p && p->data != e)
	{
		index++;
		p=p->next;//p->next 是下一个结点 
	}
	
	if(!p)
	{
		return false;
	}
	
	return true;
}

//按位置删除
bool LinkDeleteByPos(LinkList* &L,int i)
{
	LinkList *p = L,*q;//要删除的前面一个结点 
	
	int index = 0;
	
	if(!L || !L->next)
	{
		return false;
	}
	
	while((p->next) && (indexnext 指的是当前的结点 
	{
		p = p->next;//找到要删除的节点的前一个结点 
		index++;
	}
	
	if((!p->next) || (index>i-1))// 当 i>n  或 i < 1 时不合理 
	{
		return false; 
	}
	
	q = p->next; //临时保存被删除的结点的地址，以备释放空间 
	p->next = q->next; //使得被删除的结点的前一个结点，指向被删除结点的下一个结点 
	
	delete q; //把被删除的结点的内存释放掉 
	
	return true;
} 

//打印链表 
void PrintLink(LinkList* &L)
{
	LinkNode *pMove = NULL;
	
	if(!L)
	{
		cout<<"链表为空链表！！！";
		return ;
	}
	
	pMove = L->next;//指向头结点了
	
	while(pMove!=NULL)
	{
		cout<data<<" ";
		
		pMove=pMove->next;
	}
	cout<
	LinkList *p = L;

	while(p)
	{
		L= L->next;//指向下一个结点 
		delete p;  //释放当前结点 
		
		p = L;    //赋给p，让p去循环执行释放的工作 
	}
	
	cout<<"n销毁链表！！！" <
	LinkList *L = NULL;
	LinkNode *newNode =NULL;
	//1.初始化空链表 
	InitList(L);
	
	//2.头插法，插入数据
	int num;
	
	cout<<"请输入插入的元素个数:"<>num;
	printf("请以此输入%d个元素:n",num);
	
	for(int i=0;i
		newNode = new LinkNode;
		
		cin>>newNode->data;
		
		ListInsertByHead(L,newNode);
		
		delete newNode;
	} 
	cout<<"n录入完毕!n";
	
	int num1;
	 
	 PrintLink(L);
	
	//3.尾插法 
	cout<<"n请输入插入的元素个数:"<>num;
	printf("请以此输入%d个元素:n",num);
	
	for(int i=0;i
		newNode = new LinkNode;
		
		cin>>newNode->data;
		
		LinkInsertByTail(L,newNode);
		delete newNode;
	} 
	cout<<"n录入完毕!n";
	
	//4.单链表的输出 
	PrintLink(L);
	
	//5.任意位置插入
	int pos;
	int e;
	int n;
	
	cout<<"n请输入要插入的次数:";
	cin>>n;
	
	for(int i=0;i
		cout<<"n请输入要插入的位置和数据:";
	 
		cin>>pos;
		cin>>e;
		
		if(LinkInsertByApoint(L,pos,e) == false)
		{
			cout<<"n插入失败!!!n";
			PrintLink(L);
		}else 
		{
			cout<<"n插入成功！n";
			PrintLink(L);
		}	
			
		
	}
	
	//6.按位置获取元素
	
	int element = 0;

	cout<<"n请输入要按位置获取的次数:";
	cin>>n;
	
	for(int i=0;i
		cout<<"请输入要获取的元素的位置:"<>pos;
		if(LinkGetsDataByPos(L,pos,element))
		{
			printf("n获取第%d个元素成功!!!n",pos);
			cout<<"n获取的数据为:"<
			cout<>n;
	
	for(int i=0;i
		cout<<"请输入要获取的元素的值:"<>element;
		
		if(LinkGetsDataByData(L,element,post))
		{
			printf("n获取元素成功!!!");
			cout<<"n获取元素的链表位置为:"<
			cout<>n;
	
	for(int i=0;i
		cout<<"n请输入要删除的元素位置:";
		cin>>post;
		
		if(LinkDeleteByPos(L,post))
		{
			printf("n删除成功!n");
			PrintLink(L);		
		}else
		{
			cout<<"删除失败"<>i;
	cout<<"请输入插入的元素:";
	cin>>el;
	inserElementByValue(L,i,el); 
	PrintLink(L);	
	
	//9.销毁单链表
	LinkDestroy(L);
	
}
int main()
{
	Test();
	system("pause"); 
	return 0; 
} 
 
三、总结 
1.函数的传递有三种：值传递、指针传递（地址传递）、引用传递。
 2.引用传递的作用：
 （1）二级指针的传递可以借助一级指针的引用。
 （2）“引用”不会产生新的变量，形参就是实参的别名，减少传递时的开销。
 （3）引用后对形参的修改，就是对实参的修改。因此可以把“引用”理解成“类指针”。
 （4）引用可以把形参，在不用return 的情况下就可以把值带出来。
 3.弄懂链表操作的关键是画图，理解每个结点的指针域的指向！一般对一个结点进行操作时，循环指针指向的是其上一个结点，通过上一个结点的*next指针对其进行操作。

单链表的相关操作

C/C++/C#相关栏目本月热门文章