Liu, Jian's Blog

首页 归档 标签 关于

【数据结构】线性表

2020-04-01 8 min read # 计算机考研

🔑【数据结构】之线性表

线性表

知识点讲解

线性表的基本概念与实现

  1. 线性表的定义：
    线性表是具有相同特性数据元素的一个有限序列，该序列中所含元素的个数叫做线性表的长度，用n (n>=0)来表示，n可以等于0，表示一个空表。
  2. 逻辑特性
    只有一个表头元素，只有一个表尾元素，表头元素没有前驱，表尾元素没有后继，其他元素只有唯一前驱唯一后继。
  3. 存储结构
    分为顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表
    • 顺序表
      按照逻辑顺序，依次存储从存储到从指定的存储位置开始的一块连续的存储空间中，第一个元素的存储位置就是指定的存储位置
    • 链表
      每一个结点不仅包含所含元素的信息，还包含元素之间的逻辑关系。（data和指针）
  4. 顺序表和链表的比较
    • 基于空间
      • 存储分配的方式：顺序表是一次分配的，链表是多次分配的
      • 存储密度（结点值域/总的存储量）：顺序表=1；链表<1（有指针）
    • 基于时间
      • 存取方式：顺序表随机存取，也可以顺序存取；链表只能顺序存取，时间复杂度都是O（n）
      • 插入/删除是要移动元素的个数：顺序表平均近一半的元素，链表不需要移动，只需修改指针
  5. 链表有以下五种形式：

    • 单链表

      • 带头结点：头指针指向头结点，头结点不含任何信息，从头结点的后继结点开始存储信息，head始终不等于NULL，当head->next等于NULL时，链表为空
      • 不带头结点：head直接指向开始结点，head等于NULL时，链表为空

    • 双链表
      在单链表基础上增添了一个指针域，指向当前结点的前驱

    • 循环链表

      • 将单链表的最后一个指针域指向链表的第一个结点
      • 带头结点 head=head->next链表为空；不带头结点head=NULL 链表为空

    • 循环双链表

      • 将终端结点的next指针指向链表第一个结点，将第一个结点的prior指针指向最后一个结点
      • 不带头结点head等于NULL时为空，带头结点head->next,head->prior都指向head结点
      • 以下四句都可以判断循环双链表为空：
      head->next==head;
head->prior==head;
head->next==head&&head->prior==head;
head->next==head||head->prior==head;

    • 静态链表

      • 借助一维数组来表示
      • 一般链表结点空间来自整个内存，静态链表来自于一个结构体数组
      • 每个结点包含两个分量，一个时数据元素分量，一个是指针分量

线性表的结构体定义和基本操作

线性表的结构体定义

  • 顺序表

    typedef struct
{
    int data[maxSize];
    int length;
}Sqllist;

  • 单链表结点定义

    typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode //定义单链表结点类型

  • 双链表结点定义

     typedef struct DLNode
{
    int data;
    struct DLNode *next;
    struct DLNode *prior;
}DLNode

    建立新结点
    LNode *A=(LNode *)malloc(sizeof(LNode));

顺序表的操作

  • 查找

    int finddata(SqList L,int e)
{
    int i;
    for(i=0;i<n;i++)
    if(L.data[i]==e)
    return i+1;
    return 0;
}

  • 插入

    //在第i个位置插入新元素e，如果i不合法，返回false，否则将第i个元素以及之后的元素右移一个空出一个位置插入e，顺序表长度加一
bool ListInsert(SqList &L,int i, int e)
{
    int j;
    if(i>=listsize||i<1||i>L.length+1)
    return false;
    for(j=L.length;j>=i;--j)
    {
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

  • 删除

    bool ListDelete(SqList &L,int i, int &e )
{
    if(i>=listsize||i<1||i>L.length+1)
    return false;
    e=L.data[i-1];
    for(j=i;j<L.length;++j)
    {
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}

  • 算法分析

    插入 删除 查找
    平均移动次数 n/2 (n-1)/2 (n-1)/2

单链表的操作（有头）

  • 插入
    //头插法
void createlist1(LNode *&L, int n)
{
    LNode *s;
    int x;
    L=(LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    for(int i=0;i<n;i++)
    {   
        scanf("%d",&x);
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
    }
    return L;
}

    //尾插法(将新节点插入到当前列表的表尾上，必须在增加一个尾指针r指向表尾)
void createlist2(LNode *&l, int n)
{
    LNode *s,*r;
    int x;
    L=(LNode*)malloc(sizeof(LNode));
    LNode->next=NULL;
    r=L;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=r->next;
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return L;
}
  • 查找
    //按序号查找
LNode *GetElem(Linklist L,int i)
{
    LNode *p=L->next;
    int j=1;
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    if(p&&j==i)
    return p;
    else return 0;
}

    //按值查找
LinkList *find(LinkList L,ElemType e)
{
    LNode *p=LinkList->next;
    while(p&&p->data!=e)
    p=p->next;
    if(p&&p->data==e)
    return p;
    else return 0;
}
  • 插入
    bool ListInsert(LinkList &L, int i, ElemType e)
{
    LNode *s,*p=L;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p&&j=i-1)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        retrun true;
    }
    else 
        return false;
}
  • 删除结点
    bool ListDelete(LinkList &L,int i, int &e)
{
    LNode *s,*p=L;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p&&j==i-1)
    {
        s=p->next;
        p->next=s->next;
        e=s->data;
        free(s);
        return true;
    }
    else return false;
}

循环链表

  • 循环链表最后一个结点指向头结点
  • 循环单链表可以不设头指针，而只设尾指针

双向链表

  • 在单链表基础上对每个结点增加前驱指针 prior
  • 插入删除
p之后插入s p之前插入s 删除p之后继s 删除p
s->next=p->next;
p->next=s;
s->prior=p;
s->next->prior=s;		 s->prior=p->prior;
p->prior=s;
s->next=p;
s->prior->next=s;		 s=p->next;
p->next=s->next;
p->next->prior=p		 p->prior->next=p->next;
p->next->prior=p->prior;

静态链表

#define MAXSIZE 1000
typedef struct {
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];
  • 实例
data next
0 2
1 b 6
2 a 1
3 d -1
静态链表以next=-1作为结束标志，静态链表的插入、删除与动态链表相同，只需修改指针，不需要移动元素

顺序表与单链表的比较

顺序表 单链表
以地址相邻表示关系 用指针表示关系
随机访问，取元素时间复杂度为O(1)O(1) 顺序访问，取时间复杂度O(n)O(n)
插入、删除、需要移动元素，时间复杂度O(n)O(n) 插入、删除不用移动元素，时间复杂度O(n)O(n)（用于查找位置）
  • 总结：需要反复插入、删除、用链表；反复提取，很少插入、删除用顺序表
Powered by Gridea RSS