图书馆的书目信息表就是一个线性表，表中的元素就是一条记录。记录由索引号、图书名称、作者、出版社等数据项构成。本文讨论了C语言和Pyhton语言如何定义一个顺序表，并实现了顺序表的插入、访问和删除运算。

采用顺序存储结构的线性表称为顺序表，顺序表就是在内存中开辟一段连续的存储空间，依次存储线性表中的数据元素。

一、定义顺序表

定义顺序表有两种方式：一种是静态地定义一张顺序表；一种是动态地生成一张顺序表。

下面是图书馆数目信息表：

表 1-3图书馆书目信息表

C语言可以定义一个结构体来存储书目信息：

typedef struct{
char strIndex[30]; // 索引号
char name[50];     // 图书名称
char author[15];   // 作者
char press[50];    // 出版社
}BOOKINFO;

Python语言可以定义一个类来存储书目信息

# 定义一个名为BookInfo的类
class BookInfo:
    def __init__(self, index,name,author,press):
        self.index = index  # 索引号
        self.name = name    # 图书名称
        self.author = author  # 作者
        self.press = press    # 出版社

书目信息结构已定义，下一步来定义顺序表，顺序表的元素为书目信息结构。在已知图书数量并且图书数量在一段时间基本不变的情况下，可以采用静态顺序表来存储书目信息。

定义静态顺序表C语言代码如下：

// 顺序表容量
#define MAX_BOOKSIZE  10000
// 定义一张静态顺序表
BOOKINFO  bookList[MAX_BOOKSIZE];

在C语言定义一张静态顺序表和定义数组的方法完全相同。

Python语言的列表是基于顺序表结构的对象，它本身就是动态顺序表，可以随时扩充顺序表的内存空间，用于存储更多的数据元素。下面重点讨论C语言动态顺序表的实现。

使用C语言动态生成一张顺序表，可以定义一个可动态扩展的数组，数组元素为BOOKINFO结构体。宏定义CAPACITY为动态数组的默认容量，pBookArray为指向动态数组的指针，nBookSize为动态数组当前长度，nCurrentCapacity为动态数组当前容量。

代码清单：

// 定义空指针
# define NULL 0
//线性表申请内存的默认容量 
#define CAPACITY      100
//指向线性表的指针,默认值为NULL
BOOKINFO *pBookArray = NULL;
//线性表当前长度,默认为0
int  nBookSize = 0;
// 线性表当前容量
int nCurrentCapacity = 0;

指向动态数组的指针pBookArray默认为空，程序运行后需要为数组申请内存，内存大小为CAPACITY*sizeof(BOOKINFO),并将申请的内存全部初始化为0。

代码清单：

// 初始化pBookArray，默认容量为CAPACITY
pBookArray = (BOOKINFO*)calloc(CAPACITY,sizeof(BOOKINFO));
memset(pBookArray,0,CAPACITY*sizeof(BOOKINFO));
if( NULL == pBookArray )
{
   printf("内存申请失败，程序将关闭");
   exit(-1);
}

现在我们已经通过上述代码生成了一张动态顺序表，顺序表可以存储的元素为BOOKINFO结构体。下面重点讨论顺序表的插入、访问和删除运算。

二、插入运算

INSERT(L,index,Element)

该运算在长度为n的L表中插入一个数据元素Element，插入前L表的长度为n，插入后L表的长度为n+1。index为插入元素的位置，index其后的元素都需要往后移动一个位置。若index为0，则需要移动n个元素；若index为1，仅需要移动一个元素。插入元素平均要移动的元素个数为（n-1）/2，因此顺序表插入运算的算法时间复杂度为O(n)。

C语言实现

