松鼠小筑

学习笔记

发表于 更新于 分类于 Disqus： 本文字数： 1.2k 阅读时长 ≈ 2 分钟

三元组顺序表表示的稀疏矩阵转置Ⅱ。设a和b为三元组顺序表变量，分别表示矩阵M和T。要求按照a中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。

输入格式:

输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行，每行3个数，分别表示非零元素的行标、列标和值。

输出格式:

按置入b中的顺序输出置入的位置下标，转置后的三元组行标、列标和值，数据之间用空格分隔，共t行。

输入样例1:

1
2
3
4
3 4 3
0 1 -5
1 0 1
2 2 2

输出样例1:

1
2
3
1 1 0 -5
0 0 1 1
2 2 2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
typedef struct
{
    int x,y;
    int data;
}triple;

typedef struct
{
    triple data[1001];
    int mu,nu,tu;
}TSMatrix;

int main()
{
    TSMatrix m1,m2;
    int m,n,t;
    cin>>m>>n>>t;
    m1.mu=m;m1.nu=n;m1.tu=t;
    for (int i = 0; i < t; ++i) {
        cin>>m1.data[i].x>>m1.data[i].y>>m1.data[i].data;
    }
    m2.mu=m1.nu;m2.nu=m1.mu;m2.tu=m1.tu;
    if(m2.tu)
    {
        int q=0;
        for (int i = 0; i < m1.nu; ++i) {
            for (int j = 0; j < m1.tu; ++j) {
                if (m1.data[j].y==i)
                {
                    m2.data[q].x=m1.data[j].y;
                    m2.data[q].y=m1.data[j].x;
                    m2.data[q].data=m1.data[j].data;
                    q++;
                }
            }
        }
        for (int k = 0; k < m1.nu; ++k) {
            for (int i = 0; i < m1.tu; ++i) {
                if(m2.data[i].y==k)
                {
                    cout<<i<<" "<<m2.data[i].x<<" "<<m2.data[i].y<<" "<<m2.data[i].data<<endl;
                }
            }
        }
    }
}

发表于 更新于 分类于 Disqus： 本文字数： 450 阅读时长 ≈ 1 分钟

设有一个10对称矩阵A，采用压缩存储，a[0][0]地址为1000，每个元素占两个字节，则a[3][6]地址为多少？

对对称阵进行压缩存取是将对称元素只存一个，并将数据存储在一维数组中
首先来确定a[i][j]在b[k]中的i，j与k的关系
首先是判定i与j的关系， 如果是下三角存储，则分一下两种情况
1、如果i<j, 则交换i与j的值，将上copy三角的位置值变换到下三角位置
2、如果i>=j，则不用执行操作直接走下面的流程

此时，i表示行坐标，j表示了坐标i之前有i行，即有1+2+...+i = (i+1)*i/2，在i标识的第i+1行有j+1个元素，由此zd可以确定k的值为(i+1)*i/2+j+1 = k+1 由此可得k = (i+1)*i/2+j

由此可以的，a[3][6], i=3, j=6, 由于i<j, 交换得i=6， j=3
由此 k = (6+1)*6/2+3 = 24
又由于&b[0] = 1000 每个元素占两个字节, 则b[24] = 1000+2*24 = 1048
由此便得到a[3][6]的地址为1048

发表于 更新于 分类于 Disqus： 本文字数： 3.2k 阅读时长 ≈ 6 分钟

7-1 串的模式匹配 (30分)

给定一个主串S（长度<=106）和一个模式T（长度<=105），要求在主串S中找出与模式T相匹配的子串，返回相匹配的子串中的第一个字符在主串S中出现的位置。

输入格式:

输入有两行： 第一行是主串S； 第二行是模式T.

输出格式:

输出相匹配的子串中的第一个字符在主串S中出现的位置。若匹配失败，输出0.

输入样例:

在这里给出一组输入。例如：

1
2
aaaaaba
ba

输出样例:

在这里给出相应的输出。例如：

1
6

首先有kmp算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <string>
#include <cstring>

using namespace std;
typedef int Status;
typedef struct
{
    char *ch;
    int length;
}HString;

