线性表：线性表是零个或多个数据元素构成的线性序列，可以记为a0,a1,a2…an-1;
注：n表示的是线性表的长度，当n=0的时候并不是表示线性表不存在，而是表示表为空。
相关概念：
直接前驱：某一数据元素的所对应的前一个元素
直接后继：某一数据元素的所对应的后一个元素
值得注意的是，a0是表的第一个元素，所以没有直接前驱，an-1是表的最后一个元素，所以没有直接后继。
数据结构包括有逻辑结构、存储结构、运算。也就是说，在存储数据的时候，我们不仅要关注数据的类型，更要关注各个数据之间的关系。
1.线性表的顺序存储结构
其概念是：使用连续的内存空间，按照数据元素在线性表中的的序号依次存储数据元素。而采用顺序存储结构的表被称为顺序表。
下面给的是顺序表的存储结构的基本模板
#define MAXSIZE 25
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
ElemType *data;
int length;
}Sqlist;
注意：如果是动态分配类型的话，则需要配套语句：(C语言)
Sqlist L;
L.data=(ElemTpye *)malloc(MAXSIZE*sizeof(ElemType));
free(L.data);
但这样写略写繁琐，在C++中，我们通常用new这个方法来等价上述的操作。
使用样例：
int *p1=new int ;
int *p1=new int(10);
如果new失败了就会返回NULL
常用的语言抽象
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
由此可知顺序表所需要的三个基本元素是：
①顺序表的最大长度:MAXSIZE
②顺序表当前的长度:length
③顺序表的存储位置，即data数组
在顺序表中，第一个元素的位置是很关键的，由于线性表的数据存储结构是连续的，而物理上的存储结构也是连续的，那么如果我们知道第一个元素的位置，那么我们想要找到有关的元素，可以采用公式：loc(ai+n)=loc(ai)+n*c
注：其中loc代表的是线性表中元素的位置，ai及ai+n代表的是元素的下标，c代表的是每个元素占据的字节空间。
由此公式可以知道，当在顺序线性表中进行查找操作的时候，其进行计算的函数公式都是线性的，即时间复杂度是一个常数。这一类的存储、取出特点被称为是随机存储结构。
线性表的基本操作:
①创建一个空的线性表L Initlist(&L)
这里传入的参数是一个引用型的变量。
Status InitList(Sqlist &L)
{
L.elem=new ElemType[MAXSIZE];
if(!L.elem)
{
exit(OVERFLOW);
}
else
{
L.length=0;
return OK;
}
}
②销毁一个线性表 DestroyList(&L)
void DestoryList(Sqlist &L)
{
if(L.elem)
{
delete L.elem;
}
}
③线性表的重置 ClearList(&L)
说明一下，重置的意思是表依然占用着内存空间，但是长度为0了，表示的是里面所有的元素都找不到了，现在要往内存空间里面重新写入数据。
void ClearList(Sqlist L)
{
L.length=0;
}
④判断线性表是否为空 ListEmpty(L)
int ListEmpty(Sqlist L)
{
if(L.length==0)
{
return 1;
}
else
{
return 0;
}
}
⑤求线性表的长度 ListLength(L)
int ListLength(Sqlist L)
{
return (L.length);
}
⑥取出操作 GetElem(L,i,&e):
取出即通过遍历表的方式，找到相对应的元素之后，返回对应的元素值。在上面已经定义好了一个线性表的情况下，现在给出取出元素的代码。根据位置i（指的是物理意义上的位置），获取相应位置上的内容。
初始条件：线性表已经存在，而且线性表的长度满足 1<=i<=ListLength(L)
结果是用e返回线性表中第i个元素。
注：OK/ERROR代表的是1/0,，通过define的方法进行定义换名。
int GetElem(Sqlist L,int i,ElemType &e)
{
if(i<1||i>L.length)
{
return ERROR;
}
else
{
e=L.elem[i-1];
return OK;
}
}
⑦查找直接元素 LocateElem(L,e,compare())
在线性表中查找与指定值e相同的数据元素的位置，算法：从表的一端开始，逐个进行记录的关键字和给定值的比较，找到则返回该元素的位置序号，未找到则返回0。
int LocateElem(Sqlist L,ElemType e)
{
for(int i=0;i<L.length;i++)
{
if(L.elem[i]==e)
{
return i+1;
}
}
return ERROR;
}
⑧查找直接前驱 PriorElem(L,cur_e,&pre_e)
int PriorElem(Sqlist L,ElemType cur_e)
{
int pos=LocateElem(L,cur_e);
if(pos==1)
{
return ERROR;
}
else
{
return pos-1;
}
}
⑨查找直接后继 NextElem(L,cur_e,&next_e)
int NextElem(Sqlist L,ElemType cur_e)
{
int pos=LocateElem(L,cur_e);
if(pos==L.length)
{
return ERROR;
}
else
{
return pos+1;
}
}
⑩插入操作 ListInsert(&L,i,e) **
要实现的是，在线性表L中的第i的位置，插入元素e,函数元素可定义为ListInstert(*List L,int i,int e);其中int可以替换为任意数据结构类型。插入算法的实现注意点：
1.如果插入的位置不合理，无法用算法实现，抛出异常
2.如果线性表的长度大于等于数组的长度，那么就抛出异常或者是动态增加数组的长度
3.从最后一个元素**遍历到第i个元素，分别都将他们都向后移动一个位置。
4.将要插入的元素填入位置i中
5.整个表长+1
实现代码如下：
Status ListInsert(Sqlist &L,int i,ElemType e)
{
if(i<1||i>L.length+1)
{
return ERROR;
}
if(L.length==MAXSIZE)
{
return ERROR;
}
else
{
for(int j=L.length-1;j>=i-1;j--)
{
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
L.length++;
return OK;
}
}
⑪删除操作 ListDelete(&L,i,&e)
和插入的核心算法类似，这里给出四步：
F:判断删除的位置是否合理
S:将想要删除的元素保留在e中
T:将i+1位的元素到n位的元素向前移动一个位置
FO:表长+1
代码如下
Status ListDelete(Sqlist &L,int i)
{
if(i<1||i>L.length)
{
return ERROR;
}
for(int j=i;j<L.length;j++)
{
L.elem[j-1]=L.elem[j];
}
L.length--;
return OK;
}
完整的代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef int ElemType;
typedef int Status;
typedef struct
{
ElemType *elem;
int length;
}Sqlist;
using namespace std;
Status InitList(Sqlist &L)
{
L.elem=new ElemType[MAXSIZE];
if(!L.elem)
{
exit(OVERFLOW);
}
else
{
L.length=0;
return OK;
}
}
void DestoryList(Sqlist &L)
{
if(L.elem)
{
delete L.elem;
}
}
void ClearList(Sqlist L)
{
L.length=0;
}
int ListLength(Sqlist L)
{
return (L.length);
}
int ListEmpty(Sqlist L)
{
if(L.length==0)
{
return 1;
}
else
{
return 0;
}
}
int GetElem(Sqlist L,int i,ElemType &e)
{
if(i<1||i>L.length)
{
return ERROR;
}
else
{
e=L.elem[i-1];
return OK;
}
}
int LocateElem(Sqlist L,ElemType e)
{
for(int i=0;i<L.length;i++)
{
if(L.elem[i]==e)
{
return (i+1);
}
}
return 0;
}
Status ListInsert(Sqlist &L,int i,ElemType e)
{
if(i<1||i>L.length+1)
{
return ERROR;
}
if(L.length==MAXSIZE)
{
return ERROR;
}
else
{
for(int j=L.length-1;j>=i-1;j--)
{
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
L.length++;
return OK;
}
}
Status ListDelete(Sqlist &L,int i)
{
if(i<1||i>L.length)
{
return ERROR;
}
for(int j=i;j<L.length;j++)
{
L.elem[j-1]=L.elem[j];
}
L.length--;
return OK;
}
int PriorElem(Sqlist L,ElemType cur_e)
{
int pos=LocateElem(L,cur_e);
if(pos==1)
{
return ERROR;
}
else
{
return pos-1;
}
}
int NextElem(Sqlist L,ElemType cur_e)
{
int pos=LocateElem(L,cur_e);
if(pos==L.length)
{
return ERROR;
}
else
{
return pos+1;
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
