当前位置：首页 > article >正文

数据结构--【顺序表与链表】笔记

article 2025/3/13 2:16:49

顺序表

template <class T>
class arrList :public List<T> //表示 arrList 类以公有继承的方式继承自 List<T> 类
//公有继承意味着 List<T> 类的公共成员在 arrList 类中仍然是公共成员，受保护成员在 arrList 类中仍然是受保护成员。
{
private:
	T* aList;  //存储顺序表的实例，以后可以直接拿aList[]当数组用
	int maxSize;
	int curLen;   //顺序表的当前长度
	int position;  //当前处理位置
public:
	arrList(const int size)
	{
		maxSize = size;
		aList = new T[maxSize];
		curlen = position = 0;
	}
	~arrList()
	{
		delete[] aList;
	}
	void clear()
	{
		delete[] aList;
		curLen = position = 0;
		aList = new T[maxSize];
	}
	//查找操作
	bool arrList<T>::getPos(int& p, const T value)
	{
		for (int i = 0; i <= curLen; i++)
		{
			if (aList[i] == value)
			{
				p = i;
				return true;
			}
		}
		return false;
	}
	//插入操作
	bool arrList <T> ::insert(const int p, const T value)
	{
		if (curLen >= maxSize)  //检测当前数组是否越界
 		{ 
			cout << "overflow";  
			return false;
		}
		if (p<0 || p>curLen)   //检测插入位置是否合法
		{
			cout << "illegal";
			return false;
		}
		for (int i = curLen; i > p; i--)
		{
			aList[i] = aList[i = 1];
		}
		aList[p] = value;
		curLen++;
		return true;
	}
	//删除操作
	bool arrList<T> ::delete(const int p)
	{
		if (curLen <= 0)  //判断元素是否为空，空表不能删除
		{
			cout << "no element to delete \n"<<endl;
			return false;
		}
		if (p<0 || p>curLen-1)  //注意这里是p>curLen-1不是curLen
		{
			cout << "illegal";
			return false;
		}
		for (int i = p; i < curLen-1; i++)
		{
			aList[i] = aList[i + 1];
		}
		curLen--;//这里不需要再对aList[curLen-1]进行清零，因为curLen长度已经减小了
		//最后一个元素不在操作范围内
		return false;
	}
};

链表

单链表

head 是指向单链表开始结点的指针，tail 是指向单链表尾结点的指针，对链表的访问只能通过头尾指针进行操作

头结点：虚拟结点，值被忽略，不被看做表中的实际元素，避免对空表的处理

操作分别有：

结点的定义
单链表的类型定义
定义链表的构造函数和析构函数
链表的检索
链表的插入操作
链表的删除操作

说明：Link是模板类，代表着结点

lnkList是单链表类，里面存储着管理链表的方法以及首尾指针

template <class T> class Link  //代表链表中的一个结点
{
public:
	T data;  //保存结点的内容
	Link<T>* next;  //指向后继结点的指针（指向Link类的指针）
	//函数重载，一个是有一个参数的，另一个是有两个参数的
	Link(const T info, const Link<T>* nextValue = NULL)//既有下一个结点的地址，又有data
		//这里是默认值为NULL，即当只传入data时，默认为最后一个结点
	{
		data = info;
		next = nextValue;
	}
	Link(const Link<T>* nextValue)//只指向下一个结点的指针，但是并没有值
	{
		next = nextValue;
	}
};
//单链表的类型定义
//在定义模板类时，必须在类名之前加上模板参数声明template <class T>
template <class T> class lnkList:public List<T>
{
private:
	Link<T>* head, * tail;
	Link<T>* setPos(const int p);   //返回线性表指向第p个元素的指针值
public:
	lnkList(int s);
	~lnkList();
	bool isEmpty();
	...
    bool getPos(int& p, const T value);
};
//带有头结点的单链表的构造函数和析构函数
template<class T> lnkList<T>::lnkList(int defSize)
//在类外定义函数的时候要把模板类写完整了，加上<T>
{
	head = tail = new Link<T>;
}
template <class T> lnkList<T>::~lnkList()
{
	Link<T>* tmp;
	while (head != NULL)
	{
		tmp = head;
		head = head->next;
		delete tmp;
//要先将head值给tmp（注意这里是指针的关系），然后再让head等于下一个指针
//删除了tmp也就相当于删除了第一个head
//如果直接delete head就会丧失对下一个结点的访问权
	}
}
//链表的检索
template <class T> Link<T>* lnkList<T>::setPos(int i)
{
	int count = 0;
	if (i == -1) return head;
	Link<T>* p = head->next;  //创建一个新结点，p指针是一个指向Link类型变量的指针，
	//在这个Link类型变量中是
	while (p != NULL && count < i)
	{
		p = p->next;
		count++;
	}
	return p;
}
//链表的插入
template <class T> bool lnkList<T> ::insert(const int i, const T value)
{
	Link<T>* p,*q;
	//调用 setPos 函数找到插入位置的前一个节点
	if ((p = setPos(i - 1)) == NULL)
	{
		cout << "非法插入点";
		return false;
	}
	q = new Link<T>(value, p->next); //q是新构建的结点
	p->next = q; //将新的q结点插入至p结点之后，也就是说p是q的上一个结点
	if (p == tail)
		tail = q;
	return true;
}
//链表的删除
template <class T> bool lnkList<T>::delete(const int i)
{
	Link<T>* p, * q;
	if ((p = setPos(i - 1)) == NULL || p == tail)
	{
		cout << "非法删除点";
		return false;
	}
	q = p->next;//q是真正的待删结点
	if (q == tail)
	{
		tail = p;
		p->next = NULL;
		delete q;
	}
	else if (q != NULL)
	{
		p->next = q->next;
		delete q;
	}
	return true;
}