//把string类型变成char*类型
char* trans(string s)
{
    int size = s.length();
    char* s1=new char[size];
    strcpy(s1,s.c_str());
    return s1;
}
//生成串s1
Status Strassign(HString &s1,char *char1)
{
    int i;
    char *c;
    //if(s1.ch)free(s1.ch);
    //i为char1长度
    for (i = 0,c=char1; *c ; ++c,++i) ;
    //如果char1为空返回空指针
    if(!i){s1.ch=nullptr;return 0;}
    s1.ch=(char*)malloc(i* sizeof(char));
    for (int j = 0; j <i ; ++j) {
        s1.ch[j]=char1[j];
    }
    s1.length=i;
    return 0;
}

//把s2和s3链接到s1中
Status Concat(HString &s1,HString s2,HString s3)
{
    //if(s1.ch)free(s1.ch);
    if(s2.length+s3.length<=0){s1.ch= nullptr;return 0;}
    s1.ch=(char*)malloc((s2.length+s3.length)* sizeof(char));
    for (int i = 0; i < s2.length; ++i) {
        s1.ch[i]=s2.ch[i];
    }
    for (int j = 0; j < s3.length; ++j) {
        s1.ch[j+s2.length]=s3.ch[j];
    }
    s1.length=s2.length+s3.length;
    return 1;
}

//输出串
Status Printstr(HString &s1)
{
    if(!s1.ch){ return 0;}
    for (int i = 0; i < s1.length; ++i) {
        cout<<s1.ch[i];
    }
    cout<<endl;
    return 1;
}

//模式匹配
int Index(string S,string T,int pos)
{
    int i=pos,j=0;
    while (i<S.length()&&j<=T.length())
    {
        if(S[i]==T[j]){++i;++j;}
        else{i=i-j+1;j=0;}
    }
    if(j>=T.length())return i-j+1;
    else return 0;
}

int main()
{
    string s1,s2;
    HString S1,S2,S3;
    cin>>s1;
    cin>>s2;
    char*s=trans(s1);
    char*m=trans(s2);
    Strassign(S1,s);
    Strassign(S2,m);
    int i=Index(s1,s2,0);
    cout<<i;
}

还有一种bf算法

1
2
3
4
5
6
7
8
9
10
11
12
13

//BF算法模式匹配
int Index(string S,string T,int pos)
{
    int i=pos,j=0;
    while (i<S.length()&&j<=T.length())
    {
        if(S[i]==T[j]){++i;++j;}
        else{i=i-j+1;j=0;}
    }
    if(j>=T.length())return i-j+1;
    else return 0;
}

剩余时间:4天返回7-2 jmu-ds-栈与队列-stack、queue与string小综合 (5分)

使用栈与队列逐个处理字符串中的每个字符

将line中的字符依次入栈，然后输出栈中元素个数与栈顶元素。
然后将栈中元素依次出栈并输出，出栈时将不等于x的字符依次入队列，以空格分隔。
输出队列元素个数，队头与队尾，以空格分隔。
最后输出队列中所有元素。

输入格式:

输入一个个字符串 输入一个字符

输出格式:

栈中元素个数 栈顶元素 栈中符合条件的元素(以空格分隔) 队列中元素个数 队头元素 队尾元素 队列中所有元素(以空格分隔)

输入样例:

1
ThisIsATest s

输出样例:

1
2
3
4
11 t
tseTAsIsihT
8 t T
teTAIihT

可以用c++自带的stack和queue库来实现，省去自己写的麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include <stack>
#include <string>
#include <queue>
using namespace std;
int main()
{
    stack<char>s;
    string str;
    queue<char>Q;
    char x;
    cin>>str;
    for (int i = 0; str[i]!='\0'; ++i) {
        s.push(str[i]);
    }
    cin>>x;
    cout<<s.size()<<" "<<s.top()<<endl;
    while(!s.empty()) {
        cout<<s.top();
        if(s.top()!=x)
        {
            Q.push(s.top());
        }
        s.pop();
    }
    cout<<endl;
    cout<<Q.size()<<" "<<Q.front()<<" "<<Q.back()<<endl;
    while (!Q.empty())
    {
        cout<<Q.front();
        Q.pop();
    }
}

发表于 更新于 分类于 Disqus： 本文字数： 1.6k 阅读时长 ≈ 3 分钟

请实现一个MyQueue类，实现出队，入队，求队列长度.

实现入队函数 void push(int x); 实现出队函数 int pop(); 实现求队列长度函数 int size();

输入格式:

每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ，接下去n行每行一个数字，表示一种操作： 1 x ： 表示从队尾插入x，0<=x<=2^31-1。 2 ： 表示队首元素出队。 3 ： 表示求队列长度。

输出格式:

对于操作2,若队列为空，则输出 “Invalid”,否则请输出队首元素。 对于操作3，请输出队列长度。 每个输出项最后换行。

输入样例:

1
2
3
4
5
6
5
3
2
1 100
3
2

输出样例:

1
2
3
4
0
Invalid
1
100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
using namespace std;

#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef char SElemType;
typedef int Status;

    typedef struct {
        QElemType *base;
        int front;
        int rear;
    } SqQueue;

class MyQueue {

public:
    Status EnQueue(SqQueue &Q, QElemType e) {
        if (
                Q.front == (Q.rear + 1) % MAXQSIZE
                )
            return ERROR;
        Q.base[Q.rear] = e;

        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }


    Status DeQueue(SqQueue &Q) {
        if (
                Q.front == Q.rear
                ) {
            cout << "Invalid" << endl;
            return 0;
        }
        int e = Q.base[Q.front];

        Q.front = (Q.front + 1) % MAXQSIZE;
        cout<<e<<endl;
    }
    Status size(SqQueue &Q)
    {
        return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
    }


    Status InitQueue(SqQueue &Q) {

        Q.base = new QElemType[MAXQSIZE];
        if (!Q.base)
            exit(OVERFLOW);

        Q.rear = Q.front = 0;
        return OK;
    }
};

int main() {
    SqQueue q;
    MyQueue q1;
    q1.InitQueue(q);
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        int t;
        cin>>t;
        switch(t) {
            case 1:
                int temp;
                cin>>temp;
                q1.EnQueue(q,temp);
                continue;
            case 2:
                q1.DeQueue(q);
                continue;
            case 3:
                cout<<q1.size(q)<<endl;
                continue;
        }
    }
    return 0;
}

注意switch语句需要有continue

发表于 更新于 分类于 Disqus： 本文字数： 1.7k 阅读时长 ≈ 3 分钟

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

输入格式:

输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:

1
8 2 1 3 9 4 11 13 15

输出样例:

1
1 3 2 9 11 4 13 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<stdio.h>
#define MAXSIZE 1000
#define OVERFLOW -2
#define OK 1
#define ERROR -1
using namespace std;
typedef struct
{
    int *base;
    int front;
    int rear;
} SqQueue;
int InitQueue(SqQueue &Q)
{
    Q.base=new int[MAXSIZE];
    if(!Q.base)
        return OVERFLOW;
    Q.front=Q.rear=0;
    return OK;
}
int DeQueue(SqQueue &Q,int &e)
{
    if(Q.front==Q.rear)
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;
    return OK;
}
void Print(int *arr,int n)
{
    cout<<arr[0];
    for(int i=1;i<n;i++)
        cout<<" "<<arr[i];
}
int main()
{
    SqQueue A,B;
    InitQueue(A);
    InitQueue(B);
    int N,data,tmp,i=0;
    cin>>N;
    int result[N];
    for(int i=0; i<N; i++)
    {
        cin>>data;
        if(data%2!=0)
        {
            if((A.rear+1)%MAXSIZE==A.front)
                return ERROR;
            A.base[A.rear]=data;
            A.rear=(A.rear+1)%MAXSIZE;
        }
        else
        {
            if((B.rear+1)%MAXSIZE==B.front)
                return ERROR;
            B.base[B.rear]=data;
            B.rear=(B.rear+1)%MAXSIZE;
        }
    }
    while((A.front!=A.rear)&&(B.front!=B.rear))
    {
        DeQueue(A,tmp);
        result[i++]=tmp;
        DeQueue(A,tmp);
        result[i++]=tmp;
        DeQueue(B,tmp);
        result[i++]=tmp;
    }
    while(A.front!=A.rear)
    {
        DeQueue(A,tmp);
        result[i++]=tmp;
    }
    while(B.front!=B.rear)
    {
        DeQueue(B,tmp);
        result[i++]=tmp;
    }
    Print(result,N);
}