线性表C++实现(重写了一遍)

哈哈，看到你重写了线性表的C++实现，真的有点小激动呢！毕竟，线性表可是数据结构中的经典“老大哥”，掌握了它，等于在编程的世界里拿了一把“万能钥匙”。那么，我们来聊聊这个话题吧！

首先，你说你把链表和数组写在一起了，这真是个机智的操作！链表灵活但麻烦，数组简单但死板，两者结合简直是一场“互补婚姻”。比如，在处理动态数据时，链表可以随时增减节点，而数组在查找时速度更快。你有没有想过，为什么我们要用两种结构来解决问题？其实，这就是为了在不同场景下找到最优解。

再来谈谈你提到的“主元素”算法。这个问题的核心在于如何高效地找到数组中出现次数超过一半的元素。你有没有想过，如果数据量特别大，比如几百万条数据，暴力遍历的性能就会很糟糕。你的算法用了抵消的思想，很巧妙！但有没有可能进一步优化？比如，能不能用哈希表来统计每个元素的出现次数？当然，哈希表虽然直观，但空间复杂度会高一些，这就是权衡的问题了。

最后，你提到了三元组的最小距离问题。这个问题有点像“数学上的旅行推销员问题”，只不过我们是在三个数组里找最优解。你有没有想过，能不能用贪心算法来一步步缩小范围？或者，如果数组特别大，能不能用并行计算来加速？这些问题都值得深入探讨。

总之，线性表的世界就像是一个迷宫，你每走一步都会发现新的奥秘。希望你能继续探索，找到更多有趣的解法！

我把链表，数组写一起了，用.h文件和.cpp文件写了一遍，没有抄之前的代码，思路可能会有不一样的地方，重要的点都有注释，没有的地方不会的就问我

.h文件

//
// Created by Administrator on 2023/3/31.
//#ifndef SHUJUJIEGOU_LIST_H
#define SHUJUJIEGOU_LIST_H#endif //SHUJUJIEGOU_LIST_Husing namespace std;/* 假设线性表第0位为空，现在用来放线性表长度* 线性表基本操作：* InitList(&L) 初始化表* Length(L) 求表长* LocateElem(L,e) 按值查找* GetElem(L,i) 按位查找* ListInsert(&L,i,e) 插入操作，在表的第i个位置插入元素e* ListDelete(&L,i,&e) 删除操作，删除表上第i个位置的元素，返回给e* PrintList(L) 输出操作* Empty(L) 判空操作* DestroyList(&L) 销毁操作*/
void InitList(int L []);
void Length(int L []);
int LocateElem(const int L [] , int e);
int GetElem(int L[], int i);
void ListInsert(int L [] , int i , int e);
void ListDelete(int L [] , int i , int &e);
void PrintList(int L []);
int Empty(const int L []);
void DestroyList(int L []);
/ 已知一个整数序列A=(a_0,a_1,a_2,...,a_{n-1})，其中0≤a_i≤n(0≤i<n)。如果存在a_{p1}=a_{p2}=...=a_{pm}=x且m>n/2(0≤p_k<n,1≤k≤m)，* 则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的元素保存在一个一维数组中，* 请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则给出该元素；否则输出-1/
int GetMajority(const int L[]);
/ 定义三元组(a,b,c)(a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S_1,S_2,S_3，按升序分别存储在3个数组中。请设计一个尽可* 能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S_1,b∈S_2,c∈S_3)中的最小距离。例如S_1={-1,0,9}, S_2={-25,-10,10,11},* S_3={2,9,17,30,41}则最小距离为2，相应的三元组为(9,10,9)。*/
int GetMinDistance(int S1[], int S2[], int S3[]);//单链表,同时让头指针存链表长度
typedef struct LNode{int data;struct LNode* next;
}LNode,*LinkList;
//初始化链表
LinkList Init_LinkList();
//头插法建立单链表(函数内部就不去再调用cin或者是scanf了，太蠢了，增加一个列表形参,列表处理和上面的列表相同，数据下标从1开始，0位置存长度)
LinkList List_HeadInsert(LinkList &L , const int A []);
//尾插法建立单链表
LinkList List_TailInsert(LinkList &L , const int A []);
//按序号查找节点值
LNode* GetElem(LinkList L, int i);
//按值查找表节点
LNode* LocateElem(LinkList L, int e);
//插值操作：在第p个节点后插入
void LNode_InsertTail(int e, LNode* p);
//插入操作：在第p个节点前插入
void LNode_InsertHead(LinkList L, int e, LNode* p);
//删除节点操作
void Delete_LNode(LinkList L, LNode *p);
//求表长
int GetLength(LinkList L);//有一个带头节点的单链表L，编写算法使其元素递增有序
//方法一：用类似快排的方式去写这个代码，有一个起始指针和一个终止指针，我们的id值是每个子链表的第一个节点，比当前节点小的节点我们删掉然后用头插法
//插进去，比当前节点大的节点我们直接忽略掉，进行下一个节点的判断，id节点最后会移动到一个位置，于是分出了两个子链表。但是毕竟是链表，不是很方便。
//方法二：插入排序
void Sort_LinkList(LinkList L);//给定两个单链表，编写算法写出两个单链表的公共节点的起始位置
LNode* Both_Have(LinkList L1, LinkList L2);//再不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的节点(k为正整数)，若查找成功，算法输出该节点的data值，并返回1，否则只
//返回0
int Get_k_Tail(LinkList L, int k);//现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
void Delete_Same_abs(LinkList L);//设有线性表L=(a_1,a_2,a_3,...a_{n-2},a_{n-1},a_n)采用带头节点的链表存储
// 设计一个空间复杂度为O(1)且时间上尽可能高的算法，重新排列L中的各节点，得到线性表L'=(a_1,a_n,a_2,a_{n-1},...)
LinkList Resort(LinkList L);//双链表
typedef struct DNode{int data ;struct DNode * next;struct DNode * pre;
}DNode, *DLinkList;
//双链表的插入操作(默认为第p位置的后面)
void DNode_InsertTail(DLinkList DL, int e , DNode* p);
//双链表的删除操作
void DNode_Delete(DNode *p);//循环链表//静态链表
//以next==-1作为结束的标志
typedef struct {int data;int next;
}StaticLinkList[INT_MAX];

