下载文档原格式
线性表---顺序表链表⼀、线性表 1、线性表中的元素是⼀对⼀的关系，除了第⼀个与最后⼀个元素之外其他数据元素都是⾸尾相连的。
如果是⼀对多就⽤树来表⽰，如果是多对多就⽤⽹状来表⽰。
2、线性表的两种存储结构顺序表：⽤顺序结构保存数据，数据在内存中是连续的。
链表：⽤链式存储结构保存数据，数据在内存中是不连续的。
⼆、顺序表 1、顺序表：顺序表⼀般使⽤数组实现，顺序表的相关操作与数组相关，⼀般都是移动数组元素顺序表封装所需要的三个属性：存储空间的起始位置。
数组date的存储位置就是线性表存储空间的存储位置。
线性表的最⼤存储容量。
数组长度MAXSIZE.线性表的的当前长度。
length注意：数组的长度与线性表的当前长度是不⼀样的。
数组的长度是线性表的存储空间的总长度，⼀般初始化后不变。
⽽线性表的当前长度是线性表中元素的个数，其⼤⼩是会改变的。
2、顺序表的C++代码实现：模板类的代码1 #include<iostream>2using namespace std;34const int MaxSize = 100;5 template <class DataType>6class SeqList7 {8public:9 SeqList(){length=0;}10 SeqList(DataType a[],int n);11 ~SeqList(){}12int Length(){return length;}13 DataType Get(int i);14int Locate(DataType x);15void Insert(int i,DataType x);16 DataType Delete(int i);17void PrintList();18private:19 DataType data[MaxSize]; //顺序表使⽤数组实现20int length; //存储顺序表的长度21 };2223 template <class DataType>24 SeqList<DataType>::SeqList(DataType a[],int n)25 {26if(n>MaxSize) throw"wrong parameter";27for(int i=0;i<n;i++)28 data[i]=a[i];29 length=n;30 }3132 template <class DataType>33 DataType SeqList<DataType>::Get(int i)34 {35if(i<1 && i>length) throw"wrong Location";36else return data[i-1];37 }3839 template <class DataType>40int SeqList<DataType>::Locate(DataType x)41 {42for(int i=0;i<length;i++)43if(data[i]==x) return i+1;44return0;45 }4647 template <class DataType>48void SeqList<DataType>::Insert(int i,DataType x)//插⼊过程中应注意元素移动的⽅向必须从最后⼀个元素开始移动，如果表满了发⽣上溢出，如果插⼊位置不合理，则引发位置异常。
线性表之顺序表线性表之顺序表顺序表定义线性表的顺序存储⼜称顺序表。
它是⽤⼀组地址连续的存储单元依次存储线性表当中的数据元素。
从⽽使得逻辑上相邻的两个元素在物理位置上也相邻。
第1个元素存储在线性表的起始位置，第i个元素的存储位置后⾯紧接的存储的也就是第i+1个元素。
因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同其顺序存储结构如下数组下表顺序表内存地址0a1LOC(A)1a2LOC(A)+sizeof(ElemType)2a3LOC(A)+2*sizeof(ElemType)3a4LOC(A)+3*sizeof(ElemType)...┊┊MaxSize-1┊LOC(A)+(MaxSize-1)*sizeof(ElemType)假设线性表L存储的起始位置是LOC(A),sizeof(ElemType)是每个数据元素所占存储空间的⼤⼩，ElemType表⽰的是数据的类型,如果存的是整形,就是int。
(注意线性表中的位序是从1开始的,数组中元素的下表是0)顺序表类型描述如下#define MaxSize 50type struct{ElemType data[MaxSize];int length = 0;}SqList;当然⼀位数组可以是静态分配的,也可以选择⽤动态分配#define MaxSize 50type struct{ElemType *data;int length = 0;}SqList;C语⾔初始动态分配如下L.data = (ElemType*)malooc(sizeof(ElemType)*MaxSize)顺序表上的基本操作如下,上代码插⼊操作bool ListInsert(SqList; &L, int i, ElemType e){//本函数实现在第i个位置插⼊元素eif(i < 1 || i > L.length + 1) //判断i是否越界return false;if(L.length >= MaxSize) //存储空间已满,不能插⼊return false;for(int j = L.length; j >= i; j--) // 将第i个元素及后⾯的元素往后移,为元素e腾地⽅L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true;}删除操作bool ListDelete(SqList; &L, int i, ElemType &e){//本函数实现删除第i个元素,并将被删除的元素⽤引⽤变量e返回if(i < 1 || i > L.length) //判断i是否越界return falsee = L.data[i-1];for(int j = i; j < L.length; j++)L.data[j-1] = L.data[j];L.length--;return true;}查找操作int LocateElem(SqList; &L, ElemType e){//本函数实现查找元素e在表中的位序,查找失败返回0for(int i = 0; i < L.length; i++)if(L.data[i] == e)return i+1;return e;}总代码#include<stdio.h>#define MaxSize 100typedef struct{int data[MaxSize];int length = 0;}SqList;bool ListInsert(SqList &L, int i, int e){//本函数实现在第i个位置插⼊元素eif(i < 1 || i > L.length + 1) //判断i是否越界return false;if(L.length >= MaxSize) //存储空间已满,不能插⼊return false;for(int j = L.length; j >= i; j--) // 将第i个元素及后⾯的元素往后移,为元素e腾地⽅ L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true;};bool ListDelete(SqList &L, int i, int &e){//本函数实现删除第i个元素,并将被删除的元素⽤引⽤变量e返回if(i < 1 || i > L.length) //判断i是否越界return false;e = L.data[i-1];for(int j = i; j < L.length; j++)L.data[j-1] = L.data[j];L.length--;return true;}int LocateElem(SqList &L, int e){//本函数实现查找元素e在表中的位序,查找失败返回0for(int i = 0; i < L.length; i++)if(L.data[i] == e)return i+1;return 0;}int main(){int a;SqList L;ListInsert(L, 1, 10);ListInsert(L, 2, 20);ListInsert(L, 3, 15);ListInsert(L, 4, 18);printf("15在顺序表的位序是: %d\n", LocateElem(L, 15));ListDelete(L, 3, a);printf("删除了顺序表第3个元素, 值为: %d\n", a);if(LocateElem(L, 15) == 0)printf("顺序表中不存在15这个值\n");elseprintf("15在顺序表的位序是: %d\n", LocateElem(L, 15));return 0;}输出:15在顺序表的位序是: 3删除了顺序表第3个元素, 值为: 15顺序表中不存在15这个值后⾯会慢慢讲解链表。
