[数据结构与算法]【C语言】顺序表与链表

1、顺序表

顺序表是一种更为高级的数组。
数组的特点：一片连续的存储空间，存储相同类型的元素。
顺序表可以存储任意类型的元素，但是一个顺序表只能存储同一种类型的元素。

1.1 初版代码实现

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

//顺序表结构定义
typedef struct Vector {
    int *data;  //连续的存储空间
    int size; //顺序表可容纳的总元素个数
    int length; //已经存储的元素个数
} Vec;

/*
 * 顺序表的初始化
 */
Vec *init(int n) {
    Vec *v = (Vec *)malloc(sizeof(Vec)); 
    v->data = (int *)malloc(sizeof(int) * n);
    v->size = n;
    v->length = 0;
    return v;
}


/*
 * 顺序表的插入
 */
int insert(Vec *v, int val, int ind) {
    if (v == NULL) //顺序表不存在
        return 0;
    if (ind < 0 || ind > v->length) //插入的位置不合法
        return 0;
    if (v->length == v->size) //顺序表中的元素已经到达了最大容量
        return 0;
    for (int i = v->length; i > ind; i--) { //移动要插入的位置及其之后位置的元素，从最后的元素开始移动
        v->data[i] = v->data[i - 1];
    }
    v->data[ind] = val;
    v->length++;
    return 1;
}


/*
 * 顺序表的删除
 */
int erase(Vec *v, int ind) {
    if (v == NULL) //判断顺序表是否存在
        return 0;
    if (ind < 0 || ind >= v->length) //ind不合法
        return 0;
    for (int i = ind + 1; i < v->length; i++) {
        v->data[i - 1] = v->data[i];
    }
    v->length--;
    return 1;
}


/*
 * 顺序表的销毁
 */
void clear(Vec *v) {
    if (v == NULL) return ; //判断顺序表是否存在
    //销毁malloc申请的空间
    free(v->data); //释放数据区
    free(v); //销毁顺序表
    return ;
}


/*
 * 顺序表元素的输出
 */
void output(Vec *v) {
    if (v == NULL) return ;
    printf("Vector : [");
    for (int i = 0; i < v->length; i++) {
        i && printf(", ");
        printf("%d", v->data[i]);
    }
    printf("]\n");
    return ;
}


int main() {
    srand(time(0)); //设置随机种子
    #define max_op 20 
    Vec *vec = init(max_op);
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        int ind = rand() % (vec->length + 3) - 1; //随机生成的下标，使得其可能为负数，可能为大于v->length的情况，使得测试更全面
        int op = rand() % 4;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("insert %d at %d to Vector, result = %d\n", val, ind, insert(vec, val, ind));
            } break;
            case 3: {
                printf("erase an item at %d from Vector, result = %d\n", ind, erase(vec, ind));
            } break;
        }
        output(vec);
        printf("\n");
    }
    clear(vec);
    #undef max_op 

    return 0;
}

当前的顺序表满了的时候，就不可以再插入元素了，这样就和数组没什么区别了。但是顺序表是更高级的数组，它是可以扩容的。

1.2 顺序表扩容

动态开辟内存的方法：三z种方法都会开辟一块连续的内存空间，并返回这片空间的首地址。

• malloc: 在堆区动态申请空间，内存中是否有内容不确定

• calloc: 动态申请一块内存空间，并且可以将内存空间设置为固定的值，即清空操作

• realloc: 再一次开辟空间，可以对一片连续的存储空间进行再次开辟，从而达到扩容的效果。

  • 1）例如扩容为原来大小的2倍，realloc 会在当前的空间 data（data 为空间的首地址）后面，尝试开辟一块同等的空间接在当前空间 data 后面，如果开辟成功，返回的也是 data 的首地址；
  • 2）如果在 data 空间后面不能再扩大一倍了，会在内存空间中找一段是原 data 空间2倍的空间，将原来 data 的内容顺序地拷贝到新的空间中，拷贝完成后，realloc 会主动地释放原来的那片 data空间。
  • 3）如果1）和2）都失败了，则 realloc失败，会返回一个 NULL 地址。

如下代码是存在问题的：

int expand(Vec *v) {
	int extr_size = v->size;
	v->data = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size));
	return 1;
}

因为 realloc 开辟内存空间存在三种情况，如果开辟失败，返回的是空地址，即v->data 变成了 NULL，那么原来的地址 v->data 将永远丢失，造成内存泄漏。

正确的方式：

