线性表

线性表的定义

线性表：由零个或多个数据元素组成的有限序列

  • 首先它是一个序列,也就是说元素之问是有个先来后到的。
  • 若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继。
  • 另外,线性表强调是有限的,事实上无论计算松发展到多强大,它所处理的元素都是有限的。

顺序存储结构

线性表的顺序存储结构具有随机存储结构的特点 时间复杂度为 O(1)

顺序结构的优缺点

  • 线性表的顺序存储结构,在存、读数据肘,不管是哪个位置,时间复杂度都是O(1)。

    而在插入或删除时,时间复杂度都是O(n)。

  • 这就说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。

  • 优点

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

  • 缺点

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

  • 线性表的顺序存储结构,它最大的缺点就是插入和删除肘需要移动大量元素,这显然就需要耗费肘间。

链式存储结构

定义

  • 我们把存储数据元素信息的域称为数据域，把存储直接后继位置的堿称为指针域。指针堿中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像,称为结点(Node)。

  • n个结点链接成一个链表,即为线性表(a1，a2，a3.，…，an)的链式存储结构。

  • 因为此链表的每个结点中只包含一个指针域,所以叫做单链表。

单链表

  • 对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显啦

  • 对于线性表来说,总得有个头有个尾,链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针,最后一个结点指针为空(NULL)。

  • image-20211110131924626

  • 头节点的数据域不存储任何信息

  • 头指针

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

  • 头指针

    • 头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据城一般无意义(但也可以用来存放链表的长度)。
    • 有了头结点,对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
    • 头结点不一定是链表的必须要素。

  • 单链表图例

image-20211110210604957

  • 空链表图例

image-20211110210727379

1
2
3
4
5
6
typedef struct Node {
    ElemType data; //数据域
    struct Node* Next;  //指针域
} Node;

typedef struct Node* LinkList;

建立单链表

  • 头插法

    • 从一个空表开始,生成新结点,读取数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。

    • 简单来说,就是把新加进的元素放在表头后的第一个位置

      • 先让新节点的next指向头节点之后
      • 然后让表头的next指向新节点

    • img

    • LinkList  CreatList1(LinkList &L){
    //从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));  //创建头结点
    L->next=NULL;  //初始为空链表
    scanf("%d", &x);  //输入结点的值
    while(x!=9999) {  //输入 9999 表示结束
        s=(LNode*)malloc(sizeof(LNode) );  //创建新结点
        s->data-x;
        s->next=L->next;
        L->next=s;  //将新结点插入表中，L为头指针
        scanf ("%d", &x);
    }  //while 结束
    return L;
}
<!--code1-->

    • 因为附设了一个指向表尾结点的指计，故时间复杂度和头插法相同。

单链表结构与顺序存储结构优缺点

存储分配方式:

  • 存储分配方式

    • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。

    • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

  • 时间性能

    • 查找

      • 顺序存储结构 O(1)
      • 单链表 O(n)

    • 插入和删除

      • 顺序存储结构需要平均移动表长一半的元素,肘间为 O(n)
      • 单链表在计算出某位置的指针后,插入和删除时间仅为 O(1)

  • 空间性能

    • 顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出。
    • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。

  • 结论

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

静态链表

用数组描述的链表叫做静态链表,这种描述方法叫做游标实现法。

静态链表及实现（C语言）详解 (biancheng.net)

  • 存储结构

    • #define MAXSIZE 1000
typedef struct{
    ElemType data;  // 数据
    int cur;  // 游标 (Cursor)
} Component, StaticLinkedList[MAXSIZE];

循环链表

  • 将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表成为单循环链表,简称循环链表
  • image-20211116203527686
  • 循环链表不一定要有头结点。
  • 判断空链表的条件原来判断 head->next是否为 null,现在则是 head->next是否等于head
  • 终端结点用尾指针 rear 指示,则查找终端结点是 0(1),而开始结点是 rear->next->next,当然也是 0(1)。