Basic-Computer-Science：Lab 3 Array ( 计算机科学基础 )

Basic Computer Science – Learning Arrays and implement the required methods specified in the lab specification.

这是计算机科学基础课程中的第三个实验，主要是借助计算机语言来验证完成数组的相关操作。

本次实验主要考察数组的相关的概念，主要包含四个子任务

为了达到实验效果，在该实验中禁止使用STL容器。

Explain

前几次 Lab 由于程序不够通用，只能应对Lab给出的样例，所以并没有达到课程设计的要求，从 Lab3 开始将会尝试将程序写的更加“鲁棒”从而适应更多的情况。

Analysis

实验的前三个 Task 要求输入一个字符数组，最后一个输入一个整数数组，因此在输入上略有区别。

struct arrayElement

为方便存储元素，我们定义一个结构体 arrayElement ,这里给出的是一个较为全面的声明。

struct arrayElement{
    string s[N];
    int len;
    int f[N];
    int num[N];
    arrayElement()
    {
        memset(f,0,sizeof f);
    }
};

string s[] 为要存储的元素，这里直接使用字符串存储。
int len 为数组长度，通过调用len可以直到该数组有多少个元素。
int f[] 为标记数组，标记当前下标的元素是否在数组中重复出现。
int num[] 为数字数组，用于Task4的存储。
arrayElement() 为构造函数，对f数组进行初始化。

input

对于输入，我们的要求更加严格，要尽可能的满足更多的可能，这一函数在Task4中略有修改

void input(arrayElement &arr)
{
    string str;
    string empty="is an empty array";//判断空数组的标志语句
    getline(cin,str);//直接读入一行，可以识别带有空格的数组元素
    if(str==empty)//判断是否为空
    {
        arr.len=0;
        return ;
    }
    int len=str.size();
    int cnt=0;
    int head=0,tail=0;//我们使用头指针和尾指针标记一个数组元素的头和尾，便于赋值给arr.s[cnt];
    while(tail<=len)//判断结束条件，尾指针扫到行尾结束
    {
        if(str[tail]==','||str[tail]=='\0')//扫到分隔符或者行末开始复制操作
        {
            for(int i=head;i<tail;i++)
            {
                arr.s[cnt]+=str[i];//头指针前移，加给arr.s[cnt];
            }
            if(head!=tail)//判断是否有两个逗号相连或者行尾输入了逗号但是没有任何数据
            cnt++;
            head=tail+1;//头指针直接指向逗号的下一位，即下一个有效元素的首位
        }
        tail++;
    }
    arr.len=cnt;
}

首先选择了直接读入一整行，然后再对每个元素进行分隔的方式读入一个数组，这样可以保证纯数字、字符、字符串均可以被有效的存储。

在对元素进行划分的时候使用了双指针，如果考虑使用STL和库函数，那么可以尝试使用stringstream。

output

为了和输入格式统一，我们采用下列方式输出。

void output(arrayElement arr)
{
    for(int i=0;i<arr.len;i++)
    {
        if(!i) cout<<arr.s[i];
        else cout<<","<<arr.s[i];
    }
    if(!arr.len)
    {
        cout<<"is an empty array";
    }
}

Task1

Given two arrays (arr1 and arr2) of characters, write a method to check if all the elements in array1 are in array2. (need to consider the sequence of elements).

判断有序数组 arr1 中的元素是否全部在有序数组 arr2 中，并且元素出现的相关顺序相同。

根据题目意思可以分析，就是要证明 arr1 是 arr2 的子序列，可以通过动态规划求最长公共子序列的方式来证明这个问题。

int f[N][N]={0};

int check(arrayElement arr1,arrayElement arr2)
{
    for(int i=1;i<=arr1.len;i++)
	{
		for(int j=1;j<=arr2.len;j++)
		{
			if(arr1.s[i-1]==arr2.s[j-1])
			{
				f[i][j]=f[i-1][j-1]+1;
			}else f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(f[i][j]==arr1.len)//相较于完整的最长公共子序列，我们可以直接在符合条件时跳出
            {
                return 1;
            }
		}
	}
    if(f[arr1.len][arr2.len]==arr1.len)
    return 1;
    return 0;
}

