当前位置: 首页 > 后台 > C++

线性表

作者: admin 2019-12-04 19:59:18 阅读(180) 评论(0)

一. 线性表

1. 线性表的定义

线性表是具有相同特性元素的一个有限序列,所含元素个数为线性表长度,可等于 0。

线性表元素可以有序,也可以无序

2. 线性表的存储结构

线性表分为顺序存储结构链式存储结构,前者为顺序表,后者为链表

顺序表支持随机访问,占用连续空间;链表不支持随机访问,且结点存储空间利用率略低于顺序表(需要额外指针空间),支持动态分配存储空间。

(1) 单链表

单链表的结点由两部分组成,数据域和指针域,数据域存放数据,指针域用以指向其后继结点。

单链表分为带头结点不带头结点两种。

对于带头节电的单链表,头指针 head 指向头结点,当 head-> next == NULL 时,链表为空。

不带头结点的单链表,头指针 head 指向开始结点,当 head 为 NULL 时,链表为空。

(2) 双链表

双链表和单链表的区别在于,双链表的数据节点有两个指针,一个指向前驱结点,一个指向后继结点

注意区分带头结点和不带头结点的双链表,其原理和单链表类似。

(3) 循环单链表

循环单链表的最后一个指针域指向链表中的第一个结点。循环单链表可以实现从任意一个结点访问链表中的所有结点。

带头结点的循环单链表,当 head->next == head 时,链表为空。

不带头结点的循环单链表,当 head == NULL 时,链表为空。

(4) 循环双链表

循环双链表的终端结点的 next 指针指向表中的第一个结点,第一个结点的 prior 指针指向终端结点。

当循环双链表带不带头结点时,head == NULL 表示链表为空;

当循环双链表带头结点时, head->next == head 或 head->prior == head 都表示链表为空。

(5) 静态链表

静态链表来源于结构体数组,每个结点包含两个分量,一个是数据分量 data,一个是指针分量。但这个指针分量不同于一般的链表的指针,它其实是一个数字,数字的值表示该结点的下一个结点的数组下标,功能类似于真实指针。

3. 线性表的数据结构

(1) 线性表

#define maxSize 100

typedef struct {
    int data[maxSize]; // 数组
    int length; // 长度
}Sqlist; // 顺序表类型定义

考试中为了简便,一般这样定义:

int A[maxSize];
int n;

(2) 单链表

typedef struct LNode {
    int data; // 数据域
    struct LNode *next; // 指向后继结点的指针
}LNode; // 单链表类型定义

(3) 双链表

typedef struct DLNode {
    int data;
    struct DLNode *prior; // 指向前驱结点的指针
    struct DLNode *next; // 指向后继结点的指针
}DLNode; // 双链表类型定义

(4) 动态分配内存

LNode *A = (LNode *)malloc(sizeof(LNode));

(5) 单链表的头插法和尾插法(带头结点)

// 尾插法建立链表 C
void createListR(LNode *&C, int a[], int n) {
    LNode *s, *r; // s 用于申请新结点,r 始终指向末结点
    int i;
    C = (LNode *)malloc(sizeof(LNode)); // 申请 C 头结点空间
    C->next = NULL;
    r = C; // r 指向头结点,此时头结点就是末结点
    for(i = 0; i < n; ++i>) {
        s = (LNode *)malloc(sizeof(LNode)); // 初始化 s 结点
        s->data = a[i];
        r->next = s; // 让 r 来接纳新结点
        r = r->next; // r 指向末结点
    }
    r->next = NULL; // 让终端结点的 next 域置为 NULL
}

//头插法建立单链表
void createListF(LNode *&C, int a[], int n) {
    LNode *s;
    int i;
    C = (LNode *)malloc(sizeof(LNode));
    C->next = NULL;
    for(i = 0; i < n; ++i) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = C->next; // 让新结点 s 的 next 指针域指向头结点的下一个结点
        C->next = s; // 头结点的 next 指针域指向新结点 s
    }
}

(6) 双链表的头插法(带头结点)

// 尾插法创建双链表
void createDlistR(DLNode *&L, int a[], int n) {
    DLNode *s,*r;
    int i;
    L = (DLNode *)malloc(sizeof(DLNode));
    L->prior = NULL;
    L->next = NULL;
    r = L;
    for(i = 0; i < n; ++i) {
        s = (DLNode *)malloc(sizeof(DLNode));
        s->data = a[i];
        r->next = s;
        s->prior = r;
        r = s;
    }
    r->next = NULL;
}

4. 注意点

(1) 空间比较

顺序表存储空间是一次性分配,链表存储空间是多次分配

顺序表存储密度 = 1,链表存储密度 < 1(指针域存在占了额外空间)。

(2) 时间比较

顺序表是随机存储(可随机访问任一元素),链表是顺序存储(访问元素需要遍历其之前所有元素)。

插入/删除时移动的元素个数: 顺序表平均移动近一半元素,链表无需移动元素,只需修改指针。

顺序表插入/删除元素的平均时间复杂度为 O(n)

(3) 顺序表和链表的插入删除操作

无论是顺序表还是链表,进行删除或者插入操作时,一定要考虑清楚元素的移动和指针情况,保证没有元素会被覆盖或者指针会断开(因为结点通过指针连接,当中间有一个指针断开时,删除或插入操作便无法继续)。

0 条评论