int expand(Vec *v) { //每次扩大两倍
    int extr_size = v->size;
    int *p; //防止内存泄漏，定义一个指针变量p
    while (extr_size) {
        p = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size));//对v->data空间进行realloc
        if (p) break; //p不为空，说明开辟成功
        extr_size /= 2; //尝试开辟的空间大小失败，于是尝试开辟一半
    }
    if (extr_size == 0) return 0; //开辟失败
    v->data = p; //新开辟的空间的地址赋给v->data
    v->size += extr_size;
    return 1;
}

1.3 终版代码实现

完整代码：

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

#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define GREEN(a) COLOR(a, 32)

typedef struct Vector {
    int *data;
    int size;
    int length;
} Vec;

/*
 * 顺序表的初始化
 */
Vec *init(int n) {
    Vec *v = (Vec *)malloc(sizeof(Vec));
    v->data = (int *)malloc(sizeof(int) * n);
    v->size = n;
    v->length = 0;
    return v;
}

/*
 * 顺序表的扩展
 */
int expand(Vec *v) {
    int extr_size = v->size;
    int *p; //防止内存泄漏，定义指针变量保存新的地址
    while (extr_size) {
        p = (int *)realloc(v->data, sizeof(int) * (v->size + extr_size)); //对v->data指向的空间进行扩容
        if (p) break; //p为空，说明空间realloc失败
        extr_size /= 2; //尝试开辟的空间大小失败，于是尝试开辟一半
    }
    if (extr_size == 0) //开辟失败
        return 0;
    v->data = p; //将新开辟的空间地址赋给v->data
    v->size += extr_size;
    return 1;
}

/*
 * 顺序表的插入
 */
int insert(Vec *v, int val, int ind) {
    if (v == NULL) 
        return 0;
    if (ind < 0 || ind > v->length) 
        return 0;
    if (v->length == v->size) { //存储的元素已经到达最大容量
        if (!expand(v)) 
            return 0;
        printf(GREEN("Success to expand! The vector size is %d") "\n", v->size);
    }
    for (int i = v->length; i > ind; i--) {
        v->data[i] = v->data[i - 1];
    }
    v->data[ind] = val;
    v->length++;
    return 1;
}

/*
 * 顺序表的删除
 */
int erase(Vec *v, int ind) {
    if (v == NULL) return 0;
    if (ind < 0 || ind >= v->length) return 0;
    for (int i = ind + 1; i < v->length; i++) {
        v->data[i - 1] = v->data[i];
    }
    v->length--;
    return 1;
}

/*
 * 顺序表的销毁
 */
void clear(Vec *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}

/*
 * 顺序表的输出
 */
void output(Vec *v) {
    if (v == NULL) return ;
    printf("Vector : [");
    for (int i = 0; i < v->length; i++) {
        i && printf(", ");
        printf("%d", v->data[i]);
    }
    printf("]\n");
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20 
    Vec *vec = init(5);
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        int ind = rand() % (vec->length + 3) - 1;
        int op = rand() % 4;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("insert %d at %d to Vector, result = %d\n", val, ind, insert(vec, val, ind));
            } break;
            case 3: {
                printf("erase an item at %d from Vector, result = %d\n", ind, erase(vec, ind));
            } break;
        }
        output(vec);
        printf("\n");
    }
    clear(vec);
    #undef max_op
    return 0;
}

2、链表

链表可以分为两个部分：程序内部（程序是如何定义的）、内存内部。

因为链表可以分为程序内部和内存内部两部分，所以链表也分为两部分进行定义：头结点的定义（程序内部）、链表结点的定义（内存内部）。

链表的每个结点都包含两个部分：数据域和指针域。

顺序表需要开辟一片连续的存储空间，如果顺序表满了需要扩容。而链表在逻辑上是顺序的，物理上并不一定，链表不需要扩容，它所开辟的用于存储一个结点的空间在物理上并不要求连续。

2.1 代码实现

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

typedef struct ListNode { //内存内部
    int data;
    struct ListNode *next; //不能使用ListNode *next，因为当前结构体还未定义完成
} ListNode;

typedef struct List { //程序内部
    ListNode head; //定义成结点而不是指针，是为了方便对链表进行操作。head是一个头结点，数据域没有任何意义，作用就是用来代表链表的头
    int length; //当前链表结点的个数
} List;

/*
 * 链表结点的初始化
 */
ListNode *getNewNode(int val) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = val;
    node->next = NULL;
    return node;
}

/*
 * 链表的初始化
 */
List *getLinkList() {
    List *l = (List *)malloc(sizeof(List));
    l->head.next = NULL;
    l->length = 0;
    return l;
}

/*
 * 链表结点的插入
 */
