线性表

线性表、栈、队列、串和数组都属于线性结构。

线性表的的主要基本操作有插入、删除和查找等。

线性结构的基本特点是除第一个和最后一个元素外，每个数据元素只有一个前驱和一个后继。

线性表是最简单、最基本、最常用的一种数据结构，它有顺序存储和链式存储两种存储结构。

在一个线性表中，数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。

线性表的基本操作

（1）InitList(L)，线性表初始化，构造一个空的线性表L。

（2）ListLength(L)，求线性表的长度，返回线性表L中数据元素的个数。

（3）GetElem(L, i, x)，用x返回线性表中的第i个元素的值。

（4）LocationElem(L, x)，按值查找，确定数据元素x在表中的位置。

（5）ListInsert(L, i, x)，插入操作，在线性表L中第i个位置之前插入一个新元素x，L的长度加1。

（6）ListDelete(L, i)，删除操作，删除线性表L中的第i个元素，L的长度减1。

（7）ListEmpty(L)，判断线性表L是否为空，空表返回true，非空表返回false。

（8）ClearList(L)，将已知的线性表L置为空表。

（9）DestroyList(L)，销毁线性表L。

顺序表

顺序表是计算机内存中以数组的形式保存的线性表；是指用一组地址连续的存储单元依次存数数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。

#include<stdio.h>#define MAXSIZE		1000	//线性表可能到达的最大长度#define TRUE		1		//操作成功#define ERROR		0		//操作错误#define	OVERFLOW	2		//顺序表已存满	#define FALSE		-1		//操作失败	 typedef int ElemType;typedef struct{	ElemType elem[MAXSIZE];	int length;}SeqList; //定义一个顺序表SeqList L; //1.顺序表的初始化void init_SeqList(SeqList *L){	L->length = 0;} //2.顺序表的插入//操作步骤：//（1）将an ~ ai 按从后向前的顺序向下移动，为新元素让出位置。//（2）将x置入空出的第i个位置。//（3)修改表长int insert_SeqList(SeqList *L, int i, ElemType x){	int j;	if(L->length == MAXSIZE){		//表空间已满，不能插入。 		PRintf("顺序表已存满/n");		return OVERFLOW; 		}	if(i < 0 || i > L->length + 1){	//检查插入位置的正确性。 		printf("插入位置错误/n");		return ERROR;	}	for(j = L->length-1; j >= i; j--){		L->elem[j+1] = L->elem[j];	}	L->elem[i] = x;	L->length++;	return TRUE;					//插入成功，返回 } //3.顺序表的删除//操作步骤//（1）将ai+1 ~ an依次向上移动；//（2）将Length值减1。 int delete_SeqList(SeqList *L, int i) {	//删除表中第i个元素，若表空或不存在指定元素，则返回ERROR 	int j;	 if(i < 0 || i > L->length-1) {			//检查空表及删除位置的合法性。 	 	printf("不存在第i个元素");		 return ERROR;	 }	 for(j = i; j < L->length - 1; j++){	 	L->elem[j] = L->elem[j+1];			//向上移动 	 } 	 L->length--;	 return TRUE; 	  }  //4.顺序表中按值查找 //从第一个元素a0起依次和x比较，直到找到一个与x相等的数据元素， //返回它在顺序表中的序号，若查遍整个线性表都没有找到与x相等的元素，返回FALSE int location_SeqList(SeqList *L, ElemType x){ 	int i = 0; 	while(i < L->length && L->elem[i]  != x){ 		i++;	 }	 if(i >= L->length){	 	return FALSE;		//查找失败 	 } else{	 	return i;			//返回x的存储位置 	 } } //------------------------------------------- void print_SeqList(SeqList *L){	for(int i = 0; i < L->length; i++){		printf("%d ", L->elem[i]);	}	printf("/n");}int main(void){	init_SeqList(&L);	insert_SeqList(&L, 0, 2);	insert_SeqList(&L, 1, 3);	insert_SeqList(&L, 0, 4);	print_SeqList(&L);//	delete_SeqList(&L,0);	print_SeqList(&L);	int i= location_SeqList(&L, 35);	printf("%d/n",i);	return 0;}