线性表及其应用

2021年8月12日 17:02 阅读 39 评论 0

线性表的顺序存储

线性表的顺序存储一般表现为数组的方式,每个存储单元之间是连续的。

首先我们来定义一个线性表的结构体

typedef struct SqList { 
    ElemType elem[MAXSIZE]; // 线性表占用的空间 
    int length; // 当前数组长度(有效长度) 
}SqList; 
顺序表初始化

定义好之后,我们首先要做的是初始化一个顺序表

# define MAXSIZE 100 // 数组的最大长度 
Status InitSqList(SqList &L){ 
    L.elem = new ElemType[MAXSIZE]; 
    if(!L.elem){  // 若内存空间分配失败 
        reutrn exit(OVERFLOW); 
    } 
    L.length = 0; // 数组长度初始化为0 
    return OK; 
} 

调用上面的函数后,一个线性表就初始化完成了,ElemType是任意的数据类型,在初始化的时候是什么改成什么就行。

在定义了一个ADT后我们需要为其提供一些常用的方法,如:取值、查找、删除、遍历等等,接下来我们就一一实现这些操作。

顺序表取值

我们知道顺序表其实相当于是一个数组,所以我们可以使用数组下标的方式来实现

Status GetItem(SqList L,int i,ElemType &e){ 
    if(1 < 1||i>L.length){ 
        return ERROR; // 若i小于1或大于数组长度,返回ERROR 
    } 
    e = L[i-1]; // 将第i-1个元素赋给e 
    return OK; 
} 
顺序表查找

查找这里指的是给定一个元素,在顺序表中查找第1个与其相等的元素

  • 若成功,返回该元素下标+1(因为数组的下标是0开始的,不符合一般的计数习惯)
  • 若失败,即没有元素与给定元素相等,则返回0
int FindElemLocation(SqList L,elemType e){ 
    for (int i=0;i<L.length;i++){ 
        if(L[i] == e){ 
            return ++i; 
        } 
    } 
    return 0; 
} 

顺序表插入

顺序表的插入可能是顺序表最大的缺点了,因为顺序表的数据都是顺序存储的,如果要在第i的位置插入元素,那么i后面的元素都得依次后移,实现算法如下:

Status SqlListInsert(SqList L,int i,elemType e){ 
    if(i<1||i>L.length){ 
        return ERROR; 
    } 
    if (i==MAXSIZE){ // 若数组已满 
        return ERROR; 
    } 
    if(i>L.length){ // 若在当前数组末尾元素后添加 
        L.elem[i-1] = e; 
        return OK; 
    } 
    for (int j=L.length-1;j>=i-1;j--){ 
        L.elem[j+1] = L.elem[j] // 第i个位置之后的元素统一后移 
    } 
    L.elem[i-1] = e; 
    ++ L.length; 
    return OK; 
} 

有插入那么肯定就有删除,我们下面来实现删除的算法,和插入刚好相反,再删除一个数据元素后,这个数据元素之后的数据元素都需向前移动一个位置。

Status SqListDelete(SqList L,int i){ 
    if(i<1||i>L.length){ 
        return ERROR; 
    } 
    for (int j=i;j<=L.length-1;j++){ 
        L.elem[j-1] = L.elem[j]; 
    } 
    -- L.length; 
    return OK; 
} 

至此顺序表的基本操作就已经实现了。

线性表的链式存储

链表和顺序表最大的区别是,数据元素在物理上不是顺序存储的,只是在逻辑上是顺序连在一起的,这就意味着必须有个链条将每个数据元素都连接起来,没错,这个链条就是指针。

链表又分为单向链表和双向链表,我们先来看单向链表。

首先来看链表的ADT定义:

typedef struct LNode { 
    ElemType data; 
    LinkList *next; 
}LNode,*LinklList; 

由结构体可知,一个单链表的数据元素(又称结点)有两个属性,一个是data,是这个结点的数据元素对应的值,另外一个是next指针变量,用于存放下一个结点的地址。

所以当一堆LNode变量依次指向的时候,就形成了单链表。

但是这样连起来的结点,我们只知道下一个结点(后继结点)的位置,如果我们想要知道上一个结点(前驱结点)的位置就有点困难了,所以我们有了双向链表的概念。

