-数据结构考研笔记.doc
文本预览下载声明
第二章 线性表
从第二章到第四章是线性结构。
线性结构的特点是：在数据元素的非空有限集中
存在唯一的一个被称做“第一个”的数据元素；
存在唯一的一个被称做“最后一个”的数据元素；
除第一个之外，集合中和每个元素均只有一个前驱；
除最后一个之外，集合中每个数据元素均只有一个后继。
2．1 线性表的类型定义：
ADT List {
数据对象：D={ai| ai∈Elemset,i=1,2,…,n,n0}
数据关系：R1={ ai-1, ai| }
基本操作：
Initlist(L)
操作结果：构造一个空的线性表L。
DestroyList(L)
初始条件：线性表L已存在。
cearlist(l)
listempty(L)
listlength(L)
getelem(L,I,e)
LocateElem(L,e,compare())
PriorElem(L,cur_e,pre_e)
NextElem(L,cur_enext_e)
listInsert(L,I,e)
listdelete(L,I,e)
ListTraverse(L,visit())
}ADT List
例2-1 利用线性表 表示两个集合A和B， 现在要求一个新的集合A=A∪B。
算法 void union (List La,List Lb)
{ La_len=listgength(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);
}
}//union
例2-2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，
算法： void MergeList(List La, List Lb, List Lc)
{
InitList(Lc);
I=j=1;k=0;
La_len=ListLength(La);Lb_len=ListLength(Lb);
While((i=La_len)(j=Lb_len))
GetElem(La,I,ai);
GetElem(Lb,j,bj);
If(ai=bj) {ListInsert(Lc,++k,ai);++I;}
Else{ListInsert(Lc,++k,by);++j;}
}
while(i=La_len){
GetElem(La,++i,ai); ListInsert(Lc,++k,ai);}
While(j=Lb_len){
GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}
}
}//MergeList
线性表的动态分配顺序存储结构：
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem;
Int length;
Int listsize;
} SqList;
构造一个空的线性表L。
Status InitList_Sq(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;
}//InitList_Sq
算法2.4 在顺序表L中第I个位置之前插入一个元素
Status ListInsert_sq(SqList L,int I, ElemTyp
显示全部