线性表的顺序表示

0、顺序表的底层是由一维数组实现的，而关于一维数组有两种空间分配方式，分别是静态分配和动态分配：

 1 /*
 2    静态分配
 3    #define MaxSize 20
 4    typedef int ElemType
 5 */
 6 typedef struct Node {
 7     ElemType data[MaxSize];
 8     int Last;
 9 } SqList;
10 /*
11    动态分配
12    #define InitSize  100
13    #define MaxSize 20
14    typedef int ElemType
15 */
16 typedef struct Node {
17     ElemType *data;
18     int Length;
19     int MaxSize;
20 } SqList;
21 
22 /*对于动态分配，其C语言的初始动态分配的语句是：*/
23 
24 L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
25 
26 /*对于动态分配，其C++语言的初始动态分配的语句是：*/
27 
28 L.data=new ElemType[InitSize];

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

 1 bool DelMin(SqList &L,ElemType &value) {
 2     if(L.length==0) {
 3         cout << "顺序表为空";
 4         return false;
 5     }
 6     int min=L.Data[0],pos;
 7     for(int i=0; i<L.Length; i++) {
 8         if(L.Data[i]<min) {
 9             value=L.Data[i];
10             pos=i;
11         }
12     }
13     L.Data[pos]=L.Data[length-1];
14     L.Length--;
15     return true;
16 }

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

1 void Reverse(SqList &L) {
2     ElemType temp;
3     for(int i=0; i<L.length/2; i++) {
4         temp=L.data[i];
5         L.data[i]=L.data[L.length-i-1];
6         L.data[L.length-i-1]=temp;
7     }
8 }

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

1 void del_x(SqList &L,ElemType x) {
2     int k=0;
3     for(int i=0; i<L.length; i++)
4         if(L.data[i]==x)
5             k++;
6         else
7             L.data[i-k]=L.data[i];
8     L.length-=k;
9 }

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

 1 bool del_s_t(SqList &L,ElemType s,ElemType t) {
 2     if(s>=t || L.length==0) {
 3         cout << "s或t不合理或顺序表为空";
 4         return false;
 5     }
 6     int i,j;
 7     for(i=0; i<L.length && L.data[i]<=s; i++)
 8         if(i>=L.length)
 9             return false;
10     for(j=i; j<L.length && L.data[j]<t; j++)
11         for(; j<L.length; i++,j++)
12             L.data[i]=L.data[j];
13     L.length=i;//注意不是i+1
14     return true;
15 }

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

 1 bool del_s_t(SqList &L,ElemType s,ElemType t) {
 2     if(s>=t || L.length==0) {
 3         cout << "s或t不合理或顺序表为空";
 4         return false;
 5     }
 6     int k=0;
 7     for(int i=0; i<L.length; i++)
 8         if(L.data[i]>=s && L.data[i]<=t)
 9             k++;
10         else
11             L.data[i-k]=L.data[i];
12     L.length-=k;
13     return true;
14 }

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

 1 bool DelSame(SqList &L) {
 2     if(L.length==0) {
 3         cout << "顺序表为空";
 4         return false;
 5     }
 6     for(int i=0,j=1; j<L.length; j++)
 7         if(L.data[i]!=L.data[j])
 8             L.data[++i]=L.data[j];
 9     L.length=i+1;
10     return true;
11 }

★7. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

 1 /*由于生成了一个新顺序表，第一个元素需要存在，故采用X.data[i++]格式*/
 2 bool Merge(SqList A,SqList B,SqList &C) {
 3     if(A.length+B.length>C.MaxSize)
 4         return false;
 5     int i=0,j=0,k=0;
 6     while(i<A.length&&j<B.length)
 7         if(A.data[i]<=B.data[j])
 8             C.data[k++]=A.data[i++];
 9         else
10             C.data[k++]=B.data[k++];
11     while(i<A.length)
12         C.data[k++]=A.data[i++];
13     while(j<B.length)
14         C.data[k++]=B.data[j++];
15     C.length=k;
16     return true;
17 }

8. 已知在一维数组A[m + n]中依次存放两个线性表(a1, a2, a3, ..., am)和(b1, b2, b3, ..., bn). 试编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, b3, ..., bn)放在(a1, a2, a3, ..., am)的前面。

 1 typedef int DataType;
 2 void Reverse(DataType A[],int left,int right,int arraysize) {
 3     if(left>=right || right>=arraysize)
 4         return;
 5     int mid=(left+right)/2;
 6     for(int i=0; i<mid-left; i++) {
 7         DataType temp=A[left+i];
 8         A[left+i]=A[left-i];
 9         A[left-i]=temp;
10     }
11 }
12 void Exchange(DataType A[],int m,int n) {
13     Reverse(A,0,m+n-1,m+n);
14     Reverse(A,0,n-1,m+n);
15     Reverse(A,n,m+n-1,m+n);
16 }