目录

1、线性表的定义和特点

2、基本操作

3、线性表的顺序表示实现

3.1 顺序存储定义

3.2 顺序表的顺序存储表示

4、线性表的顺序表示

5、类C语言有关操作

5.1 C语言的内存动态存储

5.2 C++的内存动态存储

5.3 C++中的参数传递

5.4 操作算法中用到的预定义常量和类型

 6、顺序表基本操作

6.1  线性表L的初始化

6.2  销毁线性表

6.3  清空线性表

6.4  求线性表长度

6.5  判断线性表L是否为空

6.6  顺序表的取值

7、顺序表的查找

8、顺序表的插入

9、顺序表的删除 

---

1、线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为  L = （a1，a2...,ai,...,an）

解释：

• ai是线性表中的“第i个”元素线性表中的位序

• a1是表头元素；an是表尾元素

• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2、基本操作

ListEmpty(L)

• 初始条件：线性表L已经存在；

• 操作结果：若线性表L为空表，则返回TURE；否则返回FALSE；

ListLenth(L)

• 初始条件：线性表L已经存在；

• 操作结果：返回线性表L中的数据元素个数；

LocateElem(L,e,compare())//Elem表示元素的意思

• 初始条件：线性表L已经存在,compare()是数据元素判断函数；

• 操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0；

GetElem(L,i)

• 初始条件：线性表L已经存在，1<= i <=ListLength(L);

• 操作结果：用e返回线性表L中第i个数据元素的值；

PriorElem(L,cue_e,&pre_e)

• 初始条件：线性表L已经存在；

• 操作条件：若cue_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义

NextElem(L,cue_e,&next_e)

• 初始条件：线性表L已经存在；

• 操作条件：若cue_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败；next_e无意义；

ListInsert(&L,i,e)

• 初始条件：线性表L已经存在；1<= i <= Listlength(L)

• 操作条件：在L的第i个位置之前插入新的数据元素e，L长度加一；

ListDelete(&L,i,&e)

• 初始条件：线性表L已经存在；1<= i <= Listlength(L)

• 操作条件：删除L的第i个数据元素，并返回e，L长度减一；

ListTraverse(&L,visited())//便利，访问每个元素

• 初始条件：线性表L已经存在；

• 操作条件：依次对线性表中每个元素调用visited()；

3、线性表的顺序表示实现

线性表的顺序表示又称为顺序存储结构或顺序映像

3.1 顺序存储定义

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

线性表顺序存储结构占有一片连续的存储空间，知道某个元素的存储位置就可以计算出其他元素的存储位置；

所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

3.2 顺序表的顺序存储表示

以上可知：用一维数组表示顺序表

与数组不同的是：

• 线性表长可变（删除）

• 数组长度不可动态定义；

以上可知：用一变量表示顺序表的长度属性

线性表的模板：

#define LIST INIT SIZE 100//线性表存储空间的初始分配量
typedef struct{
    ElemType elem[LIST_INIT_SIZE];//一维数组表示：顺序表
    int length;//变量表示：当前长度
}SqList;

例子如下：图书管理系统

#define MAXSIZE 10000//图书表可能达到的最大长度
typedef struct{//图书信息定义
    char no[20];
    char name[50];
    float price;
}Book;
typedef struct{
    Book *elem;//存储空间的基地址
    int length;//图书表中当前图书个数
}SqList;//图书表的顺序存储结构类型为SqList

4、线性表的顺序表示

ElemType表示的是某个元素类型，它可以是int、char、float、double等等，也可以是结构体。

下面代码都是基于C++的伪代码，不能独立运行。

下面的具体某些操作的伪代码并不代表唯一的写法，但基本思路是一样的。

typedef char ElemType；（将ElemType自定义为char类型）；

5、类C语言有关操作

5.1 C语言的内存动态存储

格式如下：

SqList L;
​
L.data = ( ElemType * )**malloc**( **sizeof** ( ElemType ) * MaxSize)

ElemType可以是char int ......

*表示指针

malloc(m)函数：开辟m字节长度的地址空间，并返回这段空间的首地址；【需要加载头文件】（用malloc函数申请一片连续的存储空间）

sizeof(x)函数：计算变量x的长度；

free(p)函数：释放指针p所指变量的存储空间，即彻底删除一个变量【需要加载头文件】

5.2 C++的内存动态存储

格式如下：

new 类型名T（初值列表）

