1、线性结构的特点是：数据元素的非空有限集中，(1)存在惟一的一个被称做“第一个”的数据元素；(2)存在惟一的一个被称做“最后一个”的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。
2、线性表是n个数据元素的有限序列。
3、C语言实现A = A∪B 算法伪代码：
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); //取Lb中第i个数据元素赋给e
if (!LocalElem(La, e, equal))
ListInsert(La, ++La_len, e); //La中不存在和e相同的数据元素，则插入之
}
}
时间复杂度：O(ListLength(LA)XListLength(LB))
4、已知线性表LA和LB中的数据元素按值非递减有序排列，要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。C语言实现该算法伪代码如下：
void MergeList(List La, List Lb, List &Lc)
{
//已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列。
InitList(Lc);
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(Lb, j, 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);
}
}
时间复杂度：O(ListLength(LA)+ListLength(LB))
5、假设线性表的每个元素需占用l个存储单元，则线性表的第i个元素ai的存储位置为LOC(ai) = LOC(a1)+(i-1)*l。
6、C语言实现线性表的动态分配顺序存储结构伪代码：
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMMENT 10 //线性表存储空间的分配增量
typedef struct {
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
Status InitList_Sq(SqList &L)
{
//构造一个空的线性表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;
}
7、C语言实现在顺序表L中第i个位置之前插入新的元素e，伪代码如下：
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
//i的合法值为1<=i<=ListLength_Sq(L)+1
if (i<1 || i>ListLength_Sq(L)+1) return ERROR; //i值不合法
if (L.length >= L.listsize)
{
//当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(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;
}
时间复杂度：O(n)
8、C语言实现在顺序表L中删除第i元素，并用e返回其值，伪代码如下：
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
if ((i < 1) || (i > L.length)) 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; //被删除元素之后的元素左移
--L.length; //表长减1
return OK;
}
时间复杂度：O(n)
9、C语言实现顺序线性表L中查找第1个值与e满足compre()的元素位置，伪代码如下：
int LocateElem.Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType))
{
//若找到，则返回其在L中的位序，否则返回0
i= 1； //i的初始值为第一个元素的位序
p = L.elem; //p的初值为第一个元素的存储位置
while (i<=L.length && !(* compare)(*p++, e)) ++i;
if (i <= L.length) return i;
else return 0;
}
时间复杂度：O(L.length)
10、已知顺序线性表La和Lb中的数据元素按值非递减有序排列，要求将Lb和Lb归并为一个新的顺序线性表Lc，且Lc中的数据元素仍按非递减有序排列。C语言实现该算法伪代码如下：
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_last)
{
if (*pa <= *pb) *pc++ = *pa++;
else *pc++ == *pb++;
}
while (pa <= pa_last) *pc++ = *pa++; //插入La的剩余元素
while (pb <= pb_last) *pc++ = *pb++; //插入Lb的剩余元素
}
时间复杂度：O(La.length+Lb.length)
除非注明，文章均为CppLive 编程在线原创，转载请注明出处，谢谢。