int insert(List *l, int ind, int val) {
    if (l == NULL) 
        return -1;
    if (ind < 0 || ind > l->length) 
        return -1;
    ListNode *node = getNewNode(val);
    ListNode *p = &(l->head);
    while (ind--) { //找到待插入位置的前一个位置
        p = p->next;
    }
    node->next = p->next;
    p->next = node;
    l->length++;
    return 0;
} 


/*
 * 链表结点的删除
 */
int erase(List *l, int ind) {
    if (l == NULL)
        return -1;
    if (ind < 0 || ind >= l->length) 
        return -1;
    ListNode *p = &(l->head);
    while (ind--) {
        p = p->next;
    }
    ListNode *temp = p->next;
    p->next = temp->next;
    free(temp);
    l->length--;
    return 0;
}

/*
 * 链表结点的打印
 */
void output(List *l) {
    if (l == NULL) return ;
    printf("List(%d) = [", l->length);
    for (ListNode *p = l->head.next; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL]\n");
    return ;
}

/*
 * 链表结点的销毁
 */
void clear_node(ListNode *node) {
   if (node == NULL) return ;
    free(node);
    return ;
}

/*
 * 链表的销毁
 */
void clear(List *l) {
    if (l == NULL) return ;
    ListNode *p = l->head.next;
    ListNode *q;
    while (p) {
        q = p->next;
        clear_node(p);
        p = q;
    }
    free(l);
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20
    List *l = getLinkList();
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        int ind = rand() % (l->length + 3) - 1;
        int op = rand() % 4;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("insert %d at %d to List, result = %d\n", val, ind, insert(l, ind, val));
            } break;
            case 3: {
                printf("erase an item at %d from List, result = %d\n", ind, erase(l, ind));
            } break;
        }
        output(l);
        printf("\n");
    }
    clear(l);
    #undef max_op
    return 0;
}

2.2 链表的翻转：头插法

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

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

typedef struct List {
    ListNode head;
    int length;
} List;

ListNode *getNode(int val) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = val;
    node->next = NULL;
    return node;
}

List *getLinkList() {
    List *l = (List *)malloc(sizeof(List));
    l->head.next = NULL;
    l->length = 0;
    return l;
}

int insert(List *l, int ind, int val) {
    if (l == NULL) 
        return -1;
    if (ind < 0 || ind > l->length) 
        return -1;
    ListNode *node = getNode(val);
    ListNode *p = &(l->head);
    while (ind--) {
        p = p->next;
    }
    node->next = p->next;
    p->next = node;
    l->length++;
    return 0;
}

int erase(List *l, int ind) {
    if (l == NULL) return -1;
    if (ind < 0 || ind > l->length) return -1;
    ListNode *p = &(l->head);
    while (ind--) p = p->next;
    ListNode *temp = p->next;
    p->next = temp->next;
    free(temp);
    l->length--;
    return 0;
}

/*
 * 链表的翻转
 */
//头插法：每次插入结点都在虚拟结点head后面
//空间复杂度O(1)
void reverse(List *l) { 
    ListNode *p = l->head.next;
    l->head.next = NULL;
    ListNode *q;
    while (p) {
        q = p->next;
        p->next = l->head.next;
        l->head.next = p;
        p = q;
    }
    return ;
}

void output(List *l) {
    if (l == NULL) return ;
    printf("List(%d) = [", l->length);
    for (ListNode *p = l->head.next; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL]\n");
    return ;
}

void clear_node(ListNode *node) {
    if (node == NULL) return ;
    free(node);
    return ;
}

void clear(List *l) {
    if (l == NULL) return ;
    ListNode *p = l->head.next;
    ListNode *q;
    while (p) {
        q = p->next;
        clear_node(p);
        p = q;
    }
    free(l);
    return ;
}


int main() {
    srand(time(0));
    #define max_op 20 
    List *l = getLinkList();
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        int ind = rand() % (l->length + 3) - 1;
        int op = rand() % 4;
        switch (op) {
            case 0:
            case 1: {
                printf("insert %d at %d to List, result = %d\n", val, ind, insert(l, ind, val));
            } break;
            case 2: {
                printf("erase an item at %d from List, result = %d\n", ind, erase(l, ind));
            } break;
            case 3: {
                printf("Reverse the List!\n");
                reverse(l);
            } break;
        }
        output(l);
        printf("\n");
    }
    clear(l);
    #undef max_op
    return 0;
}

2.3 练习题

2.3.1 Leetcode 19. 删除倒数第N个节点

【思路】利用快慢指针，快指针先前进 $N$ 步，然后快慢指针同时前进，每次前进一步，直到快指针到达链表末尾。因为最后的结果中，头结点可能发生变化，所以需要一个虚拟头结点指向真正的头结点。
【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
    p->next = head;
    struct ListNode *slow = p, *fast = head;
    while (n--) fast = fast->next;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    struct ListNode *temp = slow->next;
    slow->next = temp->next;
    free(temp);
    return p->next;
}