int *p1 = new int；或者int *p1 = new int（10）；

功能：申请用于存放T类型对象的内存空间，并依初值列表赋以初值

结果值：

成功：T类型的指针，指向新分配的内存

失败：0（NULL）

delete 指针P

功能：释放指针P所指的内存，P必须是new操作的返回值

5.3 C++中的参数传递

1）函数调用时传送给形参表的实参必须与形参三个一致

类型、个数、顺序

2）参数传递有两种方式

参数为指针变量、引用类型、数组名

3）引用类型作参数

#include
void main(){
    int i=5;
    int &j=i;
    i=7;
    cout<<"i="<"j="<
}

注意：j是引用类型，代表i的一个代替名，i的值改变时，j的值也跟着改变，所以会输出i=7，j=7；

引用类型作形参的三点说明： 3.1）传递引用给函数与传递给指针的效果是一样的，形参变化实参也发生变化；

3.2）引用类型作参数，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本，因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好

3.3）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用"*指针变量名"的形式进行运算，这很容易产生错误且程序 的阅读性较差，另一方面，在主调函数的调用点处，必须用变量的地址作为实参；

5.4 操作算法中用到的预定义常量和类型

//函数结果状态代码
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW    -2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;//返回值的类型
typedef char ElemType;//元素的类型

 6、顺序表基本操作

6.1  线性表L的初始化

Status InitList_Sq(SqList &L){//构造一个空的顺序表
    L.elem = new ElemType[MAXSIZE];//为顺序表分配空间
    if(!L.elem)exit(OVERFLOW);//存储分配是失败
    L.length=0;//空表长度为0
    return OK;
}

6.2  销毁线性表

void DestoryList(SqList &L){
    if(L.elem)delete L.elem;//释放存储空间
}

6.3  清空线性表

void ClearList(SqList &L){
    L.length = 0;//将线性表的长度置为空
}

6.4  求线性表长度

int GetLength(SqList L){
    return (L.length)
}

6.5  判断线性表L是否为空

int IsEmpty(SqList L){
    if(L.length == 0) return 1;
    else return 0;
}

6.6  顺序表的取值

int GetElem(SqList L,int i,ElemType &e){
    if(i<1||i>L.length) return ERROR;//判断i值是否合理，如不合理返回ERROR
    e= L.elem[i-1];
    return OK;
}

7、顺序表的查找

1）按值查找

int LocateElem(SeqList L,ElemType e){
    for(int i=0;i
        if(L.data[i]==e) return i+1;
    return 0;
} //返回查找到元素的次序

2）平均查找长度ASL

为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

Pi表示：第i个记录被查找的概率

Ci表示：找到第i个记录需比较的次数

8、顺序表的插入

#define MaxSize 10            //定义最大长度
typedef struct{
    ElemType data[MaxSize];        //用静态的"数组"存放数据元素
    int length;                //顺序表的当前长度
}SqList;                    //顺序表的类型定义
//-----------------插入操作核心代码-----------------------
void ListInsert(SqList &L,int i,ElemType e){
       if(i<1||i>L.length+1) return ERROR;    //i值不合法
    if(L.length==MAXSIZE) return ERROR;    //当前存储空间已满    
    for(int j=L.length;j>=i;j--){    //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    }
      L.data[i-1]=e;    //在位置i处放入e
      L.length++;        //长度加1
}
//-----------------插入操作核心代码-----------------------
int main(){
      SqList L;            //声明一个顺序表
      InitList(L);        //初始化顺序表
      //....此处省略一些代码，插入几个元素
      ListInsert(L,3,3);
      return 0;
}

                                

计算在各种位置插入（共n+1种可能）的平均移动次数

  

9、顺序表的删除 

bool ListDelete(SeqList &L,int i,ElemType &e){
    if(i<1||i>L.length) return ERROR;
    e=L.data[i-1];
    for(int j=1;j
        L.data[j-1]=L.data[j];
    L.length--;
    return OK;
}
//-----------------删除操作核心代码-----------------------
int main(){
    SeqList L;      //声明一个顺序表
    InitList(L);    //初始化顺序表
    //...此处省略一些代码，插入几个元素
    int e=-1;       //用变量e把删除的元素"带回来"
    if(ListDelete(L,3,e))
        printf("已成功删除%d",e);
    else
        printf("位序不合法，删除失败");
    return 0;
}

 

计算在各种位置删除（共n种可能）的平均移动次数