下面是用数组邻接表模拟的链表list

我们可以考虑，对于任意一个结点 u ，需要记录与其相邻的边的以下信息：

•   这条边所连接的终点（目标结点）。
•   这条边的权重。
•   链接到下一条相邻边的编号。

注意，这里并不需要记录邻边的起点，因为在使用这些信息时，起点是已知的。为了实现这些功能，我们可以定义一个struct来表示每一条邻边，或者直接编写代码实现这些功能。

int h[N];
Edge edges[M];
int e[idx];

由于每条边都记录了下一条边的编号，这样我们只要把每个结点的第一条邻边的编号记录在h数组，我们就可以遍历它的每一条邻边了。

如果我们把Edge里的信息分开存到不同数组里，那么我们可以得到平时我们看到的变量定义：

// 注意N和M的区别
int h[N];
int e[M], w[M], next[M];//注意，如果在cpp总next可能是关键字 
// 这三个数组等价于之前的Edge edges[M]，注意这些数组的下标表示邻边的编号
int e[idx];

在这里，每个数组的下标都有不同的含义：

• h 数组的下标表示结点的编号。
• e、w、next 数组的下标表示边的编号，其中 e[idx] 表示编号为 idx 的边所连接的终点。

理解了这些后，邻接表存储有向图的方式就容易理解了。

对于有向图中的每个结点 ( u )，h[u] 记录了与 ( u ) 相连的第一条边的编号。e、w、nxt 数组的编号与建图的顺序相关，对于某个结点 ( u )，它的所有邻边的编号不一定是连续的。

nxt[idx] = h[u]; h[u] = idx; 这个操作是将新建的边插入表头位置（首先把新建的边的 next 指向当前表头的 next，然后更新表头的 next）。

最后，通过 idx++，准备为下一次建边分配新的边编号。
最后是代码及注释

const int N = 1010, M = 1010;

int h[N], e[M], w[M], nxt[M], eidx;

void add(int u, int v, int weight)   // 添加有向边 u->v, 权重为weight
{
    e[eidx] = v;        // 记录边的终点
    w[eidx] = weight;   // 记录边的权重
    nxt[eidx] = h[u];   // 将下一条边指向结点u此时的第一条边
    h[u] = eidx;        // 将结点u的第一条边的编号改为此时的eidx
    eidx++;             // 递增边的编号edix, 为将来使用
}

void iterate(int u)   // 遍历结点u的所有邻边
{
    // 从u的第一条边开始遍历，直到eid==-1为止
    for(int eid = h[u]; eid != -1; eid = nxt[eid])
    {
        int v = e[eid];
        int weight = w[eid];
        cout << u << "->" << v << ", weight: " << weight << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);  // 初始化h数组为-1
    eidx = 0;                 // 初始化边的编号为0

    while(m--)
    {
        int u, v, weight;
        cin >> u >> v >> weight;
        add(u, v, weight);
    }

    for(int u = 1; u <= n; ++u)
        iterate(u);

    return 0;
}

下面是用动态链表写的链表

动态链表是一种常见的数据结构，链表中的元素（节点）是动态分配的，可以根据需要插入和删除节点，而不需要像数组那样预先分配固定大小的内存。

1. 结构体定义

struct Node 
{
    int v;
    struct Node *next;
};

Node 结构体定义了一个链表节点的结构。每个节点包含两个部分：
- v：用于存储节点的值（即数据）。
- next：指向下一个节点的指针。如果该节点是最后一个节点，则 next 指向 NULL。

2. 链表初始化

struct Node *st;

st 是指向链表头节点的指针。链表在初始化时，st 指向一个头节点，这个节点不存储实际数据，只是为了方便操作（通常称为哨兵节点）。

st = malloc(sizeof(struct Node));
st->next = NULL;

为链表头节点分配内存并将 next 指针初始化为 NULL，表示链表为空。

3. 添加元素到链表尾部

void add_to_back(int x) {
    struct Node *p = st;
    while(p->next != NULL) p = p->next;
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->v = x;
    new_node->next = NULL;
    p->next = new_node;
}

这个函数实现了在链表末尾添加新节点的功能：
- 首先，通过遍历链表找到最后一个节点（p->next == NULL）。
- 然后，为新节点分配内存，并将 v 赋值为 x，next 赋值为 NULL（表示新节点是最后一个节点）。
- 最后，将原本的最后一个节点的 next 指针指向这个新节点，从而将它链接到链表末尾。

4. 在特定节点后插入元素

void insert(int x, int y)
{
    struct Node *p=st;
    while(p->next !=NULL && p->v != x) p = p->next;
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->next = p->next;
    p->next = new_node;
    new_node->v = y;
}

这个函数实现了在链表中某个节点后插入新节点的功能：
- 通过遍历链表找到第一个值为 x 的节点 p。
- 为新节点分配内存，并将其 next 指针指向 p 的下一个节点。
- 修改 p 的 next 指针指向新节点，从而在 p 后面插入新节点。

5. 删除特定节点

void delete(int x)
{ 
    struct Node *p1 = st;
    struct Node *p2 = NULL;
    while(p1->next !=NULL && p1->v != x)
    {   
        p2 = p1;
        p1 = p1->next;
    }
    p2->next = p1->next;
    free(p1);
}

这个函数实现了删除链表中第一个值为 x 的节点的功能：
- 通过遍历链表，使用 p1 和 p2 两个指针分别指向当前节点和前一个节点。
- 当找到第一个值为 x 的节点 p1 时，将前一个节点 p2 的 next 指针指向 p1 的下一个节点，从而跳过 p1 节点。
- 最后，释放 p1 节点的内存。

总结

在这个实现中，链表中的每个节点都是动态分配的内存。当添加或删除节点时，链表会根据需要动态调整。这种实现非常灵活，适用于需要频繁插入和删除操作的场景。

下面是代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node 
{
    int v;
    struct Node *next;
};
struct Node *st;
void add_to_back(int x) {
    struct Node *p = st;
    while(p->next != NULL) p = p->next;
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->v = x;
    new_node->next = NULL;
    p->next = new_node;
}
void insert(int x,int y)
{
    struct Node *p=st;
    while(p->next !=NULL&&p->v!=x) p=p->next;
    struct Node *new_node=malloc(sizeof(struct Node));
    new_node->next=p->next;
    p->next=new_node;
    new_node->v=y;
}
void delete(int x)
{ 
    struct Node *p1=st;
    struct Node *p2=NULL;
    while(p1->next !=NULL&&p1->v!=x)
    {   
        p2=p1;
        p1=p1->next;
    }
    p2->next=p1->next;
    free(p1);
}
int main()
{
    st = malloc(sizeof(struct Node));
    st->next = NULL;
    for(int i = 0; i < 5; ++i)
    {
        int a;
        scanf("%d", &a);
        add_to_back(a);
    }
    int input;
    do
    {
        printf("输入0退出\n");
        printf("输入1，在输入x,y,代表在链表的x节点后面插入元素y\n");
        printf("输入2，再输入x，代表删除掉链表中第一个值为x的元素\n");
        scanf("%d",&input);
        if(input==0) break;
        else if(input==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            insert(x,y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            delete(x);
        }
    }while(input!=0);
    struct Node *p = st->next;
    while(p != NULL)
    {
        printf("%d ", p->v);
        p = p->next;
    }
    printf("\n");
    return 0;
}

• 部分内容由AI辅助写作