数据结构和算法：Big-Data-Structure 大话数据结构 算法复杂度 线性表 非线性表 查找 排序_大话数据结构矩阵代码(2)

// 相关操作状态定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int  Status;            // Status 是函数的类型,其值是函数结果状态码,如 OK 等

/\*\*
 获取线性表中第 i 个元素
 
 @param L 线性表 L, 必须已存在
 @param i 要获取的编号, 需满足 i ≤ i ≤ ListLength(L)
 @param e 对应元素返回
 @return 操作结果 OK/ERROR
 \*/
Status GetSqListElem(SqList L, int i, ElemType \*e) {
    if (L.length==0 || i<1 || i>L.length) return ERROR;
    \*e = L.data[i-1];
    return OK;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

插入操作

/\*\*
 向线性表的第 i 个位置插入元素
 
 @param L 线性表, 必须存在
 @param i 位置编号, 需满足 i ≤ i ≤ ListLength(L)
 @param e 要插入的元素
 @return 操作结果 OK/ERROR
 \*/
Status SqListInsert(SqList \*L, int i, ElemType e) {
    
    // 1. 顺序线性表已满
    if (L->length == MAXSIZE) return ERROR;
    // 2. 插入位置i 不在线性表范围内
    if (i<1 || i>L->length+1) return ERROR;
    // 插入数据位置不在表尾部
    if (i <= L->length) {
        // 3.将要插入位置后的元素统一后移一位
        for (int k=L->length-1; k>=i-1; k--) {
            L->data[k+1] = L->data[k];
        }
    }
    // 4.将要插入的元素 填入 第i个位置
    L->data[i-1] = e;
    // 5. 表长+1
    L->length ++;

    return OK;
}

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

删除操作

/\*\*
 删除线性表第 i 个位置的元素
 
 @param L 线性表, 必须存在
 @param i 要删除的位置编号, 需满足 i ≤ i ≤ ListLength(L)
 @param e 被删除的元素返回
 @return 操作结果 OK/ERROR
 \*/
Status SqListDelete(SqList \*L, int i, ElemType \*e) {
    
    // 1. 空表
    if (L->length==0) return ERROR;
    // 2. 要删除的位置不正确
    if (i<1 || i>L->length) return ERROR;
    \*e = L->data[i-1];
    // 3. 若删除的不是表尾, 将删除位置 后继元素 前移
    if (i<L->length) {
        for (int k=i; k<L->length; k++) {
            L->data[k-1] = L->data[k]; // 依次前移
        }
    }
    // 4. 表长-1
    L->length --;
    
    return OK;
}

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

线性表的链式存储结构

线性表链式存储结构的定义

为了表示每个数据元素 ai 与其直接后继元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，出了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息乘坐指针或链。这两部分信息组成数据元素 ai 的存储映像，称为结点（Node）。

n 个节点（ai的存储映像）链接成一个链表，即为线性表 (a1, a2, …, an) 的连式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单链表。

链表中第一个节点的存储位置叫做头指针

有时，为了更加方便的对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点

头指针和头结点的异同

线性表链式存储结构代码描述

/\*\*
 线性表的单链表的存储结构
 
 结点由存放数据元素的数据域和存放后继结点地址的指针域组成
 \*/
typedef struct Node {
    ElemType data;     // 数据信息
    struct Node \*next; // 指向信息/单线联系
} Node;

// 定义 LinkList
typedef struct Node \*LinkList;

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

单链表的读取

/\*\*
 获取单链表第i 个位置的元素
 
 @param L 单链表, 必须存在
 @param i 要获取元素的位置标号 1 ≤ i ≤ ListLength(L)
 @param e 返回元素
 @return 操作是否成功 OK/ERROR
 \*/
Status GetLinkListElem(LinkList L, int i, ElemType \*e) {
    
    LinkList p = L->next;
    int j = 1;
    
    while (p && j<i) 
    {
        p = p->next; // 后继
        ++j;
    }
    if (!p || j > i) {
        return ERROR;
    }
    \*e = p->data;
    return OK;
}

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

单链表的插入与删除

单链表的插入

/\*\*
 向单链表第 i 个位置插入元素
 
 @param L 单链表, 必须存在
 @param i 要插入的位置标号, 1 ≤ i ≤ ListLength(L)
 @param e 要插入的元素
 @return 操作结果 OK/ERROR
 \*/
Status LinkListInsert(LinkList \*L, int i, ElemType e) {
    
    LinkList p = \*L;
    int j = 1;
    
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    // 第 i 个元素不存在
    if (!p || j >i) return ERROR;
    
    // 生成一个新节点
    LinkList s = (LinkList)malloc(sizeof(Node));
    
    // 插入元素
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

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

单链表的删除

/\*\*
 移除单链表的第 i 个位置的元素
 
 @param L 单链表,必须存在
 @param i 要移除元素的位置标号, 1 ≤ i ≤ ListLength(L)
 @param e 要删除的元素返回
 @return 操作结果 OK/ERROR
 \*/
Status LinkListDelete(LinkList \*L, int i, ElemType \*e) {
    
    LinkList p = \*L;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    // 第 i 个节点不存在
    if (!p->next || j > i) return ERROR;
    
    LinkList q = p->next;
    p->next = q->next;
    \*e = q->data;
    free(q);
    
    return OK;
}

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

单链表的整表创建

头插法

/\*\*
 随机产生 n 个元素的值, 建立带表头节点的单链线性表 L(头插法)
 
 @param L 创建的线性表 L 返回
 @param n 表元素个数
 @return 操作结果 OK/ERROR
 \*/
Status CreateLinkListHead(LinkList \*L, int n) {
    
    srand((unsigned int)time(0));
    \*L = (LinkList)malloc(sizeof(Node));
    (\*L) -> next = NULL;
    for (int i=0; i<n; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        p->data = rand() % 100 + 1;
        p->next = (\*L)->next;
        (\*L)->next = p;
    }
    return OK;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

尾插法

/\*\*
 随机产生 n 个元素的值, 建立带表头节点的单链线性表 L(尾插法)
 
 @param L 创建的线性表 L 返回
 @param n 表元素个数
 @return 操作结果 OK/ERROR
 \*/
Status CreateLinkListTail(LinkList \*L, int n) {
    
    srand((unsigned int)time(0));
    (\*L) = (LinkList)malloc(sizeof(Node));
    LinkList r = \*L;
    
    for (int i=0; i<n; i++) {
        LinkList p = (Node \*)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return OK;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

单链表的整表删除