线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础。也就是线性表的问题具有一定的普遍性
一，定义和特性
- 定义：由n个数据特性相同的的元素构成的有限序列称为线性表
- 特性：除去第一个元素无直接前驱，最后一个元素无直接后继，其他元素都有直接前驱和直接后继
- 线性表的元素存在一一对应关系
二、分类
线性表又根据存储结构可以分为顺序表和链表
1. 顺序表
- 每一个数据元素的存储位置都和线性表中的起始位置差一个常数，所以只要确定存储线性表的起始位置，可以对任意元素进行存取操作。线性表的数序存储结构是一种随机存取的存储结构。
- 特点：逻辑上相邻的元素物理上也相邻
- 结构实现和图示：
eg:实现操作的方法不止一种
#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; }
2. 链表
- 在使用链表的时候，只关心它所表示的线性表中数据元素的逻辑位置，而不关心实际在存储空间中的实际位置。
- 特点：用任意一组的存储单元存储线性表的数据元素（这组存储单元可连续，也可不连续）。
- 头结点：在首元结点之前附设的一个节点（为了统一操作 ，eg:删除算法要求我们记住被删除元素前面的表元）
首元结点：在链表中存储第一个元素的结点
头指针：指向整个链表的基地址
- 结构实现和图示
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; }
删除元素
Status DeleteElem(Link &L,ElemType e) { Node *p=L; Node *q=p->next; while(e-1>0) { p=p->next; q=p->next; e--; } p->next=p->next->next; delete q; return 0; }
显示
void show(Link L) { Node *p=L->next; while(p) { cout<<p->data<<" "; p=p->next; } cout<<endl; }
删除链表
void DeleteLinklist(Link &L) { Node *p=L->next; while(p) { delete L; L=p; p=p->next; } }
4. 顺序表和链表的区别
ps：我们可以通过数据结构中基本操作的时间复杂度和空间复杂度来判断该数据结构适用场合。