一、线性表
线性表是n个数据特性相同的元素组成的有限序列，线性表中的元素个数定义为线性表的长度，长度为0时称为空表。
二、线性表的顺序表示方式
1.基本知识
1.1 概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。
1.2 特点：逻辑上相邻的数据元素，其物理次序也是相邻的。
所以只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机存取的存储结构。
2.顺序存储结构的两种定义方式
2.1 静态定义（下面的功能实现均采用静态定义）
# define maxleng 100 typedef struct{ ElemType elem[maxleng]; int length; }SqList;2.2 动态定义
# define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 # define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基地址 int length; int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位） }SqList；3.顺序存储结构常见操作
3.1 初始化
int Init(SqList &l) { l.length = 0; return 1; //用来验证初始化成功 }3.2 插入
int Insert(SqList &l,int i,int x) { if(l.length>=maxleng) return -1; //顺序表已满，无法插入 else if(i<=0 || i>l.length+1) return -1; //插入位置错误 else { if(i==1 || i==l.length+1) //不需要移动直接赋值 { l.elem[i-1] = x; l.length++; } else { for(int j=l.length-1;j>=i-1;j--) { l.elem[j+1] = l.elem[j]; } l.elem[i] = x; l.length++; } } return 1; //用来验证插入成功 }3.3 查找
int Search(SqList &l,int x) { int i = 0; while(i<l.length && l.elem[i]!=x) i++; if(i>=l.length) return -1; //该元素不在顺序表中 else i+1; }3.4 删除
int Delete(SqList &l,int i) { if(i<=0 || i>l.length+1) return -1; //删除位置不正确 for(int j=i;j<l.length;j++) { l.elem[j-1] = l.elem[j]; } l.length--; return 1; 用来验证删除成功 }3.5 显示
void DisPlay(SqList l) { for(int i=0;i<l.length;i++) cout<<l.elem[i]<<" "; cout<<endl; }三、例子
下面给大家一个综合的例子来直观感受顺序表的这些基本操作
#include<iostream> #include<stdio.h> using namespace std; #define maxleng 100 //定义---静态 typedef struct{ int elem[maxleng]; int length; }SqList; /* int Init(SqList &l)---------------------初始化，详见上文 int Insert(SqList &l,int i,int x)-------插入，详见上文 int Search(SqList &l,int x)-------------查找，详见上文 int Delete(SqList &l,int i)-------------删除，详见上文 void DisPlay(SqList l)------------------显示，详见上文 */ int main() { SqList l; Init(l); Insert(l,1,1); Insert(l,2,2); Insert(l,3,3); Insert(l,4,4); //first display DisPlay(l); Search(l,3); Search(l,5); Insert(l,5,5); //second display DisPlay(l); Delete(l,2); //third display DisPlay(l); return 0; }输出结果如下
first display ：1,2,3,4 second display : 1,2,3,4,5 third display : 1,3,4,5