typedef struct DuLNode { 
    ElemType data; 
    DuLNode *prior; // 直接前驱 
    DuLNode *next; // 直接后继 
}DuLNode,*LinkList; //LinkList 为指向结构体 LNode 的指针类型 

和顺序表一样,链表也有着类似的基本操作。

单链表初始化
#include <stdlib.h> 
Status InitList(LinkList &L){ 
    L = new Node; // 伪代码,真实代码参考下方 
    L = (DuLNode *)malloc(sizeof(DuLNode)); 
    L -> next = NULL; 
    return OK; 
} 
单链表取值

和顺序表不同是,链表不能通过数组下标来取值了,针对无需单链表,只能从头遍历,通过计数器来取第i位置的元素

假设链表有头结点

Status GetElem(LinkList L,int i,ElemType &e){ 
    LinkList *p = (LinkList *)malloc(sizeof(LinkList)); 
    p = L -> next; 
    j = 1; 
    while(p&&j<i){ 
        p = p -> next; 
        j++; 
    } 
    if(!p||j>i){ // 若此时P指向NULL,即链表长度小于i 
        return ERROR; 
    } 
    e = p -> data; 
    return OK; 
} 
单链表取值

和链表的取值一样,只是多了比较的步骤

LNode getElemLocation(LinkList L,ElemType e){ 
    p = p -> next; // 让p指向首元结点 
    while(p){ 
        if(p -> data == e){ 
            return p; 
        } 
    } 
    return NULL; 
} 
单链表的插入

链表的插入和删除都是链表的优点,因为不是顺序存储的,在插入时我们只需要让第i-1个元素的next指针指向即将插入的元素,让即将插入元素的next指针指向原本第i个指针即可。

#include<stdlib.h> 
Status ListInsert(LinkList &L,int i,ElemType e){ 
    LNode *p = (LNode *)malloc(sizeof(LNode)); 
    p = L;  
    int j = 0; // 计数器 
    while (p && j < (i - 1) ){ // 通过循环让p指向第i-1个元素 
        p = p -> next; 
        ++j; 
    } 
    LNode *ENode = (LNode *)malloc(sizeof(LNode)); // 为e创建结点 
    ENode -> data = e;  
    ENode -> next = p -> next; // e结点的next指针指向第i-1个结点的下一个结点,也就是原本第i个结点 
    p -> next = ENode; // 第i-1个结点的next指针指向e结点 
    return OK; 
} 
单链表的删除

删除与插入一个道理,删除第i个结点时,我们只需要将第i-1个结点的next指针指向第i+1也就是指向第i个结点的next就行。

Status ListDelete(LinkList &L,int i){ 
    int j=0; // 计数器 
    LNode *p = (LNode *)malloc(sizeof(LNode)); 
    p = L; 
    while(p -> next && j < ( i -1 )){ 
        p = p -> next; 
        ++j; 
    } 
    if(!p || j > ( i - 1 )){ 
        return ERROR; 
    } 
    LNode *q = (LNode *)malloc(sizeof(LNode)); // 临时结点 
    q = p -> next; // q中保存第i+1个结点的位置 
    p -> next = q -> next; // 第i-1个结点指向第i+1个结点 
    free(q); 
    return OK; 
} 

双向链表的插入和删除操作与单链表相同,只是需要改变双向的指针。

链表拓展

上面说的单链表和双链表最后一个结点的next都指向了NULL,意味着链表的结束

但是如果我们将最后一个结点指向头结点,这样就形成了一个环,这种链表叫做循环链表。

循环单链表的操作和单链表基本一致,差别仅在于:当链表遍历时,判别当前指针p是否 指向表尾结点的终止条件不同。在单链表中,判别条件为p!=NULL或p->next!=NULL, 而循环 单链表的判别条件为p!=L或p->next!=L。

最后修改于2021年8月12日 17:05
©允许规范转载

版权声明:如无特殊说明,文章均为本站原创,转载请注明出处

本文链接:https://www.yangyingqi.com/50.html

Python
微信
支付宝
登录后即可进行评论/回复
文章目录