数据结构之线性表

数据结构之线性表

1. 什么是线性表

线性表是一种最常用，最简单的一种数据结构。它是n个数据元素的有限序列。
n 为线性表的长度，当 n = 0 时，表明该线性表为空表。

2. 线性表的特性

> 1. 线性表中存在唯一一个被称为“第一个”的数据元素。
> 2. 线性表中存在唯一一个被称为“最后一个”的数据元素。
> 3. 线性表中除第一个元素外，每一个元素均有一个直接前驱。
> 4. 线性表中除最后一个元素外，每一个元素均有一个直接后继。

3. 线性表的两种表示

1. 线性表的顺序存储
   线性表的顺序表示是指线性表中的数据元素依次存放在连续的地址连续的内存空间中。由其名称中的“ 顺序 ” 便可理解。
   线性表的顺序存储结构的特点是：逻辑关系上相邻的两个数据元素在物理位置上也相邻。
   缺点： 执行插入 或 删除操作时，需要大量移动数据。
2. 线性表的链式存储
   链式存储是指： 用一组任意的存储单元存储线性表的数据元素，这组数据单元可以是连续的，也可以是不连续的。
   特点： 不要求逻辑上相邻的数据元素在物理位置上也相邻。
   缺点： 随机存取比较麻烦。

4.线性表的基本操作

1. void InitList(&S) ;   //初始化线性表
2. int DestroyList (&S); //销毁线性表
3. int ClearList(&S);   //清空线性表
4. int ListLength(&S); //返回链表的长度
5. int listEmpty(&S); //链表为空返回1，否则返回0
6. ListData GetElem(&S,int i);  //返回第i 个数据元素
7. ListData PriorElem (&S,ListData x); //返回数据元素x的直接前驱
8. int LocateElem(&S,ListData x);  //返回数据元素x 在链表中的位置
9. ListData NextElem(&S,ListData x); //返回数据元素x的直接后继
10. int ListInsert (&S,ListData x,int i); //在链表第i 个元素之前插入x;
11. int ListDelete (&S,int i); //删除第i个数据元素