###线性表###

线性表是具有相同特征的有限序列。

（a₁, a₂, a₃, ... , a_n）

 

例：多项式P_n(x) = P₀x⁰ + P₁x¹ + P₂X² + ... + P_nxⁿ

1. 可用线性表表示P = (P₀, P₁, ... , P_n) //利用数组储存，求两个多项式相加，只要把对应指数相同的系数相加。
2. 稀疏多项式 S(x) = 1 + 3x¹⁰⁰⁰⁰ + 2x²⁰⁰⁰⁰ (大量缺陷，再用第一个方法浪费空间)

　　　　稀疏多项式用另一种线性表表示：

　　　　　　Pn = P₁X^e₁ + P₂X^e2 + ... + P_nx^e_n

　　　　这就可以用线性表表示 P = ((P₁, e₁), (P₂, e₂), ... , (P_n, e_n))

 

A(x) = 7 + 3x + 9x⁸ + 5x¹⁷

下标	0	1	2	3
系数	7	3	9	5
次数	0	1	8	17

 

 

 

 

 

B(x) = 8x + 22x⁷ - 9x⁸

下标	0	1	2
系数	8	22	-9
次数	1	7	8

 

 

 

 

 

把两个多项式相加操作如下：
A = ((7, 0), (3, 1), (9, 8), (5, 17))

B = ((8, 1), (22, 7), (-9, 8))

• 创建一个新数组c。
• 两个线性表从头头遍历。如果系数不一样，小的项复制到c中；如果一样，对应系数相加，若和不是0，则在c中加一个新项。

0	1	7	5
7	11	22	17

• 一个多项式遍历完毕，将另一个剩余项全部一次复制到c中。

 

？？？c多大比较合适呢？？？

这种方法利用顺序存储结构（数组）存在：空间分配不灵活，空间复杂度高。

因此我们用链表存储结构。

 

总结：

• 线性表中数据元素可以是简单或者复杂类型。
• 许多实际应用涉及基本操作有很大相似（图书管理系统，学生信息管理系统等）

 

=====================================================================

 

###线性表的顺序表示以及实现###

线性表的顺序表示称顺序存储结构或顺序映像。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中，既是地址连续。（数组）

注意连续存储，不能有空出存储空间。

