sdut-数据结构与算法pta-顺序表

故事和你91

620人浏览 · 2026-01-30 23:11:28

故事和你91 · 2026-01-30 23:11:28 发布

7-1 顺序表的建立及遍历

读入n值及n个整数，建立顺序表并遍历输出。

输入格式:

读入n及n个整数

输出格式:

输出n个整数，以空格分隔（最后一个数的后面没有空格）。

输入样例:

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

4
-3 10 20 78

输出样例:

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

-3 10 20 78

实现代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n<=0) return 0;
    int a[n];
    for(int i=0;i<n;i++)
    {
    scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
       cout<<a[i];
        if (i<n-1)
            cout<<" ";
    }
    return 0;
}

7-2 递增有序顺序表的插入

实验目的：1、掌握线性表的基本知识 2、深入理解、掌握并灵活运用线性表。3、熟练掌握线性表的存储结构及主要运算的实现
已知顺序表L递增有序，将X插入到线性表的适当位置上，保证线性表有序。。

输入格式:

第1行输入顺序表长度，第2行输入递增有序的顺序表，第3行输入要插入的数据元素X。

输出格式:

对每一组输入，在一行中输出插入X后的递增的顺序表。

输入样例:

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

5
1 3 5 7 9
6

输出样例:

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

1,3,5,6,7,9,

实现代码：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
	int n;
	cin>>n;
	while(n--){
		int a;
		cin>>a;
		q.push(a);
	}
	int m;
	cin>>m;
	q.push(m);
	while(q.size()){
		int t=q.top();
		q.pop();
		cout<<t<<",";
	}
	return 0;
}

7-3 顺序表（删除）

已知一组数据，采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素

输入格式:

输入包含三行数据，第一行是表中元素个数，第二行是顺序表的各个元素，第三行是区间x和y。

输出格式:

删除元素值在[x,y]之间的所有元素后，输出新的顺序表。(最后无空格)

输入样例:

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

10
55 11 9 15 67 12 18 33 6 22
10 20

输出样例:

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

55 9 67 33 6 22

实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){
	int n;
	cin>>n;
    int flase=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x,y;
	cin>>x>>y;
	for(int i=1;i<=n;i++){
		if(a[i]>=x&&a[i]<=y){
			a[i]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=-1){
         if(flase==0){
             cout<<a[i];
         }
        else{
            cout<<" "<<a[i];
        }
        flase=flase+1;
	}
    }

	return 0;
}

7-4 最大子列和问题

给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；

输入格式:

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

实现代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[100100];
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++){
		if(a[i]>0) a[i+1]=a[i]+a[i+1];
	}
	int maxn=0;
	for(int i=0;i<n;i++){
		maxn=max(maxn,a[i]);
	}
	cout<<maxn;
	return 0;
}

7-5 数组元素循环右移n位

从键盘接收两个整数m和n，分别表示一维整型数组的元素个数，和要向移动的位数。已知0<m<=100，以及n>0。

在用户输入m和n后，第二行输入相应个数的数组元素。

程序要实现的功能是，让数组元素往右移动n位。

例如，数组的5个元素是：1,2,3,4,5。

往右移动1位后：5,1,2,3,4

往右移动2位后：4,5,1,2,3

输入格式:

第一行输入两个整数，第二行输入数组元素。

输出格式:

移动后，数组的每一个元素，注意每个数组元素后有且仅有一个空格。

输入样例:

第一行的数据5和2，表示数组容量为5，让数组元素往右移动2个位置。

第二行是数组的每一个元素的值。

5 2
1 2 3 4 5

输出样例:

输出移动后的数组元素值，注意每个元素后有且仅有一个空格。

4 5 1 2 3

实现代码：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[111];

