데이터 구조 총화: (2) 링크
55964 단어 데이터 구조
Description
일원 다항식 p(x)=p0+p1x+p2x2+ … +pnxn ，각 항목 마다 계수 와 지수 두 부분 이 있 는데, 예 를 들 어 p2x 2 의 계 수 는 p2 이 고 지 수 는 2 이다.
프로 그래 밍 은 두 다항식 의 더하기 를 실현 한다.
예 를 들 어 5 + x + 2x2 + 3x3, - 5 - x + 6x2 + 4x4
둘 을 더 한 결과: 8x2 + 3x3 + 4x4
그 중에서 계수 5 와 - 5 는 모두 x 의 0 차방 의 계수 이 고 더하기 후 0 이기 때문에 표시 하지 않 습 니 다.x 의 1 차방 동 리 는 표시 되 지 않 습 니 다.
순서 표 나 단일 체인 표 로 구현 가능
Input
첫 번 째 줄: t 를 입력 하면 t 조 테스트 데이터 가 있 음 을 표시 합 니 다.
두 번 째 줄: n 을 입력 하면 1 조 의 첫 번 째 다항식 은 n 개 항목 을 포함 합 니 다.
세 번 째 줄: 첫 번 째 항목 의 계수 와 지 수 를 입력 하고 이 를 통 해 n 줄 을 입력 합 니 다.
이 어 m 를 입력 하면 1 조 의 두 번 째 다항식 은 m 항 을 포함한다.
동 리 는 두 번 째 다항식 의 m 개 항의 계수 와 지 수 를 입력 한다.
위 에서 2 조 데 이 터 를 입력 한 것 을 참고 하여 t 조 를 유추 하여 입력 합 니 다.
모든 데이터 가 정수 라 고 가정 하 세 요.
Output
각 1 조 의 데이터 에 대해 서 는 먼저 두 줄 로 두 개의 원래 다항식 을 출력 한 다음 에 한 줄 로 연산 결 과 를 출력 하 며 결과 가 모두 0 인 상황 을 고려 할 필요 가 없다.
출력 형식 은 견본 데 이 터 를 참고 하고 형식 요 구 는 다음 과 같 습 니 다.
1. 지수 나 계수 가 음수 라면 소괄호 로 묶는다
2. 계수 가 0 이면 출력 하지 않 아 도 됩 니 다.
3. 지수 가 0 이 아니라면 기호 ^ 로 표시 합 니 다. 예 를 들 어 x 의 3 차방 은 x ^ 3 로 표시 합 니 다.
4. 다항식 의 각 항목 사 이 를 기호 + 로 연결 하고 각 + 양쪽 에 빈 칸 을 하나 더 해서 분리 한다.
Sample Input
2 4 5 0 1 1 2 2 3 3 4 -5 0 -1 1 6 2 4 4 3 -3 0 -5 1 2 2 4 9 -1 2 0 3 1 -2 2
Sample Output
5 + 1x^1 + 2x^2 + 3x^3 (-5) + (-1)x^1 + 6x^2 + 4x^4 8x^2 + 3x^3 + 4x^4 (-3) + (-5)x^1 + 2x^2 9x^(-1) + 2 + 3x^1 + (-2)x^2 9x^(-1) + (-1) + (-2)x^1
코드:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 int A[200];
6 int B[200];
7
8 void print(int s[]){
9 int i;
10 int flag = 1;
11 for(i=0;i<200;++i){
12 if(s[i]){
13 if(flag == 1){
14 flag = 0;
15 }
16 else printf(" + ");
17 if(s[i]>0) printf("%d", s[i]);
18 else printf("(%d)", s[i]);
19 if(i != 100) printf("x^");
20 if(i > 100) printf("%d", i-100);
21 if(i < 100) printf("(%d)", i-100);
22 }
23 }
24 printf("
");
25 }
26
27 int main(int argc, char const *argv[])
28 {
29 int n, t, i, value, pos;
30 scanf("%d", &t);
31 while(t--){
32 memset(A, 0, sizeof(A));
33 memset(B, 0, sizeof(B));
34 scanf("%d", &n);
35 for(i=0;i<n;++i){
36 scanf("%d%d", &value, &pos);
37 A[pos+100] = value;
38 }
39 print(A);
40 scanf("%d", &n);
41 for(i=0;i<n;++i){
42 scanf("%d%d", &value, &pos);
43 B[pos+100] = value;
44 }
45 print(B);
46
47 for(i=0;i<200;++i)
48 B[i]+=A[i];
49 print(B);
50 }
51 return 0;
52 }Description
일원 다항식
p(x)=p
0
+p
1
x+p
2
x
2
+
…
+p
n
x
n
p2x 2
지수
프로 그래 밍 은 두 다항식 의 상승 을 실현 한다.
예 를 들 어 5 + x, - 5 + 6 x2
, 상승 결과: - 25 - 5x + 30x2 + 6x3
순서 표 나 단일 체인 표 로 구현 가능
Input
첫 번 째 줄: t 를 입력 하면 t 조 테스트 데이터 가 있 음 을 표시 합 니 다.
두 번 째 줄: n 을 입력 하면 1 조 의 첫 번 째 다항식 은 n 개 항목 을 포함 합 니 다.
세 번 째 줄: 첫 번 째 항목 의 계수 와 지 수 를 입력 하고 이 를 통 해 n 줄 을 입력 합 니 다.
이 어 m 를 입력 하면 1 조 의 두 번 째 다항식 은 m 항 을 포함한다.
동 리 는 두 번 째 다항식 의 m 개 항의 계수 와 지 수 를 입력 한다.
위 에서 2 조 데 이 터 를 입력 한 것 을 참고 하여 t 조 를 유추 하여 입력 합 니 다.
모든 데이터 가 정수 라 고 가정 하 세 요.
Output
각 1 조 의 데이터 에 대해 서 는 먼저 두 줄 로 두 개의 원래 다항식 을 출력 한 다음 에 한 줄 로 연산 결 과 를 출력 하 며 결과 가 모두 0 인 상황 을 고려 할 필요 가 없다.
출력 형식 은 견본 데 이 터 를 참고 하고 형식 요 구 는 다음 과 같 습 니 다.
1. 지수 나 계수 가 음수 라면 소괄호 로 묶는다
2. 계수 가 0 이면 출력 하지 않 아 도 됩 니 다.
3. 지수 가 0 이 아니라면 기호 ^ 로 표시 합 니 다. 예 를 들 어 x 의 3 차방 은 x ^ 3 로 표시 합 니 다.
4. 다항식 의 각 항목 사 이 를 기호 + 로 연결 하고 각 + 양쪽 에 빈 칸 을 하나 더 해서 분리 한다.
Sample Input
2 2 5 0 1 1 2 -5 0 6 2 3 1 0 1 1 1 2 3 2 -1 -1 0 -1 1
Sample Output
5 + 1x^1 (-5) + 6x^2 (-25) + (-5)x^1 + 30x^2 + 6x^3 1 + 1x^1 + 1x^2 2x^(-1) + (-1) + (-1)x^1 2x^(-1) + 1 + (-2)x^2 + (-1)x^3
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 int A[200],B[200],C[200],A1[100],B1[100];
6
7 void print(int s[]){
8 int i, flag = 1;
9 for(i=0;i<200;++i){
10 if(s[i]){
11 if(flag == 1){flag = 0;}
12 else printf(" + ");
13 if(s[i]>0) printf("%d", s[i]);
14 else printf("(%d)", s[i]);
15 if(i != 100) printf("x^");
16 if(i > 100) printf("%d", i-100);
17 if(i < 100) printf("(%d)", i-100);
18 }
19 }
20 printf("
");
21 }
22
23 int main(int argc, char const *argv[])
24 {
25 int n1, n2, n, t, i, j, value, pos;
26 scanf("%d", &t);
27 while(t--){
28 memset(A, 0, sizeof(A));
29 memset(B, 0, sizeof(B));
30 memset(C, 0, sizeof(C));
31 scanf("%d", &n1);
32 for(i=0;i<n1;++i){
33 scanf("%d%d", &value, &pos);
34 A[pos+100] = value;
35 A1[i] = pos+100;
36 }
37 print(A);
38
39 scanf("%d", &n2);
40 for(i=0;i<n2;++i){
41 scanf("%d%d", &value, &pos);
42 B[pos+100] = value;
43 B1[i] = pos+100;
44 }
45 print(B);
46
47 for(i=0;i<n1;++i){
48 for(j=0;j<n2;++j){
49 C[A1[i]+B1[j]-100] += A[A1[i]] * B[B1[j]];
50 }
51 }
52 print(C);
53 }
54 return 0;
55 }Description
C + + 로 헤드 노드 를 포함 하 는 단일 체인 표를 실현 한 다음 에 단일 체인 표 의 두 개의 노드 교환 위 치 를 실현 합 니 다.
두 노드 에 데 이 터 를 포함 하 는 것 을 간단하게 교환 할 수 없 으 며, 반드시 지침 을 수정 하여 두 노드 의 위치 교환 을 실현 해 야 합 니 다.
교환 함수 정 의 는 참고 할 수 있 습 니 다:
swap（int pa, int pb) //pa 와 pb 는 두 개의 결점 이 단일 체인 표 의 위치 번 호 를 나타 낸다.
swap (ListNode * p, ListNode * q) //p 와 q 는 두 결점 을 가리 키 는 지침 을 나타 낸다
Input
첫 번 째 줄 에 n 을 입력 하면 n 개의 데이터 가 있 음 을 표시 하고 n 개의 데 이 터 를 입력 합 니 다.
두 번 째 줄 은 교환 할 두 개의 노드 위 치 를 입력 하 십시오.
세 번 째 줄 은 교환 할 두 개의 노드 위 치 를 입력 하 십시오.
Output
첫 번 째 줄 출력 단일 체인 시트 생 성 후의 모든 데 이 터 는 빈 칸 으로 구분 합 니 다.
두 번 째 줄 출력 은 첫 번 째 교환 작업 을 수행 한 후의 단일 체인 시트 데 이 터 를 실행 하고 데이터 간 에 빈 칸 으로 분리 합 니 다.
세 번 째 줄 출력 은 두 번 째 교환 작업 을 수행 한 후의 단일 체인 표 데 이 터 를 빈 칸 으로 분리 합 니 다.
입력 위치 가 합 법 적 이지 않 은 것 을 발견 하면 출력 문자열 error 는 단일 체인 표를 출력 할 필요 가 없습니다.
Sample Input
5 11 22 33 44 55 1 4 2 6
Sample Output
11 22 33 44 55 44 22 33 11 55 error
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct node *link;
5 typedef struct node{
6 int data;
7 link next;
8 }Node;
9 int n;
10
11 void insert(int pos, int value, link L){
12 int i;
13 link y = malloc(sizeof(Node));
14 y->data = value;
15 link p = L;
16 for(i=0;i<pos;++i)
17 p=p->next;
18 y->next = p->next;
19 p->next = y;
20 }
21
22 void print(link L){
23 int i;
24 link p = L->next;
25 while(p){
26 if(p==L->next)
27 printf("%d", p->data);
28 else printf(" %d", p->data);
29 p = p->next;
30 }
31 printf("
");
32 }
33
34 void swap(int pos1, int pos2, link L){
35 int i;
36 if(pos1 < 0 || pos1 > n || pos2 < 0 || pos2 > n){
37 printf("error
");
38 return ;
39 }
40 link t1, t2, l1, l2;
41 link p1 = L;
42 link p2 = L;
43 for(i=0;i<pos1-1;++i)
44 p1=p1->next;
45 t1 = p1->next;
46 l1 = t1->next;
47 for(i=0;i<pos2-1;++i)
48 p2=p2->next;
49 t2 = p2->next;
50 l2 = t2->next;
51
52 if(l1 == t2){
53 p1->next = t2;
54 t2->next = t1;
55 t1->next = l2;
56 print(L);
57 return;
58 }
59
60 p1->next = t2;
61 t2->next = l1;
62 t1->next = l2;
63 p2->next = t1;
64 print(L);
65 }
66
67 int main(int argc, char const *argv[])
68 {
69 int i, pos1, pos2;
70 int value;
71 link L = malloc(sizeof(Node));
72 L->next = 0;
73 scanf("%d", &n);
74 for(i=0;i<n;++i){
75 scanf("%d", &value);
76 insert(i, value, L);
77 }
78 print(L);
79 scanf("%d%d", &pos1, &pos2);
80 swap(pos1, pos2, L);
81 scanf("%d%d", &pos1, &pos2);
82 swap(pos1, pos2, L);
83 return 0;
84 }Description
두 개의 단일 체인 표 가 점차적으로 질서 가 있 고 두 개의 단일 체인 표 의 합병 을 실현 하 며 계속 증가 하고 질서 가 있다 고 가정 한다.
만약 여러분 이 앞의 링크 클래스 정 의 를 사용 했다 면, 석조 함 수 를 차단 하 십시오. 그렇지 않 으 면 오류 가 발생 할 수 있 습 니 다.
Input
첫 번 째 줄 에 n 을 입력 하면 n 개의 데이터 가 있 음 을 표시 하고 n 개의 데 이 터 를 입력 합 니 다.
두 번 째 줄 에 m 를 먼저 입력 하면 M 개의 데이터 가 있 음 을 표시 하고, 이어서 m 개의 데 이 터 를 입력 한다.
Output
합 쳐 진 단일 링크 데 이 터 를 출력 하고 데이터 사 이 를 빈 칸 으로 구분 합 니 다.
Sample Input
3 11 33 55 4 22 44 66 88
Sample Output
11 22 33 44 55 66 88
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct node *link;
4 typedef struct node{
5 int data;
6 link next;
7 }Node;
8
9 link init(){
10 int n, value, i;
11 link L = malloc(sizeof(Node));
12 L->next = 0;
13 scanf("%d", &n);
14 for(i=0;i<n;++i){
15 link y = malloc(sizeof(Node));
16 scanf("%d", &y->data);
17 link p = L;
18 while(p->next) p = p->next;
19 y->next = p->next;
20 p->next = y;
21 }
22 return L;
23 }
24
25 link guibing(link L1, link L2){
26 link L = malloc(sizeof(Node));
27 L->next = 0;
28 link p1 = L1->next;
29 link p2 = L2->next;
30 link p = L;
31 while(p1 || p2){
32 while(p->next) p = p->next;
33 if(p1 && p2){
34 link y = malloc(sizeof(Node));
35 if(p1->data<p2->data){
36 y->data = p1->data;
37 p1 = p1->next;
38 }
39 else{
40 y->data = p2->data;
41 p2 = p2->next;
42 }
43 y->next = p->next;
44 p->next = y;
45 }
46 else if(p1){
47 p->next = p1;
48 break;
49 }
50 else if(p2){
51 p->next = p2;
52 break;
53 }
54 }
55 return L;
56 }
57
58 void print(link L){
59 link p = L->next;
60 while(p){
61 printf("%d ", p->data);
62 p = p->next;
63 }
64 printf("
");
65 }
66
67 int main(int argc, char const *argv[])
68 {
69
70 link L1 = init();
71 link L2 = init();
72 link L3 = guibing(L1, L2);
73 print(L3);
74 return 0;
75 }Input
n. 첫 번 째 줄 에 n 을 입력 하면 n 개의 데이터 가 있 음 을 나타 내 고 n 개의 데 이 터 를 입력 합 니 다.
두 번 째 줄 에 삽입 할 위치 와 새 데 이 터 를 입력 하 십시오.
세 번 째 줄 에 삽입 할 위치 와 새 데 이 터 를 입력 하 십시오.
4 번 째 줄 삭제 할 위 치 를 입력 하 십시오.
다섯 번 째 줄 삭제 할 위치 입력
여섯 번 째 줄 에서 찾 을 위 치 를 입력 하 십시오.
일곱 번 째 줄 에서 찾 을 위 치 를 입력 하 십시오.
Output
n
데이터 사 이 를 빈 칸 으로 구분 합 니 다.
첫 번 째 줄 출력 생 성 된 단일 체인 시트 의 데이터
한 번 의 작업 (삽입 또는 삭제) 을 성공 적 으로 수행 할 때마다 실행 후의 단일 링크 데 이 터 를 출력 합 니 다.
검색 을 성공 적 으로 실행 할 때마다 찾 은 데 이 터 를 출력 합 니 다.
실행 에 실패 하면 (삽입, 삭제, 찾기 등 실패 포함) 출력 문자열 error 는 단일 체인 표를 출력 할 필요 가 없습니다.
Sample Input
6 11 22 33 44 55 66 3 777 1 888 1 11 0 5
Sample Output
11 22 33 44 55 66 11 22 777 33 44 55 66 888 11 22 777 33 44 55 66 11 22 777 33 44 55 66 error error 44
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct node *link;
4 typedef struct node{
5 int data;
6 link next;
7 }Node;
8
9 int n, len;
10
11 link init(){
12 link L = malloc(sizeof(Node));
13 L->next = 0;
14 L->data = 0;
15 return L;
16 }
17
18 void print(link L){
19 int i;
20 link p = L->next;
21 while(p){
22 printf("%d ", p->data);
23 p = p->next;
24 }
25 printf("
");
26 }
27
28 void insert(int value, int pos, link L){
29 int i;
30 if(pos<1 || pos > len+1){
31 printf("error
");
32 return ;
33 }
34 link y = malloc(sizeof(Node));
35 y->data = value;
36 link p = L;
37 for(i=1;i<pos;++i)
38 p = p->next;
39 y->next = p->next;
40 p->next = y;
41 ++len;
42 print(L);
43 }
44
45 void _insert(int value, int pos, link L){
46 int i;
47 link y = malloc(sizeof(Node));
48 y->data = value;
49 link p = L;
50 for(i=1;i<pos;++i)
51 p = p->next;
52 y->next = p->next;
53 p->next = y;
54 ++len;
55 }
56
57 void delete(int pos, link L){
58 int i;
59 if(pos < 1 || pos > len){
60 printf("error
");
61 return ;
62 }
63 link p = L;
64 for(i=1;i<pos;++i)
65 p = p->next;
66 p->next = p->next->next;
67 --len;
68 print(L);
69 }
70
71 void find(int pos, link L){
72 int i;
73 if(pos < 1 || pos > len){
74 printf("error
");
75 return ;
76 }
77 link p = L->next;
78 for(i=1;i<pos;++i)
79 p = p->next;
80 printf("%d
", p->data);
81 }
82
83 int main(int argc, char const *argv[])
84 {
85 scanf("%d", &n);
86 int i, value, pos;
87 link L = init();
88 int len = 1;
89 for(i=1;i<=n;++i){
90 scanf("%d", &value);
91 _insert(value, i, L);
92 }
93 print(L);
94
95 scanf("%d%d", &pos, &value);
96 insert(value, pos, L);
97
98 scanf("%d%d", &pos, &value);
99 insert(value, pos, L);
100
101 scanf("%d", &pos);
102 delete(pos, L);
103
104 scanf("%d", &pos);
105 delete(pos, L);
106
107 scanf("%d", &pos);
108 find(pos, L);
109
110 scanf("%d", &pos);
111 find(pos, L);
112
113 return 0;
114 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
