线性表

[TOC]

第二章

时间和空间复杂度

image-20230322151152567

image-20230322151451180

时间复杂度

  1. 使用big O计数法

  2. 实例

    • O(1) 常量级的算法

      1
      2
      3
      4
      5
      6
      7
      int a=0;
      int b=0;
      int c=0;
      a=b;
      a=c;
      b=c;
      //就算重复1000000+都是一个常量

    • O(n) 

      1
      2
      3
      for(int i=0;i<n;++i){
          //代码
      }

    • O(logN) 

      1
      2
      3
      4
      while(i<n){
          i*=2;
      }

      image-20230322182248288

    • O(NM)

      1
      2
      3
      4
      5
      for(int i=0;i<n;i++){
          for(int j=0;j<m;++j){
              //
          }
      }

空间复杂度

  1. 实例

    • O(1)

      1
      2
      int a=0;
      int b=0;

    • O(n) new 一个维数组

      1
      2
      3
      4
      int[] newArray = new int[n];
      for(int i=0;i<n;++i){
          newArray[i]=i;
      }

    • O(n*n) new 二个维数组

      1
      int [][] newArray = new int[n][n];

线性表（案例分析）

  1. 线性表具有同一种特性的数据元素的一个有限的序列

    ![image-20230322183519529](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322183519529.png)

  2. 注意

    • 下标由1开始

  3. 基本代码

    1
    2
    3
    4
    5
    6
    const int MAX =100;
    //顺序结构
    typedef struct List{
        ELETMENT List[MAX];
        int listLenth;
    }List;

    image-20230322155844508

    image-20230322155956690

  4. 缺点

    • 存储空间分配不灵活
    • 空间复杂度高

线性表的类型定义

  1. 线性表的操作

    • 线性表的初始化（IniList）![image-20230322191953037](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322191953037.png)

    • 线性表的销毁（DestroyList）

      连本身都没有了

      ![image-20230322192004208](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322192004208.png)

    • 线性表的清楚（ClearList）

      还存在，但是是一个空表

      ![image-20230322192014702](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322192014702.png)

    • 判断线性表是否为空（ListEmpty）

      ![image-20230322192029109](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322192029109.png)

    • 求线性表的长度（ListLength）

      ![image-20230322192050448](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322192050448.png)

    • 获取元素(GetElem)

      ![image-20230322190529314](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322190529314.png)

    • 查找元素（LocateElem）

      ![image-20230322190615757](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322190615757.png)

    • 求一个元素的前驱（PrioElem）

      ![image-20230322190742641](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322190742641.png)

    • 获得一个元素的后继（NextElem）

      ![image-20230322190833997](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322190833997.png)

    • 插入一个元素（ListInsert）

      ![image-20230322191334889](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322191334889.png)

    • 删除一个元素（ListDelete）

      ![image-20230322191749620](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322191749620.png)

    • 遍历线性表（LIstTraverse）

      ![image-20230322191844657](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322191844657.png)

线性表的存储结构

顺序结构

  1. 定义：把逻辑上相邻的数据元素存储在物理相邻的存储单元

    ![image-20230322192505711](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230322192505711.png)

线性表的顺序表示和实现

  1. 实现：

    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
     //基本模板
    /*
    #define  SIZE 100
    typedef struct{
        ElemType elem[SIZE];
        int length;
    }SqList;
     */

    //int 型
    #define SIZE 100
    typedef struct{
        int intElem[SIZE];
        int length;
    }intList;

    //int double

    typedef struct{
        int intElem;
        double doubleElem;
    }Polynomial;

    typedef struct{
        Polynomial * PPolynomial;
        int length;
    }PolynomialList;


    //struct
    typedef struct{
        char* name;
        char* author;
        float price;
        int num;
    }Book;

    typedef struct{
        Book* pBook;
        int length;
    }BookList;


类C语言相关操作

  1. ElemType 元素

  2. C语言动态内存分配

  • malloc: 开辟连续的地址空间

    1
    2
    intList *pIntList=(intList*) malloc(sizeof (intList)*SIZE);
    free(pIntList);