链表实验题

顺序表做法

偶遇顺序表难题，用指针+结构体做拼尽全力无法战胜，用数组做十分钟轻松战胜（但是sstream学了一阵子）

#include<iostream>
#include<cmath>
#include<sstream>
using namespace std;
int a[10000], b[10000];
int main()
{
	string line1, line2;
	getline(cin, line1);
	getline(cin, line2);

	stringstream ss1(line1);
	stringstream ss2(line2);
	int m, n;//m是系数，n是指数
	while (ss1 >> m >> n)
	{
		a[n] = m;
	}
	while (ss2 >> m >> n)
	{
		b[n] = m;
	}
	int len = max(sizeof(a) / 4, sizeof(b) / 4);
	for (int i = 0; i < len; i++)
	{
		a[i] += b[i];
	}
	for (int i = len - 1; i >= 0; i--)
	{
		if (a[i] == 0)   continue;
		cout << a[i] << " " << i << " ";
	}
	return 0;
}

链表做法

#include<iostream>
#include<cmath>
#include<sstream>
using namespace std;
class node
{
	int data;
	node* next;
	node(const int info,node* nextnode)
	{
		data = info;
		next = nextnode;
	}
	node(node* nextnode)
	{
		next = nextnode;
	}
};
class list {

};
int main()
{

}

#include<iostream>
#include<cmath>
#include<sstream>
using namespace std;
struct node  //创建新结点
{
	int m;//系数
	int n;//指数
	node* next;
	node(int a, int b)
	{
		m = a;
		n = b;
		next = nullptr;
	}
};
node* creat()//创建多项式列表
{
	node* head = nullptr;  //表示指向第一个结点的指针
	node* tail = nullptr;  //表示当前最新结点的指针，等全部录入完毕就是指向最后一个结点
	string ss1;
	getline(cin, ss1);
	stringstream sss(ss1);
	int a, b;
	while (sss >> a >> b)
	{
//每次新建一个结点，给它一个新的指针
		node* newnode = new node(a, b);  //返回内存地址
		if (!head) head = tail = newnode;
		else
		{
//假设原来链表为A-->B-->C，此时tail指向C，当执行ail->next = newnode时候将C和新结点D连接在一起，
// 链表变成A-->B-->C-->D，然后再把tail更新成最新的D			
			tail->next = newnode; tail = newnode;
		}
	}
	return head;  //返回头指针就是返回整条链表
}
node* add(node* f1, node* f2) {
	node index(0, 0);
	node* tail = &index;
	while (f1 && f2) {
		if (f1->n > f2->n) {
//经典操作，同创建链表里头的
			tail->next = f1;
			tail = tail->next;
			f1 = f1->next;
		}
		else if (f1->n < f2->n) {
			tail->next = f2;
			tail = tail->next;
			f2 = f2->next;
		}
		else {
//如果相等的话就复杂了
			int sum = f1->m + f2->m;
			node* tmp1 = f1;
			node* tmp2 = f2;
//先都往后移动一个结点
			f1 = f1->next;
			f2 = f2->next;
			if (sum != 0) {
				tmp1->m = sum;
//经典操作，连接新结点tmp1并更新tail
				tail->next = tmp1;
				tail = tail->next;
				tail->next = nullptr; // 防止遗留指针，相当于切断了和原来链的联系
//假设 f1 链表为 A(系数 3, 指数 2) -> B(系数 1, 指数 1)，f2 链表为 C(系数 2, 指数 2) -> D(系数 4, 指数 1)。
// 当处理到指数为 2 的节点 A 和 C 时，系数相加结果为 3 + 2 = 5，将 A 的系数更新为 5 并连接到新链表尾部。
// 如果不将 tail->next 置为 nullptr，A 原本的 next 指针仍然指向 B，这会导致新链表中在 A 后面错误地连接了 B，
// 而后续可能会继续错误地处理这些遗留节点。
			}
			else {
				delete tmp1;
			}
//tmp2总是要删的
			delete tmp2;
		}
	}
//其实后面 f1?f1:f2 才是一个整体，如果f1存在，那么就接上f1的值
	tail->next = f1 ? f1 : f2;
//返回首结点的地址
	return index.next;
};

