C2线性表
2.1线性表的定义和基本操作（结合王道）
2.1.1 definition
线性表L：
1.相同类型数据（每个元素占有相同的大小的储存空间）
2.有限序列
3.顺序性（那句最经典的总结）
**线性表是一种逻辑结构，表示元素之间一对一的相邻关系。**也就是说，只要是一对一这种抽象的逻辑结构咱们都可以称之为线性表。而在物理上的具体的体现是。顺序表和链表。
2.1.2线性表的基本操作
InitList(&L); ... 看书
2.2线性表的顺序表示（结合王道）
2.2.1definition
逻辑物理位置都相邻。===>顺序表。
这是静态分配好的。基本就是改动不了。想要改变只能重新定义数组。
#define Maxsize 50 typedef struct { ElemType data[maxsize]; int length; }sqlist;
做一点改变，让他动态一点：
#define InitSize 100 Typedef struct { ElemType *data; int MaxSize,length; }SeqList; L.data =(ElemType*)malloc(sizeof(ElemType)*InitSize);//动态扩展内存。
总结一下特点：
随机访问；
找到元素的时间复杂度为O（1）；
删除，插入为O（n）;
2.2.2 based oparation:
1.插入：
bool ListInsert(sqlist *L,int i,ElemType e) //bool 数据说明返回的是true and false ,分别代表1，0； //？？？？sqlist &L====sqlist *L; { if(i<1||i>L.length+1) return false; if(L.length>=MaxSize) return false; for(int j=L.length;j>=i;j--) L.data[i]=L.data[i-1]; L.data[i-1]=e; L.length++; return ture; } 插入： O（1）； O（n）; 平均：n/2===========>O（n）;//结合概率论。求期望。
2.删除：
bool Listdelete(SqList *L,int i,Elemtype *e) { if(i<1 || i>L.length) return false; e=L.data[i-1]; for(int j=i;j<L.length;j++) L.data[j-1]=L.data[j]; L.length--; return true; } 删除： O（1）； O（n）; 平均：n/2===========>O（n）;//结合概率论。求期望。
3.查找：（顺序地往下查找值为e的元素，返回位序）
int LocateElem(Sqlist L,ElemType e) { int i; for(i=0;i<L.length;i++)//L.length是线性表长，元素个数。MAXSIZE是数组大小，MAXSIZE-1是数组下标。 if(L.data[i]==e) return i+1; return 0; } 查找： O（1）； O（n）; 平均：n/2===========>O（n）;//结合概率论。求期望。
!!!王道习题p19
1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删的数值。空出的位置由最后一个元素填补，若顺序表为空显示出错信息并且退出。
算法思路: 1.遍历顺序表，找出最小值（若顺序表为空显示出错信息并且退出）。 2.把最小地址数值另外一个变量中，输出。 3.然后把最后一个变量的数值赋值给他。 4.删除最后一元素的数值。 #define Maxsize 50 typedef struct { ElemType data[maxsize]; int length; }sqlist; bool Delete_Min(sqList &L,ElemType *value { if(L.length==0) return false; value=L.data[0]; int pos=0; for(int i;i<L.length;i++) if(L.data[i]<value) { value=L.data[i]; pos=i; } L.data[pos]=L.data[length-1];//赋值实则把存储在原空间的值给拿走了 空间也就空出来了 L.length--; return 0 }
2.将顺序表所有的元素逆置，要求空间复杂度为O(1) //辅助空间:储存一些为实现计算所需要的信息。 //算法原地工作是指算法所需要的辅助空间为常量， //其空间复杂度为O(1)。 void Reverse(Sqlist &L) { Elemtype temp; for(i=0;i<L.length/2;i++) { temp=L.data[i]; L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=temp; } }
3.对长度为n的线性表L，编写一个时间复杂度为O(n),空间复杂度为O(1)的算法，要求删除线性表虽有数值为x的元素。 /*思路：遍历每一个元素，如果这个元素的数值等于x,则删除。 如果这个元素的数值不等于x，则跳过去判断下一个。*/ Linklist Listdelete(SqList &L) { int i=0; for(i=0;i<=length;i++) if(L.data[i]=x) { for(int j=i;j<L.length-1;j++) L.data[j]=L.data[j+1]; L.length--; } return L; } 错：时间复杂度O(n^2)见证两个神奇的算法： 用k记录不等于x的元素累加，然后往前移动k个元素。最后修改长度； void del_x_1(Sqlist &L,Elemtype x) { int k=0; for(i=0;i<L.length;i++) { if(L.data[i]!=x) { L.data[k]=L.data[i]; k++; } } L.length=k; } 用k记录线性表中等于x的元素的个数。将不等于K的元素往前移动k个元素。最后修改长度。 void del_x_1(Sqlist &L,Elemtype x){ int k=0,i=0; while(i<L.length){ if(L.data[i]==x) k++; else L.data[i-k]=L.data[i]; i++; } L.length=L.length-k; }
4.从有序顺序表中删除其数值在给定数值s到t之间（s 如果s或t不合理或者顺序表为空，则显示出错信息并退出运行。 /*算法思路： ##注意是有顺序的顺序表，即这一顺序表是按照从小到大或者从大到小排列。 先寻找数值大于或者等于s的第一个元素，（第一个删除的元素）。 然后寻找数值大于t的第一个元素（最后一个删除的元素的元素下一个元素）， 要想要将这段元素删除，只需要将后面的元素前移动。*/ bool Del_s_t2(SqList &L,ElemType s,Elemtype t) { int i,j; if(s>=t||L.length==0) return false; for(i=0;i<L.length&&L.data[i]<=s;i++); if(i>=L.length) return false; for(j=i;j<L.length&&L.data[j]<=t;j++); i=i;//无意义的语句。此时找到了s与t. for(;j<L.length;i++,j++) { L.data[i]=L.data[j]; } L.length=i; return true; } 归纳：本题目告诉我们有序顺序表那必须是从小到大排序。 如果想删除某一段区间里面的元素， 那么你必须先找到大于最小值的第一个元素以及大于最大值的第一个元素。 然后把后面赋值给前面的元素，结束条件是后面的元素给到表结束， 那么前面的元素就是表长。
5.从顺序表中删除其数值在给定值s与t之间（包含s,t,要求s 如果s或t不合理或者顺序表为空，则显示出错信息并退出运行。 注意是无序的 bool Del_s_t2(SqList &L;ElemType s;Elemtype t） { if(s>=t||L.length==0) return false; int k=0; for(int i=0;L.data[i]>=s&&L.data[i]<=t;i++) { for(int j=i;j<L.length;j++) L.data[j]=L.data[j+1]; k=k+1; } L.length=L.length-k; return true; //我这个算法可以是可以，但是时间复杂度很高； 王道书上推荐算法： bool Del_s_t2(SqList &L;ElemType s;Elemtype t）{ int i,k=0; if(L.length==0||s>=t) return false; for(i=0;i<L.length;i++){ if(L.data[i]>=s&&L.data[i]<=t) k++; else L.data[i-k]=L.data[i]; } L.length-=k; return true; } //算法精妙，可以记录k，然后一个一个往前移动k。
6.从有序顺序表中，删除所有重复的元素，是表中的元素的数值都不相同。 bool delete(sqlist &L,Elemtype e){ int k=0; int p=0 if(L.length==0) return false; for(int i=0;i<=L.length;i++){ e=L.data[i]; for(int j=i+1;j<=L.length;J++){ if(L.data[j]=e) k=k+1; else L.data[j-k]=L.data[j] } p=p+k; k=0; } L.length=L.length-p; return true; } answer://从会面往前面插入，如果说前面这个元素和待插入的不同，没事往后插上去，如果说这两元素同，那么就不插入（不管他）。 bool Delete_same(SeqList &L){ if(L.length==0) return false; int i,j; for(i=0,j=1;j<L.length;j++) if(L.data[i]!=L.data[j]) L.length=i+1; return true; }