/**
运算：在第index个元素和第index个元素之间插入一个元素
描述：该运算在长度为n的顺序表中插入一个数据元素，
      插入前顺序表的长度为n，插入后顺序表的长度为n+1。  
参数：pArray   顺序表地址
      index    元素插入的序号
	  bookInfo  
*/
int  InsertBookInfo(BOOKINFO* pArray,int index,BOOKINFO bookInfo)
{
	int i;
	char  *p1,*p2;
	if( index<0 )
		return -1;
	// 若元素已满，重新申请内容
	if( (nBookSize+1) > nCurrentCapacity )
	{
		nCurrentCapacity += CAPACITY;
	    pBookArray = (BOOKINFO*)realloc(pBookArray,sizeof(BOOKINFO)*nCurrentCapacity);
		if( NULL == pBookArray )
		{
			printf("内存申请失败，程序将关闭");
			exit(-1);
		}
	}
	for( i=(nBookSize>0?(nBookSize):0);i>index;i-- )
	{
		p1 = (char*)pArray;
		p1 += ((i)*sizeof(BOOKINFO));
		p2 = (char*)pArray;
		p2 += (i-1)*sizeof(BOOKINFO);
		memcpy(p1,p2,sizeof(BOOKINFO));
	}
	memcpy((char*)pArray+index*sizeof(BOOKINFO),&bookInfo,sizeof(BOOKINFO));
	nBookSize += 1;
}

InsertBookInfo函数首先判断顺序表存储空间是否已满，若已满则扩展存储空间，然后将index及其后的所有元素都顺序移动到下一个位置，最后将bookInfo指向的内存区域拷贝到顺序表索引为index的位置。

三、访问运算

GET(L,index)

该运算从L表中得到第index个数据元素，index为顺序表的序号。因为顺序表采用顺序存储结构，可以直接通过index来定位元素，因此查询元素的时间复杂度为O(1)。

C语言实现

/**
运算：访问第index个数据元素
描述：该运算从顺序表中得到第index个数据元素，
      index为顺序表的序号。
参数：pArray   顺序表
      index    访问的元素序号
*/
BOOKINFO* GetBookInfo(BOOKINFO* pArray,int index)
{
	char* p = (char*)pArray;
	// 若线性表长度为0，返回NULL值
	if( nBookSize <=0  )
		return NULL;
	// 若index小于0或大于等于线性表长度，返回NULL值
	if( index<0 || index >= nBookSize )
		return NULL;
	// 返回线性表的第1个元素
	if( index == 0 )
		return pArray;
	// 返回线性表的第index个元素
	return (BOOKINFO*)(p+index*sizeof(BOOKINFO));
}

GetBookInfo函数将线性表指针pArray赋值给字符指针变量p，参数index为访问元素的索引，即访问元素在线性表内的序号，字符指针p加上index个BOOKINFO的字节数即为访问元素的指针，返回时将指针强制转换为BOOKINFO指针。

四、删除运算

DELETE(L,index)

该运算从L表中删除第index个数据元素，该运算并不是真正删除第index个数据元素，而是将index其后的所有元素都顺序往前移动一个位置，覆盖掉index位置的元素。因此删除元素的时间复杂度为O(n)。

C语言实现

/**
运算：删除index位置的元素
描述：该运算在长度为n的顺序表中删除一个数据元素，
      删除前顺序表的长度为n，删除后顺序表的长度为n-1。  
参数：pArray   顺序表
      index    待删除元素的序号
	  bookInfo  
*/
int  DeleteBookInfo(BOOKINFO* pArray,int index)
{
	int i;
	char  *p1,*p2;
	if( index<0 )
		return -1;
	if( index >= nBookSize )
		return -1;
	// 删除最后一个元素
	if( index == nBookSize - 1  )
	{
		// 顺序表长度减1即可
		nBookSize = nBookSize - 1;
		return 0;
	}
	// index其后的所有元素都顺序往前移动一个位置
	for( i=index+1; i < (nBookSize>0?(nBookSize):0);i++ )
	{
		p1 = (char*)pArray;
		p1 += ((i)*sizeof(BOOKINFO));
		p2 = (char*)pArray;
		p2 += (i-1)*sizeof(BOOKINFO);
		memcpy(p2,p1,sizeof(BOOKINFO));
	}
	nBookSize -= 1;
}

DeleteBookInfo函数首先判断index的合法性，若index不合法，函数返回-1。若是删除最后一个元素，无需移动顺序表的元素，将顺序表长度减1即可，否则需要将index其后的所有元素都顺序往前移动一个位置。