C语言数据结构之顺序表和单链表

1. 顺序表

1.1 顺序表的定义

顺序表是一种线性表结构，它的物理存储结构是数组，其数据元素存储在连续的存储单元中。在顺序表中，元素的排列顺序是固定的，元素间的逻辑关系是通过它们在数组中的下标关系进行描述的。

下面是顺序表的定义：

#define MAXSIZE 100    // 顺序表的最大长度

typedef struct {
    int data[MAXSIZE];    // 存储顺序表元素的数组
    int length;           // 当前顺序表的长度
} SqList;

1.2 常见操作

常见的操作有：插入、删除、查找、遍历。

下面是这些操作的代码实现：

插入

插入元素，需要先判断顺序表当前长度是否已经达到了最大长度，如果已经达到最大长度，则不允许插入元素。

bool ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) {
        return false;    // 插入位置不合法
    }
    if (L->length >= MAXSIZE) {
        return false;    // 顺序表已满，无法插入元素
    }
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}

删除

删除元素，需要先判断要删除的位置是否合法，如果不合法，则不允许删除元素。

bool ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) {
        return false;    // 删除位置不合法
    }
    *e = L->data[i-1];
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return true;
}

查找

查找元素，需要遍历整个顺序表，逐个与待查找元素进行比较。

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i+1;    // 返回元素在顺序表中的位置
        }
    }
    return 0;    // 未找到返回0
}

遍历

遍历元素，需要逐个输出顺序表中的元素。

void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

1.3 示例说明

下面是一条示例说明：如何用顺序表实现两个有序数组的合并。

假设有两个有序数组A和B，长度分别为m和n，将它们合并成一个有序数组C。

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

void Merge(SqList A, SqList B, SqList *C) {
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            C->data[k++] = A.data[i++];
        } else {
            C->data[k++] = B.data[j++];
        }
    }
    while (i < A.length) {
        C->data[k++] = A.data[i++];
    }
    while (j < B.length) {
        C->data[k++] = B.data[j++];
    }
    C->length = k;
}

int main() {
    SqList A = {{1, 3, 5, 7}, 4};
    SqList B = {{2, 4, 6, 8}, 4};
    SqList C;
    Merge(A, B, &C);
    for (int i = 0; i < C.length; i++) {
        printf("%d ", C.data[i]);
    }
    printf("\n");
    return 0;
}

2. 单链表

2.1 单链表的定义

单链表是一种链式存储结构，它的每个结点都包含两部分，一部分是数据域，另一部分是指针域。指针域指向链表中下一个结点的地址，通过指针域，将所有结点连接起来，形成一个单链表。

下面是单链表的定义：

typedef struct LNode {
    int data;            // 数据域
    struct LNode *next;  // 指针域
} LNode, *LinkList;

2.2 常见操作

常见的操作有：插入、删除、查找、遍历。

下面的代码实现中，省略了一些边界判断，读者可以自行添加。

插入

在单链表中插入结点，需要先找到插入位置，然后将新结点插入到该位置之后。

bool ListInsert(LinkList *L, int i, int e) {
    LNode *p = *L;
    while (--i) {
        p = p->next;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

删除

在单链表中删除结点，需要找到要删除结点的前一个结点，然后将该结点从链表中摘除。

bool ListDelete(LinkList *L, int i, int *e) {
    LNode *p = *L;
    while (--i) {
        p = p->next;
    }
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

查找

在单链表中查找元素，需要遍历整个链表，逐个与待查找元素进行比较。

LNode *GetElem(LinkList L, int i) {
    LNode *p = L;
    while (i-- && p) {
        p = p->next;
    }
    return p;
}

int LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    int i = 1;
    while (p) {
        if (p->data == e) {
            return i;
        }
        p = p->next;
        i++;
    }
    return 0;
}

遍历

遍历单链表，需要逐个输出链表中的结点数据。

void PrintList(LinkList L) {
    L = L->next;
    while (L) {
        printf("%d ", L->data);
        L = L->next;
    }
    printf("\n");
}

2.3 示例说明

下面是一条示例说明：如何用单链表实现两个有序链表的合并。

假设有两个有序链表A和B，将它们合并成一个有序链表C。

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

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

LinkList CreateList(int a[], int n) {
    LinkList L = (LNode *)malloc(sizeof(LNode));
    LNode *p = L;
    for (int i = 0; i < n; i++) {
        LNode *q = (LNode *)malloc(sizeof(LNode));
        q->data = a[i];
        q->next = NULL;
        p->next = q;
        p = p->next;
    }
    return L;
}

void Merge(LinkList A, LinkList B, LinkList *C) {
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r = *C;
    while (p && q) {
        if (p->data < q->data) {
            r->next = p;
            p = p->next;
        } else {
            r->next = q;
            q = q->next;
        }
        r = r->next;
    }
    if (p) {
        r->next = p;
    }
    if (q) {
        r->next = q;
    }
}

int main() {
    int a[] = {1, 3, 5, 7};
    int b[] = {2, 4, 6, 8};
    LinkList A = CreateList(a, 4);
    LinkList B = CreateList(b, 4);
    LinkList C = (LNode *)malloc(sizeof(LNode));
    C->next = NULL;
    Merge(A, B, &C);
    PrintList(C);
    return 0;
}