[线性表](1)顺序线性表
线性表是一线性结构，我们已了解到的数组和链表都属于线性表
线性表的特点是：在数据元素的非空有限集中
- 存在唯一的一个被称做“第一个”的数据元素
- 存在唯一 的一个被称做“最后一个”的数据元素
- 除第一个之外，集合中的每个数据元素均只有一个前驱
- 除最后一个之外，集合中的每个数据元素均只有一个后驱
对于这个我们可以拿数组a[3]来理解，a[3]中的元素包括a[0]、a[1]、a[2]
那么a[0]为第一个元素，a[2]为最后一个元素，a[1]只有一个前驱a[0]、a[1]只有一个后驱a[2]
线性表(linear_list)是最常用且最简单的一种数据结构，简而言之，一个线性表是n个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同，他可以是一个数或者一个符号，也可以是复合型数据
例如，26个字母可构成的顺序线性表（A、B、C、D......Z）
表中的数据是单个字母字符，又如，某校从1978到1983年各种型号的计算机拥有量的变化，可用线性表表示：（6、17、28、50、92、188）
表中的数据元素是整数
在稍复杂的线性表中，一个数据元素可以由若干个数据项(itme) 组成，在这种情况下，常把数据元素称为记录(record)，含大量记录的线性表又称为文件(file)
线性表中的元素个数n(n>=0)定义为线性表的长度，n=0时称为空表，在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai，在线性表中的位序
线性表示一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等
抽象数据类型线性表的定义如下：
ADT List
{
数据对象：D{ai | ai属于ElemSet，i = 1,2，...，n，n >= 0}
数据关系：R1 = {<ai - 1,ai> | ai - 1 > ,ai属于D，i = 2，....，n}
基本操作：
InitList(&t)
操作结果：构建一个空表L
DestroyList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将L重置为空表
ListEmpty(L)
初始条件：线性表L已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE
ListLength(L)
初始条件：线性表L已存在
操作结果：返回L中数据元素个数
GetElem(L,i,&e)
初始条件：线性表L已存在
操作结果：用e返回线性表中第i个元素的值
LocateElem(L,e,compare())
初始条件：线性表L已存在
操作条件：返回L中第1一个与e满足关系compar()的数据元素的位序
若这样的数据元素不存在则返回0
PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在
操作结果：若cur_e是L中的数据元素，且不是第一个
则用pre_e返回它的前驱，否则操作失败pre_e无定义
NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个
则用next_e返回它的后继，否则操作失败cur_e无定义
ListInsert(&L,i,e)
初始条件：线性表L已存在，1 <= i <= ListLength() + 1
操作结果：在L中第i个位置之前插入新的数据元素e，L的表长加1
ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，1 <= i <= ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ListTraverse(L,visit())
初始条件：线性表L已存在
操作结果：依次对L的每个数据元素调用函数visit()
一旦visit()失败，则操作失败
}ADT List对上述定义的抽象数据类型线性表，还可进行一些更复杂的操作，例如：
- 将两个或两个以上的线性表合并成一个线性表
- 把一个线性表拆开成两个或两个以上的线性表
- 重新复制一个线性表
一、
假设利用两个线性表LA和LB分别表示两个集合A和B（线性表中的数据元素即为集合中的成员），现要求一个新的集合A=A U（相交） B。
这就要求：
- 扩大线性表 LA，将存在于线性表LB中而不存在线性表LA中的数据元素插入到线性表LA中去，只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。
上述操作可用算法（抽象实现）：
void union(List& La, List& Lb)
//将所有在线性表Lb中但不再La中的数据元素插入到La中
{
La_len = ListLength(La);//求线性表长度
Lb_len = ListLength(Lb);//求线性表长度
for (i = 1; i <= Lb_len; i++)
{
GetElem(Lb, i, e);
if (!LocateElem(La, e, equal))
{
ListInsert(La, ++La_len, e);
}
}
}首先将La和Lb的实际参数两个链表复制到形参中，类型为线性表。无返回值，函数名为union
然后定义两个变量La_len和Lb_len
- 利用ListLength函数求出La的长度赋值给La_len
- 利用ListLength函数求出Lb的长度赋值给Lb_len
for循环的作用是将i从1开始，直到Lb_的长度
然后调用GetElem(Lb,i,e)函数，将Lb中第i个元素传入e内
再进行判断，LocateElem函数，第一参数为La，则将e放到La中判断La中是否与其相等的数，若有，则返回该数，若没有，则返回0
前边有个逻辑非运算符，就是说，返回0的时候代表没有，则表达式为真，进入if语块
然后调用ListInsert(La,++La_len,e)，将La中第++La_len的位置插入e，++La_len就是末尾插入，当然这时La的长度得扩大一位
C语言实现:
#include<stdio.h>
#include<stdlib.h>
void GetElem(int*, int, int*);
int ListLeng(int*);
int LocateElem(int*, int, int);
void ListInsert(int*, int, int);
int main()
{
int a[10] = { 1,2,3 };
int b[10] = { 2,3,4,5,6 };
int La_len = ListLeng(a); int Lb_len = ListLeng(b);//计算长度
int i, e = 0, equal;
for (i = 0; i <Lb_len; i++)
{
GetElem(b, i, &e);//从b中取出数传入a中
if ((equal = LocateElem(a, e, La_len)) == 0)//判断a中没有的数
{
ListInsert(a, La_len++, e);//将它放到数组a中
}
}
for (int l = 0; l <La_len; l++)/*输出*/
{
printf("%d", a[l]);
}
system("pause");
return 0;
}
int ListLeng(int* c)
{
int i = 0, j = 0;
while (c[i] != NULL)
{
j++;
i++;
}
return j;
}
void GetElem(int* b, int i, int* e)
{
*e = b[i];
}
int LocateElem(int* a, int e,int len)
{
for (int i = 0; i < len; i++)
{
if (a[i] == e)
{
return e;
}
}
return 0;
}
void ListInsert(int* a, int b, int c)
{
a[b] = c;
}我们来看看有哪些基础算法
二、
已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列，例如：
- LA = (3,5,8,11)
- LB = (2,6,8,9,11,15,20)
则：LC = (2,3,5,6,8,8,9,11,11,15,20)
从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素插入到LC中即可，为使LC中元素按值非递减有序排列
可设两个指针i和j分别指向LA和LB中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到LC中的元素c为
当a<=b时，c=a，当a>b时，c=b。
显然，指针i和j的初值均为1，在所指元素插入LC之后，在LA或LB中顺序后移，上述归并算法可表示为：
void MergeList(List La, List Lb, List& Lc)
{
//已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列
InitList(Lc);
int i, j, k;
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len))
{
GetElem(La, i, ai);
GetElem(La, b, bj);
if (ai <= bj)
{
ListInsert(Lc, ++k,ai);
++i;
}
else
{
ListInsert(Lc, ++k, bj);
++j;
}
}
while (i <= La_len)
{
GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai);
}
while (j <= Lb_len)
{
GetElem(Lb, j++, bj);
ListInsert(Lc, ++k, bj);
}
}C语言实现：
#include<stdio.h>
#include<stdlib.h>
int ListLength(int*);
void GetElem(int*, int, int*);
void ListInsert(int*, int, int);
int main()
{
int a[10] = { 3,5,8,11 };
int b[10] = { 2,6,8,9,11,15,20 };
int a_len, b_len;
/*计算长度*/
a_len = ListLength(a);
b_len = ListLength(b);
int c[20] = { 0 };
int i, j, k;
i = j = 0;
k = 0;
int ai = 0, bj = 0;
while ((i < a_len) && (j < b_len))
{
GetElem(a, i, &ai);
GetElem(b, j, &bj);
if (ai <= bj)
{
ListInsert(c, k++, ai);
++i;
}
else
{
ListInsert(c, k++, bj);
++j;
}
}
while (i < a_len)
{
GetElem(a, i, &ai);
ListInsert(c, k, ai);
}
while (j < b_len)
{
GetElem(b, j++, &bj);
ListInsert(c, k++, bj);
}
k = 0;
while (c[k] != NULL)
{
printf("%d ", c[k]);
k++;
}
system("pause");
return 0;
}
int ListLength(int* a)
{
int i = 0, j = 0;
while (a[i] != NULL)
{
i++;
j++;
}
return j;
}
void GetElem(int* d, int i, int* e)
{
*e = d[i];
}
void ListInsert(int* a, int k, int p)
{
a[k] = p;
}这题有点像我们接触过的插入算法，值得庆幸的是，在排序之前，两个数组之中的值都是有序排列的，不然还需要排序好一个数组后，将它作为有序组
上述两个算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间。
假设GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比
则第一个算法的时间复杂度为O(ListLength(La)*ListLength(Lb))
第二个算法的时间复杂度为O(ListLength(La)*ListLength(Lb))，虽然第二个算法包揽着三个while循环，但只有当i和j均指向表中实际存在的数据元素后，再通过其中一个循环将剩余元素传入进去即可，因此，只会执行其中一个循环
线性表的顺序表示和实现
线性表的顺序表示是指用一组地址连续的存储单元一次存储线性表的数据元素
假设线性表的每个元素需要占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置
则线性表中第i+1个数据元素的存储位置LOC(a(i+1))和第i个数据元素的存储位置LOC(ai)之间满足下列关系：
LOC(a(i+1))=LOC(ai)+l
一般来说，线性表的第i个数据元素ai的存储位置为：
LOC(ai) = LOC(ai)+(i-1)*l
上述的LOC(ai)是线性表的第一个数据元素ai的存储位置，通常称做线性表的起始位置或基地址
这种表示的线性表被称为线性表的顺序存储结构或顺序映像(sequential map-ping)
通常，称这种存储结构的线性表为顺序表，它的特点是：
- 为表中相邻的元素ai和a(i+1)赋以相邻的存储位置LOC(ai)和LOC(ai+1)
- 以元素在计算机内的“物理位置相邻”来表示线性表中的数据元素之间的逻辑关系
- 每一个数据元素的存储位置都和线性表的起始位置 相差一个和数据元素在线性表中的位序成正比的常数
只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随即存取，所以线性表的顺序结构是一种随即存取的存储结构
由于高级程序设计语言中的数据类型也有随即存取的特性，因此，通常用数组来描述数据结构中的顺序存储结构
由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语音中可用动态分配一维数组，如下描述：
#define LIST_INIT_SIZE 100;//线性表存储空间的初始分配
#define LISTINCREMENT 10;//线性表存储空间的分配增量
typedef struct
{
ElemType* elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配到存储容量(以sizeof(ElemType)为单位)
}SqList;在上述定义中，elem指针指示线性表的基地址，length指示线性表的当前长度。
顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”
listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT
抽象代码实现一维动态数组分配如下：
Status InitList_Sq(SqList& L)
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
{
exit(OVERFLOW);//分配失败
}
L.length = 0;//空表长度为0
L.listsize = LIST_INIT_SIZE;//初始存储容量
return OK;
}InitList_SqC语言代码实现一维动态数组分配如下：
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct
{
int* elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配到存储容量(以sizeof(ElemType)为单位)
}SqList;
SqList L;
int main()
{
L.elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
if (L.elem == NULL)
{
exit(OVERFLOW);
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return 0;
}在这种存储结构中，容易实现线性表的某些操作，如随机存储第i个数据元素等。
只是要特别注意的是，C语言中数组的下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。下面重点讨论线性表的插入和删除两种操作，在顺序存储表示时的实现方法
线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表：
(a1,...,a(i-1),ai,...,an)
变成n+1长度的线性表
(a1,...,a(i-1),b,ai,...,an)
数据元素a(i-1)和ai之间的逻辑关系发生了变化，在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化
一般情况下，在第i(1<=i<=n)个元素之前插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置，如下列算法所示：
Status ListInsert_Sq(SqList& L, int i, ElemType e)
//在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1<=i<=ListLength_Sq(L)+1
{
if (i<1 || i>L.length + 1)
{
return ERROR;//i值不合法
}
if (L.length >= L.listsize)//当前存储空间已满，增加分配
{
newbase = (ElemType*)reallco(L.elem, (L.listsize + LISTINCREMENT) * sizef(ElemType));
if (!newbase)
{
exit(OVERFLOW);//存储分配失败
}
L.elem = newbase;//新基址
L.listsize += LISTINCREMENT;//增加存储容量
}
q = &(L.elem[i - 1]);//q为插入位置
for (p = &(L.elem[L.length - 1]); p >= q; --p)
{
*(p + 1) = *p;//插入位置及之后的元素右移
}
*q = e;//插入e
++L.length;//表长增1
return OK;
}//ListInsert_Sq用C语言实现：
int ListInsert_Sq(SqList L, int i, int e)
//在顺序线性表L中第i个位置之前插入新的元素
//i的合法值为1<=i<=ListLength_Sq(L)+1
{
int newbase = 0;
int* q, * p;
if (i<1 || i>L.length + 1)
{
return 0;//i值不合法
}
if (L.length >= L.listsize)//当前存储空间已满，增加分配
{
newbase = (int*)reallco(L.elem, (L.listsize + 10) * sizeof(int));
if (!newbase)
{
exit(1);//存储分配失败
}
L.elem = newbase;//新基址
L.listsize += 10;//增加存储容量
}
q = &(L.elem[i - 1]);//q为插入位置
for (p = &(L.elem[L.length - 1]); p >= q; --p)
{
*(p + 1) = *p;//插入位置及之后的元素右移
}
*q = e;//插入e
++L.length;//表长增1
return 0;
}//ListInsert_Sq反之，线性表的删除操作是使长度为n的线性表
(a1,...,a(i-1),ai,a(i+1),...,an)
变成长度为n-1的线性表
(ai,...,a(i-1),a(i+1),...,an)
数据元素a(i-1)、ai和a(i+1)之间的逻辑关系发生变化，为了在存储结构上反映这个变化，同样需要移动元素。如果删除第i个元素，则需要将i+1到n个元素全部移动到前方
一般情况下，删除第i(1<=i<=n)个元素时需将从第i+1至第n(共n-i)个元素依次向前移动一个位置，如下算法的抽象代码所示：
Status ListDelete_Sq(SqList& L, int i, ElemType& e)
//在顺序线性表L中删除第i个元素，并用e返回其值
//i的合法值为1<=i<=ListLeng_Sq(L)
{
if ((i < 1) || (i > L.length))//i值不合法
{
return ERROR;
}
p = &(L.elem[i - 1]);//p为被删除元素的位置
e = *p;//被删除元素的值赋给e
q = L.elem + L.length - 1;//表尾元素的位置
for (++p; p <= q; ++p)//被删除元素之后的元素左移
{
*(p - 1) = *p;
}
}以上所有功能——新建、插入、删除的功能利用C语言实现（顺序线性表结构）如下所示：
#define _CRT_SECURE_NO_WARNINGS
#define INSERTLIST 100
#define INSTERELEM 10
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int* elem;
int length;
int listsize;
}SqList;
SqList L;
void InitList(int*, int);
void ListInsert_Sq(SqList*, int, int);
void ListDelete_Sq(SqList*, int);
int main()
{
/*创建一个新的数组，分配空间*/
L.elem = (int*)malloc(INSERTLIST * sizeof(int));
L.length = 0;
L.listsize = INSERTLIST;
int a;
printf("请输入原数组元素个数：");
scanf("%d", &a);
while (a)
{
InitList(L.elem, a);
a--;
}
/*指定位置插入元素*/
int i, e;
printf("请输入需要插入的位置：");
scanf("%d", &i);
printf("请输入需要插入的元素：");
scanf("%d", &e);
ListInsert_Sq(&L, i, e);
printf("请输入需要删除的位置：");
scanf("%d", &i);
ListDelete_Sq(&L, i);
for (int i = 0; i < L.length; i++)
{
printf("%d\n", L.elem[i]);
}
system("pause");
return 0;
}
void InitList(int* p, int a)
{
int i = 0;
if (a > L.listsize)
{
L.elem = (int*)realloc(L.elem, (INSTERELEM + L.listsize) * sizeof(int));
L.listsize += INSTERELEM;
}
scanf("%d", &i);
*(p + L.length) = i;
L.length++;
L.listsize--;
}
void ListInsert_Sq(SqList* L, int i, int e)
{
int newbase;
if (i <1 || i>L->length + 1)
{
printf("i值不合法");
exit(-1);
}
if (L->length == L->listsize)
{
printf("表满\n");
newbase = (int*)realloc(L->elem, (L->listsize + INSTERELEM) * sizeof(int));
if (newbase == NULL)
{
printf("分配失败\n");
exit(0);
}
L->elem = newbase;
L->listsize += INSTERELEM;
}
int* q = &L->elem[i - 1];
int* p;
for (p = &L->elem[L->length - 1]; p >= q; p--)
{
*(p + 1) = *p;
}
*q = e;
++(L->length);
}
void ListDelete_Sq(SqList* L, int i)
{
if (i<1 || i>L->length)
{
printf("i的位置不合法");
exit(-1);
}
int* q;
for (q = &L->elem[i]; q <= L->elem + L->length - 1; q++)
{
*(q - 1) = *q;
}
--(L->length);
}从上述讲解来看，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗在移动元素上(换句话说，移动元素的操作为预估算法时间复杂度的基本操作)，而移动元素的个数取决于插入或删除元素的位置
在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动表中一半的元素，若表长为n，则算法ListInsert_Sq和ListDelete_Sq的时间复杂度为O(n)
对于“顺序表的合并”，可利用下述算法：
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)
{
pa = La.elem;
pb = Lb.elem;
Lc.Listsize = Lc.length = La.length + Lb.length;
pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem)
{
exit(OVERFLOW);//分配失败
}
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_list)//归并
{
if (*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while (pa <= pa_last)
{
*pc++ = *pa++;//插入La中剩余的元素
}
while (pb <= pb_last)
{
*pc++ = *pb++;//插入Lb中剩余的元素
}
}C语言代码实现为：
#define LISTINSERT 100
#define LISTELEM 10
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int* elem;
int length;
int listsize;
}SqList;
SqList La, Lb, Lc;
void MergeList_Sq(SqList, SqList, SqList*);
void ListInsert_Sq(SqList*);
int main()
{
La.elem = (int*)malloc(LISTINSERT * sizeof(int));
La.length = 0;
La.listsize = LISTINSERT;
Lb.elem = (int*)malloc(LISTINSERT * sizeof(int));
Lb.length = 0;
Lb.listsize = LISTINSERT;
printf("请输入La:\n");
ListInsert_Sq(&La);
printf("\n请输入Lb:\n");
ListInsert_Sq(&Lb);
MergeList_Sq(La, Lb, &Lc);
printf("\n");
int i = 0;
while (Lc.elem[i] <= Lc.length)
{
printf("%d ", Lc.elem[i]);
i++;
}
system("pause");
return 0;
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
{
int* pa, * pb, * pc;
pa = La.elem;
pb = Lb.elem;
Lc->listsize = Lc->length = La.length + Lb.length;
pc = Lc->elem = (int*)malloc(Lc->listsize * sizeof(int));
if (!Lc->elem)
{
exit(0);//分配失败
}
int *pa_last = La.elem + La.length - 1;
int *pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)//归并
{
if (*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while (pa <= pa_last)
{
*pc++ = *pa++;//插入La中剩余的元素
}
while (pb <= pb_last)
{
*pc++ = *pb++;//插入Lb中剩余的元素
}
}
void ListInsert_Sq(SqList* L)
{
int j;
for (int i = 0; i < 10; i++)
{
scanf("%d", &j);
L->elem[i] = j;
L->length++;
}
}若对上述算法中合并函数内的第一个循环的循环体做如下修改：以“开关语句”代替“条件语句”，即分出元素比较的第三种情况，，当*pa=*pb的时候，只将两者中之一插入Lc，则该算法完成的操作和算法union完全相同，而时间复杂度却不同。
上述改变之所以有线性的时间复杂度，其原因有二：
- 由于La和Lb中的元素依值递增(同一集合中元素不等)，则对Lb中每个元素，不需要在La中从表头至表尾进行全程搜索
- 由于新表Lc表示“并集”，
则插入操作实际上是借助“复制”操作来完成的
（若将Lb中的元素插入La，为保持La中元素递增有序，必须移动元素，除非插入的元素大于La中所有的元素）
- 为了得到元素依值递增（或递减）的有序表，可利用以后会讨论的快速排序，它的时间复杂度为(O(nlogn))其中n表示待排序的元素个数
由此可见，若以线性表表示集合并进行集合的各种运算，应先对表中元素进行排序