【数据结构和算法】线性表
线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础。也就是线性表的问题具有一定的普遍性
一，定义和特性
- 定义：由n个数据特性相同的的元素构成的有限序列称为线性表
- 特性：除去第一个元素无直接前驱，最后一个元素无直接后继，其他元素都有直接前驱和直接后继
- 线性表的元素存在一一对应关系
二、分类
线性表又根据存储结构可以分为顺序表和链表
- 顺序表
- 每一个数据元素的存储位置都和线性表中的起始位置差一个常数，所以只要确定存储线性表的起始位置，可以对任意元素进行存取操作。线性表的数序存储结构是一种随机存取的存储结构。
- 特点：逻辑上相邻的元素物理上也相邻
- 结构实现和图示：
#define MAXSIZE 100; typedef struct { int *elem; //指向基地址 int length; //记录表长度 }Sqlist;
- 基本操作
初始化
Status Initlist(Sqlist &L) { L.elem = new int[MAXSIZE]; if(!L.elem) exit(OVERFLOW); L.length = 0; return 0; }
取值
Status GetElem(Sqlist L, int i, int &e) { if(i<1 || i>L.length) return ERROR; e = L.elem[i-1]; return 0; }
插入
Status SqInsert(Sqlist &L, int i, int e) { if( (i<1)|(i>L.length+1) ) return ERROR: if(L.length == MAXSIZE) return ERROR; for( int j=L.length-1; j>=i-1; j--) { L.elem[j+1] = L.elem[j]; } L.elem[j] = e; L.length = L.length + 1; return OK; }
删除
Status ListDelete(Sqlist &L, int i) { if( (i<1) | (i>L.length) return ERROR; for( int j=i; j<=L.length-1; j++) L.elem[j-1] = L.elem[j]; L.length--; return OK; }
- 链表
- 在使用链表的时候，只关心它所表示的线性表中数据元素的逻辑位置，而不关心实际在存储空间中的实际位置。
- 特点：用任意一组的存储单元存储线性表的数据元素（这组存储单元可连续，也可不连续）。
- 结构实现和图示
typedef struct LNode { int data; struct LNode *next; }LNocd,*LinkList；
- 基本操作
初始化
Status Initlist(LinkList &L) { L = new LNode;
L->next LNode;
return OK;
}
取值
Status GetElem(LinkLink L, int i, ElemType &e) { p=L->next j=1; while(p && j<i) { p=p->next; ++j; } if( !p || j>i) return ERROR; e=P->data; return OK; }
