线性表的定义与使用

线性表(linear_list)是最常用且最简单的一种数据结构。间而言之，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至可以是其它复杂的信，常见的线性表：顺序表，链表，栈，队列，字符串。

线性表在逻辑上是线性结构，也就是说是一条连续的直线。但是在物理结构上并不一定是连续的，线性表在物理上储存时，通常以数组和链式结构的形式储存。

2.顺序表的实现

2.1概念及结构

顺序表是用一段物理地址连续的储存单元依次储存数据元素的线性结构，一般情况下采用数组储存。在数组上完成数据的增删查改。

顺序表一般可分为：

1.静态顺序表：使用定长数组储存。

2.动态顺序表：使用动态开辟的数组储存。

//顺序表的静态储存
#define N 100
typedef int SLDataType
typedef struct SqeList
{
 SLDataType arr[N];//定长数组
 size_t size;//有效数据的个数
}SqeList;

//顺序表的动态储存
#define N 100
typedef int SLDataType
typedef struct SqList
{
 SLDataType*arr;//指向动态开辟的数组
 size_t size;//有效数据的个数
 size_tcapicity;//空间容量的大小
}SqList；

3. 一般情况下我们使用动态顺序表对数据进行储存，因为动态可以改变表的空间大小，而静态表无法改变空间的大小所以对数据的储存比较麻烦。所以动态顺序表就要想内存申请开辟属于自己的空间。

//下面我们用malloc函数来开辟空间
struct*BuyListNode(LTDatatype x)//这里我们用结构体指针类型接收
{
 	struct*newnode = (struct*)malloc(sizeof(ListNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

4.完成表的创建以后我们就要对顺序表进行一系列的操作，即对顺序表的增，删，查，改，等基本操作。

（1）头插

void SeqListPushFront(SL*ps,SQDataType x)
{
 SeqListCheckCapacity(ps);
 int end=ps->size-1;
 while(end>=0)
 {
   ps->a[end-1]=ps->a[end];
   --end;
 }
 ps->a[0]=x;
 ps->size++;
}

（2）尾删

void SeqListPopBack(SL*ps)
{
 assert(ps->size>0)
 ps->size--;
}

(3)头删

void SeqListPopFront(SL*ps)
{
 assert(ps->size>0)
 int start=1;
 while(start<ps->size)
 {
  ps->a[start-1]=ps->a[start];
  ++start;
 }
 ps->size--;
}

(4)在pos位置前插入元素

void SeqListInser(SL*ps,int pos,SQDataType x)
{
 assert(po>ps->size)
 SeqListCheckCapacity(ps);
 int end=ps->size-1;
 while(end>=pos)
 {
  ps->a[end+1]=ps->a[end]
  --end;
 }
 ps->a[pos]=x;
 ps->size++;
}