int main(){
	cin>>m>>n;
	n=n%m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=m-n+1;i<=m;i++){
		cout<<a[i]<<" ";
	}
	for(int i=1;i<=m-n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

7-6 单词逆置

输入一个可能包含若干（至少1个）单词的句子（可以假设每个单词之间有且仅有一个空格，标点符号视为单词的组成部分），输出每个单词逆置后的英文句子（参看样例输出）。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入一个字符串（长度不超过80），表示英文句子。

输出格式:

对于每组测试，输出每个单词逆置后的英文句子。

输入样例:

1
emoclew era uoY

输出样例:

welcome are You

实现代码：

#include<bits/stdc++.h>
using namespace std;
char ch[88];
int main(){
	int n;
	cin>>n;
	getchar();
	while(n--){
		cin.getline(ch,88);
		stack<char> st;
		int len=strlen(ch);
		for(int i=0;i<len;i++){
		if(ch[i]==' '){
			while(st.size()){
				char b=st.top();
				st.pop();
				cout<<b;
			}
			cout<<" ";
		}
		else{
			st.push(ch[i]);
		}
		}
        while(st.size()){
				char b=st.top();
				st.pop();
				cout<<b;
			}
        cout<<endl;
	}
	return 0;
}

7-7 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

实现代码：


#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int coefficient; 
    int exponent;    
    struct Node *next;
} Node, *LinkList;

void initList(LinkList *head)
{
    if ((*head = (LinkList)malloc(sizeof(Node))) == NULL)
        exit(-1);
    (*head)->next = NULL;
}
void creatList(LinkList head)
{
    LinkList p, tail = head;
    int count;
    scanf("%d", &count);
    while (count-- > 0)
    {
        p = (LinkList)malloc(sizeof(Node));
        scanf("%d%d", &p->coefficient, &p->exponent);
        tail->next = p;
        tail = p;
    }
    tail->next = NULL;
}
void printList(LinkList head)
{
    LinkList p = head->next;
    while (p)
    {
        if (p == head->next)
            printf("%d %d", p->coefficient, p->exponent);
        else
            printf(" %d %d", p->coefficient, p->exponent);
        p = p->next;
    }
}

void addition(LinkList list1, LinkList list2)
{
    LinkList result, p = list1->next, q = list2->next, tail, newNode;
    initList(&result);
    tail = result;
    while (p && q)
    {
        int coefficient1, coefficient2, exponent1, exponent2;
        newNode = (LinkList)malloc(sizeof(Node));
        if (p->exponent > q->exponent)
        {
            newNode->coefficient = p->coefficient;
            newNode->exponent = p->exponent;
            newNode->next = NULL;
            tail->next = newNode;
            tail = newNode;
            p = p->next;
        }
        else if (p->exponent < q->exponent)
        {
        
            newNode->coefficient = q->coefficient;
            newNode->exponent = q->exponent;
            newNode->next = NULL;
            tail->next = newNode;
            tail = newNode;
            q = q->next;
        }
        else
        {
            if (p->coefficient + q->coefficient == 0)
            {
                p = p->next;
                q = q->next;
                free(newNode);
            }
            else
            {
                newNode->coefficient = p->coefficient + q->coefficient;
                newNode->exponent = p->exponent;
                newNode->next = NULL;
                tail->next = newNode;
                tail = newNode;
                p = p->next;
                q = q->next;
            }
        }
    }
    if (!p)
    {
        tail->next = q;
    }
    if (!q)
    {
        tail->next = p;
    }

    if (!result->next)
    {
        free(result);
        printf("0 0");
    }
    else
    {
        printList(result);
    }
}

void multiplication(LinkList list1, LinkList list2)
{
    LinkList result, p = list1->next, q , tail, newNode;
    initList(&result);
    tail = result;
    while (p)
    {
        q = list2->next;
        while (q)
        {
            newNode = (LinkList)malloc(sizeof(Node));
            newNode->coefficient = p->coefficient * q->coefficient;
            newNode->exponent = p->exponent + q->exponent;
            newNode->next = NULL;

            LinkList temp = result;
            while (temp->next && newNode->exponent < temp->next->exponent)
            {
                temp = temp->next;
            }
            if (temp->next == NULL || newNode->exponent > temp->next->exponent)
            {
                newNode->next = temp->next;
                temp->next = newNode;
            }
            else if (newNode->exponent == temp->next->exponent)
            {
                temp->next->coefficient += newNode->coefficient;
                if(!temp->next->coefficient){
                    LinkList deleteNode=temp->next;
                    temp->next=deleteNode->next;
                    free(deleteNode);
                }
                free(newNode);
            }
            q = q->next;
        }
        p = p->next;
    }
    if (!result->next)
    {
        free(result);
        printf("0 0");
    }
    else
    {
        printList(result);
    }
}
int main()
{
    LinkList list1, list2;
    initList(&list1);
    initList(&list2);
    creatList(list1);
    creatList(list2);
    multiplication(list1, list2);
    printf("\n");  
    addition(list1, list2);
    return 0;
}

