Programming

数据结构——线性表

定义

线性表:零个或多个数据元素的有限序列

线性表元素的个数n(n>0)定义为线性表的长度,当n=0时,称为空表。

抽象数据类型

ADT 线性表(list)
Data
	线性表的数据对象集合为(a1,a2,a3....,an),每个元素的类型均为DataType
Operation
	Initlist(*L); 初始化操作,建立一个空的线性表L
	ListEmpty(L); 若线性表为空,返回true,否则返回false
	ClearList(*L); 将线性表清空
	GetElem(L,i,*e); 将线性表L中的第i个位置元素值返回给e
	LocateElem(L,e); 在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否						则,返回0表示失败
	ListInsert(*L,i,e); 在线性表L中的第i个位置插入新元素e
	ListDelete(*L,i,*e); 删除线性表L中第i个位置元素,并用e返回其值
	ListLength(L); 返回线性表L的元素个数
endADT

假设La表示集合A,Lb表示集合B, 如果要实现线性表集合A和B的并集操作。即要使得集合A = AUB

/*将所有的线性表Lb中但不在La中的数据元素插入到La中*/
void union(List *La,List Lb)
{
    int La_len,Lb_len,i;
    ElemType e;						/*声明与La和Lb相同的数据元素e*/
    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))	/*La中不存在和e相同数据元素*/
            ListInsert(La,++La_len,e);/*插入*/
    }
}

对于复杂的个性化的操作,其实就是把基本操作组合起来实现的。

线性表的顺序存储结构

顺序存储定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素

顺序存储方式

可以用C语言的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。

线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。

#define MAXSIZE 20
typedef int ElemType;  /*ElemType类型根据实际情况而定,这里假设为int * */
typedef struct
{
    ElemType data[MAXSIZE];	/*数组存储数据元素,最大值为MAXSIZE*/
    int length;				/*线性表当前长度*/
}Sqlist

这里,我们就发现描述顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量:数组长度Maxsize
  • 线性表的当前长度:length

顺序存储结构的插入与删除

获得元素操作

对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表L中的第i个位置元素值返回,其实是非常简单的。就程序而言,只要i的数值在数组下标范围内,就是把数组第i-1下标的值返回即可。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem(Sqlist L, int i,ElemType *e)
{
    if(L.length==0||i<1||i>L.length)
        return ERROR;
    *e = L.data[i-1];
    return OK;
}

插入操作

如果我们要实现ListInsert(*L,i,e),即在线性表L中的第i个位置插入新元素e,应该如何操作?

插入算法的思路:

  • 如果插入位置不合理,抛出异常;
  • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
  • 从最后一个元素开始向前遍历到第i个元素,分别将它们都向后移动一个位置;
  • 将要插入元素填入位置i处;
  • 表长+1

代码如下

/*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
/*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/
Status ListInsert(Sqlist *L,int i,Elemtype e)
{
    int k;
    if (L->length==MAXSIZE)   /*顺序线性表已经满*/
        return ERROR
    if(i<1||i>L->length+1)    /*当i不在范围内时*/
        return ERROR
    if(i<=L->length)		/*若插入数据位置不在表尾*/
    {
        for(k=L->length-1;k>=i-1;k--) /*将要如数位置后数据元素向后移动一位*/
    		L->data[k+1] = L->data[k];
    }
    L->data[i-1] = e;		/*将新元素插入*/
    L->length++;
    return OK;
}

删除操作

删除算法的思路:

  • 如果删除位置不合理,抛出异常
  • 取出删除元素
  • 从删除元素位置开始遍历到最后一个元素位置,分别将他们都向前移动一个位置
  • 表长-1

代码如下

/*初始条件:顺序线性表L已存在*/
/*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1*/
Status ListDelete(Sqlist *L,int i,ElemType *e)
{
    int k;
    if(L->length==0)		/*线性表为空*/
        return ERROR
    if(i<1||i>L->length)    /*删除位置不正确*/
        return ERROR
    *e = L->data[i-1]
    if(i<L->length)
    {
        for(k=i;k<L->length;k++)	/*将删除位置后继元素前移*/
        	L->data[k-1] =L->data[k];
    }
    L->length--;
    return OK;
}

线性表顺序存储结构的优缺点

优点:

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素

缺点:

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时,难以确定存储空间的容量
  • 造成存储空间的“碎片”

线性表的链式存储结构

顺序存储结构最大的缺点就是插入和删除时需要移动大量元素,这显然需要耗费时间,有没有别的办法呢。

线性表链式存储结构的定义

为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。

