】编写算法，在带头结点的单链表结构上实现线性表操作

Question

编写算法，在带头结点的单链表结构上实现线性表操作：InitList（），Length（L），Locate（L, x），Insert（L, i, x），Delete（L, i），PrintList（L）。

Answer 1

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

// 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} ListNode;

// 初始化链表
void InitList(ListNode** L) {
    *L = (ListNode*)malloc(sizeof(ListNode));
    (*L)->next = NULL;
}

// 获取链表长度
int Length(ListNode* L) {
    int len = 0;
    ListNode* p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

// 在链表中查找元素位置
int Locate(ListNode* L, int x) {
    int pos = 0;
    ListNode* p = L->next;
    while (p != NULL) {
        pos++;
        if (p->data == x) {
            return pos;
        }
        p = p->next;
    }
    return -1; 
}

// 在链表指定位置插入元素
void Insert(ListNode* L, int i, int x) {
    if (i < 1 || i > Length(L) + 1) {
        printf("插入位置非法\n");
        return;
    }
    ListNode* p = L;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = x;
    newNode->next = p->next;
    p->next = newNode;
}

// 在链表指定位置删除元素
void Delete(ListNode* L, int i) {
    if (i < 1 || i > Length(L)) {
        printf("删除位置非法\n");
        return;
    }
    ListNode* p = L;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    ListNode* q = p->next;
    p->next = q->next;
    free(q);
}

// 打印链表
void PrintList(ListNode* L) {
    ListNode* p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}