线性表(一)

线性表的定义类型

线性表（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)初始条件:线性表已存在操作结果:销毁线性表LclearList(&L)初始条件:线性表L已存在操作结果:将L重置为空表listEmpty(&L)初始条件:线性表L已存在操作结果:若L为空表，则返回TRUE，否则返回FALSElistLength(&L)初始条件:线性表L已存在操作结果:返回L中数据元素个数GetElem(&L,i,e)初始条件:线性表L已存在,1<=i<=listLength(&L)locateElem(&L,e,compare())初始条件:线性表L已存在,compare()是数据元素判定函数操作结果:返回L中第1个与e满足关系compare()的数据元素的位序，若这样的元素不存在，则返回0priorElem(&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的长度+1listDelete(&L,i,e)初始条件:线性表L已存在且非空,1<=i<=listLength(L)操作结果:删除L的第i个数据元素，并用e返回其值,L的长度-1listTraverse(L,visit())初始条件:线性表L已存在操作结果:依次对L的每个数据元素调用函数visit()，一旦visit()失败，则操作失败}ADT List

?

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

?

#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define MAXSIZE 11typedef 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;}