数据结构-实验二

实验二

#include <iostream>

using namespace std;

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

// 创建一个新节点
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// 插入节点到单链表尾部
void insertNodeAtEnd(Node*& head, int value) {
    Node* newNode = createNode(value);

    if (head == nullptr) {
        head = newNode;
    }
    else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 查找节点在单链表中的位置
int findNodePosition(Node* head, int value) {
    int position = 1;
    Node* current = head;
    while (current != nullptr) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }
    return -1;  // 未找到
}

// 删除节点在单链表中的位置
bool deleteNodeAtPosition(Node*& head, int position) {
    if (position < 1) {
        return false;  // 无效的位置
    }

    if (position == 1) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return true;
    }

    Node* current = head;
    int currentPosition = 1;
    while (currentPosition < position - 1 && current != nullptr) {
        current = current->next;
        currentPosition++;
    }

    if (current == nullptr || current->next == nullptr) {
        return false;  // 位置超出链表长度
    }

    Node* temp = current->next;
    current->next = current->next->next;
    delete temp;
    return true;
}

// 合并两个有序单链表
Node* mergeSortedLists(Node* list1, Node* list2) {
    Node* mergedList = nullptr;
    Node* current = mergedList;

    while (list1 != nullptr && list2 != nullptr) {
        if (list1->data < list2->data) {
            insertNodeAtEnd(current, list1->data);
            list1 = list1->next;
        }
        else {
            insertNodeAtEnd(current, list2->data);
            list2 = list2->next;
        }

        if (mergedList == nullptr) {
            mergedList = current;
        }
    }

    // 处理剩余的元素
    while (list1 != nullptr) {
        insertNodeAtEnd(current, list1->data);
        list1 = list1->next;
    }

    while (list2 != nullptr) {
        insertNodeAtEnd(current, list2->data);
        list2 = list2->next;
    }

    return mergedList;
}

// 打印单链表
void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    Node* list1 = nullptr;
    Node* list2 = nullptr;

    // 建立单链表
    for (int i = 1; i <= 5; i++) {
        insertNodeAtEnd(list1, i * 2);
        insertNodeAtEnd(list2, i * 2 - 1);
    }

    cout << "List 1: ";
    printList(list1);

    cout << "List 2: ";
    printList(list2);

    // 合并有序单链表
    Node* mergedList = mergeSortedLists(list1, list2);

    cout << "Merged List: ";
    printList(mergedList);

    // 查找节点位置
    int searchValue = 6;
    int position = findNodePosition(mergedList, searchValue);
    if (position != -1) {
        cout << "Found " << searchValue << " at position " << position << endl;
    }
    else {
        cout << searchValue << " not found in the merged list." << endl;
    }

    // 删除节点
    int deletePosition = 3;
    if (deleteNodeAtPosition(mergedList, deletePosition)) {
        cout << "Deleted node at position " << deletePosition << endl;
        cout << "Updated List: ";
        printList(mergedList);
    }
    else {
        cout << "Unable to delete node at position " << deletePosition << endl;
    }

    // 释放内存
    while (mergedList != nullptr) {
        Node* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}