Task2

Write a method which takes 2 arrays of characters as parameters and returns a new array containing the common elements without duplication(the comment elements need to maintain their relative positions of their first appearances in array 1).

输入两个有序数组 arr1 arr2，输出两个数组中的重复元素并且相同的元素只输出一次，顺序按照 arr1 排列。

根据题目，可以提前对单个数组中的重复元素进行处理，从而在寻找两个数组的重复元素时不出现重复输出的情况。

void remove(arrayElement &arr)
{
    for(int i=0;i<arr.len-1;i++)
    {
        if(arr.f[i]) continue;
        for(int j=i+1;j<arr.len;j++)
        {
            if(arr.f[j]) continue;
            if(arr.s[i]==arr.s[j])
            {
                arr.f[j]=1;
            }
        }
    }
}

去除重复元素之后可以通过 getCommon() 函数来寻找重复元素，并添加到新数组中。

arrayElement getCommon(arrayElement arr1,arrayElement arr2)
{
    arrayElement arr;
    int cnt=0;
    for(int i=0;i<arr1.len;i++)
    {
        if(arr1.f[i]) continue;
        for(int j=0;j<arr2.len;j++)
        {
            if(arr2.f[j]) continue;
            if(arr1.s[i]==arr2.s[j])
            {
                arr.s[cnt++]=arr1.s[i];
                arr2.f[j]=1;
                break;
            }
        }
    }
    arr.len=cnt;
    return arr;
}

Task3

Write a method which takes 2 arrays of characters as parameters and returns a new array that appends the second array to the end of the first array.

输入两个有序数组 arr1 arr2，连接 arr1 和 arr2 。

arrayElement merge(arrayElement arr1,arrayElement arr2)
{
    arrayElement arr;
    arr=arr1;
    for(int i=0;i<arr2.len;i++)
    {
        arr.s[arr1.len+i]=arr2.s[i];
    }
    arr.len=arr1.len+arr2.len;
    return arr;
}

Task4

Given a array of numbers, please write a method that can sort the numbers in the array from small to large.

输入一个数字数组，对其进行排序。

我们可以选择二叉平衡树对数据进行维护，然后通过一个中序遍历得到排序后的结果,具体实现原理及细节不在详述，AVL的实现可以参考二叉查找树和二叉平衡树(BST&AVL)，具体源代码可以参考下面的Example。

Example

Task1

Given two arrays (arr1 and arr2) of characters, write a method to check if all the elements in array1 are in array2. (need to consider the sequence of elements).

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;

struct arrayElement{
    string s[N];
    int len;
};

void input(arrayElement &arr)
{
    string str;
    string empty="is an empty array";
    getline(cin,str);
    if(str==empty)
    {
        arr.len=0;
        return ;
    }
    int len=str.size();
    int cnt=0;
    int head=0,tail=0;
    while(tail<=len)
    {
        if(str[tail]==','||str[tail]=='\0')
        {
            for(int i=head;i<tail;i++)
            {
                arr.s[cnt]+=str[i];
            }
            if(head!=tail)
            cnt++;
            head=tail+1;
        }
        tail++;
    }
    arr.len=cnt;
}

int f[N][N]={0};

int check(arrayElement arr1,arrayElement arr2)
{
    for(int i=1;i<=arr1.len;i++)
	{
		for(int j=1;j<=arr2.len;j++)
		{
			if(arr1.s[i-1]==arr2.s[j-1])
			{
				f[i][j]=f[i-1][j-1]+1;
			}else f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(f[i][j]==arr1.len)
            {
                return 1;
            }
		}
	}
    if(f[arr1.len][arr2.len]==arr1.len)
    return 1;
    return 0;
}

