静态链表

静态链表、单链表和双链表都是链式存储结构，但它们在内存分配方式、节点结构和操作方式上有所不同。

1. 静态链表（Static Linked List）：

   • 静态链表使用数组来实现链式结构，而不是通过指针。数组中的每个元素对应于链表中的一个节点。
   • 静态链表在静态内存中分配节点，节点的数量在编译时确定，无法动态调整。
   • 静态链表的插入和删除操作比较麻烦，因为需要手动维护空闲节点的链表。

2. 单链表（Singly Linked List）：

   • 单链表是由节点构成的线性链表，每个节点包含数据和指向下一个节点的指针。
   • 单链表的优点是插入和删除节点的操作效率高，时间复杂度为 O(1)。
   • 单链表不能直接访问前一个节点，因此删除节点时需要先找到待删除节点的前一个节点，时间复杂度为 O(n)。

3. 双链表（Doubly Linked List）：

   • 双链表是由节点构成的线性链表，每个节点包含数据和指向前一个节点和后一个节点的指针。
   • 双链表的优点是可以直接访问前一个节点和后一个节点，因此删除节点的操作效率高，时间复杂度为 O(1)。
   • 双链表的缺点是每个节点需要额外存储一个指向前一个节点的指针，占用的空间更多。

综上所述，静态链表、单链表和双链表在内存分配、节点结构和操作效率上存在差异。选择哪种链表取决于具体的应用场景和需求。通常情况下，单链表是最常用的链表类型，因为它具有较高的操作效率和灵活性。

代码定义静态链表

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

#define MaxSize 10 //静态链表的最大长度

typedef int ElemType;
struct Node{ //静态链表结构类型的定义
    ElemType data; //存储数据元素
    int next; //下一个元素的数组下标
};
//typedef struct Node SLinkList[MaxSize];
int main() {
    struct Node a[MaxSize]; //数组a作为静态链表
    return 0;
}

上面注释的代码含义：用SlinkList定义一个长度为MaxSize的Node型数组。

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

#define MaxSize 10 //静态链表的最大长度

typedef int ElemType;
struct Node{ //静态链表结构类型的定义
    ElemType data; //存储数据元素
    int next; //下一个元素的数组下标
};

typedef  struct {
    int data;
    int next;
}SLinkList[MaxSize];

void testSLinkList(){
    struct Node x;
    printf("sizeX=%d\n",sizeof(x));
    struct Node a[MaxSize];
    printf("sizeA=%d\n", sizeof(a));
    SLinkList b;
    printf("sizeB=%d\n", sizeof(b));
}
int main() {
    testSLinkList();
    return 0;
}

代码的运行结果为：

sizeX=8
sizeA=80
sizeB=80

进程已结束，退出代码为 0

静态链表是一种使用数组实现的链式存储结构，其中数组的每个元素表示一个链表节点，通过数组下标建立节点之间的链接关系。静态链表的基本操作包括元素的查找、增加和删除。

1. 元素查找：

   • 遍历静态链表的节点，比较每个节点的数据域与目标元素，直到找到目标元素或遍历到链表末尾。
   • 如果找到目标元素，则返回该元素所在节点的位置；否则返回查找失败的信息。

2. 元素增加：

   • 分配一个新的节点作为待插入节点。
   • 将待插入节点的数据域设置为目标元素。
   • 调整链表中的链接关系，将待插入节点插入到合适的位置，使得链表仍然保持有序或满足其他条件。

3. 元素删除：

   • 遍历静态链表的节点，找到待删除节点。
   • 调整链表中的链接关系，将待删除节点从链表中摘除，并释放其内存空间。

下面是用三个子函数实现上述功能：

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

#define MaxSize 10 // 静态链表的最大长度

typedef int ElemType;
struct Node {
    ElemType data; // 存储数据元素
    int next; // 下一个元素的数组下标
};

typedef struct {
    struct Node nodes[MaxSize]; // 静态链表的节点数组
    int head; // 头指针，指向第一个节点
    int length; // 静态链表的长度
} SLinkList;

// 初始化静态链表
void InitSLinkList(SLinkList *L) {
    L->head = -1; // 头指针置为-1，表示空链表
    L->length = 0; // 链表长度置为0
}

// 查找元素在静态链表中的位置
int LocateElem(SLinkList L, ElemType e) {
    int p = L.head; // 从头节点开始遍历
    while (p != -1 && L.nodes[p].data != e) {
        p = L.nodes[p].next; // 移动到下一个节点
    }
    return p; // 返回元素位置
}

// 在静态链表中插入元素
void InsertElem(SLinkList *L, ElemType e) {
    int newNode = L->length; // 新节点的位置
    if (newNode < MaxSize) {
        L->nodes[newNode].data = e; // 设置新节点的数据域
        L->nodes[newNode].next = L->head; // 新节点的next指向原来的头节点
        L->head = newNode; // 头指针指向新节点
        L->length++; // 链表长度加1
    } else {
        printf("Static linked list is full. Insert failed.\n");
    }
}

// 从静态链表中删除元素
void DeleteElem(SLinkList *L, ElemType e) {
    int pre = -1; // 待删除节点的前一个节点位置
    int p = L->head; // 从头节点开始遍历
    while (p != -1 && L->nodes[p].data != e) {
        pre = p; // 记录前一个节点位置
        p = L->nodes[p].next; // 移动到下一个节点
    }
    if (p != -1) {
        if (pre == -1) {
            L->head = L->nodes[p].next; // 待删除节点是头节点
        } else {
            L->nodes[pre].next = L->nodes[p].next; // 调整前一个节点的next指针
        }
        L->length--; // 链表长度减1
    } else {
        printf("Element not found. Delete failed.\n");
    }
}

int main() {
    SLinkList L;
    InitSLinkList(&L);

    InsertElem(&L, 1);
    InsertElem(&L, 2);
    InsertElem(&L, 3);

    printf("Location of element 2: %d\n", LocateElem(L, 2)); // 查找元素2的位置

    DeleteElem(&L, 2); // 删除元素2
    printf("Location of element 2 after deletion: %d\n", LocateElem(L, 2)); // 再次查找元素2的位置

    return 0;
}