n个节点(ai的存储映像)链结成一个链表,即为线性表(a1,a2,a3…,an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

我们把链表中第一个结点的存储位置叫做头指针。

我们会在单链表的第一个结点前附设一个结点,称为头结点。头结点的数据域可以不存储任何信息,头结点的指针域存储指向第一个结点的指针。

头指针和头结点的异同点

头指针:

  • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
  • 头指针具有标识作用,所以常用头指针冠以链表的名字
  • 无论链表是否为空,头指针均不为空。头指针时链表的必要元素

头结点:

  • 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义
  • 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就同意了
  • 头结点不一定是链表必须要素

代码描述

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;
typedef struct Node *LinkList; 

如果p->data = ai,那么p->next->data=a(i+1)

单链表操作

单链表的读取

获取链表第i个数据的算法思路:

  • 声明一个结点p指向链表第一个结点,初始化j从1开始
  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  • 若到链表末尾p为空,则说明第i个元素不存在
  • 否则查找成功,返回结点p的数据
/*初始条件:顺序线性表L已存在*/
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;   /*声明一结点p*/
    p = L->next;  /*让p指向链表L的第一个结点*/
    j = 1;       /*j为计数器*/
    while(p && j<i) /*p不为空或者计数器j还没有等于i时,循环继续*/
    {
        p = p->next; /*让p指向下一个结点*/
        ++j;
    }
    if(!p||j>i)
        return ERROR;  /*第i个元素不存在*/
    *e = p->data;		/*取第i个元素的值*/
    return OK;
}

插入

假设存储元素e的结点为s,要实现结点p,p->next和s之间的逻辑关系的转化,只需将结点s插入到结点p和p->next之间即可。

s->next = p->next;
p->next = p;

注意,这两句的顺序不能交换。

单链表第i个数据插入结点的算法思路:

  • 声明一结点p指向链表第一个结点,初始化j从1开始
  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  • 若到链表末尾p为空,则说明第i个元素不存在
  • 否则查找成功,在系统中生成一个空结点s
  • 将数据元素e赋值给s->data
  • 单链表的插入标准语句s->next = p->next,p->next = s
  • 返回成功

代码

/*初始条件:顺序线性表L已存在*/
/*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度+1*/
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,a;
    p = *L;
    j=1;
    while(p&&j<i)	/*寻找第i个结点*/
    {
        p = p->next;
        ++j;
    }
    if(!p||j>i)   /*第i个元素不存在*/
        return ERROR
    s = (LinkList)malloc(sizeof(Node))   /*生成新结点*/
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

删除

如果要删除p和q->next之间的结点q

q = p->next;
p->next = q->next;

删除结点的思路:

  • 声明一结点p指向链表第一个结点,初始化j从1开始
  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
  • 若到链表末尾p为空,则说明第i个元素不存在
  • 否则查找成功,将欲删除的结点p->next赋值给q
  • 单链表的删除标准语句p->next = q->next
  • 将q结点中的数据赋值给e,作为返回
  • 释放q结点
  • 返回成功

代码

/*初始条件:顺序线性表L已存在*/
/*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p->next&&j<i)   /*遍历寻找第i个元素*/
    {
        p = p->next;
        ++j;
    }
    if(!(p->next)||j>i)
        return ERROR;    /*第i个元素不存在*/
    q = p->next;
    p->next = q->next;	/*将q的后继赋值给p的后继*/
    *e = q->data;		/*将q结点中的数据给e*/
    free(q);			/*让系统回收此结点,释放内存*/
    return OK;
}

单链表的整表创建

算法思路:

  • 声明一结点p和计数器变量i
  • 初始化一空链表L
  • 让L的头结点的指针指向NULL,即建立一个带头结点的单链表
  • 循环:
    • 生成一新结点赋值给p
    • 随机生成一数字赋值给p的数据域p->data
    • 将p插入到头结点与前一新结点之间

代码:

