线性表的定义

  • 线性表是具有相同数据类型的n(n>=0)个数据元素的有限数列,用L命名线性表,则其一般表示为
    L=(a_1,a_2,……,a_i,a_i+1,……,a_n)
  • 除第一个元素外,每个元素有且仅有一个直接前驱。
  • 除最后一个元素外,每个元素有且仅有一个直接后继。

题1.线性表是具有n个()的有限序列
A.表元素 B.字符 C.数据元素 D.数据项

答案C

线性表的基本操作:

1
2
3
4
5
6
7
8
9
10
1.InitList(&L): 初始化表.构造一个空的线性表。
2.Length(L): 求表长.返回线性表L的长度,即L中数据元素的个数.
3. LocateElem(L,e):按值查找操作。获取表L中查找具有给定关键字值的元素。
4.GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
5.ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。
6.ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值.
7.PrintList(L):输出操作。按前后顺序输出线性表L的元素值。
8.Empty(L): 判空操作
9.DestroyList(&L):销毁操作

3,4,5,6操作是重点

顺序表的结构

  • 线性表的顺序存储称为顺序表,它是由一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。

  • 题1.线性表采用顺序存储结构表示时,必须占用一片连续的存储单元。()
    答案:正确

  • 题2.如果一个顺序表中第一个元素的存储地址为1000,每个元素占4个地址单元,那么第6个元素的存储地址应是( )。
    A.1020 B.1010 C.1016 D.1024

答案:A 1000+(6-1)*4=1020

解析:套公式
LOC(A)+sizeof(ElemType)*(i-1)
1000 + 4 * (6-1) =1020

  • 假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为

    1
    2
    3
    4
    5
    6
    7
    #define MaxSize 50 //定义线性表的最大长度
    typedef struct{
    ElemType data[MaxSize]; //顺序表的元素
    int length; //顺序表的当前长度
    }SqList; //顺序表的类型定义


  • 上述一维数组是属于静态分配,由于数组的大小和空间事先已经固定,一旦空间占满,再加入新的数据将会产生溢出,进而导致程序崩溃。

  • 而在动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,就另外开辟一块更大的存储空间,用以替换原来的存储空间,从而达到扩充存储数据空间的目的,而不需要为线性表一次性地划分所有空间。

1
2
3
4
5
6
7
8
9
#define InitSize 50 //表长度的初始定义
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize,length; //数组的最大容量和当前个数
}SeqList; //动态分配数组顺序表的类型定义

C 语言的初始动态分配语句为
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

顺序表的特点:

  • 顺序表最主要的特点是随机存取,即通过首地址和元素序号可在时间O(1)内找到指定的元素。
  • 顺序表的存储密度高,每个结点只存储数据元素。
  • 顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素。
  • 题3.当需要随机查找线性表的元素时,宜采用( )作存储结构。

A.双向链表 B.循环链表 C.顺序表 D. 单链表

答案:C

  • 顺序表最主要的特点是随机存取.

顺序表的实现

插入操作

  • 在顺序表L的第i(1<=i<=L.lengh+1)个位置插入新元素e。若i的输入不合法,则返回false,表示插入失败;否则,将顺序表的第i个元素及其后的所有元素右移一个位置,腾出一个空位置插入新元素e,顺序表长度增加1,插入成功,返回true。
1
2
3
4
5
6
7
8
9
10
bool ListInsert(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1) //判断的范围是否有效
return false;
for(int j=L.length;j>=i;j--) //将第个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置处放入
L.length++; //线性表长度增加
return true;
}

时间复杂度:
n

0+1+2+…+n=n(n+1)/2
移动结点的平均次数,再除于n+0=n+1项
所以平均次数为n/2
时间复杂度忽略1/2
所以为O(n)

  • 题1.在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1),元素的移动次数为( )。

A.n-i+1 B.n-i C.i D.i-1

答案:A

解析:
第i个位置,则它前面是i-1
在第i个位置进行插入,所以要从i开始到第n个位置往后移动一位
所以移动次数是:n-(i-1)=n-i+1

删除操作

  • 删除线性表中第i(1<=i<=L.length)个位置的元素,若成功则返回true,并将被删除的元素用引用变量e返回,否则返回false。
1
2
3
4
5
6
7
8
9
10
11
bool ListDelete(SqList &L,int i,ElemType &e){
if(i<1||i>L.length) //判断的范围是否有效
return false;
e=L.data[i-1]; //将被删除的元素赋给e
for(int j=i;j<L.length;j++) //将第个位置后的元素后移
L.data[j-1]=L.data[j];
L.length--; //线性表长度减1
return true;
}


时间复杂度计算:
0+1+2+….+n-1=n(n-1)/2
移动结点的平均次数(n-1)/2
所以O(n)

  • 题2.设顺序线性表中有n个数据元素,则删除表中第i个元素需要移动( )个元素。

A.n-i B.n-i-1 C.n-i+1 D.i

答案:A

删除表中第i个元素,需要移动i后面的第n个元素
则i后面的元素=n-i个

  • 题3.对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为( )。

A.O(n),O(n) B.O(n),O(1) C.O(1),O(n) D.O(1),O(1)

答案:C

解析:
根据顺序表特点:顺序表最主要的特点是随机存取,即通过首地址和元素序号可在时间O(1)内找到指定的元素。

所以左边是O(1),上文已经计算出插入和删除都是O(n)
故选C

按值查找操作

  • 在顺序表L中查找第一个元素值等于e的元素,并返回其位序。
1
2
3
4
5
6
7
8
int LocateElem(SqList L,ElemType e){
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1; //下标为的元素值等于,返回其位序
return 0; //退出循环,说明查找失败
}

按位查找操作

1
2
3
4
5
6
int GetElem(SqList L,int i){
if(i<1||i>L.length) //判断的范围是否有效
return 0;
return L.data[i-1];
}

  • 题4.将两个有序顺序表A,B合并为一个新的有序顺序表C,并用函数返回结果顺序表。
  • 算法思想:首先,按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后,看哪个表还有剩余,将剩下的部分添加到新的顺序表后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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++]=B.data[j++];
while(j<B.length)
C.data[k++]=B.data[j++];
C.length=k;
return true;
}