C语言实现顺序表与单链表

本文提供一个完整的C语言代码示例，用于演示如何实现顺序表和单链表。

顺序表

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

// 定义顺序表结构体
typedef struct {
    int *data;  // 数据指针
    int length; // 当前长度
    int maxSize; // 最大长度
} SeqList;

// 初始化顺序表
void init(SeqList *list, int maxSize) {
    list->data = (int *)malloc(maxSize * sizeof(int));
    list->length = 0;
    list->maxSize = maxSize;
}

// 插入元素
int insert(SeqList *list, int index, int element) {
    if (index < 0 || index > list->length) {
        printf('插入位置错误\n');
        return 0;
    }
    if (list->length >= list->maxSize) {
        printf('顺序表已满，无法插入\n');
        return 0;
    }
    for (int i = list->length; i > index; i--) {
        list->data[i] = list->data[i-1];
    }
    list->data[index] = element;
    list->length++;
    return 1;
}

// 删除元素
int removeElement(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        printf('删除位置错误\n');
        return 0;
    }
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i+1];
    }
    list->length--;
    return 1;
}

// 取元素
int getElement(SeqList *list, int index) {
    if (index < 0 || index >= list->length) {
        printf('取元素位置错误\n');
        return -1;
    }
    return list->data[index];
}

单链表

// 单链表结点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建单链表
Node* createLinkedList() {
    Node *head = NULL;
    int value;
    printf('请输入元素的值，以-1结束输入：\n');
    scanf('%d', &value);
    while (value != -1) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = value;
        newNode->next = head;
        head = newNode;
        scanf('%d', &value);
    }
    return head;
}

// 输出单链表
void printLinkedList(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf('%d ', p->data);
        p = p->next;
    }
    printf('\n');
}

// 在单链表的第index个位置插入元素
void insertLinkedList(Node *head, int index, int element) {
    Node *p = head;
    int count = 0;
    while (p != NULL && count < index - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL || count > index - 1) {
        printf('插入位置错误\n');
        return;
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = element;
    newNode->next = p->next;
    p->next = newNode;
    printf('插入成功\n');
}

// 删除单链表中的第index个元素
void removeLinkedList(Node *head, int index) {
    Node *p = head;
    int count = 0;
    while (p != NULL && count < index - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL || count > index - 1 || p->next == NULL) {
        printf('删除位置错误\n');
        return;
    }
    Node *temp = p->next;
    p->next = temp->next;
    free(temp);
    printf('删除成功\n');
}

// 取单链表中的第index个元素
int getLinkedListElement(Node *head, int index) {
    Node *p = head;
    int count = 0;
    while (p != NULL && count < index) {
        p = p->next;
        count++;
    }
    if (p == NULL || count > index) {
        printf('取元素位置错误\n');
        return -1;
    }
    return p->data;
}

测试代码

int main() {
    // 顺序表操作
    SeqList list;
    init(&list, 10);
    insert(&list, 0, 1);
    insert(&list, 1, 2);
    insert(&list, 2, 3);
    printf('顺序表中的元素：');
    for (int i = 0; i < list.length; i++) {
        printf('%d ', list.data[i]);
    }
    printf('\n');

    removeElement(&list, 1);
    printf('删除后顺序表中的元素：');
    for (int i = 0; i < list.length; i++) {
        printf('%d ', list.data[i]);
    }
    printf('\n');

    printf('顺序表中的第2个元素：%d\n', getElement(&list, 1));

    // 单链表操作
    Node *head = createLinkedList();
    printf('单链表中的元素：');
    printLinkedList(head);

    insertLinkedList(head, 3, 67);
    insertLinkedList(head, 9, 10); // 此处插入位置无效，将输出错误信息
    printf('插入后单链表中的元素：');
    printLinkedList(head);

    removeLinkedList(head, 6);
    removeLinkedList(head, 8); // 此处删除位置无效，将输出错误信息
    printf('删除后单链表中的元素：');
    printLinkedList(head);

    printf('单链表中的第5个元素：%d\n', getLinkedListElement(head, 4));
    printf('单链表中的第7个元素：%d\n', getLinkedListElement(head, 6));

    return 0;
}