/*随机产生n个元素的值,建立带表头结点的单链线性表L(头插法)*/
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;
    srand(time(0))    /*初始化随机种子*/
    *L = (LinkList)malloc(sizeof(Node))
    (*L)->next = NULL;	`	/*先建立一个带头结点的单链表*/
    for(i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));  /*生成新结点*/
        p->data = rand()%100 +1;
        p->next = (*L)->next;
        (*L)->next = p;     /*插入到表头*/
    }
    
}

在这段代码我们用的是插队的办法,始终让新结点在第一的位置,这种方法称为头插法

头结点L和L->next之间一直插入结点p

但事实上,我们也可以把新结点都放到最后,称为尾插法

/*随机产生n个元素的值,建立带表头结点的单链线性表L*/
void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));  /*为整个线性表*/
    r = *L;				/*r为指向尾部的结点*/
    for(i=0;i<n;i++)
    {
        p = (Node *)malloc(sizeof(Node));  /*生成新结点*/
        p->data = rand()%100+1;
        r->next = p;			/*将表尾终端结点的指针指向新结点*/
        r = p;					/*将当前的新结点定义为表尾终端结点*/
    }
    r->next =NULL;   /*表示当前链表结束*/
    
}

单链表的整表删除

算法思路:

  • 声明一个结点p和q
  • 将第一个结点赋值给p
  • 循环:
    • 将下一个结点赋值给q
    • 释放p
    • 将q赋值给p

代码:

/*初始条件:顺序线性表L已存在*/
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;			/*p指向第一个结点*/
    while(p)
    {
        q = p->next;
        free(p);
        p=q;
    }
    (*L)->next = NULL;		/*头结点指针域为空*/
    return OK;    
}

若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。

静态链表

怎么用数组来代替指针描述单链表呢?

首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每个下标都对应一个data和一个cur。数据域data,用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next指针,存放该元素的后继在数组中的下标。

我们把这种用数组描述的链表叫做静态链表,这种描述方法还有个名字叫做游标实现法。

/*线性表的静态链表存储结构*/
#define MAXSIZE 1000  /*假设链表的最大长度是1000*/
tyoedef struct
{
    ElemType data;
    int cur;		/*游标(Cursor),为0时表示无指向*/
}Component,StaticLinkList[MAXSIZE];

我们对数组第一个和最后一个元素作为特殊元素处理,不存数据。我们通常把未使用的数组元素称为备用链表。而数组第一个元素,即下标为0的元素的cur就存放备用链表的第一个结点的下标;而数组的最后一个元素的cur则存放第一个有数值的元素的下标,相当于单链表中的头结点作用,当整个链表为空时,则为0。

/*将一维数组space中各分量链成一备用链表*/
/*space[0].cur为头指针,"0"表示空指针*/
Status InitList(StaticLinkList space)
{
    int i;
    for(i=0;i<MAXSIZE-1;i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
    return OK;
}

静态链表的插入操作

每当进行插入时,可以从备用链表上取得第一个结点作为待插入的新结点

我们需要自己实现malloc()函数和free()函数

/*若备用空间链表非空,则返回分配的结点下标,否则返回0*/
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;	/*当前数组第一个元素cur存的值*/
    						/*就是要返回的第一个备用空闲的下标*/
    if(space[0].cur)
        space[0].cur = space[i].cur;/*由于要拿出一个分量来使用,所以我们*/
									/*就得把它的下一个分量用来做备用*/
    return i;
}
/*在L中第i个元素之前插入新的数据元素e*/
Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE -1;  /*注意k首先是最后一个元素的下标*/
    if(i<1||i>ListLnegth(L)+1)
        return ERROR
    j = Malloc_SSL(L)   /*获得空闲分量的下标*/
    if(j)
    {
        L[j].data = e; /*将数据赋值给此分量的data*/
        for(l = 1;l<= i-1;l++)   /*找到第i个元素之前的位置*/
            k = L[k].cur;
        L[j].cur = L[k].cur;   /*把第i个元素之前的cur赋值给新元素的cur*/
        L[k].cur = j; /*将新元素的下标赋值给第i个元素之前元素的cur*/
        return OK;
    }
    return ERROR;
}

静态链表的删除操作

同样,我们要手动实现释放结点的函数free()

/*删除在L中第i个数据元素e*/
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    if(i<1||i>ListLength(L))
        return ERROR;
    k = MAX_SIZE -1;
    for(j=1;j<=i-1;j++)
    {
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L,j);
    return OK;
}

Free_SSL(L,j)是什么意思呢,来看代码:

/*将下标为k的空闲结点回收到备用链表*/
void Free_SSL(StaticLinkList space,int k)
{
    space[k].cur = space[0].cur;  /*把第一个元素cur值赋给要删除的分量cur*/
    space[0].cur = k;    /*把要删除的分量下标赋给第一个元素的cur*/
}

ListLength函数

/*初始条件:静态链表L已存在*/
int ListLength(StaticLinkList L)
{
    int j =0;
    int i = L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

静态链表优缺点

  • 优点:在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的优缺点
  • 缺点:
    • 没有解决连续存储分配带来的表长难以确定的问题
    • 失去了顺序存储结构随机存取的特性

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。

双向链表

单链表总是要从头到尾找结点,难道就不可以正反遍历都可以吗?

为了克服单向性这一缺点,我们设计了双向链表。双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。

/*线性表的双向链表存储结构*/
typedef struct DulNode
{
    ElemType data;
    struct DulNode * prior;
    struct DulNode * next;
}DulNode,*DuLinkList;

发表评论

电子邮件地址不会被公开。 必填项已用*标注