数据结构与算法-D2D3线性表之顺序表

线性表：包含若干数据元素的一个线性序列，特征如下：

        1）对非空表，a0是表头，无前驱；

        2）an-1是表尾，无后继；

        3）其他元素仅且仅有一个前驱，一个后继

 线性表L可以用二元组表示：

        L=(D,R)

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

---

顺序存储特点：

        1）逻辑上相邻的元素，其存储位置也相邻

        2）对数据元素ai的存取为随机存取或按位置存取

        3）存储密度高

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

顺序存储缺点：

        1）数据插入和删除等运算的时间复杂度较差

顺序存储结构的表示：

        通常使用数组

 上图为顺序表的通常定义，typedef int data_t中data_t是表中元素，使用typedef是为了能够使得data_t可以更换数据类型；下面的typedef struct是顺序表，其中data_t data[N]是数据，int last是最后一个元素下标。

---

线性表的基本运算

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

        2）置空表：list_clear(L)

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

        4）求表长：liength(L)

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

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

        7）插入 ：

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

         8）删除：

                Delete(L,i)。删除表L中i个元素ai，且表长减1，要求0≤i≤n-1。

---

---

线性表的顺序存储缺点：

顺序表实现

sqlist.h    sqlist.c      test.c

        sqlist.h：数据结构定义、运算

        sqlist.c：运算实现

        test.c：整个实现

list_create

        1）申请内存

        2）成员初始化

        3）返回线性表地址

给大片内存赋同样的值

        第1个参数：内存首地址

        第2个参数：所要赋的值

        第3个参数：所要赋值的字节数

 list_clear

        成功返回0，失败返回1

 list_empty

        检查链表是否为空，1为空，0为非空

        last=0表示有一个数据，定义last=-1时是空表

list_length

        last表示最后一个元素的下标，lat+1就是长度了

 list_insert

         1、验证表是否满了

        2、插入的位置区间范围为[0, last+1]

        3、中间位置插入要涉及空间移动（从后往前移动）

       4、存新值，last+1

 list_show

list_delete

将指定位置元素删除

        首先不是空表

        1、检查位置pos在[0,last]

        2、移动元素

        3、更新last

list_merge

将两个线性表合并

        1、La = La 并Lb

        2、bi是否在La中

        3、不在，插入

list_locate

        判断元素是否在线性表中

总： 

 

list_purge

删除线性表当中的重复元素

 

---

注：一种简便书写struct方法