一、线性表的定义：线性表就是零个或多个数据元素的有效序列。
二、线性表的顺序存储结构
1.定义：指的是用一段地址连续地存储单元依次存储线性表的数据元素。
2.顺序存储方式：线性表的每个数据元素的类型都相同，所以可以用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。线性表中，估算最大存储容量就是数组的长度。
3.描述顺序存储结构需要三个属性：
- 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量：数组长度MaxSize。
- 线性表的当前长度：length。
4.数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。而线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
5.地址计算方法：由于数据是从0开始第一个下标的，因此线性表的第i个元素是要存储在数据下标为i - 1 的位置。存储器中每个存储单元都有自己的编号，这个编号称为地址。
6.线性表顺序存储结构的优缺点：
- 优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任意位置的元素。
- 缺点：插入和删除操作需要移动大量元素；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的“碎片”。（实际存储空间小于分配的空间）
6.C语言版本的代码实现：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */ /* 将数据元素c打印出来 */ Status visit(ElemType c) { printf("%d ",c); return OK; } /* 线性表的顺序存储的结构 */ typedef struct { ElemType data[MAXSIZE]; /* 数组，存储数据元素 */ int length; /* 线性表当前长度 */ }SqList; /* 给结构体命名 */20 /* 初始化顺序线性表，建立一个空的线性表L */ Status InitList(SqList *L) { L->length=0; return OK; } /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */ Status ListEmpty(SqList L) { if(L.length==0) return TRUE; else return FALSE; } /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */ Status ClearList(SqList *L) { L->length=0; return OK; } /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */ int ListLength(SqList L) { return L.length; } /* 获得元素操作：将线性表L中的第i个位置元素值返回，*/ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */ Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) return ERROR; *e=L.data[i-1]; /* 将线性表的第i个位置，也就是数组的第i-1个位置的元素返回 */ return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0 */ int LocateElem(SqList L,ElemType e) { int i; if (L.length==0) return 0; for(i=0;i<L.length;i++) { if (L.data[i]==e) break; } if(i>=L.length) return 0; return i+1; } /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; /* 线性表L的长度增加1 */ return OK; } /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) /* 线性表为空 */ return ERROR; if (i<1 || i>L->length) /* 删除位置不正确 */ return ERROR; *e=L->data[i-1]; /* 将被删除的数据元素返回给e */ if (i<L->length) /* 如果删除不是最后位置 */ { for(k=i;k<L->length;k++) /* 将删除位置后继元素前移1个位置 */ L->data[k-1]=L->data[k]; } L->length--; /* 线性表L的长度减1 */ return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：依次对L的每个数据元素输出 */ Status ListTraverse(SqList L) { int i; for(i=0;i<L.length;i++) visit(L.data[i]); printf(" "); return OK; } /* 将所有的在线性表Lb中但不在La中的数据元素插入到La中 */ void unionL(SqList *La,SqList Lb) { int La_len,Lb_len,i; /* 声明线性表La和Lb的长度 */ ElemType e; /* 声明线性表La和Lb相同的数据元素e */ La_len=ListLength(*La); /* 求线性表La的长度 */ Lb_len=ListLength(Lb); /* 求线性表Lb的长度 */ for (i=1;i<=Lb_len;i++) { GetElem(Lb,i,&e); /* 去Lb中第i个数据元素赋给e */ if (!LocateElem(*La,e)) /* 如果线性表La中不存在和e相同的数据元素 */ ListInsert(La,++La_len,e); /* 就把线性表中La中不存在的这个元素插入线性表La中 */ } } int main() { SqList L; SqList Lb; ElemType e; Status i; int j,k; i=InitList(&L); printf("初始化L后：L.length=%d ",L.length); printf(" "); for(j=1;j<=5;j++) i=ListInsert(&L,1,j); printf("在L的表头依次插入1～5后：L.data="); ListTraverse(L); printf("L.length=%d ",L.length); printf(" "); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否) ",i); i=ClearList(&L); printf("清空L后：L.length=%d ",L.length); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否) ",i); printf(" "); for(j=1;j<=10;j++) ListInsert(&L,j,j); printf("在L的表尾依次插入1～10后：L.data="); ListTraverse(L); printf("L.length=%d ",L.length); printf(" "); ListInsert(&L,1,0); printf("在L的表头插入0后：L.data="); ListTraverse(L); printf("L.length=%d ",L.length); printf(" "); GetElem(L,5,&e); printf("第5个元素的值为：%d ",e); for(j=3;j<=4;j++) { k=LocateElem(L,j); if(k) printf("第%d个元素的值为：%d ",k,j); else printf("没有值为%d的元素： ",j); } printf(" "); printf("依次输出L的元素："); ListTraverse(L); k=ListLength(L); /* k为表长 */ for(j=k+1;j>=k;j--) { i=ListDelete(&L,j,&e); /* 删除第j个数据 */ if(i==ERROR) printf("删除第%d个数据失败 ",j); else printf("删除第%d个的元素值为：%d ",j,e); } printf("依次输出L的元素："); ListTraverse(L); printf(" "); j=5; ListDelete(&L,j,&e); /* 删除第5个数据 */ printf("删除第%d个的元素值为：%d ",j,e); printf("依次输出L的元素："); ListTraverse(L); printf(" "); //构造一个有10个数的Lb i=InitList(&Lb); for(j=6;j<=15;j++) i=ListInsert(&Lb,1,j); printf("依次输出Lb的元素："); ListTraverse(Lb); unionL(&L,Lb); printf("依次输出合并了Lb的L的元素："); ListTraverse(L); return 0; }
输出：
初始化L后：L.length=0
在L的表头依次插入1～5后：L.data=5 4 3 2 1
L.length=5
L是否空：i=0(1:是 0:否)
清空L后：L.length=0
L是否空：i=1(1:是 0:否)
在L的表尾依次插入1～10后：L.data=1 2 3 4 5 6 7 8 9 10
L.length=10
在L的表头插入0后：L.data=0 1 2 3 4 5 6 7 8 9 10
L.length=11
第5个元素的值为：4
第4个元素的值为：3
第5个元素的值为：4
依次输出L的元素：0 1 2 3 4 5 6 7 8 9 10
删除第12个数据失败
删除第11个的元素值为：10
依次输出L的元素：0 1 2 3 4 5 6 7 8 9
删除第5个的元素值为：4
依次输出L的元素：0 1 2 3 5 6 7 8 9
依次输出Lb的元素：15 14 13 12 11 10 9 8 7 6
依次输出合并了Lb的L的元素：0 1 2 3 5 6 7 8 9 15 14 13 12 11 10
7.Java语言版本的代码实现：
接口类：
package bigjun.iplab.sequenceList; public interface IList { //置空操作 public void clear(); //判空操作 public boolean isEmpty(); //取表长度 public int getLength(); //取表元素 public int getElem(int i) throws Exception; //插入操作 public void insert(int i, int x) throws Exception; //删除操作 public void remove(int i) throws Exception; //显示 public void display(); // 定位元素e public int locateElem(int e); // 合并两个集合 public void union(IList bIList) throws Exception; }
实现类：
package bigjun.iplab.sequenceList; public class SqList implements IList{ private final static int MAXSIZE = 20; private int[] data; //线性表存储空间 private int length; //线性表当前长度 //顺序表构造函数,构造一个长度为maxSize的线性表 public SqList(int maxSize){ length = 0; data = new int[maxSize]; } //置空操作 public void clear() { length = 0; } //判断当前长度是否为0,为0即为空表 public boolean isEmpty() { return length == 0; } //取表长度，返回length当前长度即可 public int getLength() { return length; } // 获取第i个位置的元素的值 public int getElem(int i) throws Exception { if (length==0 || i < 1 || i > length) throw new Exception("ERROR"); return data[i-1]; } // 在线性表的第i个位置插入新的元素 public void insert(int i, int x) throws Exception { if (length == MAXSIZE) throw new Exception("顺序线性表已经满"); if (i < 1 || i > length+1) throw new Exception("插入的位置已经超出的线性表的范围"); if (i <= length) { for(int k=length-1;k>=i-1;k--) data[k+1]=data[k]; } data[i-1]=x; length++; } // 删除线性表第i个位置的元素，并且返回被删除的元素 public void remove(int i) throws Exception { if (length==0) { throw new Exception("线性表为空"); } if (i < 1 || i > length) { throw new Exception("删除位置不正确，无法删除"); } if (i < length) { for (int j = i; j < length; j++) { data[j-1] = data[j]; } } length--; } public void display() { for (int j = 0; j < length; j++) System.out.print(data[j] + " "); System.out.println(); } // 获取元素e在线性表中是什么位置 public int locateElem(int e) { int j; if (length==0) return 0; for (j = 0; j < length; j++) { if (data[j]==e) break; } if (j >= length) { return 0; } return j+1; } // 合并两个集合 public void union(IList bIList) throws Exception { int bLength = bIList.getLength(); for (int i = 1; i <= bLength; i++) { int bElem = bIList.getElem(i); if (this.locateElem(bElem) == 0) { System.out.println(bElem); this.insert(1, bElem); } } } public static void main(String[] args) throws Exception { SqList sqList = new SqList(MAXSIZE); System.out.println(sqList.isEmpty()); for (int i = 1; i <= 5; i++) sqList.insert(1, i); System.out.println(sqList.isEmpty()); sqList.display(); sqList.clear(); System.out.println(sqList.isEmpty()); for (int j = 1; j <= 10; j++) sqList.insert(j, j); sqList.display(); sqList.insert(1, 0); sqList.display(); System.out.println("第5个位置的元素是：" + sqList.getElem(5)); for (int i = 3; i <= 4; i++) { int k = sqList.locateElem(i); if (k != 0) { System.out.println("第" + k + "个位置的元素是：" + i); } else { System.out.println("没有值为" + i + "的元素"); } } sqList.display(); int len = sqList.getLength(); System.out.println(len); System.out.println(sqList.getElem(len)); sqList.remove(len); sqList.display(); System.out.println(sqList.getElem(5)); sqList.remove(5); sqList.display(); SqList bList = new SqList(MAXSIZE); for (int i = 6; i <= 15; i++) bList.insert(1, i); bList.display(); sqList.union(bList); sqList.display(); } }
输出：
true false 5 4 3 2 1 true 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 第5个位置的元素是：4 第4个位置的元素是：3 第5个位置的元素是：4 0 1 2 3 4 5 6 7 8 9 10 11 10 0 1 2 3 4 5 6 7 8 9 4 0 1 2 3 5 6 7 8 9 15 14 13 12 11 10 9 8 7 6 15 14 13 12 11 10 10 11 12 13 14 15 0 1 2 3 5 6 7 8 9