数据结构基础 线性表之单链表

一开始学习数据结构，还是不够熟练，想通过总结的方式，巩固所学的知识，也算是自己成长路上的一些碎片吧！
如果恰好能够帮助到你，那我们一起努力啦

一、单链表的操作

1、初始化

写在程序前面

#include <iostream>
using namespace std;
#define OK 1;
#define ERROR 0;//函数结果状态代码

typedef int Elemtype;//先把Elemtype 定义为int型
typedef int Status;//函数运行状态函数

（1）创建一个结点

struct LNode{
	Elemtype data;
	struct LNode* next;//结点类型的指针

};

(2)初始化，先创建一个头结点，用来管理链表，只需要管理好头就行了

Status Initlist( LNode* &L) {
	L = new LNode;
	L->next = NULL;//头结点的指针域指向空
	return OK;

}

为了方便读程序，用typedef 重命名

typedef struct LNode LNode;
typedef struct LNode* Linklist;//代表链表

(2)主函数创建一个链表，并调用

int main() {
	Linklist L;//创建一个结点类型的指针,指的是链表
	Initlist(L);//调用

以上操作完成链表的初始化

2、插入操作

（1）找到i-1

//插入元素，待插入点
Status ListInsert(Linklist& L,int i,Elemtype e ) {//插入哪个表、插入到哪个位置、插入什么元素
	
	if (i < 1) {
		return ERROR;
	}//非法值
												  
	//要插哪里，找其前一个结点								  
	LNode* p = L;//定义一个指针，把头地址抄过来
	int j = 0;//标记跳到哪里
	while (p && j < i - 1) {//直到==i-1；当传入非法数值的时候，p不能指向NULL;
		p = p->next;
		j++;
	}
	//待插入点已找到，就是p

(2)插入，算法

if (p != NULL) {
		LNode* s = new LNode;//创建一个新节点s，把头给新节点
		s->data = e;
		s->next = p->next;
		p->next = s;//执行顺序不能互换，换了就指向自己本身了p->next=s;s->next=p->next;
	}
	return OK;
}

算法图解：
在这里插入图片描述

3、遍历

(1)p不为空，遍历（2）输出


//遍历   返回值类型是void 
void  bianli(Linklist L) {//这里不是引用，因为不用修改
	LNode* p = L->next;//第一个结点不存放数据，从l->next 开始

	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}

	cout << endl;
}

图解：
在这里插入图片描述

4、取值（按位取值）

（1）要取第i个的值就得先找到i
（2）判断是否是需要找的e
（3）返回OK
（4）在主函数中设计输出格式


//取值 按位取值
Status Getelem(Linklist L, int i,Elemtype &e) {//e是个指针
	LNode* p = L->next;//头结点不存放数据，从下一个结点开始
	int j=1;
	while (p && j < i) {//要的是i
		p = p->next;
		j++;
	}
	if (p != NULL) {
		e = p->data;
	}
	else {
		return ERROR;
	}
	return OK;
}

图解：

5、查找（按值查找）


//查找 按值查找

LNode* LocalElem(Linklist L, Elemtype e) {//返回类型为e 的指针  即地址
	LNode* p = L->next;
	
	while (p != NULL) {//考虑能不能进去
		if (p->data == e) {
			break;
		}
		p = p->next;//往后找，不等于空，一直往后找，直到等于e,跳出来，返回地址，如果一开始就等于空，直接返回空地址
		

	}
	return p;

}

6、删除结点（和插入一样，都需要先找到i-1）

（1）找到i-1

//删除节点

Status Listdelete(Linklist& L, int i) {
	if (i < 1) {
		return ERROR;
	}
	
	//找到i-1
	
	LNode* p = L;
	int j = 0;
	
	while (p != NULL&&j<i-1) {
		p = p->next;
		j++;
	}

（2）删除


	//删除
	if (p!= NULL) {
		LNode* q = p->next;//先把j==i的节点存到q中
		p->next = p->next->next;//越过被删节点
		delete q;
	}
	else {
		return ERROR;
	}

	return OK;
}

图解：
在这里插入图片描述

7、销毁

（1）先把下一个结点存下来
（2）再把本结点删掉
（3）再把下一个结点存进L
（4）直到L指向空了，循环结束


//销毁   返回值类型是void
void Destroylist(Linklist &L){//把表头传进来

	while (L != NULL) {
		LNode* p = L->next;
		delete L;
		L = p;//P指向NULL也就是L==null，循环结束
	}

}

图解：
在这里插入图片描述

8、主函数代码

