（此文仅用于记录我复习数据结构的过程，以便个人后续复习用）
绪论：
数据：信息的载体
数据项：最小不可分割单位，如一个人的名字
数据元素：数据的基本单位，由若干个数据项组成
数据类型：1.原子类型：int、char等；2.结构类型：struct；3.抽象数据类型。
数据结构三要素：逻辑结构，存储结构（物理结构），数据的运算
1.逻辑结构又分为线性结构与非线性结构，逻辑结构与存储结构无关，独立于计算机
线性结构：线性表、栈、队列（线性结构：一对一关系）
非线性结构：树、图、集合（集合：同属于一个集合，无其他关系；树形结构：一对多；图状结构：多对多）
2.存储结构分为：顺序存储、链式存储、索引存储、散列存储；存储结构是用计算机语言实现的逻辑结构，依赖于计算机语言；
顺序存储：物理位置也相邻，优点是可随机存取，缺点是只能使用相邻的一整块存储单元；
链式存储：物理位置可以不邻，使用地址指针表示逻辑关系，优点可以充分利用所以存储单元，缺点是每个元素都要存放指针占用空间，且只能实现顺序存取；
索引存储：存储元素同时建立一个索引表（存放索引项：地址，关键字），优点是检索速度快，缺点是索引表占用额外存储空间，增删数据还要修改索引表，浪费时间。
散列存储：根据元素关键字直接计算出该元素的存储地址，又叫哈希存储。优点是增删改查都很快，缺点是若散列函数不好，可能出现冲突而浪费时间空间。
3.数据的运算：定义+实现。定义针对逻辑结构（文字表达都行），传达功能；实现针对存储结构，指出具体操作步骤。
算法：指令的有限序列。有穷性（有穷步、有限时间）、确定性（同输入同结果）、可行性、输入（0或多）、输出（1或多）。
好算法：正确性、可读性、健壮性（非法数据不会出bug）、效率与低存储量需求。
算法效率度量：时间复杂度、空间复杂度
时间复杂度：只看数量级。看循环。多个循环加起来看最高，循环嵌套相乘。
空间复杂度：原地工作即辅助空间为常量。考虑存放数据结构类型、函数自身调用等情况计算。
1<log2N<n<nlog2N<幂函数（n平方）<指数函数（2的n次方）<n的阶乘<n的n次方
线性表：
数据类型相同的有限序列，n为0时为空表。a1表头，an表尾。
基本操作：
InitList(&L) 初始化空表
Length(L) 表长，元素个数
LocateElem(L,e) 按照值e查找
GetElem(L,i) 按照位置i查找
ListInsert(&L,i,e) 在第i个位置插入值e的元素
ListDelete(&L,i,e) 删除第i个位置的元素，e返回删除元素的值
PrintList(L) 按序输出所有元素
DestroyList(&L) 销毁线性表，释放空间
线性表中顺序表表示：
逻辑结构与物理结构相同，地址连续。
第i个元素的地址为：LOC(A)+sizeof(元素数据类型)*（i-1），i小于最大表长。
静态分配：（利用数组）
#define MaxSize 100 //最大长度
typedef struct {
ElemType data[MaxSize]; //元素
int length; //当前长度
}SqList;动态分配：可以随时扩大空间
#define InitSize 100 //定义初始长度
typedef struct {
ElemType *data; //指示动态分配的指针
int MaxSize,length; //数组最大容量及当前长度
}SqList;L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
//初始分配空间插入操作：
bool ListInsert(SqList &L, int i, ElemType e){
if(i<1||i>L.length+1)
return false; //i需要在范围内
if(L.length>=MaxSize)
return false; //顺序表不能原本就是满的
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1]; //从最后一个元素开始，每个元素向后移动一位
L.data[i-1]=e; //将值e赋给第i个元素
L。length++; //表长度加1
return true;
}
//使用布尔型是为了方便使用者判断插入操作是否成功时间复杂度：
最好情况：插入最后位置，时间复杂度为1
最坏情况：插入第一个位置，时间复杂度为n
平均情况：为n；
删除操作：
bool ListDelete(SqList &L, int i, ElemType &e){
if(i<1||i>L.length+1)
return false; //i需要在范围内
e=L.data[i-1]; //将被删除元素的值赋给e用于返回存储
for(int j=i;j<L.length;j++)
L.data[j-1]=L.data[j-]; //从需要删除得到元素开始，每个往前移一位
L.data[i-1]=e; //将值e赋给第i个元素
L.length--; //表长度减一
return true;
}时间复杂度：平均为n
按值查找（即按顺序比对）
int LocateElem(Sqlist L,ElemType e){
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1; //一个一个按顺序比对后返回值为1的元素位序
return 0; //查找失败，返回0
}时间复杂度：平均为n
按位查找（即随机存取）
int GetElem(Sqlist L, int i){
return L.data[i-1]; //直接返回第i个元素的值
}时间复杂度：为1
练习
?思路：
题目要我们实现的是类似：数组【1，2，3，4，5，6，7】，左移3个元素，变成数组【4，5，6，7，1，2，3】
那我们从第p个元素开始，将p及其之前的元素转置，即变为【3，2，1】，再将p之后元素也转置，即变为【7，6，5，4】，数组此时为【3，2，1，7，6，5，4】，再将整个数组转置，即可得到【4，5，6，7，1，2，3】，符合题意。
代码实现：
void Reverse(int R[], int from, int to){
int i, temp;
for(i=0;i<(to-from+1)/2;i++){
temp=R[from+i];
R[from+i]=R[to-i];
R[to-i]=temp;
}
} //转置操作，from为初始位置，to为转置完的位置
void Converse(int R[], int n, int p){
Reverse(R, 0, p-1);//转置第一个到第P个元素的位置
Reverse(R, p, n-1);//转置第P个到最后一个元素的位置
Reverse(R, 0, n-1);//转置上述操作完成的数组得到最终结果
} //完成上述操作一共分3步，第一步要进行P/2次，第二步要进行(N-P)/2次，第三步要进行N次，故时间复杂度为O(n)
只增加了变量i和temp，故空间复杂度为O(1)
总结：
该算法比较简单，需要注意的是，位序和数组下标的关系，不要搞混了。
另有其他解法，可以创建一个暂存数组S，把前P个元素存在暂存数组里面，然后直接把R中后面的元素左移P个，最后把暂存数组S中的元素续到R后。时间复杂度同样为O(n），但由于创建了一个暂存数组S，存放了P长度的数组，故空间复杂度为O(p)。
思路：
先要理清楚，两个序列中位数和最终所求的中位数有什么关联。可以得到，所求的中位数，一定是位于两个序列中位数的中间值，例如题中11位于6和15之间，那么比较小中位数还要小的数字对解题就没有意义，同理，比较大中位数还要大得到数字也没意义。
那么对于二者的中位数，设S1中位数为a，S2中位数为b，则进行以下操作：
1.a=b，结果即为题目所求；
2.a<b，舍弃a中较小的一半，舍弃b中较大的一半，得到新的S1以及S2；
3.a>b，舍弃b中较小的一半，舍弃a中较大的一半，得到新的S1以及S2；
对数组不断进行上述判断，并进行相应操作，直至满足条件两个序列都只剩一个元素时，较小的那个即为题目所求。
代码实现：
int M_Search(int A[],int B[], int n){
int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
//分别表示序列A和B的首位、末位以及中位数位置
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]==B[m2])
return A[m1];//满足条件1
if(A[m1]<B[m2}{ //满足条件2
if((s1+d1)%2==0){
s1=m1;//放弃A前半部分元素
d2=m2;//放弃B后半部分元素
}//考虑元素个数为奇数
else{
s1=m1+1;//放弃A前半部分元素
d2=m2;//放弃B后半部分元素
}//考虑元素个数为偶数
else{ //满足条件3
if((s2+d2)%2==0){
s2=m2;//放弃B前半部分元素
d1=m1;//放弃A后半部分元素
}//考虑元素个数为奇数
else{
s2=m2+1;//放弃B前半部分元素
d2=m2;//放弃A后半部分元素
}//考虑元素个数为偶数
}
}
retrun A[s1]<B[s2] ? A[s1]:B[s2];//取剩下的A、B序列中位数的较小的一个，即为题目所求
}由于每次操作元素都会变为原来的一半，设操作次数为k，即有2的k次方=n，则k=log2n，故时间复杂度为O(log2n)，并未引入其他数据结构，空间复杂度为O(1)
总结：由于两个都是同等长度的升序序列，所以只需要先思考中位数的关系，在分析算法，而不是直接把两个序列合起来排序再找中位数，这样太过复杂，先考虑数学关系，再考虑算法实现！！需要注意的是，有奇数偶数两种情况时需要分开讨论，避免出错。可以先在草稿上写几个符合题意的序列，自己用笔跑一下，再考虑代码实现，避免做无用功。
思路：
主元素即为一个数组中，出现次数最多且次数过总数一半的元素。因为数组中每一个元素都有成为主元素的可能性，故需要从前往后扫描整个数组。
初始思路是，依次扫描数组，获取一个数作为候选主元素，然后扫描整个数组，记录该元素出现个数；然后重新扫描数组，选取第二个与前一次不同的数作为候选主元素，重复扫描整个数组，记录该元素出现次数；不停重复上述操作，直至所有不同的数都成为过候选主元素。但这个思路实现起来太过于麻烦，因为会有太多次扫描整个数组的过程，不可取。
优化思路是，由于我发现乱序会出现太多次重复扫描的情况，考虑到是否可以先对数组进行排序后再统计，这样某个数的坐标差值即为其出现次数，这样求得时间复杂度即为O(nlog2n)，好像仍然过于复杂。
最终优化思路是，扫描数组，将遇到的第一个数，用一个变量保存，称为候选主元素，记录次数为1，然后继续扫描下一个，若为该数字，将记录次数+1，若不为该数字，将记录次数-1，知道记录次数=0时，选取下一个数字作为候选主元素。开始新一轮计数，从当前位置开始重复上述过程，直到扫描完所有数组元素。最后留存在变量中保存的数字，极有可能是主元素，但也不一定。所以需要重新扫描该数组，记录该数字出现的次数，与n/2对比，若大于则是，否则，则没有主元素。
代码实现：
int Majority(int A[],int n){
int i,temp,count=1;//用temp保存候选的主元素，count用来计数
temp=A[0];
for(i=1;i<n;i++)//扫描查找候选主元素
if(A[i]==temp)
count++;//对候选主元素计数
else //处理扫描到不是候选主元素的情况
if(count>0)//若计数仍大于0
count--;
else{ //更换候选主元素
temp=A[i];
count=1;//重新开始计数
}
if(count>0)
for(i=count=0;i<n;<i++)//统计候选主元素出现次数
if(A[i]==temp)
count++;
if(count>n/2)
return temp;//确认主元素
else
return -1;//不存在主元素
}此算法由于只会扫描2遍（即查找时扫描和验证时扫描），故时间复杂度为O(n）。而未引入其他数据结构，故空间复杂度为O(1)。
总结：该问题最后代码实现其实并不复杂，需要考虑的是如何实现才会使得操作更加简单编辑快速。其次，需要注意的是，如果是面对408统考，需要考虑的不是如何最优化算法，而是代码的正确性，倘若在有限的时间内难以想出优化的算法，选择代码好写的那一种。（只要能解决问题即可获得绝大多数分数，而最优解只会高1-2分）