2.3.2 Leetcode 24. 两两交换链表中的节点

【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* swapPairs(struct ListNode* head){
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
    p->next = head;
    struct ListNode *now = p;
    while (now->next && now->next->next) {
        struct ListNode *l = now->next, *r= now->next->next;
        now->next = r;
        l->next = r->next;
        r->next = l;
        now = l;
    }
    return p->next;
}

2.3.3 Leetcode 83. 删除排序链表中的重复元素

【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteDuplicates(struct ListNode* head){
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *p = head;
    while (p->next) {
        if (p->next->val == p->val) {
            p->next = p->next->next;
        } else {
            p = p->next;
        }
    }
    return head;
}

2.3.4 Leetcode 141.环形链表

【思路】环形链表的判断就是用快慢指针：快指针一次走两步，慢指针一次走一步，如果快慢指针重合，则存在环；否则，无环。
【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    //快慢指针：快指针每次走两步，慢指针每次走一步，二者若重合则链表中有环，否则无环
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

2.3.5 Leetcode 160.相交链表

【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//双指针
//pA到达A链表的末尾后，指向B链表的头部；pB到达B链表的末尾后，指向A链表的头部
//若二者有相交节点，则最终pA = pB; 否则，最终pA和pB会以pA = pB = NULL 结束循环
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) return NULL;
    struct ListNode *pA = headA, *pB = headB;
    while (pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    } 
    return pA;
}

2.3.6 Leetcode 202.快乐数

【题目】
编写一个算法来判断一个数 $n$ 是不是快乐数。
「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到整个数变为 1，也可能是 无限循环 但始终变不到1。
• 如果可以 变为1，那么这个数就是快乐数。

如果 $n$ 是快乐数就返回 true； 不是则返回 false

【思路】本质就是个链表判环问题。

【代码】

int getNext(int x) {
    int z = 0;
    while (x) {
        z += (x % 10) * (x % 10);
        x /= 10;
    }
    return z;
}

//快慢指针
bool isHappy(int n){
    int slow = n, fast = n;
    do {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    } while (slow != fast && fast != 1);
    return fast == 1;
}

2.3.7 Leetcode 203.移除链表元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *dummyHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode *temp = dummyHead;
    while (temp->next != NULL) {
        if (temp->next->val == val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return dummyHead->next;
}

2.3.8 Leetcode 206. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL) return head;
    struct ListNode *p = head->next;
    head->next = NULL;
    struct ListNode *q;
    while (p) {
        q = p->next;
        p->next = head;
        head = p;
        p = q;
    }
    return head;
}

2.3.9 Leetcode 234. 回文链表

• 方法一：用数组保存每个节点的值，然后双指针判断数组中的值

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

#define MAX_N 100000
int arr[MAX_N + 5];

bool isPalindrome(struct ListNode* head){
    //数组保存每个节点的值，然后用双指针遍历数组
    if (head == NULL || head->next == NULL) return true;
    struct ListNode *p = head;
    int k = 0;
    while (p) {
        arr[k++] = p->val;
        p = p->next;
    }

    for (int i = 0, j = k - 1; i < j; i++, j--) {
        if (arr[i] != arr[j]) return false;
    }
    return true;
}

• 方法二

1. 利用快慢指针（快指针每次走2步，慢指针每次走1步）找到链表中点
2. 反转链表的后半段（即从中点到最后一个节点）
3. 双指针判断前半段和后半段每个节点的数据是否相等。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    //1.快慢指针找到链表中点
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        if (fast != NULL) slow = slow->next;
    }
    //此时slow为中点
    //2.翻转后半段
    struct ListNode *l = slow, *r = slow->next;
    l->next = NULL;
    while (r) {
        struct ListNode *temp = r->next;
        r->next = l;
        l = r;
        r = temp;
    }
    //3.双指针判断前后半段
    struct ListNode *p = head, *q = l;
    while (p && q) {
        if (p->val != q->val) return false;
        p = p->next;
        q = q->next;
    }
    return true;

}

2.3.10 Leetcode 237. 删除链表中的节点

【题目】
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点。
现有一个链表 —— head = [4,5,1,9]，它可以表示为：

示例1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

• 链表至少包含两个节点
• 链表中所有节点的值都是唯一的
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点
• 不要从你的函数中返回任何结果

【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    if (node == NULL || node->next == NULL) {
        node = NULL;
        return ;
    }
    //获取下一个节点的值
    node->val = node->next->val;
    //删除已经获得值的节点
    node->next = node->next->next;
}