int main() {
	Linklist L;//创建一个结点类型的指针,指的是链表
	Initlist(L);//调用
	//插入
	cout << "插入几个数:" << endl;
	Elemtype e;
	e = 10;
	ListInsert(L, 1, e);
	e = 11;
	ListInsert(L, 1, e);
	e = 12;
	ListInsert(L, 1, e);
	//遍历
	bianli(L);
	//取值
	Elemtype re;
	Status st = Getelem(L,2,re);
	cout << "找第二个元素" << endl;
	if (st == 1) {
		cout << "找到了" << re << endl;
	}
		else if (st ==0) {
		cout << "没找到！" << endl;
	}
	//查找
	e = 11;
	LNode* s=LocalElem(L, e);
	cout << s << endl;
	//删除
	Listdelete(L, 2);
	cout<<"删除之后的结果："<<endl;	
	bianli(L);
	//销毁
	Destroylist(L);
	return 0;
}

9、运行结果

图示：
在这里插入图片描述

二、源代码

#include <iostream>
using namespace std;
#define OK 1;
#define ERROR 0;

typedef int Elemtype;//先把Elemtype 定义为int型
typedef int Status;//函数运行装态函数


//创建一个结点
struct LNode{
	Elemtype data;
	struct LNode* next;//结点类型的指针

};
typedef struct LNode LNode;
typedef struct LNode* Linklist;//代表链表



//初始化，先创建一个空头结点，管理链表，管理好头就行了
Status Initlist( LNode* &L) {
	L = new LNode;
	L->next = NULL;
	return OK;

}


//插入元素，待插入点
Status ListInsert(Linklist& L,int i,Elemtype e ) {//插入哪个表、插入到哪个位置、插入什么元素
	
	if (i < 1) {
		return ERROR;
	}//非法值
												  
	//要插哪里，找其前一个结点								  
	LNode* p = L;//定义一个指针，把头地址抄过来
	int j = 0;//标记跳到哪里
	while (p && j < i - 1) {//直到==i-1；当传入非法数值的时候，p不能指向NULL;
		p = p->next;
		j++;
	}
	//待插入点已找到，就是p  
	
	//插入操作 
	if (p != NULL) {
		LNode* s = new LNode;//创建一个新节点s，把头给新节点
		s->data = e;
		s->next = p->next;
		p->next = s;//执行顺序不能互换，换了就指向自己本身了p->next=s;s->next=p->next;
	}
	return OK;
}



//取值 按位取值
Status Getelem(Linklist L, int i,Elemtype &e) {//e是个指针
	LNode* p = L->next;//头结点不存放数据，从下一个结点开始
	int j=1;
	while (p && j < i) {//要的是i
		p = p->next;
		j++;
	}
	if (p != NULL) {
		e = p->data;
	}
	else {
		return ERROR;
	}
	return OK;
}


//查找 按值查找

LNode* LocalElem(Linklist L, Elemtype e) {//返回值为e 的指针
	LNode* p = L->next;
	
	while (p != NULL) {//考虑能不能进去
		if (p->data == e) {
			break;
		}
		p = p->next;//往后找，不等于空，一直往后找，直到等于e,跳出来，返回地址，如果一开始就等于空，直接返回空地址
		

	}
	return p;

}

//删除节点

Status Listdelete(Linklist& L, int i) {
	if (i < 1) {
		return ERROR;
	}
	
	//找到i-1
	
	LNode* p = L;
	int j = 0;
	
	while (p != NULL&&j<i-1) {
		p = p->next;
		j++;
	}


	//删除
	if (p!= NULL) {
		LNode* q = p->next;//先把j==i的节点存到q中
		p->next = p->next->next;//越过被删节点
		delete q;
	}
	else {
		return ERROR;
	}

	return OK;
}


//遍历   返回值类型是void 
void  bianli(Linklist L) {//这里不是引用，因为不用修改
	LNode* p = L->next;//第一个结点不存放数据，从l->next 开始

	while (p != NULL) {
		cout << p->data << " ";
		p = p->next;
	}

	cout << endl;
}

//销毁   返回值类型是void
void Destroylist(Linklist &L){//把表头传进来

	while (L != NULL) {
		LNode* p = L->next;
		delete L;
		L = p;//P指向NULL也就是L==null，循环结束
	}

}
int main() {
	Linklist L;//创建一个结点类型的指针,指的是链表
	Initlist(L);//调用
	
	//插入
	cout << "插入几个数:" << endl;
	Elemtype e;
	e = 10;
	ListInsert(L, 1, e);
	e = 11;
	ListInsert(L, 1, e);
	e = 12;
	ListInsert(L, 1, e);
	//遍历
	bianli(L);
	//取值

	Elemtype re;
	Status st = Getelem(L,2,re);
	cout << "找第二个元素" << endl;
	if (st == 1) {
		cout << "找到了" << re << endl;
	}
		else if (st ==0) {
		cout << "没找到！" << endl;
	}	
	//查找
	e = 11;
	LNode* s=LocalElem(L, e);
	cout << s << endl;
	//删除
	Listdelete(L, 2);
	cout<<"删除之后的结果："<<endl;	
	bianli(L);
	//销毁
	Destroylist(L);
	return 0;
}
版权声明：本文为weixin_47198051原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。