1, Sequence table
1. Merging of two ordered linked list sequences
Two non descending linked list sequences S1 and S2 are known, and the function is designed to construct a new non descending linked list S3 after the combination of S1 and S2.
Input format:
The input is divided into two lines. Each line gives a non descending sequence composed of several positive integers, and − 1 is used to represent the end of the sequence (− 1 does not belong to this sequence). Numbers are separated by spaces.
Output format:
Output the combined new non descending linked list in one line, separate the numbers with spaces, and there shall be no redundant spaces at the end; If the new linked list is empty, NULL is output.
Example:
1 3 5 -1 2 4 6 8 10 -1 No blank lines at the end
1 2 3 4 5 6 8 10 No blank lines at the end
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int data;
struct list* next;
}list;
list* Initlist()//initialization
{
list* head = (list*)malloc(sizeof(list));
head->next = NULL;
return head;
}
void Createlist(list* List)//Construction sequence table
{
list* L = List;
list* p;
int num, flag = 1;
while (flag)
{
scanf("%d", &num);
if (num >= 0)//Judgment '- 1'
{
p = (list*)malloc(sizeof(list));
p->data = num;
L->next = p;
L = L->next;
}
else
{
flag = 0;
L->next = 0;
}
}
}
void Resolve(list* l1, list* l2, list* l3)//merge
{
list* s1 = l1->next;
list* s2 = l2->next;
list* s3 = l3;
while ((s1 != NULL) && (s2 != NULL))
{
if (s1->data < s2->data)
{
s3->next = s1;
s3 = s3->next;
s1 = s1->next;
}
else
{
s3->next = s2;
s3 = s3->next;
s2 = s2->next;
}
}
if (s1 != NULL)
{
s3->next = s1;
}
if (s2 != NULL)
{
s3->next = s2;
}
}
void Print(list* l)//output
{
list* p = l->next;
int flag = 1, num = 0;
while (p)
{
num++;
if (flag)
{
printf("%d", p->data);
flag = 0;
}
else
{
printf(" %d", p->data);
}
p = p->next;
}
if (num == 0)
{
printf("NULL");
}
}
int main()
{
list* l1, * l2, * l3;
l1 = Initlist();
l2 = Initlist();
l3 = Initlist();
Createlist(l1);
Createlist(l2);
Resolve(l1, l2, l3);
Print(l3);
return 0;
}
2. Establishment and traversal of sequence table
Read in n values and N integers, establish a sequence table and traverse the output.
Input format:
Read in n and n integers
Output format:
Output n integers separated by spaces (there is no space after the last number).
4 -3 10 20 78 No blank lines at the end
3 10 20 78 No blank lines at the end
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int data;
struct node* next;
}node;
node* Create(int n)
{
node* list, * p, * q;
list = (node*)malloc(sizeof(node));
q = list;
for (int i = 0; i < n; i++)
{
p = (node*)malloc(sizeof(node));
scanf("%d", &p->data);
q->next = p;
q = p;
}
q = list->next;
return q;
}
void Print(node* list)
{
printf("%d", list->data);
list = list->next;
for (; list != NULL; list = list->next)
{
printf(" %d", list->data);
}
printf("\n");
}
int main()
{
int n;
node* list;
scanf("%d", &n);
if (n == 0)
{
return 0;
}
else
{
list = Create(n);
Print(list);
}
}
3. Sequence table (deleted)
(this problem is element deletion. In fact, location deletion is similar to this one. Location deletion is just a shift after a given location is set.)
A set of data is known and stored in a sequential storage structure, in which all elements are integers. Design an algorithm to delete all elements with element values between [x,y]
Input format:
The input contains three rows of data. The first row is the number of elements in the table, the second row is each element of the sequential table, and the third row is the interval x and y.
Output format:
After deleting all elements with element values between [x,y], a new sequence table is output. (no space at the end)
10 55 11 9 15 67 12 18 33 6 22 10 20 No blank lines at the end
55 9 67 33 6 22 No blank lines at the end
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node* next;
}node;
void Initlist(node** list)
{
*list = (node*)malloc(sizeof(node));
(*list)->next = NULL;
}
void Create(int n, node* list)
{
node* p, * q;
q = list;
while (n--)
{
p = (node*)malloc(sizeof(node));
scanf("%d", &p->data);
p->next = NULL;
q->next = p;
q = p;
}
}
void Delete(int x, int y,node* list)
{
node* p = list;
for (; p->next != NULL;)
{
if (p->next->data <= y && p->next->data >= x)
{
p->next = p->next->next;
p = list;
continue;
}
p = p->next;
}
}
void Print(node* list)
{
node* p = list;
p = p->next;
printf("%d", p->data);
while (p->next != NULL)
{
printf(" %d", p->next->data);
p = p->next;
}
}
int main()
{
int m;
scanf("%d", &m);
node* list;
Initlist(&list);
Create(m, list);
int x, y;
scanf("%d%d", &x, &y);
Delete(x, y, list);
Print(list);
return 0;
}
4. Maximum subsets and problems
Given the sequence {N1, N2,..., NK} composed of K integers, the "continuous sub column" is defined as {Ni, Ni+1,..., Nj}, where 1 ≤ i ≤ j ≤ K. "Maximum child column sum" is defined as the largest sum of all consecutive child column elements. For example, given the sequence {- 2, 11, - 4, 13, - 5, - 2}, its continuous sub columns {11, - 4, 13} have a maximum sum of 20. Now you are required to write a program to calculate the maximum sub column sum of a given integer sequence.
This topic aims to test the performance of different algorithms under various data conditions. The characteristics of test data of each group are as follows:
Data 1: equivalent to the sample to test the basic correctness;
Data 2: 102 random integers;
Data 3: 103 random integers;
Data 4: 104 random integers;
Data 5: 105 random integers;
Input format:
Enter the first line to give a positive integer k (≤ 100000); Line 2 gives K integers separated by spaces.
Output format:
Outputs the maximum child column sum in a row. If all integers in the sequence are negative, 0 is output.
6 -2 11 -4 13 -5 -2 No blank lines at the end
20 No blank lines at the end
//Note how large the array should be. One of the conditions is "the fifth power of 10"!!!!
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int main()
{
int k,s = 0;
scanf("%d", &k);
int a[100001];
for (int i = 0; i < k; i++)
{
scanf("%d", &a[i]);
if (a[i] < 0)
{
s++;
}
}
if (s == k)
{
return 0;
}
else
{
int Max = 0, Thissum = 0;
for (int i = 0; i < k; i++)
{
Thissum += a[i];
if (Thissum < 0)
{
Thissum = 0;
}
if (Thissum > Max)
{
Max = Thissum;
}
}
printf("%d", Max);
}
return 0;
}
5. Insertion of incremental order table
Experimental purposes: 1. Master the basic knowledge of linear table. 2. Deeply understand, master and flexibly use linear table. 3. Master the storage structure of linear table and the realization of main operations. The known order table L is incremented and orderly. Insert X into the appropriate position of linear table to ensure the order of linear table..
Input format:
Enter the length of the sequence table in line 1, the sequence table in ascending order in line 2, and the data element X to be inserted in line 3.
Output format:
For each set of inputs, the incremental sequence table after inserting X is output in one row.
5 1 3 5 7 9 6 No blank lines at the end
1,3,5,6,7,9, No blank lines at the end
#include<stdio.h>
#include<stdlib.h>
int main() {
int n, i,e,j,t;
int a[100];
scanf("%d", &n);
scanf("%d", &e);
for (i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
a[n]=e;
for(i=0;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<=n;i++)
{
printf("%d,", a[i]);
}
return 0;
}
6. Addition of univariate polynomials
Design a program to find the sum of two univariate polynomials.
Input format:
The input is divided into two lines. In each line, the number of non-zero terms of the polynomial is given respectively, and then the coefficient and exponent of a non-zero term of the polynomial are input in an exponential descending manner. Numbers are separated by spaces.
Output format:
Output 1 line, and output the coefficients and exponents of non-zero terms of polynomials in an exponential descending manner (ensure that they do not exceed the representation range of integers). Numbers are separated by spaces, but there must be no extra spaces at the end. Zero polynomial should output 0.
4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1 No blank lines at the end
5 20 -4 4 -5 2 9 1 -2 0 No blank lines at the end
#include<stdio.h>
#include<stdlib.h>
struct node {
int coef;//coefficient
int exp;//index
struct node* next;
};
struct node* Read() {
struct node* head, * p, * tail;
int i, n;
head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
tail = head;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
p = (struct node*)malloc(sizeof(struct node));
scanf("%d%d", &p->coef, &p->exp);
p->next = NULL;
tail->next = p;
tail = p;
}
tail->next = NULL;
return head;
}
struct node* addition(struct node* l1, struct node* l2) {
struct node* t1, * t2, * l3, * p, * head;
t1 = l1->next;
t2 = l2->next;
head = (struct node*)malloc(sizeof(struct node));
head->next = NULL;
l3 = head;
while (t1 && t2) {
p = (struct node*)malloc(sizeof(struct node));
if (t1->exp == t2->exp) {
p->coef = t1->coef + t2->coef;
p->exp = t1->exp;
t1 = t1->next;
t2 = t2->next;
}
else if (t1->exp < t2->exp) {
p->coef = t2->coef;
p->exp = t2->exp;
t2 = t2->next;
}
else if (t1->exp > t2->exp) {
p->coef = t1->coef;
p->exp = t1->exp;
t1 = t1->next;
}
l3->next = p;
l3 = l3->next;
}
if (t1) {
l3->next = t1;
}
else if (t2) {
l3->next = t2;
}
return head;
}
void Print(struct node* list) {
struct node* p = list->next;
int flag = 1;
for (; p; p = p->next) {
if (flag == 0 && p->coef) {
printf(" ");
}
if (p->coef) {
printf("%d %d", p->coef, p->exp);
flag = 0;
}
}
if (flag == 1) {
printf("0 0");
}
printf("\n");
}
int main() {
struct node* l1, * l2, * head;
l1 = Read();
l2 = Read();
head = addition(l1, l2);
Print(head);
return 0;
}