int main()
{
    arrayElement arr1,arr2;
    input(arr1);
    input(arr2);
    if(check(arr1,arr2))
    {
        cout<<"Yes";
    }else cout<<"No";
    return 0;
}

Task2

Write a method which takes 2 arrays of characters as parameters and returns a new array containing the common elements without duplication(the comment elements need to maintain their relative positions of their first appearances in array 1).

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;

struct arrayElement{
    string s[N];
    int len;
    bool f[N];
    arrayElement()
    {
        memset(f,0,sizeof f);
    }
};

void input(arrayElement &arr)
{
    string str;
    string empty="is an empty array";
    getline(cin,str);
    if(str==empty)
    {
        arr.len=0;
        return ;
    }
    int len=str.size();
    int cnt=0;
    int head=0,tail=0;
    while(tail<=len)
    {
        if(str[tail]==','||str[tail]=='\0')
        {
            for(int i=head;i<tail;i++)
            {
                arr.s[cnt]+=str[i];
            }
            if(head!=tail)
            cnt++;
            head=tail+1;
        }
        tail++;
    }
    arr.len=cnt;
}

arrayElement getCommon(arrayElement arr1,arrayElement arr2)
{
    arrayElement arr;
    int cnt=0;
    for(int i=0;i<arr1.len;i++)
    {
        if(arr1.f[i]) continue;
        for(int j=0;j<arr2.len;j++)
        {
            if(arr2.f[j]) continue;
            if(arr1.s[i]==arr2.s[j])
            {
                arr.s[cnt++]=arr1.s[i];
                arr2.f[j]=1;
                break;
            }
        }
    }
    arr.len=cnt;
    return arr;
}

void output(arrayElement arr)
{
    for(int i=0;i<arr.len;i++)
    {
        if(!i) cout<<arr.s[i];
        else cout<<","<<arr.s[i];
    }
    if(!arr.len)
    {
        cout<<"is an empty array";
    }
}

void remove(arrayElement &arr)
{
    for(int i=0;i<arr.len-1;i++)
    {
        if(arr.f[i]) continue;
        for(int j=i+1;j<arr.len;j++)
        {
            if(arr.f[j]) continue;
            if(arr.s[i]==arr.s[j])
            {
                arr.f[j]=1;
            }
        }
    }
}

int main()
{
    arrayElement arr1,arr2,arr3;
    input(arr1);
    input(arr2);
    remove(arr1);
    remove(arr2);
    arr3=getCommon(arr1,arr2);
    output(arr3);
    cout<<endl;
    return 0;
}

Task3

Write a method which takes 2 arrays of characters as parameters and returns a new array that appends the second array to the end of the first array.

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;

struct arrayElement{
    string s[N];
    int len;
};

void input(arrayElement &arr)
{
    string str;
    string empty="is an empty array";
    getline(cin,str);
    if(str==empty)
    {
        arr.len=0;
        return ;
    }
    int len=str.size();
    int cnt=0;
    int head=0,tail=0;
    while(tail<=len)
    {
        if(str[tail]==','||str[tail]=='\0')
        {
            for(int i=head;i<tail;i++)
            {
                arr.s[cnt]+=str[i];
            }
            if(head!=tail)
            cnt++;
            head=tail+1;
        }
        tail++;
    }
    arr.len=cnt;
}

arrayElement merge(arrayElement arr1,arrayElement arr2)
{
    arrayElement arr;
    arr=arr1;
    for(int i=0;i<arr2.len;i++)
    {
        arr.s[arr1.len+i]=arr2.s[i];
    }
    arr.len=arr1.len+arr2.len;
    return arr;
}

void output(arrayElement arr)
{
    for(int i=0;i<arr.len;i++)
    {
        if(!i) cout<<arr.s[i];
        else cout<<","<<arr.s[i];
    }
    if(!arr.len)
    {
        cout<<"is an empty array";
    }
}

int main()
{
    arrayElement arr1,arr2,arr3;
    input(arr1);
    input(arr2);
    arr3=merge(arr1,arr2);
    output(arr3);
    return 0;
}

