首页 > 其他分享 >2024/11/18日 日志 数据结构实验(1)---链表逆置、线性表A,B顺序存储合并、双向循环链表应用、修改数组(蓝桥杯)

2024/11/18日 日志 数据结构实验(1)---链表逆置、线性表A,B顺序存储合并、双向循环链表应用、修改数组(蓝桥杯)

时间:2024-11-19 20:18:17浏览次数:1  
标签:Node current head 线性表 int next 链表 节点 顺序存储

链表逆置
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/6?problemSetProblemId=1855808768018968576
解答:

点击查看代码
struct ListNode*reverse(struct ListNode*head){
    struct ListNode*prev = NULL;
    struct ListNode*current = head;
    struct ListNode*next = NULL;
    while(current!= NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
思路:通过三个新的节点指针 pre,cur, next 来完成,主要是通过pre来构建新的链表,核心代码为: next = current->next; current->next = pre; prev = current; current = next; 通过循环遍历链表 完成链表的逆转。 补充图示: ![](/i/l/?n=24&i=blog/3478956/202411/3478956-20241119202127879-898431177.jpg)

线性表A,B顺序存储合并
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968577
解答:

点击查看代码
#include <bits/stdc++.h>
#include<iostream>
using namespace std;

const int MAXSIZE = 20;
typedef int ElemType;

typedef struct arrList{
    ElemType *elem;
    int length;
}SqList;

void creatArrList(SqList*L){
    L->elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!L->elem){
    }
    L->length = 0;
}

void ListInsert(SqList * L ,int i,ElemType e){
    if(L->length == MAXSIZE){
    }
    if(i<1||i>L->length+1){
    }
    if(i<=L->length){
        for(int k = L->length;k>=i-1;k--){
            L->elem[k+1] = L->elem[k];
        }
    }
    L->elem[i-1]=e;
    L->length++;
}
void Output(SqList&L){
    for(int i = 0;i<L.length;i++){
      if(i!=L.length - 1){
          cout<<L.elem[i]<<",";
      }else{
          cout<<L.elem[i];
      }
    }
}
void mergeLists(SqList*La,SqList*Lb,ElemType*arr,int&totalLength){
    for(int i = 0;i<La->length;i++){
        arr[i]=La->elem[i];
    }
    for(int i = 0;i<Lb->length;i++){
        arr[La->length+i] = Lb->elem[i];
    }
    totalLength = La->length+Lb->length;
}
int main(){
    SqList La,Lb;
    creatArrList(&La);
    creatArrList(&Lb);
    while(true){
        int num;
        cin>>num;
        if(num== -1)break;
        ListInsert(&La,La.length+1,num);
    }
    int lena =La.length;
    while(true){
        int num;
        cin>>num;
        if(num==-1)break;
        ListInsert(&Lb,Lb.length+1,num);
    }
    int lenb = Lb.length;

    int arr[MAXSIZE*2]={0};
    int totalLength;
    mergeLists(&La,&Lb,arr,totalLength);
    sort(arr,arr+totalLength);
    bool allsame = true;
    for(int i = 1;i<totalLength;i++){
        if(arr[i]!=arr[0]){
            allsame = false;
            break;
        }
    }
    if(allsame){
        cout<<arr[0];
    }else{
    int temp = -1;
    for(int i = 0;i<totalLength;i++){
        if(temp!=arr[i]){
            cout<<arr[i];
            if(i<totalLength-1){
                cout<<",";
            }
            temp = arr[i];
        }
    }
    }
    free(La.elem);
    free(Lb.elem);
    
}
思路:先创建并输出表A表B再将表AB合并并分别填到结果数组中,再按非递减顺序将数组sort,最后按要求输出。 补充图示: ![](/i/l/?n=24&i=blog/3478956/202411/3478956-20241119202418445-1952327066.jpg)

双向循环链表应用
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968578
解答:

点击查看代码
#include <bits/stdc++.h>

using namespace std;

// 节点结构
struct Node {
    int data;
    Node* prior;
    Node* next;
    
