数据结构第二章线性表.ppt

第二章 线性表 2.1 线性表的逻辑结构 线性表: 有且仅有一个开始结点和一个终端结点,每一结点只有一个直接前趋和一个直接后继，开始结点没有直接前趋，终端结点没有直接后继。 线性表的抽象数据类型 ADT list { 数据对象：D={ ai | ai ∈Elemset,i=1,2,…,n, n=0 } 数据关系：R1={ ai-1 , ai | ai-1 , ai∈D,i=2,3,…,n } 基本操作： InitList(L) DestroyList(L) ClearList(L) ListEmpty(L) ListLength(L) //返回表L的数据元素个数 GetElem(L, i, e) //读取L中第i个数据元素的值，赋给e ListInsert(L, i, e) ListDelete(L, i, e) LocateElem(L, e, compare()) } ADT list 例2-1 实现算法A=AUB void union(List La, List Lb) //将所有在Lb表中但不在La表中的数据元素插入到La中 { La_len=ListLength(la); //求表的长度 Lb_len=ListLength(lb); for(i=1; i=Lb_len; i++) { GetElem(Lb,i,e);　//取Lb表中第i个元素赋给e if( !LocateElem(La, e, equal)) ListInsert(La, ++La_len, e); } } 例2-2 两表的合并 Void MergeList(List la, List lb, List lc) //表La和Lb为非递减表，将La和Lb合并为非递减的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, bj); ++j; } } while ((i=la_len) //La表还没处理完 { getelem(la, i++, ai); listinsert(lc, ++k, ai); } while ((j=lb_len) //Lb表还没处理完 {getelem(lb, j++, bj); listinsert(lc, ++k, bj); } } 2.2 线性表的顺序表示和实现 顺序存储结构：用一组地址连续的存储单元依次存储线性表 的各元素。（sequential mapping) 连续的存储单元可用一维数组来表示 #define list_init_size 100 #define listincrement 10 typedef struct { Elemtype *elem; //存储空间基地址 int length; //当前表的长度 int listsize //当前分配的存储容量 } sqlist; 注：数组指针elem表示线性表的基地址 顺序表的初始化 Status initlist_sq(sqlist L) //创建一个空的线性表L { L.elem=(elemtype *)malloc(list_init_size *sizeof(elemtype)); if (!L.elem) exit(overflow);