数据结构教程 第六课 线性表的顺序表示和实现

用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。

2000:0001 2000:0003 2000:0005 2000:0007 2000:0009 2000:0011 2000:0013 2000:0015 2000:0017 ... 2000:1001 2000:1003

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

a[9]

1 2 3 4 5 6 7 8 9

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：

LOC(ai+1)=LOC(ai)+l

LOC(ai)=LOC(a1)+(i-1)*l

式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。

        

线性表的动态分配顺序存储结构

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{             ElemType *elem; //存储空间基址             int length; //当前长度             int listsize; //当前分配的存储容量以一数据元素存储长度为单位             }SqList;

顺序表的插入与删除操作：
                

序号	数据元素		序号	数据元素		序号	数据元素		序号	数据元素
1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	<-25	1 2 3 4 5 6 7 8 9	12 13 21 24 25 28 30 42 77		1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	->24	1 2 3 4 5 6 7 8 9	12 13 21 28 30 42 77
插入前n=8;插入后n=9;						删除前n=8;删除后n=7;

                                                        

顺序表的插入算法

status ListInsert(List *L,int i,ElemType e) {             struct STU *p,*q;             if (i<1||i>L->length+1) return ERROR;             q=&(L->elem[i-1]);             for(p=&L->elem[L->length-1];p>=q;--p)                          *(p+1)=*p;                          *q=e;             ++L->length;             return OK;             }/*ListInsert Before i */

顺序表的合并算法

void MergeList(List *La,List *Lb,List *Lc) {             ElemType *pa,*pb,*pc,*pa_last,*pb_last;             pa=La->elem;pb=Lb->elem;             Lc->listsize = Lc->length = La->length + Lb->length;             pc = Lc->elem =                          (ElemType *)malloc(Lc->listsize * sizeof(ElemType));                          if(!Lc->elem) exit(OVERFLOW);             pa_last = La->elem + La->length - 1;             pb_last = Lb->elem + Lb->length - 1;             while(pa<=pa_last && pb<=pb_last) {                          if(Less_EqualList(pa,pb)) *pc++=*pa++;             else *pc++=*pb++;                          }             while(pa<=pa_last) *pc++=*pa++;             while(pb<=pb_last) *pc++=*pb++;             }

顺序表的查找算法

int LocateElem(List *La,ElemType e,int type) {             int i;             switch (type) {                          case EQUAL:                          for(i=0;i<length;i++)             if(EqualList(&La->elem,&e))                          return 1;                          break;                          default:                          break;                          }                          return 0;             }

顺序表的联合算法

void UnionList(List *La, List *Lb) {             int La_len,Lb_len; int i; ElemType e;             La_len=ListLength(La); Lb_len=ListLength(Lb);             for(i=0;i<Lb_len;i++) {                          GetElem(*Lb,i,&e);             if(!LocateElem(La,e,EQUAL))                          ListInsert(La,++La_len,e);                          }                          }

线性表的顺序表示
顺序表的插入算法顺序表的合并算法