Task4

Given a array of numbers, please write a method that can sort the numbers in the array from small to large.
Code:

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+10;

struct arrayElement {
    int num[N];
    int len;
};
//树的结构体声明
struct node{
    int data;
    int h;
    int tot;//统计重复元素
    node *l,*r;
    node()
    {
    	tot=1;
        h=1;
        l=NULL;
        r=NULL;
    }
};
//数组输入
void input(arrayElement &arr)
{
    string str;
    string empty="is an empty array";
    getline(cin,str);
    if(str==empty)
    {
    	cout<<"Empty array cannot be sort.";
        return ;
    }
    int len=str.size();
    int cnt=0;
    int head=0,tail=0;
    while(tail<=len)
    {
        if(str[tail]==','||str[tail]=='\0')
        {
            int temp=0;
            for(int i=head;i<tail;i++)
            {
                temp*=10;
                temp+=str[i]-'0';
            }
            if(head!=tail)
            arr.num[cnt++]=temp;
            head=tail+1;
        }
        tail++;
    }
    arr.len=cnt;
}

// 以下是AVL部分
// 获取树的高度
int get_h(node *root)
{
    if(!root)
    return 0;
    return root->h;
}

int get_bal(node *root)//计算平衡因子
{
    return get_h(root->l)-get_h(root->r);
}

void updata_h(node *(&root))//更新高度
{
    root->h=max(get_h(root->l),get_h(root->r))+1;
}

node *turn_left(node *root)//左旋
{
    node *t=root->r;
    root->r=t->l;
    t->l=root;
    updata_h(root);
    updata_h(t);
    return t;
}

node *turn_right(node *root)//右旋
{
    node *t=root->l;
    root->l=t->r;
    t->r=root;
    updata_h(root);
    updata_h(t);
    return t;
}

node *insert(node *root,int data)//插入AVL
{
    if(!root)
    {
    	root=new node;
        root->data=data;
        return root;
    }
    if(data==root->data)//对重复元素进行处理
    {
		root->tot++;
	}else if(data<root->data)
    {
        root->l=insert(root->l,data);
        updata_h(root);
        if(get_bal(root)==2)
        {
            switch(get_bal(root->l))
            {
                case -1:root->l=turn_left(root->l);
                case 1:root=turn_right(root);
            }
        }
    }else{
        root->r=insert(root->r,data);
        updata_h(root);
        if(get_bal(root)==-2)
        {
            switch(get_bal(root->r))
            {
                case 1:root->r=turn_right(root->r);
                case -1:root=turn_left(root);
            }
        }
    }
    return root;
}

// 以上是AVL部分

int flag=1;
void midorder(node *root)//中序遍历排序
{
    if(root->l)
    {
        midorder(root->l);
    }
    if(flag)
    {
        flag=0;
        for(int i=0;i<root->tot;i++)
        {
        	if(!i)
			cout<<root->data;
			else cout<<","<<root->data;
		}
    }else{
    	for(int i=0;i<root->tot;i++)
        cout<<","<<root->data;
    }
    if(root->r)
    {
        midorder(root->r);
    }
}

void sortArray(arrayElement arr)
{
    node *root=NULL;
    for(int i=0;i<arr.len;i++)
    {
        root=insert(root,arr.num[i]);
    }
    midorder(root);
    cout<<endl;
    return ;
}

int main()
{
    arrayElement arr;
    input(arr);
    sortArray(arr);
    return 0;
}

一	二	三	四	五	六	日
				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

联系方式

Explain

Analysis

struct arrayElement

input

output

Task1

Task2

Task3

Task4

Example

Task1

Task2

Task3

Task4

发送评论编辑评论

Explain

Analysis

struct arrayElement

input

output

Task1

Task2

Task3

Task4

Example

Task1

Task2

Task3

Task4

发送评论 编辑评论

推荐文章

发送评论编辑评论