avatar

数据结构-线性表

线性表

  • 具有相同特性数据元素的一个有限序列

顺序表

定义

  • 顺序表的结构体定义
    1
    2
    3
    4
    5
    typedef struct
    {
    int data[maxSize];
    int length;
    }Sqlist;

操作

  • 初始化顺序表

    1
    2
    3
    4
    void initList(Sqlist &L)
    {
    L.length = 0;
    }
  • 求指定位置元素的算法

    1
    2
    3
    4
    5
    6
    7
    int getElem(Sqlist L, int p, int &e)
    {
    if(p < 0 || p > L.length - 1)
    return 0;
    e = L.data[p];
    return 1;
    }
  • 按元素值的查找算法

    1
    2
    3
    4
    5
    6
    7
    8
    int findElem(Sqlist L, int e)
    {
    int i;
    for(i = 0; i < L.length; ++i)
    if(e == L.data[i])
    return i;
    return -1;
    }
  • 插入元素的算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    bool insertElem(Sqlist &L, int p, int e)
    {
    int i;
    if(p < 0 || p > L.length || maxSize == L.length)
    return false;
    for(i = L.length - 1; i >= p; --i)
    L.data[i+1] = L.data[i];
    L.data[p] = e;
    ++(L.length);
    return true;
    }
  • 删除元素的算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    bool deleteElem(Sqlist &L, int p, int &e)
    {
    int i;
    if(p < 0 || p > L.length - 1)
    return 0;
    e = L.data[p];
    // 这个i<L.length-1, 特别精髓!!!
    // L.data[length-1]的值没有被覆盖
    for(i = p; i < L.length - 1; ++i)
    L.data[i] = L.data[i+1];
    --(L.length);
    return bool;
    }

单链表

定义

  • 单链表结点定义
    1
    2
    3
    4
    5
    typedef struct LNode
    {
    int data;
    struct LNode *next;
    }LNode;

操作

  • 尾插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void createlistR(LNode &C, int a[], int n)
    {
    LNode *s, *r;
    int i;
    C = (LNode *)malloc(sizeof(LNode));
    C->next = NULL;
    r = C;
    for(i = 0; i < n; ++i)
    {
    s = (LNode *)malloc(sizeof(LNode));
    s->data = a[i];
    r->next = s;
    r = r->next;
    }
    r->next = NULL;
    }
  • 头插法建立单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void creeatelistF(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;
    C->next = s;
    }
    }
  • 归并为递增单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    // A, B都是递增有序
    // 这种情况下用尾插法
    void merge(LNode *A, LNode *B, *&C)
    {
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C = A;
    C->next = NULL;
    free(B);
    r = C;
    while(p != NULL && q != NULL)
    {
    if(p->data <= q->data)
    {
    r->next = p;
    p = p->next;
    r = r->next;
    }
    else
    {
    r->next = q;
    q = q->next;
    r = r->next;
    }
    }
    r->next = NULL;
    if(p != NULL) r->next = p;
    if(q != NULL) r->next = q;
    }
  • 归并为递减单链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    // A, B都是递增有序
    // 这种情况下用头插法
    void merge(LNode *A, LNode *B, LNode *&C)
    {
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *s;
    C = A;
    C->next = NULL;
    free(B);
    while(p != NULL && q != NULL)
    {
    if(p->data <= q->data)
    {
    s = p;
    p = p->next;
    s->next = C->next;
    C->next = s;
    }
    else
    {
    s = q;
    q = q->next;
    s->next = C->next;
    C->next = s;
    }
    }
    // 此时不能直接把剩下的直接挂在C上了
    while(p != NULL)
    {
    s = p;
    p = p->next;
    s->next = C->next;
    C->next = s;
    }
    while(q != NULL)
    {
    s = q;
    q = q->next;
    s->next = C->next;
    C->next = s;
    }
    }
  • 删除单链表中结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // 删除属性为x的结点
    bool deleteNode(LNode *C, int x);;
    {
    LNode *p, *q;
    p = C;
    while(p->next != NULL)
    {
    if(x == p->next->data)
    break;
    p = p->next;
    }
    if(p->next == NULL)
    return false;
    else
    {
    q = p->next;
    p->next = p->next->next;
    free(q);

    return true;
    }
    }

双链表

定义

  • 双链表结点定义
    1
    2
    3
    4
    5
    6
    typedef struct DLNode
    {
    int data;
    struct DLNode *prior;
    struct DLNode *next;
    }DLNode;

操作

  • 尾插法建立双链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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; // 和单链表一样,r始终指向终端结点,开始头节点也是为尾结点
    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;
    }
  • 双链表查找结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 注意这里换了一种方法,直接先指向了头结点的下一个结点
    DLNode * findNode(DLNode *C, int x)
    {
    DLNode *p = C->next;
    while(p != NULL)
    {
    if(p->data == x)
    break;
    p = p->next;
    }
    return p;
    }
  • 双链表插入节点

    1
    2
    3
    4
    5
    6
    7
    // 可以将其视为一个公式
    // 先将待插结点的两边衔接好,先保证不会断链
    // 假设在双链表中p结点后面加s结点
    s->next = p->next;
    s->prior = p;
    p->next = s;
    s->next->prior = s;
  • 双链表删除节点

    1
    2
    3
    4
    5
    // 删除双链表中p结点的后继节点
    q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
文章作者: Gy
文章链接: http://sgyat.cn/2020/04/28/线性表/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 年轻没有梦
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论