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

顺序表

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 是指向单链表尾结点的指针，对链表的访问只能通过头尾指针进行操作

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

操作分别有：

1. 结点的定义
2. 单链表的类型定义
3. 定义链表的构造函数和析构函数
4. 链表的检索
5. 链表的插入操作
6. 链表的删除操作 

说明：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并更新tailtail->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，输出一个数字，用换行隔开。

输入输出样例

输入 

6
1 1 99
1 99 50
1 99 75
2 99
3 75
2 1

输出

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;//记录最小的Ajint 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定义