当前位置:   article > 正文

数据结构 第二章 线性表_整数集是线性表吗

整数集是线性表吗

第一章 绪论

持续更新中。。。


2.1 线性表的类型定义

定义:线性表是n个数据元素的有限序列。

思考:
1.整数是不是线性表?
  不是,因为整数不是有限序列。
  • 1
  • 2
  • 3

抽象数据类型线性表

抽象数据类型线性表的定义如下:

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 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

例.线性表的合并

例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相同的数据元素,则插入之
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

例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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

2.2 线性表的顺序表示和实现

顺序表的特点:
1.支持随机访问  2.占用连续的存储空间
  • 1
  • 2

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

//-----------线性表的动态分配顺序存储结构------------
#define LIST_INIT_SIZE 100      //线性表动态存储空间的初始分配量
#define LISTINCREMENT 10        //线性表存储空间的分配增量

typedef struct 
{
    ElemType *elem;     //存储空间基地址
    int length;         //当前长度
    int listsize;       //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
//-----------线性表的静态分配顺序存储结构------------
#define Maxsize 100             //线性表静态存储空间的初始分配量

typedef struct 
{
    ElemType data[Maxsize];
    int length;
} SqList;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
//-----------------构造一个空的线性表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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

基本语句表示

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

线性表的基本操作

(1)插入操作

/**
 * @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)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

(2)删除操作

/**
 * @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)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

思考题

  • 1.顺序表的插入和删除操作效率? 不高
  • 2.删除表中所有值=x的元素?
/**
 * @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)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

(3)查找

/* 初始条件:顺序线性表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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
/* 算法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++;

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

2.3 线性表的链式表示和实现

链式存储结构是用一组任意的存储单元存储线性表的数据元素。
链表:n个结点连接成一个链表。
结点:包括数据域和指针域。数据域用来存储数据元素信息,指针域存储直接后继的存储位置,指针域中存储的信息叫做指针或链

链表的特点: 1.不支持随机访问   2.结点的存储空间利用率低   3.支持动态分配
  • 1

基本语句表示

1.已知链表: Lnode *L;
2.表空的条件:L->next = Null;
3.表满的条件:无
4.初始化链表

void Initlist_Ln(Lnode *&L){
	L=(Lnode *)malloc(sizeof(Lnode));
	L->next = Null;
}
  • 1
  • 2
  • 3
  • 4
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号