线性表是什么
线性表是包含若干数据元素的一个线性序列,记为: L = (a0,…ai-1,ai,ai+1,…an-1)
- L为表名,ai(0≤ i ≤n-1)为数据元素;
- n为表长,n>0时,线性表 L 为非空表,否则为空表。
线性表L可用二元组形式描述(程序员间的表述):
L = (D,R)
即线性表 L 包含数据元素集合 D 和关系集合 R
D = {ai | ai ∈ datatype ,i=0,1,2, …n-1 ,n≥0}
R = {<ai, ai+1> | ai,ai+1∈D,0 ≤ i ≤ n-2}
- 关系符<ai,ai+1>在这里称为有序对
- 表示任意相邻的两个元素之间的一种先后关系
- ai 是 ai+1的直接前驱,ai+1 是 ai的直接后继
线性表的特征
- 对非空表,a0是表头,无前驱;
- an-1是表尾,无后继;
- 其它的每个元素 ai 有且仅有一个直接前驱 ai-1 和 一个直接后继 ai+1 。
线性表 - 顺序表
顺序存储结构的表示1
若将线性表 L = (a0,a1,…,an-1) 中的各元素依次存储于计算机一片连续的存储空间。
设 Loc(ai) 为 ai 的地址,Loc(a0) = b,每个元素占 d 个单元, 则:Loc(ai) = b + i*d
顺序存储结构的特点
- 逻辑上相邻的元素 ai,ai+1,其存储位置也是相邻的
- 对数据元素 ai 的存取为随机存取或按地址存取
- 存储密度高
- 存储密度 D = (数据结构中元素所占存储空间)/ (整个数据结构所占空间)
- 不足:对表的插入和删除等运算的时间复杂度较差
顺序存储结构的表示2
在 C 语言中,可借助于一维数组类型来描述线性表的顺序存储结构:
#define N 100
typedef int data_t;
typedef struct
{data_t data[N]; //表的存储空间;int last;
} sqlist, *sqlink;
上面的代码可以这么理解:
typedef struct sqlist
可以看作是整个图书馆,而这里的data[N]
是图书馆里的书,结构体里的last
就可以看作是一共有多少本书,虽然叫作last
是因为它是顺序表里最后一个元素的下标,但是这个下标也可以标识一共有多少本书,只要可以代表总数,也可以换成别的。- 那为什么要用 typedef 定义变量和结构体?因为这样可以复用代码,比如这里的 data_t 可以换成 char ,也可以换成别的类型,它可以是书,也可以是餐具等等,结构体 typedef 同理。
线性表的基本运算
设线性表 L = (a0,a1,…,an-1) , 对 L 的基本运算有:
1)建立一个空表:list_create(L)
2)置空表:list_clear(L)。若成功返回1,失败返回0。
3)判断表是否为空:list_empty(L)。若表为空,返回值为 0,否则返回 -1
4)求表长:length(L)
5)取表中某个元素:GetList(L,i),即ai。要求0≤ i ≤ length(L) - 1
6)定位运算:Locate(L,x)。确定元素 x 在表 L 中的位置(或序号)
L o c a t e ( L , x ) = { i 当元素 x = a i ∈ L ,且 a i 是第一个与 x 相等时 − 1 当 x 不属于 L 时 Locate(L,x)=\left\{ \begin{array}{rcl} i & & {当元素x=a_i∈L,且a_i是第一个与x相等时}\\ -1 & & {当x不属于L时}\\ \end{array} \right. Locate(L,x)={i−1当元素x=ai∈L,且ai是第一个与x相等时当x不属于L时
7)插入:Insert(L,x,i)。将元素 x 插入到表 L 中第 i 个元素 ai 之前,且表长 +1。
线性表运算的实现
我们在实现时一般会写三个文件(顺序表):
1、sqlist.h 定义数据结构,定义线性表运算
2、sqlist.c 实现线性表运算
3、 test.c 实现实际功能,调 sqlist.h 接口
这样写的好处是:①结构清晰; ②代码复用性高:自己可以反复用,不管是现在的项目,还是以后的项目都可以用;同事也可以用。③给外包公司接口,实现部分给他们二进制 .so 文件,这样以后业务升级还找你
分文件编写以后怎么编译运行呢?
-
可以一条一条的把 .c 汇编为 .o ,最后链接 .o 和 库文件 运行:
例如:gcc -c sqlist.c -o sqlist.o
gcc -c test.c -o test.o
gcc test.o sqlist.o -o test
-
利用简洁的命令进行编译执行:
gcc *.c -o test
-
利用 Makefile 进行编译
SRC=sqlist.c SRC+=test.ctest:$(SRC)gcc $^ -o $@.PHONY:cleanclean:rm *.o
sqlist.c 中线性表运算具体实现
-
创建顺序表 list_create()
- 思路:
- 分配内存空间(一定要注意检查分配成功没有)
- 初始化
- 返回顺序表指针
- 代码:
sqlink list_create() {//mallocsqlink L;L = (sqlink)malloc(sizeof(sqlist));if(L == NULL){printf("list malloc failed!\n");return L;}//initmemset(L, 0, sizeof(sqlist));L->last = -1;//returnreturn L; }
- 思路:
-
清空顺序表 list_clear(sqlink L)
- 思路:
- 先检查表原来是否是空表(如果是空表的话清空也没啥意义)(有疑问??)
- 然后给表空间置0,给表尾元素挪到初始位置(-1)
- 代码:
int list_clear(sqlink L){if(L == NULL){printf("the list is null!\n");return -1;}memset(L, 0, sizeof(sqlist));L->last = -1;return 0;}
- 思路:
-
判断顺序表是否为空表 list_empty(sqlink L)
- 思路:
- 判断指针 L 是否为空,避免非法操作
- 判断表尾元素是否还在初始位置(-1),如果在初始位置证明是空表,返回 0,如果不是的话就返回 1
- 代码:
int list_empty(sqlink L) {if (L == NULL){printf("illegal operation!\n");return -1;}if (L->last == -1){return 0;}else{return 1;} }
- 思路:
-
计算顺序表长度 list_length(sqlink L)
- 思路:
- 判断指针 L 是否为空,避免非法操作
- 顺序表长度可以看作是表尾元素下标 + 1
- 代码:
int list_length(sqlink L) {if (L == NULL){return -1;}return (L->last + 1); }
- 思路:
-
向顺序表中插入元素
- 思路:
- 判断顺序表满不满,如果已经满了就不能再插入元素了
- 判断元素插入位置是否合法(插入位置不能小于下标 0 ,也不能大于顺序表末尾元素下标 L->last 的后一位)
- 如果以上两条都通过,那么开始新增元素,新增元素按照下图的箭头所示,依次从后往前的每个元素都向后移动一位给新增元素腾地方。比如插入元素位置在下标为 1 的地方,那么就先移动下标 4 的元素 9 到下标 5 ,然后移动下标 3 的元素 4 到 下标 4,······以此类推,把下标 1 的元素移动到下标 2 后,就可以进行下一步了
- 把要新增的值赋给数组的新增元素
- 末尾元素下标加一
- 代码:
int list_insert(sqlink L, data_t value, int pos) {int i;if (L->last == N - 1){printf("the list is full!\n");return -1;}if (pos < 0 || pos > L->last + 1){printf("the insertion position is invalid\n");return -1;}for (i = L->last; i <= pos ; i--){L->data[i+1] = L->data[i];}L->data[pos] = value;L->last++;return 0; }
- 思路:
-
打印顺序表 list_show(sqlink L)
- 思路:
- 判断表指针 L 是否为空,避免非法操作
- 判断表尾元素是否在初始位置,给予空表提示
- 打印顺序表
- 代码:
int list_show(sqlink L) {int i;if (L == NULL){printf("invalid!\n");return -1;}if (L->last == -1){printf("the list is null!\n");return 0;}for (i = 0; i <= L->last; i++){printf("%d ", L->data[i]);}printf("\n");
- 思路:
-
销毁顺序表 list_free(sqlink L) ,因为有时候程序并不能主动释放顺序表内存空间,一直占用内存会造成浪费
- 思路:
- 判断表指针 L 是否为空,如果为空那么这个表就没有建立起来,也没必要销毁
- 释放 L 内存空间
- 把表指针 L 置空,不再让其指向这段已经被释放的内存空间
- 代码:
int list_delete(sqlink L) {if (L == NULL){printf("invalid!\n");return -1;}free(L);L = NULL;return 0; }
- 思路: