线性表的顺序存储

顺序存储的线性表称顺序表

顺序存储 特点 建立 方式 1地址连续,2随机存取,3顺序存储 1首地址,2储存空间大小,3表长 1静态,2动态

物理顺序存储方式

数组下标顺序表内存地址0a1LOC(A)1a2LOC(A)+sizeof(Elemtype)………i-1aiLOC(A)+(i-1)*sizeof(Elemtype)………n-1anLOC(A)+(n-1)*sizeof(Elemtype)………MaxSize-1…LOC(A)+(MaxSize-1)*sizeof(Elemtype)

优缺点

优点缺点存储密度大，不需要为元素的逻辑关系额外开辟空间插入和删除操作需要移动大量元素，平均时间复杂度O(n)随机存取，可快速存取表中任一元素对存储要求高，会出现存储碎片

（注意，随机存取这个概念很重要，它不是存储）

顺序存储 1、线性表是一种逻辑结构，存储单元地址连续；顺序表和链表是储存结构； 2、线性表的顺序表示

//线性表的静态分配 #define MaxSize 50 //定义线性表的最大长度 typedef struct{//注意：线性表元素位序从1开始，而数组从0开始 ElemType data[MaxSize]; int length; }SqList; //线性表的动态分配 #define InitSize 100 //定义表的初始长度 typedef struct{ ElemType *data; int MaxSize,length; }SeqList; SeqList L;//初始化一个叫做L的线性表 L.data=new ElemType[InitSize]; //动态分配虽然使用指针，但是它不是链式存储，而是顺序存储，因为开辟的空间是连续的

3、顺序表的操作 插入操作 在顺序表第i个元素的位置插入一个新元素e

bool ListInsert(SqList &L,int i,Elemtype e){ if(i<1||i>L.length+1)//判断i的范围是否有效 return false;//顺序表首位是1，末位是length，length+1则正好插到最后 if(L.length>=MaxSize)//储存空间已满，不可插入 return false; for(int j=L.length;j>=i;j--)//注意，这里从length开始减少，因为数组下标从0开始 L.data[j]=L.data[j-1]; L.data[i-1]=e;//注意，这里i-1，因为数组下标从0开始 L.length++; return true; }

删除操作 删除顺序表第i个元素，并把删除元素的值赋给e，返回出来

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.lenth;j++) L.data[j-1]=L.data[j]; L.length--; return true; }

按值查找 在顺序表L中查找第一个元素为e的元素，并返回其位序

int LocateElem(Sqlist L,ElemType e){ int i; for(i=0;i<L.length;i++){ if(L.Data[i]==e){ return i+1; } } }

习题 1、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置又最后一个元素填补，若顺序表为空则显示错误信息并退出运行。