    Node(int value) : data(value), prior(nullptr), next(nullptr) {}
};

// 创建双向链表
Node* createList(const vector<int>& elements) {
    if (elements.empty()) return nullptr;

    Node* head = new Node(elements[0]);
    Node* current = head;
    for (int i = 1; i < elements.size(); i++) {
        current->next = new Node(elements[i]);
        current->next->prior = current;
        current = current->next;
    }
    // 形成循环
    current->next = head;
    head->prior = current;
    return head;
}

// 打印
void printList(Node* head) {
    if (!head) return;
    Node* current = head;
    do {
        cout << current->data;
        current = current->next;
    } while (current != head);
    cout << endl;
}
// 交换p节点与其前驱节点
void swap(Node* p) {
    if (!p || !p->prior) return;
    Node* previous = p->prior;
    
    // 数据交换
    swap(p->data, previous->data);

    // // 连接交换
    // Node* pNext = p->next;
    // Node* prevNext = previous->next;

    // // 调整指针
    // if (prevNext != p) {
    //     previous->next = pNext;
    //     p->next = prevNext;

    //     if (pNext) pNext->prior = previous;
    //     if (prevNext) prevNext->prior = p;
    // }

    // // 调整前驱指针
    // previous->prior = p;
    // p->prior = previous->prior;
}

// 释放内存
void freeList(Node* head) {
    if (!head) return;
    Node* current = head;
    do {
        Node* toDelete = current;
        current = current->next;
        delete toDelete;
    } while (current != head);
}

int main() {
    int n;
    cin >> n;
    vector<int> elements(n);
    for (int& elem : elements) { 
        cin >> elem;
    }
    int num;
    cin >> num;

    Node* head = createList(elements);
    Node* current = head;
    bool found = false;

    // 遍历寻找目标
    do {
        if (current->data == num) {
            swap(current);
            found = true;
            break;
        }
        current = current->next; 
    } while (current != head);

    if (found) {
        printList(head);
    } else {
        cout << "未找到" << num << endl;
    }

    // 释放内存
    freeList(head);
    
    return 0;
}
思路:一种是“伪交换”,即我们只交换所要交换的节点和其前驱节点的数据即可。另一种是画图可视化断连和连接,更改两节的节点位置,更改两节点的prior和next指针以及p的前驱节点的前驱节点的next指针和p的后驱节点的prior指针。 补充图示: ![](/i/l/?n=24&i=blog/3478956/202411/3478956-20241119202631339-780271787.jpg)

修改数组(蓝桥杯)
题目:https://pintia.cn/problem-sets/1855808612225744896/exam/problems/type/7?problemSetProblemId=1855808768018968579
解答:

define _CRT_SECURE_NO_WARNINGS 1

include <bits/stdc++.h>

using namespace std;

const int MAX = 1000005;
int N;
int fat[MAX+1]; //并查集父节点
bool vis[MAX+1]; //判断每位数字是否出现过

//父节点查找
int find(int x) {
//在不断查找过程中压缩路径

if (fat[x] == x) return x;
else return fat[x] = find(fat[x]);

}

int main() {
//初始化
memset(vis, false, sizeof(vis));
for (int i = 1; i <= MAX; i++) {
fat[i] = i;
}

cin >> N;
int x;
for (int i = 1; i <= N; i++) {
    cin >> x;
    if(x > 10e6 || x < 1){
        cout<<"error"<<endl;
        return 0;
    }
    
    //如果数字出现过,则找到它的根节点 加 1
    if (vis[x]) x = find(x) + 1;
    //输出 标记
    cout << x << " ";
    vis[x] = true;
    //判断数字前后是否连续
    if (vis[x - 1] && x != 1) {
        fat[x - 1] = x;
    }
    if (vis[x + 1]) {
        fat[x] = x + 1;
    }
}

return 0;

}
思路:将出现过的连续数字都构造到一棵树里,然后将每一个数的父节点直接标记为与它连续的且前面出现过的最大数,那么在之后读入数据的时候如果这个数已经出现过,就可以直接找它的父节点,将这个数修改为父节点的数字加一输出。 如:输入数据为: 2 1 6 7 5 4 5 可以获得树 1-2 与 456 - 7 此时,再读入 5 时,便可以直接找到 5 的根节点 7,再 7 + 1 = 8 ;此时,我们有两个问题: 1. 树不是直接就构造成这样的,涉及到了并查集的路径压缩 2. 如果在上述例子中再读入一个 3 ,那么两棵树就会合并,合并成一个所有元素的父节点都是 8 的样子,所以在读入元素修改过后,还要判断修改数的前后数字是否出现过,也就是看树能不能合并。 所以我们共需要 fat 和vis 两个数组来分别储存每个数的父节点以及判断数字是否出现过,之后循环查找对应x便解决。
补充:https://blog.csdn.net/qq_59700927/article/details/123075547

标签:Node,current,head,线性表,int,next,链表,节点,顺序存储
From: https://www.cnblogs.com/MoonbeamsC/p/18555528

相关文章

