线性表(一)

线性表的定义类型

线性表（linear_list）

一个线性表是n个数据元素的有限序列。

一个数据元素可以由多个数据项（item）组成，这个时候把数据元素称为记录（record），含有大量记录的线性表又称为文件（file）。

同一线性表中的元素必定具有相同特性，即属同一数据对象。

线性表中元素的个数n（n>=0）定义为线性表的长度，n=0时称为空表。

在非空表中的每个数据元素都有一个确定的位置，a[i]是第i个数据元素，称i为数据元素a[i]在线性表中的位序。

线性表的长度可根据需要而变化，对线性表的数据元素不仅可以访问，还可以进行插入和删除等。

抽象数据类型线性表的定义如下：

ADT List{
	数据对象:D={a[i],i=1,2,...,n,n>=0}
	数据关系:R1={<a[i-1],a[i]>,i=2,...,n}
	基本操作:
		initList(&L)
			操作结果:构造一个空的线性表
		destroyList(&L)
			初始条件:线性表已存在
			操作结果:销毁线性表L
		clearList(&L)
			初始条件:线性表L已存在
			操作结果:将L重置为空表
		listEmpty(&L)
			初始条件:线性表L已存在
			操作结果:若L为空表，则返回TRUE，否则返回FALSE
		listLength(&L)
			初始条件:线性表L已存在
			操作结果:返回L中数据元素个数
		GetElem(&L,i,e)
			初始条件:线性表L已存在,1<=i<=listLength(&L)
		locateElem(&L,e,compare())
			初始条件:线性表L已存在,compare()是数据元素判定函数
			操作结果:返回L中第1个与e满足关系compare()的数据元素的位序，若这样的元素不存在，则返回0
		priorElem(&L,cur_e,e)
			初始条件:线性表L已存在
			操作结果:若cur_e是L的数据元素，且不是第一个，则用e返回它的前驱，否则操作失败
		nextElem(&L,cur_e,e)
			初始条件:线性表L已存在
			操作结果:若cur_e是L的数据元素，且不是最后一个，则用e返回它的后继，否则操作失败
		listInsert(&L,i,e)
			初始条件:线性表L已存在，1<=i<=listLength(&L)+1
			操作结果:在L中第i个位置之前插入新的数据元素e，L的长度+1
		listDelete(&L,i,e)
			初始条件:线性表L已存在且非空,1<=i<=listLength(L)
			操作结果:删除L的第i个数据元素，并用e返回其值,L的长度-1
		listTraverse(L,visit())
			初始条件:线性表L已存在	
			操作结果:依次对L的每个数据元素调用函数visit()，一旦visit()失败，则操作失败
}ADT List

 

C语言程序模拟线性表如下：

 

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 11

typedef int elemType;
typedef struct{
	elemType *list;
	int length;	
}sqList;
/*1.初始化线性表L，分配内存空间*/
void initList(sqList *L){
	L->length = 0;
	L->list = malloc(MAXSIZE * sizeof(elemType));
	if(!L->list){
		printf("空间分配失败!\n");
		exit(0);
	}
	printf("空间分配成功!\n");
	return;
}
/*2.销毁线性表，释放内存空间*/
void destroyList(sqList *L){
	if(!L->list){
		printf("该线性表不存在!\n");
		exit(0);
	}
	free(L->list);
	L->list = NULL;
	L->length = 0;
	printf("线性表销毁成功!\n");
	return;
}
/*3.将线性表置为空表，不释放存储空间*/
void clearList(sqList *L){
	if(L->list != NULL){
		L->length = 0;
	}
	return;
}
/*4.若L为空表，则返回TRUE，否则返回FALSE*/
int listEmpty(sqList *L){
	return L->length == 0 ? TRUE : FALSE;
}
/*5.返回线性表L中数据元素的个数*/
int listLength(sqList *L){
	return L->length;
}
/*6.获取线性表中指定位置的元素*/
elemType getElem(sqList *L,int i){
	if(i<1 || i >listLength(L)){
		printf("序号越界!");
		exit(0);
	}
	return L->list[i-1];
}
/*7.返回L中第1个等于e的数据元素的位序，不存在，则返回0*/
int locateElem(sqList *L,elemType e){
	elemType *p = L->list;
	int i=0;
	while(i<listLength(L) && *p!=e){
		p++;
		i++;
	}
	if(i == listLength(L)){
		i=0;
	}
	return i+1;
}
/*8.若cur_e是L的数据元素，且不是第一个，则用e返回它的前驱，否则操作失败*/
elemType priorElem(sqList *L,elemType cur_e){
	int i;
	elemType *p = L->list;
	for(i=1;i<listLength(L);i++,p++){
		if(*p == cur_e){
			break;
		}
	}
	if(i == listLength(L)){
		printf("输入的不是该线性表的元素!");
		exit(0);
	}
	if(i == 1){
		printf("输入的元素没有前驱元素!");
		exit(0);
	}
	return L->list[i-2];
}
/*9.若cur_e是L的数据元素，且不是最后一个，则用e返回它的后继，否则操作失败*/
elemType nextElem(sqList *L,elemType cur_e){
	int i;
	elemType *p = L->list;
	for(i=1;i<listLength(L);i++,p++){
		if(*p == cur_e){
			break;
		}
	}
	if(i == listLength(L)){
		printf("输入的不是该线性表的元素!");
		exit(0);
	}
	if(i == listLength(L)-1){
		printf("输入的元素没有后继元素!");
		exit(0);
	}
	return L->list[i];
}
/*10.在线性表L中第i个位置之前插入新的数据元素e,L的长度+1*/
void listInsert(sqList *L,int i,elemType e){
	if(i < 1 || i >listLength(L)+1){
		printf("序号越界，插入失败!\n");
		exit(0);
	}
	if(listLength(L) >= MAXSIZE){
		printf("元素已满，不能插入\n");
		exit(0);
	}
	int j=listLength(L);
	while(j >= i){
		L->list[j] = L->list[j-1];
		j--;
	}
	L->list[i-1] = e;
	L->length++;
	return;
}
/*11.删除线性表L的第i个元素，并使用e返回，L长度-1*/
void listDelete(sqList *L,int i,elemType e){
	if(i < 1 || i >listLength(L)){
		printf("序号越界，插入失败!\n");
		exit(0);
	}
	e = L->list[i-1];
	while(i<listLength(L)+1){
		L->list[i-1] = L->list[i];
		i++; 
	}
	L->length--;
}
/*12.依次对线性表L的每个元素调用函数visit()*/
void listTraverse(sqList *L){
	int i;
	for(i=0;i<listLength(L);i++){
		printf("%d ",L->list[i]);
	}
	printf("\n");
	return;
}

int main(){
	sqList L;
	initList(&L);
	int i;
	for(i=1;i<=10;i++){
		listInsert(&L,i,i);
	}
	listTraverse(&L);
	elemType e;
	listDelete(&L,5,e);
	listTraverse(&L);
	e = L.list[3];
	printf("元素 %d 下一个元素是: %d\n",e,nextElem(&L,e));
	printf("元素 %d 前一个元素是: %d\n",e,priorElem(&L,e));
	printf("元素 %d 的位序是: %d\n",e,locateElem(&L,e));
	printf("线性表的第 %d 个元素是 : %d\n",9,getElem(&L,9));
	printf("当前线性表长度为:%d\n",listLength(&L));
	destroyList(&L);
	return 0;	
}