7-8 一元多项式的加法

设计程序求两个一元多项式的和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数。数字间以空格分隔。

输出格式:

输出1行，以指数递降方式输出和多项式非零项的系数和指数（保证不超过整数的表示范围）。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

5 20 -4 4 -5 2 9 1 -2 0

实现代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m;
    int n;
    cin>>m;
    int a[2][m];
    for(int i=1;i<=m;i++){
        cin>>a[0][i]>>a[1][i];
    }
    cin>>n;
    int b[2][n];
    for(int i=1;i<=n;i++){
        cin>>b[0][i]>>b[1][i];
    }
    int sum[2][m+n];
    int x=1,y=1,s=0;
    while(x<=m&&y<=n){
        if(a[1][x]<b[1][y]){
            sum[0][s]=b[0][y];
            sum[1][s]=b[1][y];
            s++;
            y++;
        }
        else if(a[1][x]==b[1][y]){
            sum[0][s]=a[0][x]+b[0][y];
            sum[1][s]=a[1][x];
            if(sum[0][s]!=0){
                s++;
            }
            x++;
            y++;
        }
        else{
            sum[0][s]=a[0][x];
            sum[1][s]=a[1][x];
            s++;
            x++;
        }
    }
    if(x==m+1&&y<n+1){
        for(int i=y;i<=n;i++){
            sum[0][s]=b[0][i];
            sum[1][s]=b[1][i];
            s++;
        }
    }
    if(x<m+1&&y==n+1){
        for(int i=x;i<=m;i++){
            sum[0][s]=a[0][i];
            sum[1][s]=a[1][i];
            s++;
        }
    }
    for(int i=0;i<s;i++){
        if(i==0) cout<<sum[0][i]<<" "<<sum[1][i];
        else cout<<" "<<sum[0][i]<<" "<<sum[1][i];
    }
    if(s==0) cout<<"0 0";
    return 0;
}

7-9 合并有序数组

给定2个非降序序列，要求把他们合并成1个非降序序列。假设所有元素个数为N，要求算法的时间复杂度为O(N)。

输入格式:

输入有4行。
第1行是一个正整数m，表示第2行有m个整数，这些整数构成一个非降序序列，每个整数之间以空格隔开。第3行是一个正整数n，表示第4行有n个整数，这些整数也构成一个非降序序列，每个整数之间以空格隔开。

输出格式:

把第2行的m个整数和第4行的n个整数合并成一个非降序序列，输出这个整数序列。每个数之间隔1个空格。

输入样例:

6
1 3 6 6 8 9  
4
2 4 5 7

输出样例:

1 2 3 4 5 6 6 7 8 9

实现代码：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> st;

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		st.push(a);
	}
	int m;
	cin>>m;
	for(int i=1;i<=m;i++){
		int a;
		cin>>a;
		st.push(a);
	}
	while(st.size()){
		int t=st.top();
		st.pop();
		cout<<t<<" ";
	}
	return 0;
}

乐奇 Rokid 开放社区

更多推荐

用径向菜单完成 macOS 窗口管理的 Loop 上手指引

周三上午，你要同时摆好代码、终端、文档三个窗口。别急着来回拖拽，先按住触发键，把鼠标指向屏幕右侧，窗口就落进了右半屏。这就是 macOS 窗口管理工具 Loop，它用径向菜单和预览窗口，替掉了繁琐的拖边操作。## 🚀 5 步装好 Loop 并完成第一次窗口调整**第 1 步：安装**用 Homebrew 一行装好：```brew install loop```也可以克隆源

乐奇 Rokid 开放社区

Hydra 1.1 到 1.2 升级指南：@hydra.main() 与 hydra.initialize() 的 config_path 默认行为变更

Hydra 从 1.2 开始，当 `version_base >= "1.2"` 时，`@hydra.main()` 和 `hydra.initialize()` 的 `config_path` 参数默认值由"应用所在的目录"变更为 `None`，即不再向配置搜索路径（Config Search Path）中自动添加任何目录。这篇指南梳理 Hydra 1.0 → 1.1 → 1.2 三个阶段 `c