数据结构6(下)
上一篇 /
下一篇 2010-07-04 20:45:19
假设线性表的每个元素需占用l个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系:
LOC(ai+1)=LOC(ai)+l
LOC(ai)=LOC(a1)+(i-1)*l
式中LOC(a1)是线性表的第一个数据元素的存储位
置,通常称做线性表的起始位置或基地址。常用b表示。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。
称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表
示线性表中数据元素之间的逻辑关系。
二、顺序存储结构的线性表类C语言表示:
线性表的动态分配顺序存储结构 |
#define
LIST_INIT_SIZE 100 #define LISTINCREMENT 10
typedef struct{ ElemType *elem;
//存储空间基址 int length;
//当前长度 int listsize;
//当前分配的存储容量以一数据元素存储长度为单位 }SqList; |
三、顺序存储结构的线性表操作及C语言实现:
顺序表的插入与删除操作:
序号 | 数据元素 | 序号 | 数据元素 | | 序号 | 数据元素 | 序号 | 数据元素 |
| | <-25
| | | | | | ->24 | | |
插入前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[i],&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); } } |
三、C语言源
程序范例
四、总结
线
性表的顺序表示
顺
序表的插入算法
顺
序表的合并算法
回目录上一课下一课
收藏
举报
TAG: