首页 > 其他分享 >数据结构-串、数组、广义表

数据结构-串、数组、广义表

时间：2022-10-16 15:24:38浏览次数：47  
标签：p2 Node p1 数组 int ++ include 广义 数据结构

@

目录
懒。

XDOJ0224 矩阵相乘

在这里插入图片描述

//xdoj0224.cpp
#include<cstdio>
using namespace std;
//A矩阵2行3列，B矩阵3行2列
int** MartixMultiply(int A[][3],int B[][2],int r,int c){
​
    int **C=new int*[r];
    for(int i=0;i<r;++i){
        C[i]=new int[c];
    }
​
    for(int i=0;i<r;++i){
        for(int j=0;j<c;++j){
            C[i][j]=0;
            for(int k=0;k<c;++k){
                C[i][j]+=A[i][k]*B[k][j];
            }
        }
    }
    return C;
}
int main(){
    int A[2][3];
    int B[3][2];
    for(int i=0;i<2;++i){
        for(int j=0;j<3;++j){
            scanf("%d",&A[i][j]);
        }
    }
    for(int i=0;i<3;++i){
        for(int j=0;j<2;++j){
            scanf("%d",&B[i][j]);
        }
    }
​
    int** C=MartixMultiply(A,B,2,3);
​
    for(int i=0;i<2;++i){
        for(int j=0;j<2;++j){
            printf("%d ",C[i][j]);
        }
        printf("\n");
    }
    return 0;
}

XDOJ0250 螺旋填数

在这里插入图片描述

//xdoj0250.cpp
//xdoj0250.c
#include<stdio.h>
int main(){
    int nums[100][100]={0},n,m,count=1,r=0,c=0;
    scanf("%d%d",&n,&m);
    int total=n*m;
    //四个边界 Right Left Up Down
    int Rlimit=m,Llimit=0,Ulimit=0,Dlimit=n;
​
    //理解为n次螺旋填数，每次填完，边界缩小
    while(count<=total){
        while(c<Rlimit){
            nums[r][c++]=count++;
        }c--;r++;
​
        while(r<Dlimit){
            nums[r++][c]=count++;
        }r--;c--;
​
        while(c>=Llimit){
            nums[r][c--]=count++;
        }c++;r--;
​
        while(r>Ulimit){
            nums[r--][c]=count++;
        }r++;c++;
​
        //每次螺旋之后，边界缩小
        Rlimit--;Llimit++;Ulimit++;Dlimit--;
    }
​
    //输出
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            printf("%d ",nums[i][j]);
        }
        printf("\n");
    }
​
    return 0;
}

XDOJ0257 公共子串

在这里插入图片描述

//xdoj0257.cpp
//最长公共子串，并计算相似度
/*  注意有空格输入，他妈的
    s h i t o
m   0 0 0 0 0
i   0 0 1 0 0
t   0 0 0 2 0
m   0 0 0 0 0
i   0 0 1 0 0
t   0 0 0 2 0
o   0 0 0 0 3
LCS等价于max，每次给矩阵赋值就刷新一下
*/
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int main(){
    int Martix[100][100];
    int LCS=0;
    string S1;
    string S2;
    getline(cin,S1);
    getline(cin,S2);
    int l1=S1.length();
    int l2=S2.length();
    for(int i=0;i<l1;++i){
        if(S1.at(i)>=65 && S1.at(i)<=90){
            S1.at(i)+=32;//是大写字母就改为小写
        }
    }
    for(int i=0;i<l2;++i){
        if(S2.at(i)>=65 && S2.at(i)<=90){
            S2.at(i)+=32;//是大写字母就改为小写
        }
    }
    for(int i=0;i<l2;++i){//i操作s2
        for(int j=0;j<l1;++j){//j操作s1
            if(S2.at(i)==S1.at(j)){
                //字符匹配上了
                if(i==0||j==0){
                    //如果是矩阵的边界，则直接赋值1
                    Martix[i][j]=1;
​
                    if(LCS<Martix[i][j]){
                        LCS=Martix[i][j];//刷新最大值
                    }
                }else{
                    //对角线加1
                    Martix[i][j]=Martix[i-1][j-1]+1;
​
                    if(LCS<Martix[i][j]){
                        LCS=Martix[i][j];//刷新最大值
                    }
                }
            }else{
                //不一样
                Martix[i][j]=0;
            }
        }
    }
    cout<<LCS<<endl;
    //记得三位小数
    printf("%.3lf",2*(double)LCS/(l1+l2));
​
    return 0;
}

XDOJ0287 求矩阵中的马鞍点

在这里插入图片描述

//xdoj0287.cpp
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
//min: 2 0 8 4
//max: 8 23 13 18
typedef struct Node{
    int i,j,value;
}Node;
int main(){
    int n,m,input[100][100],i=0,j=0,flag=0;//i,j操作，flag标记是否有马鞍点，默认没有
    vector<Node>min;
    vector<Node>max;
    Node* t=(Node*)malloc(sizeof(Node));//临时结点t，用于存贮三元组
    //输入部分 m是行，n是列，但是xdoj给的不清不楚，纯sb
    cin>>m>>n;
    for(i=0;i<m;++i){
        for(j=0;j<n;++j){
            cin>>input[i][j];
        }
    }
    //先按行查找每一行的最小值，把每一行的最小值入min
    for(i=0;i<m;++i){
        t->value=input[i][0];
        t->i=i+1;//在这里赋值，防止第一个就是最小值，导致ij未赋值
        for(j=1,t->j=j;j<n;++j){//t->j=j,不用加一，因为j赋值为1了
            if(t->value>input[i][j]){
                t->value=input[i][j];
                t->i=i+1;
                t->j=j+1;
            }
        }
        min.push_back(*t);
    }
    //再按列查找每一列的最大值，把每一列的最大值入max
    for(i=0;i<n;++i){
        t->value=input[0][i];
        t->j=i+1;//在这里赋值，防止第一个就是最大值，导致ij未赋值
        for(j=1,t->i=j;j<m;++j){
            if(t->value<input[j][i]){
                t->value=input[j][i];
                t->i=j+1;
                t->j=i+1;//注意这里反了一下
            }
        }
        max.push_back(*t);
    }
    //优先行来找马鞍点,也就是min先遍历,先遍历的在内层循环
    for(i=0;i<max.size();++i){//i操作max，j操作min
        for(j=0;j<min.size();++j){
            if(min.at(j).i==max.at(i).i && min.at(j).j==max.at(i).j && min.at(j).value==max.at(i).value){
                //结点相同，则符合马鞍点的定义
                cout<<min.at(j).i<<' '<<min.at(j).j<<' '<<min.at(j).value<<endl;
                flag=1;//输出过，说明有马鞍点
            }
        }
    }
    if(flag==0){
        cout<<"NO";
    }
    return 0;
}

XDOJ0288 求一个顺序串的next函数值

在这里插入图片描述

//xdoj0288.cpp
#include<iostream>
using namespace std;
//注意下面这个next函数是根据一般的情况来的，也就是从1数起，第一二个固定是0，1
//题目是从0数，第一二个固定是-1，0，只要最后输出减一就行了
void Next(char* T,int* next,int Tlength){
    next[1]=0;
    next[2]=1;
    int i=2;
    int j=1;
    while(i<Tlength){
        if(j==0||T[i-1]==T[j-1]){
            ++i;
            ++j;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
​
int main(){
    int n,next[100];
    char T[100];
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>T[i];
    }
    Next(T,next,n);
    for(int i=1;i<=n;++i){
        cout<<next[i]-1<<' ';
    }
    return 0;
}

XDOJ0296 中心对称的字符串

在这里插入图片描述

//xdoj0296.cpp
#include<iostream>
using namespace std;
int main(){
    int n;
    char str[100];
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>str[i];
    }
    int i=0,j=n-1;
    while(i<n/2){
        if(str[i++]!=str[j--]){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}

XDOJ0309 矩阵加法运算

在这里插入图片描述

//xdoj0309.cpp
#include<iostream>
#include<list>
#include<cstdlib>
using namespace std;
typedef struct Node{
    int x,y,v;
}Node;
list<Node>B1;
list<Node>B2;
list<Node>B;
​
void MartixAdd(){
    //B用于存储结果 按照行小的先压入， 总体分为行相等，行1大，行2大
    list<Node>::iterator p1=B1.begin();
    list<Node>::iterator p2=B2.begin();
​
    while(p1!=B1.end() && p2!=B2.end()){
        //遍历俩个链表
        if(p1->x==p2->x){
            if(p1->y == p2->y){
                //坐标相同，实行相加
                if(p1->v + p2->v == 0){
                    //坐标相同，但是和为0，故无视
                    ;
                }else{
                    //和不为0，压入B
                    Node* s=(Node*)malloc(sizeof(Node));
                    s->x=p1->x;
                    s->y=p1->y;
                    s->v=p1->v+p2->v;
                    B.push_back(*s);
                }
                //坐标一样，俩迭代器都后移
                ++p1;
                ++p2;
            }else if(p1->y > p2->y){
                //列小的压入
                B.push_back(*p2);
                ++p2;
            }else if(p1->y < p2->y){
                B.push_back(*p1);
                ++p1;
            }
        }else if(p1->x > p2->x){
            //B1结点行比B2当前结点行 大，先入B2的结点
            B.push_back(*p2);
            ++p2;
        }else if(p1->x < p2->x){
            //入p1结点
            B.push_back(*p1);
            ++p1;
        }
    }//while
    //没完，可能有一个没遍历完
    if(p1==B1.end() && p2==B2.end()){
        //都遍历完，则返回
        return;
    }else{
        if(p1==B1.end()){
            while(p2!=B2.end()){
                B.push_back(*p2);
                ++p2;
            }
        }else if(p2==B2.end()){
            while(p1!=B1.end()){
                B.push_back(*p1);
                ++p1;
            }
        }
        return;
    }
}
​
int main(){
    int n,m,t;
    
    list<Node>::iterator p1;//p1迭代器遍历B1
    list<Node>::iterator p2;
    list<Node>::iterator p3;
    cin>>n>>m;
​
    //输入部分
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>t;
            if(t==1){
                Node* s=(Node*)malloc(sizeof(Node));
                s->x=i;
                s->y=j;
​
                B1.push_back(*s);
            }
        }
    }
    for(p1=B1.begin();p1!=B1.end();p1++){
        cin>>t;
        (*p1).v=t;
    }
​
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>t;
            if(t==1){
                Node* s=(Node*)malloc(sizeof(Node));
                s->x=i;
                s->y=j;
​
                B2.push_back(*s);
            }
        }
    }
    for(p2=B2.begin();p2!=B2.end();p2++){
        cin>>t;
        (*p2).v=t;
    }
​
    //处理部分，相当于俩个链表x，y相同的运算，不同的合并，类似多项式加法
    MartixAdd();
​
    p3=B.begin();
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(p3==B.end()){
                cout<<"0 ";
                continue;
            }else{
                if(i==p3->x&&j==p3->y){
                    cout<<"1 ";
                    ++p3;
                }else{
                    cout<<"0 ";
                }
            }
        }
        cout<<endl;
    }
    p3=B.begin();
    while(p3!=B.end()){
        cout<<p3->v<<' ';
        ++p3;
    }
​
    return 0;
}

标签：p2,Node,p1,数组,int,++,include,广义,数据结构
From： https://www.cnblogs.com/iamnotphage/p/16796248.html

相关文章

  • 1441. 用栈操作构建数组
    本题非常简单，一个简单的模拟题解题思路：如果两个相邻数字相差不为1，那么对两个数字的差值减1进行“Push”和“Pop”如果两个相邻数字相差不1，那么直接“Push”即可......
  • 数组去重方法
    1. 使用es6set方法[...newSet(arr)]letarr=[1,2,3,4,3,2,3,4,6,7,6];letunique=(arr)=>[...newSet(arr)];unique(arr);//[1,2,3,4,6,7] 2.inde......
  • 【leetcode_C语言_数组_day2】977.有序数组的平方&&209.长度最小的子数组&&59. 螺旋矩
    977.有序数组的平方1.题目给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例1：输入：nums=[-4,-1,0,3,10]......
  • C语言之字符串与字符数组的区别
     1.字符串的定义：（1）单个字符：charch='i';//单个字符的定义（2）一维字符串数组：chararr[]="love";（这种方法定义的一维字符串数组必须赋值)chararr[4];（想内存申请创建可以......
  • 广义表转二叉树
    前序遍历和中序遍历&后序遍历和中序遍历可以还原出唯一的二叉树，而前序遍历和后序遍历不行（满二叉树时貌似可以，但只有一个根节点和一个子孩子时一定不行）//输入：A(B(,D),......
  • 748. 数组的右下半部分
    文章目录​​Question​​​​Ideas​​​​Code​​Question输入一个二维数组M[12][12]，根据输入的要求，求出二维数组的右下半部分元素的平均值或元素的和。右下半部分是指......
  • 747. 数组的左上半部分
    文章目录​​Question​​​​Ideas​​​​Code​​Question输入一个二维数组M[12][12]，根据输入的要求，求出二维数组的左上半部分元素的平均值或元素的和。左上半部分是指......
  • javascript 数组
    javascript数组文章目录​​javascript数组​​​​1.简介​​​​2.创建数组​​​​3.访问数组​​​​4.数组方法和属性​​​​5.创建新方法​​​​6.实例​​......
  • 1441. 用栈操作构建数组
    1441.用栈操作构建数组给你一个数组target和一个整数n。每次迭代，需要从 list={1,2,3...,n}中依次读取一个数字。请使用下述操作来构建目标数组targ......
  • redis bitmap数据结构之java对等操作
    在之前的文章中，我们有说过bitmap，bitmap在很多场景可以应用，比如黑白名单，快速判定，登录情况等等。总之，bitmap是以其高性能出名。其基本原理是一位存储一个标识，其他衍生知......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99