单链表adt模板简单应用算法设计：单链表中前 m 个元素和后 n 个元素的互换

算法设计：

1. 判断链表是否为空，若为空则直接返回。

2. 判断链表长度是否小于 m+n，若小于则直接返回。

3. 定义三个指针：p1、p2、p3，分别指向第 m-1 个元素、第 m 个元素、第 m+n 个元素的前一个元素。

4. 将 p2 指向的元素插入到 p3 指向的元素的后面。

5. 将 p1 指向的元素插入到 p2 指向的元素的后面。

6. 将 p3 指向的元素插入到 p1 指向的元素的后面。

7. 返回链表头节点。

代码实现：

def swap_m_n(head, m, n):
    if not head:
        return head
    length = 0
    p = head
    while p:
        length += 1
        p = p.next
    if length < m + n:
        return head
    p1 = head
    for i in range(m-2):
        p1 = p1.next
    p2 = p1.next
    p3 = p2
    for i in range(n):
        p3 = p3.next
    p1.next = p3
    p2.next = p3.next
    p3.next = p2
    return head

其中，head 为链表头节点，m 和 n 分别为前 m 个元素和后 n 个元素。

相关问题

顺序表adt模板设计及简单应用：将顺序表中前 m 个元素和后 n 个元素进行互换

顺序表ADT模板设计：

1. 定义顺序表结构体，包含元素数组和当前元素个数等信息。

2. 初始化顺序表，分配元素数组空间，将当前元素个数置为。

3. 插入元素，判断是否已满，若未满则在末尾插入元素并更新当前元素个数。

4. 删除元素，判断是否为空，若非空则删除指定位置的元素并更新当前元素个数。

5. 获取元素，判断是否越界，若未越界则返回指定位置的元素。

6. 修改元素，判断是否越界，若未越界则修改指定位置的元素。

7. 互换元素，将顺序表中前m个元素和后n个元素进行互换，需要先判断m和n是否合法，然后使用一个临时数组进行交换。

简单应用：

假设有一个顺序表L，其中有10个元素，需要将前3个元素和后4个元素进行互换，可以按照以下步骤实现：

1. 判断m和n是否合法，即m+n是否等于L中元素个数。

2. 创建一个临时数组temp，将前m个元素复制到temp中。

3. 将后n个元素依次移动到前m个元素的位置上。

4. 将temp中的元素依次移动到后n个元素的位置上。

5. 更新顺序表L的当前元素个数。

代码示例：

#define MAXSIZE 100 // 定义顺序表最大长度

typedef struct {
    int data[MAXSIZE]; // 元素数组
    int length; // 当前元素个数
} SqList;

// 初始化顺序表
void InitList(SqList *L) {
    L->length = ;
}

// 插入元素
void Insert(SqList *L, int pos, int x) {
    if (L->length == MAXSIZE) {
        printf("List is full.\n");
        return;
    }
    if (pos < 1 || pos > L->length + 1) {
        printf("Invalid position.\n");
        return;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = x;
    L->length++;
}

// 删除元素
void Delete(SqList *L, int pos) {
    if (L->length == ) {
        printf("List is empty.\n");
        return;
    }
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return;
    }
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
}

// 获取元素
int GetElem(SqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return -1;
    }
    return L->data[pos - 1];
}

// 修改元素
void SetElem(SqList *L, int pos, int x) {
    if (pos < 1 || pos > L->length) {
        printf("Invalid position.\n");
        return;
    }
    L->data[pos - 1] = x;
}

// 互换元素
void Swap(SqList *L, int m, int n) {
    if (m + n != L->length) {
        printf("Invalid parameters.\n");
        return;
    }
    int temp[m];
    for (int i = ; i < m; i++) {
        temp[i] = L->data[i];
    }
    for (int i = ; i < n; i++) {
        L->data[i] = L->data[m + i];
    }
    for (int i = ; i < m; i++) {
        L->data[n + i] = temp[i];
    }
    L->length = m + n;
}

顺序栈adt模板简单应用算法设计：奇怪的键盘

题目描述：

有一个奇怪的键盘，它只有两个按键：A和B。初始时，屏幕上没有任何字符。每次按下A键，会在屏幕上打印一个字符A；每次按下B键，会将屏幕上最后一个字符删除。现在给定一个字符串S，你需要按照其中的字符顺序，在屏幕上输出对应的字符串。

算法设计：

使用顺序栈ADT模板，将字符串S中的字符依次入栈。当遇到字符A时，将其入栈；当遇到字符B时，将栈顶元素出栈。最后，将栈中剩余的元素依次出栈，即可得到屏幕上的字符串。

代码实现：

#include <iostream>
#include <string>
#include "SeqStack.h" // 顺序栈ADT模板

using namespace std;

int main()
{
    SeqStack<char> s; // 定义一个字符类型的顺序栈
    string str;
    cin >> str; // 输入字符串
    for (int i = ; i < str.length(); i++)
    {
        if (str[i] == 'A')
        {
            s.Push(str[i]); // 将字符A入栈
        }
        else if (str[i] == 'B')
        {
            if (!s.IsEmpty())
            {
                s.Pop(); // 将栈顶元素出栈
            }
        }
    }
    while (!s.IsEmpty())
    {
        cout << s.GetTop(); // 输出栈中剩余的元素
        s.Pop();
    }
    return ;
}