线性表的顺序存储

![image-20230323091558306](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230323091558306.png)

  1. 代码示例

    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    #include <stdio.h>
    #include "stdlib.h"
    #include "string.h"

    #define status int
    #define OK 1
    #define ERROR -1
    #define true 1
    #define false 0
    #define ElemType char
    #define SIZE 100

    typedef struct {
        ElemType *elem;
        int length;
    } IntList;

    status initList_Sq(IntList *list);

    status destroyList(IntList *list);

    status clearList(IntList *list);

    status getListLength(IntList *list);

    status getElem(IntList *list, int i, ElemType *e);

    status isEmpty(IntList *list);

    status locateElem(IntList *list, ElemType e);

    status listInsert(IntList *list, int s, ElemType e);

    status listDelete(IntList *list, int s, ElemType *e);

    int main() {
        ElemType *e;
        IntList *list = (IntList *) malloc(sizeof(IntList));
        //初始化
        if (initList_Sq(list) != 1) {
            printf("ERROR\n");
            exit(ERROR);
        }
        for (int i = 0; i < 26; ++i) {
            list->elem[i] = 'A' + i;
            list->length++;
        }
        for (int i = 0; i < list->length; ++i) {
            printf(" %c ", list->elem[i]);
        }

        clearList(list);
        printf("\n%s\n", isEmpty(list) ? "true" : "false");

        for (int i = 0; i < 26; ++i) {
            list->elem[i] = 'A' + i;
            list->length++;
        }

        printf("\n%d\n", getListLength(list));
        getElem(list, 4, e);
        printf("\n%c\n", *e);
        printf("%d\n", locateElem(list, 'd'));
        printf("%d\n", locateElem(list, 'D'));
        listInsert(list, 5, '5');

        for (int i = 0; i < list->length; ++i) {
            printf(" %c ", list->elem[i]);
        }
        printf("\n");
        listDelete(list,5,e);
        printf("%c\n",*e);
        printf("%s",list->elem);

        listDelete(list,26,e);
        printf("\n%c\n",*e);
        printf("%s",list->elem);

        destroyList(list);
        return 0;
    }
    //删除
    status listDelete(IntList *list, int s, ElemType *e) {
        if (s < 1 || s > list->length) {
            return ERROR;
        }
        *e=list->elem[s-1];
        for (int i = s - 1; i < list->length - 1; ++i) {
            list->elem[i] = list->elem[i + 1];
        }
        list->elem[--list->length] = 0;
        return OK;
    }

    //插入
    status listInsert(IntList *list, int s, ElemType e) {
        if (s > SIZE || s < 1) {
            return ERROR;
        }
        for (int i = list->length - 1; i >= s - 1; --i) {
            list->elem[i + 1] = list->elem[i];
        }
        list->elem[s - 1] = e;
        list->length++;
        return OK;
    }

    //顺序查找空间复杂度为  O(n)
    status locateElem(IntList *list, ElemType e) {
        for (int i = 0; i < list->length; ++i) {
            if (e == list->elem[i]) {
                return i + 1;
            }
        }
        return 0;
    }

    status getElem(IntList *list, int i, ElemType *e) {
        if (i < 0 || i > list->length) {
            return ERROR;
        }
        *e = list->elem[i - 1];
        return OK;
    }

    status getListLength(IntList *list) {
        if (!list) {
            return ERROR;
        }
        return list->length;
    }

    status isEmpty(IntList *list) {
        if (list->length == 0) {
            return true;
        }
        return false;
    }

    status clearList(IntList *list) {
        memset(list->elem, 0, sizeof(list->elem));
        list->length = 0;
        return true;
    }

    status destroyList(IntList *list) {
        if (list) free(list);
        if (!list) return OK;
        return ERROR;
    }

    status initList_Sq(IntList *list) {
        list->elem = (ElemType *) malloc(sizeof(ElemType) * SIZE);
        if (!list) return ERROR;
        list->length = 0;
        return OK;
    }

