数据结构学习（1）--- 线性表的定义与基本功能实现

一、线性表

线性表是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(il.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) return -1; //该元素不在顺序表中
    else i+1;
}

3.4 删除

int Delete(SqList &l,int i)
{
    if(il.length+1) return -1; //删除位置不正确
    for(int j=i;j