LOC(a_i+1) = LOC(a₁) + （i - 1）× l           (每个元素占l个空间，等差数列）

知道一个地址，就可以知道每个元素的地址；任一元素均可随机存取。

 

顺序表可用一维数组表示，但是数组的长度是不可动态定义（对于c/c++），而线性表长度可变（增删）

 

下面提供一个定义顺序表的模板：

#define LIST_INIT_SIZE 100　　

//线性表存储空间的初始分配量，是动态数组的最大存储空间，实际使用空间由length表示。

typedef structa  //typedef 给已有类型取别名。如typedef int noint;表示int也可以叫做noint

{
　　ElemType elem[LIST_INIT_SIZE];

　　int length;　　//当前长度

}  SqList;

 

 

例1：多项式的顺序存储结构类型定义

P_n = P₁X^e₁ + P₂X^e2 + ... + P_nx^e_n

线性表P = ((P₁, e₁), (P₂, e₂), ... , (P_n, e_n))

#define MAXSIZE 1000　　//多项式可以达到最大长度

typedef struct {　　　　　　//多项式非零项的定义

　　float p;　　　　　　　　//系数

　　int e;    　　　　　　　　//指数

} Polynomial;//多项式

typedef struct {

　　Polynomial *elem;　　　//存储空间的基地址,知道基地址可以知道p和e的地址

　　int length;　　　　　　　//多项式当前有几项

} SqList;                                   //多项式的顺序存储结构类型位SqList

 

 

例2：图书表的顺序存储结构类型定义

#define MAXSIZE 10000　　//图书表可达最大长度

typedef struct {//图书信息定义

　　char no[20];

　　char name[50];

　　float price;

} Book;

typedef struct {

　　Book *elem;　　//存储空间的基地址

　　int length;　　　　//图书表中当前图书个数

} SqList；　　　　//图书表的顺序存储结构类型是SqList

 

=====================================================================

 

###一些知识补充###

• 数组定义
  • 数组静态分配

　　　　　　typedef struct

　　　　　　{
　　　　　　　　ElemType data[MaxSize];

　　　　　　　　int length;

　　　　　　}  SqList;　　//顺序表类型

• • 数组动态分配

　　　　　　typedef struct

　　　　　　{
　　　　　　　　ElemType* data;

　　　　　　　　int length;

　　　　　　}  SqList;　　//顺序表类型

　　　　　　利用动态内存分配与静态分配等价

　　　　　　SqList L;

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

• • • malloc(m)：开辟m字节长度的空间，返回这段空间的的首地址（void*类型，故要强制类型转化）
    • sizeof(x)：计算变量x长度
    • free(p)：释放指针p所指变量的储存空间，彻底删除一个变量
    • 需要加载头文件<stdlib.h>
    • c++动态储存分配
    • new 类型名T （初值列表）

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

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

　　　　　　　　　　　　失败：0（NULL）

　　　　　　　　　　　　例：int* p1 = new int; 或者 int *p1 = new int(10);//10是初值

• • • • delete 指针P　　　　　　　　

　　　　　　　　　　　　功能：释放由new操作形成的指针指向的内存，和new成对使用

• • • 参数传值的两种方式
      • 传值：参数是整型，实型，字符型等，改变形参实参不变
      • 传地址：参数为指针，引用&，数组名（首元素地址）等，改变形参实参改变
    • 什么是引用？

　　　　　　　　　　它用来给对象提供一个替代名字

　　　　　　　　　　例如：int i = 5; int& j = i; i = 7;

　　　　　　　　　　　　　此时i = j = 7，i 和 j 是一样的，它们公用一块地址空间，对i操　　　　　　　　                                               作就是对j操作，就类似于英语和English,只是一个变量的两个                                                 名字

 

=====================================================================

 

###线性表的基本操作实现###

//函数结果状态码

#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；

 

算法1：线性表L的初始化（参数用引用）

Status InitList_Sq(SqList &L) { //构造一个空的顺序表L

　　L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间，这也是new一个数组的用法

　　if (!L.elem) exit(OVERFLOW); //存储分配失败，exit()推出函数，并返回括号内的内容

　　L.length = 0; //空表长度为0

　　return OK;

}     

 

算法2：销毁线性表L

void DestoryList(SqList &L) {

　　if (L.elem) delete L.elem;　　//释放存储空间

}     

 

算法3：清空线性表L

void ClearList（SqList &L）{

　　L.length = 0;　　//将线性表的长度置为0,表中元素并没有在内存中消除，只是不考虑了

}         　　　　　　//等待，下一次赋值，把原有数据覆盖

 

算法4：求线性表L的长度

int GetLength(SqList L) {

　　return L.length;

}

 

算法5：判断线性表L是否为空

int IsEmpty(SqList L) {

　　if (L.length == 0) return 1;

　　else return 0;

}

 

算法6：顺序表的取值（根据位置i获取相应位置数据元素的内容）

int GetElem(SqList L, int i, ElemType &e) {

　　if (i < 1|| i > length) return ERROR; //判断i是否合理，不合理返回ERROR

　　e = L.elem[i-1]; //第i-1的单元储存第i个数据

　　return OK;

}

 

算法7：顺序表的按值查找

这里使用顺序查找法，从头到尾，一个一个看

int LoacteElem(SqList L, ElemType e) {

//在线性表中查找值是e的元素，返回序号（第几个元素）

　　for (i = 0; i < L.length; i++)

　　　　if (L.elem[i] == e) return i+1;　　//查找成功返回序号

　　return 0;　　//查找失败返回0

}

平均查找长度ASL(Average Search Length)　　ASL = ∑P_iC_i

求查找次数的期望值（查找第i个记录比较次数×第i个记录被查找对应概率，累加）

 

算法8：顺序表的插入

 Status ListInsert_Sq(SqList &L, int i，ElemType e) {

　　if (i < 1 || i > L.length+1) return ERROR;　　//i值不合法

　　if (L.length == MAXSIZE) return ERROR;　　//当前存储空间已满

　　for (j = L.length-1; j >= i-1; j--)

　　　　L.elem[j+1] = L.elem[j];　　　　　　//插入位置及以后的元素往后移一个单位

　　L.elem[i-1] = e;                                         //将新插入的e放在第i个位置

　　L.length++;　　　　　　　　　　　　　//表长加1

　　return OK;                                                //返回函数结果状态为成功

}

平均移动次数是执行最多次数E_ins  = 1/(n+1)∑(i = 1, n+1)(n-i+1) = n/2

故时间复杂度是O(n)

 

算法9：顺序表元素的删除

Status ListDelete_Sq(SqList &L, int i) {

　　if (i < 1 || i > L.length) return ERROR;　　//i值不合法

　　for (j = i; j <= L.length-1; j++)

　　　　L.elem[j-1] = L.elem[j];　　//被删除之后的元素前移

　　L.length--;　　　　　　　　　　//表长减1

　　return OK;

}

平均移动次数是执行最多次数E_del = 1/n∑(i = 1, n)(n-i) = (n-1)/2

故时间复杂度是O(n)

 

这9大算法很重要，一定要掌握！！！

小结：

• 时间复杂度：查找、插入、删除算法的平均时间复杂度为O(n)
• 空间复杂度：显然顺序表操作算法的空间复杂度S(n) = O(1) (没有占用辅助空间)
• 优点：存储密度大（节点本身存储量/节点结构所占存储量），可以随机存取表中任意一个元素
• 缺点：在插入删除某一元素时，需要大量元素；浪费空间；属于静态存储形式，元素个数不能够*扩充（有一个最大存储量MAXSIZE的约束）

 

=====================================================================

 

线性表介绍和顺序表就介绍到这里，主要是掌握顺序表的常见算法，它们的思想很重要，为接下来链式存储结构打基础。