.cpp文件

//

// Created by Administrator on 2023/3/31.

//

#include <iostream>

#include "../Public/List.h"using namespace std;/* 假设线性表第0位为空，现在用来放线性表长度* 线性表基本操作：* InitList(&L) 初始化表* Length(L) 求表长* LocateElem(L,e) 按值查找* GetElem(L,i) 按位查找* ListInsert(&L,i,e) 插入操作，在表的第i个位置插入元素e* ListDelete(&L,i,&e) 删除操作，删除表上第i个位置的元素，返回给e* PrintList(L) 输出操作* Empty(L) 判空操作* DestroyList(&L) 销毁操作*/void InitList(int L []){int *List = new int [20];L = List;for(int i = 0 ; i < 20 ; i++){L[i] = -1; //初始化}

}void Length(int L []){int i = 0;int count = 0;while(L[i]!=-1){count++;i++;}L[0] = count;}//此处用二分法优化,前提是线性表为一个有序列表

//返回-1表示没有找到

int LocateElem(const int L [] , int e){int low = 1;int high = L[0]-1;int mid ;while(low<high){mid = (low+high)>>1;if (L[mid]>e){high = mid-1;continue;} else if (L[mid]<e){low = mid+1;continue;} else {return mid;}}return -1;}int GetElem(int L[], int i){if (i>=L[0]) return -1;else return L[i];

}void ListInsert(int L [] , int i , int e){

//    判断是否越界if (i>=L[0]){printf("OUT OF BOUNDARY!");return;}else{

//        在表长内，先挪位置for (int j = L[0]; j >= i; --j) {L[j+1] = L[j];}L[i] = e;cout<<L[i]<<endl;L[0]++;}}void ListDelete(int L [] , int i , int &e){

//    判断是否越界if (i>L[0]){cout<<"OUT OF BOUNDARY"<<endl;return;}e = L[i];

//    用覆盖的方式去删除for (int j = i; j <= L[0] ; ++j) {L[j] = L[j+1];}L[0]--;

}void PrintList(int L []){for (int i = 1; i <= L[0]; ++i) {cout<<L[i]<<endl;}

}int Empty(const int L []){if (L[0]==0)return 1;else return 0;

}void DestroyList(int L []){free(L);

}/ 已知一个整数序列A=(a_0,a_1,a_2,...,a_{n-1})，其中0≤a_i≤n(0≤i<n)。如果存在a_{p1}=a_{p2}=...=a_{pm}=x且m>n/2(0≤p_k<n,1≤k≤m)，* 则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的元素保存在一个一维数组中，* 请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则给出该元素；否则输出-1/

int GetMajority(const int L[]){//初始化int id = L[1];int count = 1;//  找出个数最多的那个元素，前面的指定元素个数和后面的其它元素个数相互抵消，只要前面的指定元素够多，那么id所指的元素一定是前面的那个指定元素

//  如果前面的指定元素个数不够多，那么当指定元素的个数被抵消完后，会将下一个元素重设为指定元素，然后继续进行抵消，整个数组遍历下来会有几个情况：

//  1.count结果=0，意味着所有指定元素的个数(赋值给id的元素)等于未指定的所有元素的个数之和(没有给id赋值的)，那么指定过的元素也肯定不是主元素

//  2.count结果>0，意味着这个count所指向的元素就是这个数组内出现次数最多的，但是还需要确定该元素出现的次数是否大于数组长度的一半//  寻找出现次数最多的元素for (int i = 2; i <= L[0]; ++i) {if (id == L[i]){count++;} else{if (count>0){count--;} else{count = 1;id = L[i];}}}//  确定指定元素的出现次数是否大于数组长度的一半if (count>0){count = 0;for (int i = 1; i <= L[0]; ++i) {if (id==L[i]){count++;}}if (count>L[0]/2) return id;else return -1;}return -1;

}/ 定义三元组(a,b,c)(a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S_1,S_2,S_3，按升序分别存储在3个数组中。请设计一个尽可* 能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S_1,b∈S_2,c∈S_3)中的最小距离。例如S_1={-1,0,9}, S_2={-25,-10,10,11},* S_3={2,9,17,30,41}则最小距离为2&#x