void print(node* f1)
{
	node* cur = f1;
	bool first = true;
	while (cur)
	{
		if (!first)
		{
			cout << " ";
		}
		cout << cur->m << " " << cur->n;
		first = false;
		cur = cur->next;
	}
}
void free(node* f)
{
	while (f)
	{
		node* tmp = f;
		f = f->next;
		delete tmp;
	}
}
int main()
{
	node* f1 = creat();
	node* f2 = creat();
	node* summ = add(f1, f2);
	print(summ);
	free(summ); 
    free(f1);
    free(f2);
	return 0;
}

链表实验选做题

照葫芦画瓢总算出来一个，但是需要逆序输出，但是爷爷懒得写直接存个数组里头逆序输出了hhh

#include<iostream>
#include<sstream>
using namespace std;

struct node
{
	int data;
	node* next;
	node(int a)
	{
		data = a;
		next = nullptr;
	}
};
node* creat()
{
	node* head=nullptr;
	node* tail=nullptr;
	
	string s;
	getline(cin, s);
	stringstream ss(s);
	int a;
	while (ss >> a)
	{
		node* newnode = new node(a);
		if (!head) head = tail = newnode;
		else 
		{
			tail->next = newnode;
			tail = newnode;
		}
	}
	return head;
}
node* order(node* f1, node* f2)
{
	node index(0);
	node* tail = &index;
	while (f1 && f2)
	{
		if (f1->data < f2->data)
		{
			tail->next = f1;
			tail = tail->next;
			f1 = f1->next;
		}
		else if (f1->data > f2->data)
		{
			tail->next = f2;
			tail = tail->next;
			f2 = f2->next;
		}
		else
		{
			
			f1 = f1->next;
			f2 = f2->next;
			
			tail->next = f1;
			tail = tail->next;
			tail->next = f2;
			tail = tail->next;
			
		}
	}
	tail->next= f1 ? f1 : f2;
	return index.next;
}
void print(node* head)
{
	int count = 0;
	int a[100000] = { 0 };
	node* tail = head;
	while (tail)
	{
		count++;
		a[count] = tail->data;
		tail = tail->next;
	}
	for (int i = count; i >= 1; i--) cout << a[i] << " ";
}
void free(node* f)
{
	while (f)
	{
		node* cur = f;
		f = f->next;
		delete cur;
	}
}
int main()
{
	node* f1 = creat();
	node* f2 = creat();
	node* result = order(f1, f2);
	print(result);
	free(result);
	return 0;
}

洛谷单向链表

题目描述

实现一个数据结构，维护一张表（最初只有一个元素 1）。需要支持下面的操作，其中 x 和 y 都是 1 到 106 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 105：

1 x y ：将元素 y 插入到 x 后面；
2 x ：询问 x 后面的元素是什么。如果 x 是最后一个元素，则输出 0；
3 x：从表中删除元素 x 后面的那个元素，不改变其他元素的先后顺序。

输入格式

第一行一个整数 q 表示操作次数。

接下来 q 行，每行表示一次操作，操作具体见题目描述。

输出格式

对于每个操作 2，输出一个数字，用换行隔开。

输入输出样例

输入

输出

75
99

一开始写的完美无瑕的代码~~结果T了两个点~~