bool Del_Min(SqList &L,ElemType &value){ //删除顺序表L中最小元素节点，并通过引用型参数value返回其值 //若删除成功，则返回true；否则返回false if(L.length==0)return false; value=L.data[0];//先给value一个初值 int pos=0; for(int i=0;i<L.length;i++){ if(L.data[i]<value){ value=L.data[i]; pos=i; } } L.data[pos]=L.data[L.length-1];//空出的位置由最后一个元素填补 L.length--; return true; }

2、设计一个高效算法，将顺序表L中所有元素逆置，要求算法的空间复杂度为O(1)。

void Reverse(SqList &L){ if(L.length==0)return false; if(L.length==1)return true; ElemType temp; for(int i=0;i<L.length/2;i++){ temp=L.data[i]; L.data[i]=L.data[L.length-1-i]; L.data[L.length-1-i]=temp; } return true; }

3、对于长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的元素。

void Del_x(SqList &L,ElemType x){ int k=0,i=0; for(;i<L.length;i++){ if(L.data[i]!=x){ L.data[k]=L.data[i]; k++;//用k记录不等于x的元素个数 } } L.length=k; } 程序的执行过程: 假设起始数列 [a] [b] [x] [c] [d] [x] [e] k=0 i=0 判断真 [a] [b] [x] [c] [d] [x] [e] k=1 i=1 判断真 [a] [b] [x] [c] [d] [x] [e] k=2 i=2 判断假 [a] [b] [x] [c] [d] [x] [e] k=2 i=3 判断真 [a] [b] [c] [c] [d] [x] [e] k=3 i=4 判断真 [a] [b] [c] [d] [d] [x] [e] k=4 i=5 判断假 [a] [b] [c] [d] [d] [x] [e] k=4 i=6 判断真 [a] [b] [c] [d] [e] [x] [e] k=5 for循环结束 L.length = 5 [a] [b] [c] [d] [e]

这段代码所给出的消除方法我确实想不到，背过就好

4、从有序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出运行。 注意，此题是有序表

bool Del_s_t(SqList &L,ElemType s,Elemtype t){ int i,j; if(s>=t||L.length==0)//如果s和t的值不合适或线性表为空，返回错误信息 return false; for(i=0;i<L.length&&L.data[i]<s;i++);//寻找值大于等于s的第一个元素 if(i>=L.length)//没有合适的s，返回错误信息 return false; for(j=i;j<L.length&&L.data[j]<=t;j++);//寻找值小于等于t的第一个元素 for(;j<L.length;i++,j++) L.data[i]=L.data[j]; L.length=i; return true; } [a] [b] [s] [c] [d] [t] [e] 经过i的for循环，i=2 经过j的for循环，j=6 推演第三个for循环 i=2 j=6 判断真 [a] [b] [e] [c] [d] [t] [e] i=3 j=7 判断假 推出循环 L.length=3 [a] [b] [e]

5、从顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，如果s或t不合理或顺序表为空，则显示错误信息并退出运行。

bool Del_s_t(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; } [a] [b] [s] [c] [d] [t] [e] i=0 k=0 判断假 [a] [b] [s] [c] [d] [t] [e] i=1 k=0 判断假 [a] [b] [s] [c] [d] [t] [e] i=2 k=0 判断真 [a] [b] [s] [c] [d] [t] [e] k=1 i=3 判断假 [a] [b] [c] [c] [d] [t] [e] k=1 i=4 判断假 [a] [b] [c] [d] [d] [t] [e] k=1 i=5 判断真 [a] [b] [c] [d] [d] [t] [e] k=2 i=6 判断假 [a] [b] [c] [d] [e] [t] [e] k=2 i=7 循环结束 L.length=L.length-k

6、从有序表中删除所有其值重复的元素，使表中所有元素均不相同。

bool Del_Same(SqList &L){ if(L.length==0) return false; int i,j;//i储存第一个不相同元素j为工作指针 for(i=0,j=1;j<L.length;j++){ if(L.data[i]!=L.data[j]){ L.data[++i]=L.data[j]; } } L.length=i+1; return true; } [a] [b] [b] [c] [d] [e] [e] i=0 j=1 判断真 [a] [b] [b] [c] [d] [e] [e] i=1 j=2 判断假 [a] [b] [b] [c] [d] [e] [e] i=1 j=3 判断真 [a] [b] [c] [c] [d] [e] [e] i=2 j=4 判断真 [a] [b] [c] [d] [d] [e] [e] i=3 j=5 判断真 [a] [b] [c] [d] [e] [e] [e] i=4 j=6 判断假 [a] [b] [c] [d] [e] [e] [e] i=4 j=7 退出循环 L.length=i+1

7、把两个有序表合并为一个新的有序表，并由函数返回结果顺序表。 典型方法，牢固掌握。

bool Merge(SqList A,SqList B,SqList &C){ if(A.length+B.length>C.MaxSize) return false; int i=0,j=0,k=0; while(i<A.length&&j<B.length){ if(A.data[i]<=B.data[j]){ C.data[k++]=A.data[i++]; }else{ C.data[k++]=B.data[j++]; } } while(i<A.length) C.data[k++]=A.data[i++]; while(j<B.length) C.data[k++]=B.data[j++]; C.length=k; return true; } 注意 while(i<A.length) C.data[k++]=A.data[i++]; 其实它的执行顺序是 while(i<A.length){ C.data[k]=A.data[i] k++; i++; }

8、已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…am)和(b1,b2,b3…bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3…bn)放在前面。 这是王道给出的代码，确实非常高效：

typedef int DataType;//方便维护和修改 void Reverse(DataType A[],int left,int right,int arraySize){ if(left>=right||right>=arraySize) return;//如果left或right的参数设置有问题，退出函数 int mid=(left+right)/2; for(int i=0;i<mid-left;i++){//逐个进行调换 DataType temp=A[left+i]; A[left+i]=A[right-i]; A[right-i]=temp; } } void Exchange(DataType A[],int m,int n,int arraySize){ Reverse(A,0,m+n-1,arraySize); Reverse(A,0,n-1,arraySize); Reverse(A,n,m+n-1,arraySize); }

我要是自己做的话，肯定会新开一个数组

9、线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储于计算机内。要求设计一算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素仍递增有序。

//使用折半查找法比较合适 void SearchExchangeInsert(ElemType A[],ElemType x){ int low=0,high=n-1,mid,i,temp;//这里，n就是线性表的长度 while(low<=high){ mid=(low+high)/2; if(A[mid]==x) break;//如果可以找到这个x退出循环 else if(A[mid]<x) low=mid+1;//如果中值比x小，循环体下次研究后半部分 else high=mid-1;//如果中值比x大，研究上半部分 }//下面两个if语句只会执行一个 if(A[mid]==x&&mid!=n-1){//若找到x，与后继元素的值交换 temp=A[mid];A[mid]=A[mid+1];A[mid+1]=temp; } if(low>high){//如果查找失败，即数组里面没有x，插入数据x for(i=n-1;i>high;i--)//high正好是应插入x的前一个位置 A[i+1]=A[i];//元素后移 A[i+1]=x;//这时，x==high } }

10、【2010统考真题】设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间都尽可能高效的算法，将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据 由(X0,X1,…,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)。 要求： 1）给出算法基本设计思想 2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释 3）说明算法的时间复杂度和空间复杂度

ab-->ba ab->a-1b->a-1b-1->(a-1b-1)-1->ba void Reverse(int R[],int from,int to){ int i,temp; for(i=0;i<(to-from+1);i++){ temp=R[from+i]; R[from+i]=R[to-i]; R[to-i]=temp; } } void Converse(int R[],int p,int n){ Reverse(R,0,p-1); Reverse(R,p,n-1); Reverse(R,0,n-1); } 时间复杂度O(n)，空间复杂度O(1)

11、【2011统考真题】一个长度为L(L>=1)的升序序列S，处在第L/2个位置的数称为S的中位数，两个序列的中位数是含它们所有元素的升序序列的中位数。现有等长两个升序序列A和B，试设计一个在时间和空间都尽可能高效的算法，找出AB的中位数。 要求： 1）给出算法基本设计思想 2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释 3）说明算法的时间复杂度和空间复杂度

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]; if(A[m1]<B[m2]){ if((s1+d1)%2==0){ s1=m1; d2=m2; }else{ s1=m1+1; d2=m2; } }else{ if((s2+d2)%2==0){ d1=m1; s2=m2; }else{ d1=m1; s2=m2+1; } } } return A[s1]<B[s2]?A[s1]:B[s2];//三目运算 }