C语言线性表与链表操作实验：区间删除与倒数第m个元素

本实验通过C语言代码实现线性表元素的区间删除（顺序存储）和链表的倒数第m个元素查找（链式存储）。

1. 线性表的ADT表示

线性表的ADT表示可以使用结构体来定义，其中包括线性表的长度和存储元素的数组。

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 存储元素的数组
    int length;  // 线性表的长度
} SeqList;

2. 数据类型定义和核心算法和程序

2.1 线性表元素的区间删除 (顺序存储）

核心算法：

遍历线性表，找到区间的起始位置和结束位置。
将区间内的元素删除，将后面的元素依次前移。
更新线性表的长度。

void deleteRange(SeqList *list, int start, int end) {
    if (start < 1 || end > list->length || start > end) {
        printf('Invalid range.
');
        return;
    }
    
    int i, j;
    for (i = start - 1, j = end; j < list->length; i++, j++) {
        list->data[i] = list->data[j];
    }
    
    list->length -= (end - start + 1);
}

2.2 求链表的倒数第m个元素(链式存储)

核心算法：

使用两个指针p和q，初始时都指向链表的头节点。
先将指针q向后移动m-1个位置。
然后同时将指针p和q向后移动，直到指针q指向链表的尾节点。
此时指针p指向的节点就是倒数第m个节点。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* findLastM(Node *head, int m) {
    if (head == NULL || m <= 0) {
        return NULL;
    }
    
    Node *p = head;
    Node *q = head;
    
    int i;
    for (i = 0; i < m - 1; i++) {
        if (q->next != NULL) {
            q = q->next;
        } else {
            return NULL;
        }
    }
    
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
    }
    
    return p;
}

3. 实验过程中出现的问题和解决的方法

问题1: 如何删除线性表中的元素？ **解决方法: ** 可以使用遍历和移动元素的方法来删除线性表中的元素。

问题2: 如何找到链表的倒数第m个元素？ **解决方法: ** 可以使用两个指针来遍历链表，一个指针先移动m-1个位置，然后两个指针同时移动，直到第一个指针指向链表的尾节点。

4. 完整的程序代码

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];  // 存储元素的数组
    int length;  // 线性表的长度
} SeqList;

void deleteRange(SeqList *list, int start, int end) {
    if (start < 1 || end > list->length || start > end) {
        printf('Invalid range.
');
        return;
    }
    
    int i, j;
    for (i = start - 1, j = end; j < list->length; i++, j++) {
        list->data[i] = list->data[j];
    }
    
    list->length -= (end - start + 1);
}

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* findLastM(Node *head, int m) {
    if (head == NULL || m <= 0) {
        return NULL;
    }
    
    Node *p = head;
    Node *q = head;
    
    int i;
    for (i = 0; i < m - 1; i++) {
        if (q->next != NULL) {
            q = q->next;
        } else {
            return NULL;
        }
    }
    
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
    }
    
    return p;
}

int main() {
    // 线性表元素的区间删除 (顺序存储）
    SeqList list = {{1, 2, 3, 4, 5, 6}, 6};
    deleteRange(&list, 2, 4);
    for (int i = 0; i < list.length; i++) {
        printf('%d ', list.data[i]);
    }
    printf('
');
    
    // 求链表的倒数第m个元素(链式存储)
    Node n6 = {6, NULL};
    Node n5 = {5, &n6};
    Node n4 = {4, &n5};
    Node n3 = {3, &n4};
    Node n2 = {2, &n3};
    Node n1 = {1, &n2};
    Node *head = &n1;
    Node *lastM = findLastM(head, 3);
    if (lastM != NULL) {
        printf('The last mth element is: %d
', lastM->data);
    } else {
        printf('Invalid m.
');
    }
    
    return 0;
}