#include<iostream>
#include<sstream>
using namespace std;
struct node
{
	int data;
	node* next;
	node(int n)
	{
		data = n;
		next = nullptr;
	}
};
node* setpos(node* head,int x)  
{
	node* cur = head;
	while (cur->data != x)
	{
		cur = cur->next;
	}
	return cur;
}
node* insert(node* head,int x,int y)
{
	node* cur = setpos(head, x);
	node* cur2 = cur->next;
	node* newnode=new node(y);
	newnode->next = cur2;
	cur->next = newnode;
	return head;
}
node* remove(node* head,int x)
{
	node* cur = setpos(head, x);
	node* cur1 = cur->next;	
	cur->next=cur1->next;
	delete cur1;
	return head;
}
void print(node* curnode)
{
	cout <<curnode->data<<endl;
}
void free(node* head)
{
	while (head)
	{
		node* tmp = head;
		head = head->next;
		delete tmp;
	}
}
int main()
{
	int n,k,x,y;
	cin >> n;
	node* index = new node(1);
	node* cur = nullptr;

	for (int i = 0; i < n; i++)
	{
		cin >> k;
		if (k == 1)
		{
			cin >> x >> y;
			index = insert(index, x, y);
		}
		else if (k == 2)
		{
			cin >> x;
			cur= setpos(index, x);
			cur = cur->next;
			if (!cur) {cout << 0<< endl; continue;}
			print(cur);
		}
		else if (k == 3)
		{
			cin >> x;
			index = remove(index, x);
		}
	}
	free(index);
	return 0;
}

那应该是还得优化，但是怎么优化呢，网上优化代码看不懂思密达，但是我会写数组呀嘻嘻

#include<iostream>
#include<sstream>
using namespace std;
int a[1000000];  //a[i]中i表示data，a[i]表示下一个结点的地址（就是第几位）
void insert()
{
	int x, y;
	cin >> x >> y;
	a[y] = a[x];
	a[x] = y;
}
void remove()
{
	int x;
	cin >> x;
	a[x] = a[a[x]];
}
int main()
{
	a[1] = 0;
	int k,n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> k;
		if (k == 1) insert();
		if (k == 2)
		{
			int x;
			cin >> x;
			if (!a[x])
			{
				cout << 0 << endl;
				continue;
			}
			else cout << a[x]<<endl;
		}
		if (k == 3) remove();
	}
	return 0;
}

洛谷临值查找

题目描述

给定一个长度为 n 的序列 A，A 中的数各不相同。

对于 A 中的每一个数 Ai，求：

min1≤j<i∣Ai−Aj∣

以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。

输入格式

第一行输入整数 n，代表序列长度。

第二行输入 n 个整数 A1∼An，代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共 n−1 行，每行输出两个整数，数值之间用空格隔开。

分别表示当 i 取 2∼n 时，对应的 min1≤j<i∣Ai−Aj∣ 和 Pi 的值。

输入输出样例

输入

3
1 5 3

输出

4 1
2 1

全WA（笑）后来发现题目理解错了，人家让找最小的data，不是最小的id

修改后还是错

#include<iostream>
#include<sstream>
#include<cmath>
#include<climits> //使用INT_MAX
using namespace std;
struct node
{
	int data;
	int id;
	node* next = NULL;
	node(int n,int z)
	{
		data = n;
		id = z;
	}
};
void result(node* head, node* cur)
{
	int min_ans = INT_MAX;
	int index = -1;
	int select_val = INT_MAX;
	while (head != cur)
	{
		int cur_data = abs(cur->data - head->data);
		if (cur_data< min_ans||cur_data==min_ans&&head->data<select_val)
		{
			min_ans = cur_data;
			select_val = head->data;
			index = head->id;
		}
		head = head->next;
	}
	cout << min_ans << " " << index << endl;
}

int main()
{
	int n,k;
	cin >> n;
	node* head = NULL;
	node* tail = NULL;
	bool flag = true;
	for (int i = 1; i <= n; i++)
	{
		cin >> k;
		node* newnode = new node(k,i);
		if (!head) { head = tail = newnode; flag = false; }
		tail->next = newnode;
		tail = newnode;
		if(i!=1) result(head, tail);
	}
	return 0;
}

这里出现问题的在于

if (!head) { head = tail = newnode; flag = false; }
		tail->next = newnode;
		tail = newnode;

这里在首结点吧tail的next赋值newnode，造成循环链表，正确写法应该是：

if (!head) { head = tail = newnode; flag = false; }
		else {tail->next = newnode;
		tail = newnode;}

全部改完以后没问题了，但是还是T了四个点

用set优化，快速排序，这样就不用一个一个找了

