赞
踩
持续更新中。。。
定义:线性表是n个数据元素的有限序列。
思考:
1.整数是不是线性表?
不是,因为整数不是有限序列。
抽象数据类型线性表的定义如下:
ADT List{ 数据对象:D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长(也是元素个数); 称 n=0 时的线性表为空表。} 数据关系:R1={ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } i是位序 基本操作: 初始化 ->InitList(&L){构造空的线性表L} 销毁 ->Destroy(&L){销毁} 是否为空表->ListEmpty(L){若L为空 返回TRUE} 求表长 ->ListLength(L){返回L中的元素个数,即表长} 取前驱 ->PriorElem(L,cur_e,&pre_e){cur_e为一个元素且不是第一个,则用pre_e返回它的前驱} 去后继 ->NextElem(L,cur_e,&next_e) 取元素 ->GetElem(L,i,&e){用e返回L中第i个元素的值} 定位 ->LocateElem(L,e,compare()){返回L中第一个与e满足compare()的元素位序,否则返回0} 遍历 ->ListTraverse(L,visit()){依次对L的每个元素调用visit()函数} 置空 ->ClearList(&L){置空} 改变元素 ->PutElem(&L,i,e){把e覆盖第i个位置,是改变元素,不是插入} 插入 ->ListInsert(&L,i,e){插入的位置是i的前面} 删除 ->ListDelete(&L,i,&) }ADT List
例2-1 假设利用两个线性表LA和LB分别表示两个集合A和B(即线性表中的数据元素即为集合中的成员),现要求一个新的集合A=AUB。这就要求对线性表作如下操作:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插人到线性表LA中去。只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入之。
void Union(void){
int La_lenth = ListLenth(La);
int Lb_lenth = ListLenth(Lb);//求线性表的长度
for(int i = 0; i<Lb_lenth; i++){
GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e
if(!LocateElem(La,e,equal))
ListInsert(La,++La_lenth,e);//La中不存在和e相同的数据元素,则插入之
}
}
例2-2 已知线性表LA和LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。
例如,设LA =(3,5,8,11) LB =(2,6,8,9,11,15,20)则LC =(2,3,5,6,8,8,9,11,11,15,20)
void MergeList(void){ InitList(Lc); int La_lenth = ListLenth(La); int Lb_lenth = ListLenth(Lb);//求线性表的长度 int i = 0,j = 0; While((i<=La_Length) && (j<=Lb_Length))//两线性表均有元素 { if(GetElem(La,i,ai)<GetElem(Lb,i,bi)) { ListInsert(Lc,++Lc_lenth,ai); ++i; } else { ListInsert(Lc,++Lc_lenth,bi); ++j; } } while (i<La_Length) { GetElem(La,i++,ai); ListInsert(Lc,++Lc_length,ai); } while (j<Lb_Length) { GetElem(Lb,j++,bi); ListInsert(Lc,++Lc_length,bi); } }
顺序表的特点:
1.支持随机访问 2.占用连续的存储空间
//-----------线性表的动态分配顺序存储结构------------
#define LIST_INIT_SIZE 100 //线性表动态存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct
{
ElemType *elem; //存储空间基地址
int length; //当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
//-----------线性表的静态分配顺序存储结构------------
#define Maxsize 100 //线性表静态存储空间的初始分配量
typedef struct
{
ElemType data[Maxsize];
int length;
} SqList;
//-----------------构造一个空的线性表L----------------
Status InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE* sizeof(ElemType));//分配100个元素的存储空间
//void *malloc(size_t size) 分配所需的内存空间,并返回一个指向它的指针。
if (!L.elem) exit(OVERFLOW);
L.length = 0;//空表长度为0
L.listsize = LIST_INIT_SIZE;
return OK;
}
1.已知顺序表L:SqList *L;
或SqList L;
2.顺序表L长度:*L.length或L->length;
3.空表判断条件:L->length=0;
(空表不能删除)
表满判断条件:
(1)L->length=maxsize;
(2)L->length=L->listsize;(元素个数=空间长度)
4.表中第一个元素:
(1)L->data[0]
(2)L->elem[0]
(3)*(L->elem)
(4)ElemType *p;p=L->elem;*p
表中最后一个元素:
(1)L->data[L->length-1]
(2)*(L->elem+L->length-1)
(3)*L->elem[L->length-1]
(4)ElemType *p;p=L->elem+L->length-1;*p
/** * @brief 线性表的插入操作 * 在第i(1<=i<=n)个元素之前插入一个元素时,需将第n至第i个元素(共n-i+1个)向后移动一个位置 */ Status ListInsert(SqList &L,int i,ElemType e){ int *q,*p; if( i<1 || i>L.length+1 )//i值不合法返回ERROR return ERROR; if(L.length>=L.listsize){//如果存储空间已满,分配存储空间 L.elem = (ElemType *)malloc((LIST_INIT_SIZE+LISTINCREMENT)* sizeof(ElemType));//分配10个元素的存储空间 if (!L.elem) exit(OVERFLOW); //存储分配失败 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; }//O(n)
/** * @brief 线性表的删除操作 * 删除第i个元素时,需要将第i+1至第n个元素(共n-i个)往前移动一个位置 * ElemType &e:将删除的元素放在缓冲区; */ Status ListDelete(SqList &L,int i,ElemType &e){ int *q,*p; if (i<1 || i>L.length+1) return ERROR;//i值不合法返回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; }//O(n)
/**
* @brief 删除值为X的数据元素
* 从数组开头往后扫并用K记录不等于X的元素个数,且边扫描边统计K,同时将不等于X的元素往前移K位
* 最后修改顺序表的长度,实现删除顺序表L中所有值为X的元素
*/
void Del_X(SqList L,ElemType x) {
int k = 0; //记录K不等于0的个数
for (int i = 0; i < L.length-1; i++) {
if (L.elem[i] != x) {
L.elem[k] = L.elem[i];
k++; //不等于0的个数加1
}
}
L.length = k + 1;
}//O(n)
/* 初始条件:顺序线性表L已存在 */
/* 操作结果:返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在,则返回值为0 */
int LocateElem(SqList L,ElemType e,Status (* compare)(ElemType,ElemType)){
int i, *q,*p;
i = 1;
p = L.elem;
while (i<=L.length && !(*compare)(*p++,e))
++i;
if(i<=L.length)
return i;
else
return 0;
}
/* 算法2.7 MergeList函数改写*/ void MergeList_sq(SqList La,SqList Lb,SqList &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 ( *pa <= *pb) *pc++ = *pa++; else *pc++ = *pb++; } while (pa<=pa_last) *pc++ = *pa++; while (pb<=pb_last) *pc++ = *pb++; }
链式存储结构是用一组任意的存储单元存储线性表的数据元素。
链表:n个结点连接成一个链表。
结点:包括数据域和指针域。数据域用来存储数据元素信息,指针域存储直接后继的存储位置,指针域中存储的信息叫做指针或链。
链表的特点: 1.不支持随机访问 2.结点的存储空间利用率低 3.支持动态分配
1.已知链表: Lnode *L;
2.表空的条件:L->next = Null;
3.表满的条件:无
4.初始化链表
void Initlist_Ln(Lnode *&L){
L=(Lnode *)malloc(sizeof(Lnode));
L->next = Null;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。