线性表的链式储存

  1. 指针的组成：数据域和指针域（指向下一个）

  2. 链表的类型

    • 单链表：

      只有一个指针域的链表

    • 双链表：

      有两个指针域的链表

    • 循环链表：

      首尾相连的链表

  3. 空表的判断：

    看一下头指针的是否为NULL,如果为NULL则是空链表

  4. 设置头节点的好处：

    1. 便于首元节点的处理
    2. 处理空表和非空表就一样了

    ![image-20230324170004103](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230324170004103.png)

  5. 存取元素的方法叫做顺序存取法

    ![image-20230324170213582](C:\Users\12414\OneDrive - cuit.edu.cn\学\笔记\数据结构和算法\数据结构和算法.assets\image-20230324170213582.png)

    顺序表是随机存取

  6. 链表的操作

    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    //链表
    #include "stdio.h"
    #include "stdlib.h"

    #define status int
    #define OK 1
    #define ERROR (-1)
    #define true 1
    #define false 0
    #define ElemType char


    typedef struct node {
        ElemType date;
        struct node *next;
    } node, *linkList;
    //使用node表示节点
    //使用linkList表示链表的
    status destroyList(linkList headNode);

    status printfNode(linkList headNode);

    status initList(linkList headNode);

    status isEmpty(linkList headNode);

    status clearList(linkList headNode);

    status listLength(linkList headNode);

    int getElemSub(linkList headNode, const char e);

    status getElemBySub(linkList headNode, const int sub, ElemType *e);

    node *getElemPoint(linkList headNode, const char e);

    status insertNode(linkList headNode, int sub, ElemType e);

    status deleteNode(linkList headNode, int sub);

    int main() {
        linkList charListHead = NULL;
        char e;
        int sub;
        //创建头节点
        charListHead = (linkList) malloc(sizeof(node));
        charListHead->next = NULL;
        charListHead->date = '0';
        //初始化链表
        initList(charListHead);

        printfNode(charListHead);
        printf("\n%s", isEmpty(charListHead) ? "true" : "false");

        //清空链表
        clearList(charListHead);
        printf("\n%s\n", isEmpty(charListHead) ? "true" : "false");

        initList(charListHead);
        printfNode(charListHead);
        printf("\n%d", listLength(charListHead));

        printf("\n%d", getElemSub(charListHead, 'e'));

        getElemBySub(charListHead, 5, &e);
        printf("\n%c", e);
        printf("\n%p", getElemPoint(charListHead, 'e'));

        printf("\n%d", insertNode(charListHead, 1, 'a'));
        printf("\n%d", getElemSub(charListHead, 'a'));
        getElemBySub(charListHead, 2, &e);
        printf("\n%c", e);



        printf("\n%d\n", listLength(charListHead));
        printfNode(charListHead);

        sub = 28;
        deleteNode(charListHead, sub);
        printf("\n");
        printfNode(charListHead);
        printf("\n%d", getElemSub(charListHead, 'Z'));
        return 0;
    }
    //

    //删除
    status deleteNode(linkList headNode, int sub) {
        node *moveNode = headNode;
        node* temNode=NULL;
        int i=1;
        while(i<sub&&moveNode->next!=NULL){
            moveNode=moveNode->next;
            i++;
        }
        if(i>=sub||moveNode==NULL){
            return ERROR;
        }
        temNode=moveNode->next;
        moveNode->next=moveNode->next->next;
        free(temNode);
        return OK;

    }

    //插入元素
    status insertNode(linkList headNode, int sub, ElemType e) {
        node *moveNode = headNode;
        node *temNode = (node *) malloc(sizeof(node));
        temNode->next = NULL;
        temNode->date = e;
        if (headNode == NULL || sub >= listLength(headNode)) {
            free(temNode);
            return ERROR;
        }
        int tem = 1;
        while (tem != sub) {
            moveNode = moveNode->next;
        }
        temNode->next = moveNode->next;
        moveNode->next = temNode;
        return OK;
    }


    //取出元素返回地址
    node *getElemPoint(linkList headNode, const ElemType e) {
        node *moveNode = headNode->next;
        while (moveNode != NULL && moveNode->date != e) {
            moveNode = moveNode->next;
        }
        return moveNode;
    }


    //通过下标取出元素
    status getElemBySub(linkList headNode, const int sub, ElemType *e) {
        node *moveNode = headNode->next;
        int tem = 1;
        while (tem != sub) {
            moveNode = moveNode->next;
            tem++;
        }
        *e = moveNode->date;
        return OK;
    }

    //取出元素通过下标
    int getElemSub(linkList headNode, const ElemType e) {
        node *moveNode = headNode->next;
        int sub = 1;
        while (moveNode && moveNode->date != e) {
            moveNode = moveNode->next;
            sub++;
        }
        if (moveNode == NULL) {
            return ERROR;
        } else {
            return sub;
        }
    }


    //求链表的长度
    status listLength(linkList headNode) {
        int i = 1;
        node *moveNode = headNode->next;
        if (headNode->next == NULL) {
            return ERROR;
        }
        while (moveNode != NULL) {
            i++;
            moveNode = moveNode->next;
        }
        return i-1;
    }


    //清空链表
    status clearList(linkList headNode) {
        node *moveNode = NULL;
        node *deleteNode = NULL;
        moveNode = headNode->next;
        if (headNode->next = NULL) {
            return ERROR;
        }
        while (moveNode != NULL) {
            deleteNode = moveNode;
            moveNode = moveNode->next;
            free(deleteNode);
        }
        headNode->next = NULL;
        return OK;
    }

    //判断是否为空
    status isEmpty(linkList headNode) {
        if (headNode->next == NULL) {
            return true;
        }
        return false;
    }

    //打印
    status printfNode(linkList headNode) {
        node *moveNode = headNode->next;
        if (headNode->next == NULL) {
            return ERROR;
        }
        while (moveNode != NULL) {
            printf(" %c ", moveNode->date);
            moveNode = moveNode->next;
        }
        return OK;
    }

    //删除，包括头节点
    status destroyList(linkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode;
        node *deleteNode;
        moveNode = headNode;
        while (moveNode) {
            deleteNode = moveNode;
            moveNode = moveNode->next;
            free(deleteNode);
        }
        return OK;
    }

    //初始化
    status initList(linkList headNode) {
        node *moveNode = headNode;
        for (int i = 0; i < 26; ++i) {
            node *nextNode = (node *) malloc(sizeof(node));
            nextNode->next = NULL;
            nextNode->date = 'A' + i;
            moveNode->next = nextNode;
            moveNode = nextNode;
        }
        return OK;
    }

  7. 链表操作的时间和空间复杂度

    • 查找 O(n)

    • 插入和删除 O(1)

      理由是，插入和删除都是在一瞬间发生的事，不包括前面的查找

      所以在查找的时间复杂度为 O(n);

  8. 链表初始化的方式

    • 头插法

      意思是每次都是从头节点后面一位插入数据

      这个是反循序的

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      status initList(linkList headNode) {
          for (int i = 0; i < 26; ++i) {
              node* temNode=(node*)malloc(sizeof(node));
              if(temNode==NULL){
                  return ERROR;
              }
              temNode->date='a'+i;
              temNode->next=headNode->next;
              headNode->next=temNode;
          }
          return OK;
      }

    • 尾插法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13

      //初始化
      status initList2(linkList headNode) {
          node *moveNode = headNode;
          for (int i = 0; i < 26; ++i) {
              node *nextNode = (node *) malloc(sizeof(node));
              nextNode->next = NULL;
              nextNode->date = 'A' + i;
              moveNode->next = nextNode;
              moveNode = nextNode;
          }
          return OK;
      }

  9. 问题代码

    • 为什么将头节点放进函数malloc,在main函数中，头节点却是空？
    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include "stdio.h"
    #include "stdlib.h"

    #define status int
    #define OK 1
    #define ERROR (-1)
    #define true 1
    #define false 0
    #define ElemType char


    typedef struct node {
        ElemType date;
        struct node *next;
    } node, *linkList;

    status destroyList(linkList headNode);

    status initList(linkList headNode);

    status printfNode(linkList headNode);

    int main() {
        linkList headNode = NULL;
        initList(headNode);
        printfNode(headNode);
        destroyList(headNode);
        return 0;
    }

    status initList(linkList headNode) {
        headNode = (linkList) malloc(sizeof(node));
        if (headNode == NULL) {
            return ERROR;
        }
        headNode->next = NULL;
        headNode->date = '0';
        node *moveNode = headNode;
        for (int i = 0; i < 26; ++i) {
            node *temNode = (node *) malloc(sizeof(node));
            temNode->date = 'a' + i;
            temNode->next = NULL;
            moveNode->next = temNode;
            moveNode = temNode;
        }
        return OK;
    }


    //打印
    status printfNode(linkList headNode) {
        node *moveNode = headNode->next;
        if (headNode->next == NULL) {
            return ERROR;
        }
        while (moveNode != NULL) {
            printf(" %c ", moveNode->date);
            moveNode = moveNode->next;
        }
        return OK;
    }

    //删除，包括头节点
    status destroyList(linkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode;
        node *deleteNode;
        moveNode = headNode;
        while (moveNode) {
            deleteNode = moveNode;
            moveNode = moveNode->next;
            free(deleteNode);
        }
        return OK;
    }

    原因：

    C语言的传参本质上都是传值，也就是拷贝传参，普通变量拷贝的普通的值，指针变量拷贝的是指针

    具体参考：深入理解C语言函数传参方式 深入理解C语言函数传参方式_c 为什么是一个一个传参的_amcomputer的博客-CSDN博客](https://blog.csdn.net/qq_39463175/article/details/115566613))

    所以修改后的代码是：

    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81

    #include "stdio.h"
    #include "stdlib.h"

    #define status int
    #define OK 1
    #define ERROR (-1)
    #define true 1
    #define false 0
    #define ElemType char

    typedef struct node {
        ElemType date;
        struct node *next;
    } node, *linkList;

    status initList(linkList *headNode);

    status printfNode(linkList headNode);

    status destroyList(linkList headNode);

    int main() {
        linkList headNode = NULL;
        initList(&headNode);
        printfNode(headNode);
        destroyList(headNode);
        return 0;
    }

    status initList(linkList* headNode) {
        (*headNode)=(linkList)malloc(sizeof(node));
        if((*headNode)==NULL){
            return ERROR;
        }
        (*headNode)->next=NULL;
        (*headNode)->date='0';
        node* moveNode=(*headNode);
        for (int i = 0; i < 26; ++i) {
            node* temNode=(node*)malloc(sizeof(node));
            temNode->next=NULL;
            temNode->date='A'+i;
            moveNode->next=temNode;
            moveNode=moveNode->next;
        }
        return true;
    }

    //打印
    status printfNode(linkList headNode) {
        node *moveNode = headNode->next;
        if (headNode->next == NULL) {
            return ERROR;
        }
        while (moveNode != NULL) {
            printf(" %c ", moveNode->date);
            moveNode = moveNode->next;
        }
        return OK;
    }

    //删除，包括头节点
    status destroyList(linkList headNode) {
        int num = 0;
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode;
        node *deleteNode;
        moveNode = headNode;
        while (moveNode != NULL) {
            num++;
            deleteNode = moveNode;
            moveNode = moveNode->next;
            free(deleteNode);
            deleteNode = NULL;
        }
        headNode = NULL;
        printf("%d", num);
        return OK;
    }

循环链表

  1. 最后一个节点指向首节点

  2. 因为没有最后一个节点为空，所以我们在遍历的时候，我们需要判断等不等于头节点

  3. 使用尾指针更加的方便（更快的操作末节点，头节点和a1）

  4. 简单的代码示例

    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #include "stdio.h"
    #include "stdlib.h"

    #define status int
    #define OK 1
    #define ERROR (-1)
    #define true 1
    #define false 0
    #define ElemType char

    typedef struct node {
        ElemType date;
        struct node *next;
    } node, *circularLinkList;

    circularLinkList initList(circularLinkList *headNode);

    status destroyList(circularLinkList headNode);

    status printfList(circularLinkList headNode);

    status combineList(circularLinkList tailNode1, circularLinkList tailNode2);

    int main() {
        circularLinkList headNode1 = NULL;
        circularLinkList headNode2 = NULL;
        circularLinkList tailNode1 = NULL;
        circularLinkList tailNode2 = NULL;
        tailNode1 = initList(&headNode1);
        tailNode2 = initList(&headNode2);
        printfList(headNode1);
        printf("\n");
        combineList(tailNode1,tailNode2);
        printfList(headNode1);
        destroyList(headNode1);
        return 0;
    }

    //将链表2接在链表一的后面，且保留链表一的头节点
    status combineList(circularLinkList tailNode1, circularLinkList tailNode2) {
        if (tailNode1 == NULL || tailNode1 == NULL) {
            return ERROR;
        }
        node *temNode = tailNode1->next;
        tailNode1->next = tailNode2->next->next;
        free(tailNode2->next);
        tailNode2->next=NULL;
        tailNode2->next = temNode;
        return OK;
    }


    status printfList(circularLinkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode = headNode->next;
        while (moveNode != headNode) {
            printf(" %c ", moveNode->date);
            moveNode = moveNode->next;
        }
        return OK;
    }


    status destroyList(circularLinkList headNode) {
        node *moveNode = headNode->next;
        node *deleteNode = NULL;
        if (headNode == NULL) {
            return ERROR;
        }
        while (moveNode != headNode) {
            deleteNode = moveNode;
            moveNode = moveNode->next;
            free(deleteNode);
        }
        free(headNode);
        return OK;
    }

    circularLinkList initList(circularLinkList *headNode) {
        (*headNode) = (node *) malloc(sizeof(node));
        (*headNode)->next = NULL;
        (*headNode)->date = '0';
        char a;
        scanf("%c", &a);
        getchar();
        node *moveNode = (*headNode);
        for (int i = 0; i < 26; ++i) {
            node *temNode = (node *) malloc(sizeof(node));
            temNode->date = a + i;
            temNode->next = NULL;
            moveNode->next = temNode;
            moveNode = moveNode->next;
        }
        moveNode->next = (*headNode);
        return moveNode;
    }

双向链表

  1. 代码示例

    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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    #include <stdio.h>
    #include<stdlib.h>


    #define status int
    #define OK 1
    #define ERROR (-1)
    #define true 1
    #define false 0
    #define ElemType char


    typedef struct node {
        ElemType data;
        struct node *next, *prior;
    } node, *linkList;


    status insertNode(linkList headNode, ElemType data, int sub) {
        if (headNode == NULL || sub < 1) {
            return ERROR;
        }
        node *temNode = (node *) malloc(sizeof(node));
        temNode->data = data;
        node *moveNode = headNode;
        while (--sub) {
            moveNode = moveNode->next;
        }
        moveNode->next->prior = temNode;
        temNode->next = moveNode->next;
        temNode->prior = moveNode;
        moveNode->next = moveNode->next->prior;
        return OK;
    }

    int getLinkLength(linkList headNode){
        if(headNode==NULL){
            return ERROR;
        }
        int i=1;
        node* moveNode=headNode->next;
        while(moveNode!=headNode){
            moveNode=moveNode->next;
            i++;
        }
        return i;
    }


    status deleteNode(linkList headNode, int sub) {
        if (headNode == NULL || sub < 1||sub%getLinkLength(headNode)==0) {
            printf("deleteNode ERROR\n");
            return ERROR;
        }
        node *moveNode = headNode->next;
        while (--sub) {
            moveNode = moveNode->next;
        }
        moveNode->next->prior = moveNode->prior;
        moveNode->prior->next = moveNode->next;
        free(moveNode);
        moveNode=NULL;
        return OK;
    }

    status insertLink(linkList headNode, linkList insertHeadNode) {
        if (headNode == NULL || insertHeadNode == NULL) {
            return ERROR;
        }
        node *temNode = headNode;
        headNode->prior->next = insertHeadNode->next;
        insertHeadNode->next->prior = headNode->prior;
        headNode->prior = insertHeadNode->prior;
        headNode->prior->next = headNode;
        free(insertHeadNode);
        return OK;
    }

    status destroyLink(linkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode = headNode->next;
        node *deleteNode = moveNode;
        int num = 0;
        while (moveNode != headNode) {
            moveNode = moveNode->next;
            free(deleteNode);
            deleteNode = NULL;
            num++;
        }
        free(headNode);
        printf("%d", num);
        headNode = NULL;
        return OK;
    }

    status initLinkList(linkList *headNode) {
        (*headNode) = (node *) malloc(sizeof(node));
        if ((*headNode) == NULL) {
            return ERROR;
        }
        char a;
        (*headNode)->data = '0';
        (*headNode)->next = NULL;
        (*headNode)->prior = NULL;
        node *moveNode = (*headNode);
        printf("a=");
        scanf("%c", &a);
        getchar();
        for (int i = 0; i < 26; ++i) {
            node *temNode = (node *) malloc(sizeof(node));
            temNode->data = a + i;
            moveNode->next = temNode;
            moveNode->next->prior = moveNode;
            moveNode = moveNode->next;
        }
        moveNode->next = (*headNode);
        moveNode->next->prior = moveNode;
        return OK;
    }

    status printNodeACW(linkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode = headNode->prior;
        while (moveNode != headNode) {
            printf(" %c ", moveNode->data);
            moveNode = moveNode->prior;
        }
        printf("\n");
        return OK;
    }

    status printNodeCW(linkList headNode) {
        if (headNode == NULL) {
            return ERROR;
        }
        node *moveNode = headNode->next;
        while (moveNode != headNode) {
            printf(" %c ", moveNode->data);
            moveNode = moveNode->next;
        }
        printf("\n");
        return OK;
    }

    int main() {
        linkList headNode;
        linkList headNode2;
        initLinkList(&headNode);
        initLinkList(&headNode2);
        printNodeCW(headNode);
        printNodeACW(headNode);

        insertLink(headNode, headNode2);
        printNodeCW(headNode);

        insertNode(headNode, '&', 54);
        printNodeCW(headNode);
        printf("\n%d\n", getLinkLength(headNode));

        deleteNode(headNode,55);
        printNodeCW(headNode);

        printf("\n%d\n", getLinkLength(headNode));

        destroyLink(headNode);

        return 0;
    }


    不同链表的比较

    多种链表的比较

    链式存储的优点

线性表的应用

  1. 有序表的合并

    • 线性表

      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
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      #include <stdio.h>
      #include<stdlib.h>


      #define status int
      #define OK 1
      #define ERROR (-1)
      #define true 1
      #define false 0
      #define ElemType int


      typedef struct node {
          ElemType *elem;
          int length;
      } node, *linkList;

      status printfList(linkList headNode) {
          if (headNode == NULL) {
              return ERROR;
          }
          for (int i = 0; i < headNode->length; ++i) {
              printf(" %d ", headNode->elem[i]);
          }
          return OK;
      }

      status initList(linkList *headNode) {

          int num;
          printf("num:");
          scanf("%d", &num);
          (*headNode) = (node *) malloc(sizeof(node));
          (*headNode)->length = num;
          (*headNode)->elem = (ElemType *) malloc(sizeof(ElemType) * num);
          for (int i = 0; i < num; ++i) {
              scanf("%d", &(*headNode)->elem[i]);
          }
          return OK;
      }

      status combineList(linkList *headNode1, linkList headNode2) {
          int subLa = 0, subLb = 0;
          int l1 = (*headNode1)->length, l2 = headNode2->length;
          int i = 0;
          ElemType *temC = (int *) malloc(sizeof(int) * (l1 + l2));
          for (i = 0; subLa < l1 && subLb < l2; ++i) {
              temC[i] = (*headNode1)->elem[subLa] < headNode2->elem[subLb] ? (*headNode1)->elem[subLa++]
                                                                           : headNode2->elem[subLb++];
          }
          while (i < l1 + l2) {
              *(temC + i) = subLb < l2 ? (headNode2)->elem[subLb++] : (*headNode1)->elem[subLa++];
              i++;
          }
          (*headNode1)->elem = temC;
          (*headNode1)->length = l1 + l2;

          return OK;
      }


      status destroyLink(linkList pDel) {
          if (pDel == NULL) {
              return ERROR;
          }
          free(pDel->elem);
          free(pDel);
          return OK;
      }

      int main() {
          linkList headNode1 = NULL;
          linkList headNode2 = NULL;
          initList(&headNode1);
          initList(&headNode2);
          combineList(&headNode1, headNode2);
          printfList(headNode1);
          destroyLink(headNode1);
          destroyLink(headNode2);
          return 0;
      }

    • 链表

      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
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96

      #include <stdio.h>
      #include<stdlib.h>


      #define status int
      #define OK 1
      #define ERROR (-1)
      #define true 1
      #define false 0
      #define ElemType int


      typedef struct node {
          ElemType elem;
          struct node *next;
      } node, *linkList;

      status initList(linkList *headNode) {

          (*headNode) = (node *) malloc(sizeof(node));
          (*headNode)->elem = 0;
          (*headNode)->next = NULL;
          int num;
          printf("num:");
          scanf("%d", &num);
          node *moveNode = (*headNode);
          for (int i = 0; i < num; ++i) {
              node *temNode = (node *) malloc(sizeof(node));
              temNode->next = NULL;
              scanf("%d", &temNode->elem);
              moveNode->next = temNode;
              moveNode = moveNode->next;
          }
      }

      status destroyList(linkList headNode) {
          if (headNode == NULL) {
              return ERROR;
          }
          node *moveNode = headNode;
          node *deleteNode = NULL;
          int num=0;
          while (moveNode != NULL) {
              deleteNode = moveNode;
              moveNode = moveNode->next;
              free(deleteNode);
              num++;
          }
          printf("%d",num);
          return OK;
      }

      status combineList(linkList *headNode, linkList headNode2) {
          if (headNode == NULL || headNode2 == NULL) {
              return ERROR;
          }
          node *moveNode1 = (*headNode)->next, *moveNode2 = headNode2->next, *moveNodeC = (*headNode);
          while (moveNode1 != NULL && moveNode2 != NULL) {
              if (moveNode1->elem > moveNode2->elem) {
                  moveNodeC->next = moveNode2;
                  moveNode2 = moveNode2->next;
                  moveNodeC=moveNodeC->next;
              } else {
                  moveNodeC->next = moveNode1;
                  moveNode1 = moveNode1->next;
                  moveNodeC=moveNodeC->next;
              }
          }
          moveNodeC->next = moveNode1==NULL ? moveNode2 : moveNode1;
          free(headNode2);
          return OK;
      }
      status printfNode(linkList headNode) {
          if (headNode == NULL) {
              return ERROR;
          }
          node *moveNode = headNode->next;
          while (moveNode != NULL) {
              printf(" %d ", moveNode->elem);
              moveNode = moveNode->next;
          }
          printf("\n");
          return OK;
      }
      int main() {
          linkList headNode1=NULL;
          linkList headNode2=NULL;
          initList(&headNode1);
          initList(&headNode2);
          printfNode(headNode1);
          combineList(&headNode1,headNode2);
          printfNode(headNode1);
          destroyList(headNode1);
          return 0;
      }
#数据结构和算法
线性表
https://tsy244.github.io/2023/03/27/算法/数据结构/线性表/
Author
August Rosenberg
Posted on
March 27, 2023
Licensed under