#include<iostream>
#include<sstream>
#include<cmath>
#include<set>
#include <climits> // 添加头文件以使用INT_MAX
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, val;
	
	cin >> n;
	set<pair<int,int>> nums;
	for (int i = 1; i <= n; i++)
	{
		cin >> val;
		int min_diff = INT_MAX;//记录最小差值
		int min_val = INT_MAX;//记录最小的Aj
		int ans_id = -1;
		if (i == 1)
		{
			nums.insert({ val,i });
			continue;
		}
		auto it = nums.lower_bound({val,0});
		//nums.end() 返回的末尾迭代器不指向任何有效元素
		if (it != nums.end())
		{
			if (abs(val - it->first) < min_diff || abs(val - it->first) == min_diff && it->first < min_val)
			{
				min_diff = abs(val - it->first);
				min_val = val;
				ans_id = it->second;
			}
		}
		if (it != nums.begin()) 
		{
            it--;
		    if (abs(val - it->first) < min_diff || abs(val - it->first) == min_diff && it->first < min_val)
		    {
			    min_diff = abs(val - it->first);
			    min_val = val;
			    ans_id = it->second;
		    }
		}
		cout << min_diff << " " << ans_id<<'\n';
		nums.insert({ val,i });
	}
	return 0;
}

学到了用set的很多知识，比如：

1.set中每一个元素的键值都唯一，所以在向set中插入相同的数据的时候，会插不进去

2.所有元素都会根据元素的字典序进行排序，先比较第一个，第一个一样大就比较第二个，默认从小到大

3.迭代器声明时用auto it=nums容器中某个元素，表示这个元素的时候就用 it->first 和 it->second 来表示

4.nums.end()返回的末尾迭代器不指向任何有效元素

5.用于解除cin和cout的绑定，加快速度防止TLE

ios::sync_with_stdio(false);
cin.tie(0);

6.set声明：set<pair<int,int>>

用STL写链表（蓝桥杯书上的）

#include<iostream>
#include<list>
using namespace std;
list<int> list1;//创建一个STLlist实例
int main()
{
	int n, m, x, y, z;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		list1.push_back(i); //在链表尾部添加元素
	while (m --)
	{
		cin >> x >> y >> z;
		list1.remove(x);
		list<int>::iterator it = find(list1.begin(), list1.end(), y);
		//也可以用auto it定义
		if (z == 0) list1.insert(++it, x);
		if (z == 1) list1.insert(it, x);
	}
	for (int x : list1)
	{
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

知识点：

list1.push_back(x)：将x添加至链表的尾部
pop_back()：删除链表尾部元素
pop_front()：删除链表头部元素
front()：读取头部元素
back()：读取尾部元素
insert(it,x)：在it位置插入元素x
erase(it)：在it位置删除元素，也可以用list1.remove(x)删除x元素

定义迭代器：

list<int>::iterator it = find(list1.begin(), list1.end(), y);
        //也可以用auto it定义

查看全文

http://www.kler.cn/a/582144.html

第42天：WEB攻防-PHP应用MYSQL架构SQL注入跨库查询文件读写权限操作

DeepSeek 助力 Vue3 开发：打造丝滑的表格（Table）之添加列宽调整功能,示例Table14_02带边框和斑马纹的固定表头表格

【从零开始学习计算机科学】操作系统（四）进程的死锁

DeepSeek R1在医学领域的应用与技术分析（Discuss V1版）

Html5学习教程，从入门到精通， HTML5 新的 Input 类型：语法知识点与案例代码（16）

Git创建仓库和基本命令

图纸的安全怎么管理？

Android 粘包与丢包处理工具类：支持多种粘包策略的 Helper 实现

沉浸式CSS学习路径

【实战ES】实战 Elasticsearch：快速上手与深度实践-7.3.2使用GraphQL封装查询接口

C++数组，链表，二叉树的内存排列是什么样的，结构体占多大内存如何计算，类占多大内存如何计算，空类的空间是多少，为什么？

Kotlin学习笔记之类与对象

云创智城 ×YunParking停车源码+YunCharge充电源码+DeepSeek：AI 驱动城市级停车平台升级，构建安全智慧出行新生态

【赵渝强老师】管理MongoDB的运行

c语言程序设计---（动态内存分配）考研复试面试问答

QEMU构建基于ubuntu的根文件系统

vue知识点（2）

Docker基础入门

从0到1搭建前端项目

ROS实践（四）机器人建图及导航

顺序表

链表

单链表

链表实验题

顺序表做法

链表做法

链表实验选做题

洛谷 单向链表

题目描述

输入格式

输出格式

输入输出样例

洛谷 临值查找

题目描述

输入格式

输出格式

输入输出样例

学到了用set的很多知识，比如：

用STL写链表（蓝桥杯书上的）

相关文章：

洛谷单向链表

洛谷临值查找