1.概述

通常来说顺序表是在计算机的内存中以数组的形式保存的线性表，是用一组地址连续的存储单元依次存储数据元素的线性数据结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构就是顺序结构。

采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len

location (ki) = location(k1) + (i-1)len

存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

2.基本操作

#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 typedef struct { ElemType *elem; int length; int listsize; }SqList; Status InitList(SqList *L) { (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!(*L).elem) exit(OVERFLOW); (*L).length=0; (*L).listsize=LIST_INIT_SIZE; return OK; } Status DestroyList(SqList *L) { free((*L).elem); (*L).elem=NULL; (*L).length=0; (*L).listsize=0; return OK; } Status ClearList(SqList *L) { (*L).length=0; return OK; } Status ListEmpty(SqList L) { if(L.length==0) return TRUE; else return FALSE; } int ListLength(SqList L) { return L.length; } Status GetElem(SqList L,int i,ElemType *e) { if(i<1||i>L.length) exit(ERROR); *e=*(L.elem+i-1); return OK; } int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)) { ElemType *p; int i=1; p=L.elem; while(i<=L.length && !compare(*p++,e)) ++i; if(i<=L.length) return i; else return 0; } Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e) { int i=2; ElemType *p=L.elem+1; while(i<=L.length && *p!=cur_e) { p++; i++; } if(i>L.length) return INFEASIBLE; else { *pre_e=*--p; return OK; } } Status NextElem(SqList L,ElemType cur_e,ElemType *next_e) { int i=1; ElemType *p=L.elem; while(i<L.length && *p!=cur_e) { i++; p++; } if(i==L.length) return INFEASIBLE; else { *next_e=*++p; return OK; } } Status ListInsert(SqList *L,int i,ElemType e) { ElemType *newbase,*q,*p; if(i<1||i>(*L).length+1) return ERROR; if((*L).length>=(*L).listsize) { newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); (*L).elem=newbase; (*L).listsize+=LISTINCREMENT; } q=(*L).elem+i-1; for(p=(*L).elem+(*L).length-1;p>=q;--p) *(p+1)=*p; *q=e; ++(*L).length; return OK; } Status ListDelete(SqList *L,int i,ElemType *e) { ElemType *p,*q; if(i<1||i>(*L).length) return ERROR; p=(*L).elem+i-1; *e=*p; q=(*L).elem+(*L).length-1; for(++p;p<=q;++p) *(p-1)=*p; (*L).length--; return OK; } Status ListTraverse(SqList L,void(*vi)(ElemType*)) { ElemType *p; int i; p=L.elem; for(i=1;i<=L.length;i++) vi(p++); printf("\n"); return OK; } #include"c1.h" typedef int ElemType; #include"c2-1.h" #include"bo2-1.c" Status equal(ElemType c1,ElemType c2) { if(c1==c2) return TRUE; else return FALSE; } void Union(SqList *La,SqList Lb) { ElemType e; int La_len,Lb_len; int i; La_len=ListLength(*La); Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++) { GetElem(Lb,i,&e); if(!LocateElem(*La,e,equal)) ListInsert(La,++La_len,e); } } void print(ElemType *c) { printf("%d ",*c); } int main() { SqList La,Lb; Status i; int j; i=InitList(&La); if(i==1) for(j=1;j<=5;j++) i=ListInsert(&La,j,j); printf("La= "); ListTraverse(La,print); InitList(&Lb); for(j=1;j<=5;j++) i=ListInsert(&Lb,j,2*j); printf("Lb= "); ListTraverse(Lb,print); Union(&La,Lb); printf("new La= "); ListTraverse(La,print);　 return 0; }