  • 24. 两两交换链表中的节点
    https://leetcode.cn/problems/swap-nodes-in-pairs/?envType=study-plan-v2&envId=top-100-liked对于我们正常交换单向链表的两个节点我们需要知道三个节点的信息,1.对于a->b->c,我们要交换a、b就要知道a、b、c三个节点,因为我们需要将a的next指向c,将b的next指向a,由于b->c这条......
  • 常见链表类型
    单向链表双向链表循环链表双向循环链表1.单向链表单向链表的每个节点只包含数据和指向下一个节点的指针。它只能从头到尾单向遍历。[数据|下一节点指针]->[数据|下一节点指针]->NULL 示例#include<stdio.h>#include<stdlib.h>structNode{intdata;st......
  • LeetCode 1290[二进制链表转整数]
    题目链接LeetCode1290[二进制链表转整数]详情实例提示题解思路遍历链表,获取链表的值添加到容器内在容器内遍历值,由高位到地位遍历,为权重,然后算值代码/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*......
  • 力扣刷题--027.回文链表
    想放弃吗?,那当初为什么要开始?题目描述给定一个链表的头节点head,请判断其是否为回文链表。如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。示例1:输入:head=[1,2,3,3,2,1]输出:true示例2:输入:head=[1,2]输出:false思路分析如......
  • 代码随想录:移除链表元素
    代码随想录:移除链表元素简单的链表操作,注意C++中在访问一个实体结构体时,用.来进行元素访问ListNodehead;head.val=10;head.next=nullptr;在访问一个指针变量时,用→来进行元素访问,如在本题中,题目给的head是一个指针,所以所有的变量访问都用→/***Definitionforsing......
  • 代码随想录:设计链表
    代码随想录:设计链表这题遇到的问题是,在private中声明后,在构造函数中初始化的时候又声明了一次,大类的构造函数和结构体的构造函数弄晕掉了。另外虚头节点是真好用,以后记得用。一开始写成了这样:classMyLinkedList{public:structLinkNode{intvalue;......
  • 代码随想录算法训练营第四天|LC24.两两交换链表中的节点|LC19. 删除链表的倒数第 N 个
    24.两两交换链表中的节点-力扣(LeetCode)    1、需要一个虚拟节点进行帮助;    2、注意虚拟节点的连接以及变化(尝试有点困惑它的变化,后面有点理解);    3、注意后续第二组的交换时如何与第一组交换进行连接;fromtypingimportOptionalclassLis......
  • 《 C++ 修炼全景指南:二十 》不止是链表升级!跳表的核心原理与超强性能解析
    摘要这篇博客全面解析了跳表(SkipList)作为一种高效的链表数据结构的特性和应用。跳表以多层链表和随机化策略实现O(logn)的查找、插入和删除性能,简化了平衡树结构中常见的复杂旋转操作。通过剖析跳表的结构设计和核心操作,我们探讨了其在范围查询和动态更新中的优势,......
  • Leetcode141-环形链表
    思路链表判环方法:快慢指针法其实没那么高级,很简单的理解就是,采用两个指针,一个每次走两步,一个每次走一步,如果链表有环,那么每次走两步的指针,也就是走得快的指针一定会追上走得慢指针。代码第一种写法://写法1publicclassSolution{publicbooleanhasCycle(ListN......
  • 数据结构(单向链表)
    链式存储的优缺点:优点:1、动态分配内存:链式存储不需要在数据插入之前分配固定大小的数组或内存块,因此它更适合存储动态变化的数据2、高效的插入和删除操作:在链表中插入或删除元素只需要调整相邻节点的指针,不需要移动大量数据,因此时间复杂度通常为O(1)(在已知位置时)或O(n)(在......