一、线性表D1-D2

1.1 线性表和顺序表

线性表是包含若干数据元素的一个线性序列 记为： L=(a0, ...... ai-1, ai, ai+1 ...... an-1)

L为表名，ai (0≤i≤n-1)为数据元素； n为表长,n>0 时，线性表L为非空表，否则为空表。

重点：链式存储结构—>单链结构

线性表L可用二元组形式描述

L=(D,R)   D是元素集合 R是关系集合

即线性表L包含数据元素集合D和关系集合R

什么是线性表：1）对非空表，a0是表头，去前驱；

                          2）a（n-1）是表尾，无后继；

                          3）其他的每个元素a(i）有且仅有一个直接前驱a（i-1）和一个直接后继a（i+1）

1.1.1顺序存储结构的表示

若将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。

设Loc(ai)为ai的地址，Loc(a0)=b，每个元素占d个单元 则：Loc(ai)=b+i*d  

1.1.2顺序存储结构的特点

优点

 逻辑上相邻的元素 ai, ai+1，其存储位置也是相邻的

对数据元素ai的存取为随机存取或按地址存取

存储密度高

存储密度D=(数据结构中元素所占存储空间)/（整个数据结构所占空间）

缺点

对表的插入和删除等运算的时间复杂度较差

1.1.3顺序存储结构的表示

在c语言中，可借助于一维数组类型来描述线性表的顺序存储结构

线性表的顺序存储也叫顺序表

例子：

#define N 1OO
typedef int date_t;

typedef struct
{  date_t date[N];
    int last;
} sqlist, *sqlink;

---

1.2 线性表的基本运算

设线性表L=(a0,a1,....,an-1),对L的基本运算又：

1）建立一个空表：list_create(L)

2）置空表：list_clear(L)

3)判断表是否为空：list_empty(L)。若表为空，返回值为1，否则返回0

4）求表长：length(L)

5）取表中某个元素：GetList(L,i），即ai。要求0<=i<=length(L)-1

6)定位运算：locate（L,x)。确定元素x在表中的位置（或序号）

7)插入：

Insert(L,x,i)。将元素x插入到表L中第i个元素ai之前,且表长+1。

插入前: (a0,a1,---,ai-1,ai,ai+1-------,an-1) 0≤i≤n,i=n时,x插入表尾

插入后: (a0,a1,---,ai-1, x, ai,ai+1-------,an-1)

1.3顺序表的实现

---

/*慕课补课内容：

一、绪论

数据的基本单位：数据元素也就是结构体（struct）

数据对象：具有相同类型的数据元素的集合

数据项：是数据的不可分割的最小单位

什么是数据结构：数据+结构->数据之间的关系。数据是一个个元素，元素构成集合，元素之间的关系就是结构。

逻辑结构：数据元素之间的逻辑关系的整体。它是数据结构在用户面前呈现的形式。

                  集合、线性结构、树形结构、图形结构

存储结构：数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。

                顺序存储:元素连续，地址连续，通过存储关系直接反映逻辑关系

                链式存储:每个存储单元（结点）单独存储，附加指针表示存储单元（结点）之间的地址关系

运算：施加在该数据上的操作。在数据结构中，数据运算就是插入、删除、查询、等操作。

运算定义：确定运算的功能，是抽象的

运算实现：在存储结构上确定对应运算实现算法，是具体的。

c语言中的自定义类型typedef

typedef char Elemtype;

        该语句将char类型与Elemtype等同起来。这样做有两个好处;

1.方便程序调试，例如，将上述语句改为typedef int Elemtype，则程序中所有的Elemtype都改为int类型。

2.可以简化代码

2、抽象数据类型

?
抽象数据类型（
ADT
）是指一个
数学模型
以及定义

在此数学模型上的
一组操作
。

?
定义一个抽象数据类型时，需要给出其名称和各运

算名称及其功能描述。

?
抽象数据类型需要通过固有数据类型（高级编程语

言中已实现的数据类型）来实现。
?
从数据结构的角度看，一个
求解问题
可以通过抽象数

据类型来描述。

?
也就是说，抽象数据类型（
ADT
）对一个求解问题
从

逻辑上进行了准确的定义
，所以抽象数据类型由数据

逻辑结构和运算定义两部分组成。

抽象数据类型（
ADT
）
=
数据逻辑结构
+
运算定义