PAT 데이터 구조 기초 - 선형 구조 연습
표 의 주요 조작 은 Insert, Delete, Find 몇 가지 가 있 습 니 다.배열 은 O (1) 시간 에 K 항 을 찾 을 수 있 지만 Insert 와 Delete 작업 은 O (N) 시간 이 필요 합 니 다. 배열 요 소 를 대량으로 이동 하고 복사 해 야 하기 때 문 입 니 다.반면 링크 의 실현 은 정반 대로 O (1) 시간 내 에 Insert 와 Delete 작업 을 할 수 있 지만 K 항 을 찾 는 작업 은 O (N) 시간 이 필요 합 니 다.
스 택 은 LIFO (Last - In - First - Out) 의 데이터 구조 로 주로 Push 와 Pop 두 가지 가 있 습 니 다. Push 작업 은 새로운 요 소 를 스 택 꼭대기 에 누 르 고 Pop 작업 은 스 택 꼭대기 요 소 를 옮 깁 니 다.스 택 의 실현 방법 도 배열 과 링크 두 가지 가 있 습 니 다. 배열 이 실현 하 는 주요 단점 은 먼저 고정 크기 의 배열 을 정의 하 는 것 입 니 다. 저 장 된 요소 의 수량 이 배열 크기 보다 많 으 면 데 이 터 는 더 큰 공간 을 재분배 하고 원래 의 요 소 를 새로운 공간 으로 복사 해 야 합 니 다.스 택 구조의 주요 응용 은 접두사, 접두사, 접두사 표현 식 의 계산 과 전환, 그리고 프로그램 이 실 행 될 때의 함수 호출 도 스 택 구 조 를 사용 합 니 다.
대기 열 은 FIFO (First - In - First - Out) 의 데이터 구조 로 주로 Enqueue (입 대) 와 Dequeue (출 대) 두 가지 조작 이 있 으 며 스 택 과 마찬가지 로 대기 열 도 배열 이나 링크 를 통 해 이 루어 질 수 있다.대기 열 구조의 주요 응용 은 컴퓨터 시스템 내 메시지 대기 열 등 이 많다.
1. Reversing Linked List
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6. Input Specification: Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is an integer, and Next is the position of the next node. Output Specification: For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input. Sample Input: 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 Sample Output: 00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
사고: 문제 가 요소 의 개 수 를 제 시 했 기 때문에 저 는 배열 을 사용 하여 이 루어 졌 습 니 다. 배열 의 요소 교환 은 링크 의 실현 보다 더욱 간단 하기 때 문 입 니 다.사고방식 이 매우 간단 하 다. 데 이 터 를 읽 고 체인 테이블 을 구성 한 다음 에 체인 테이블 요 소 를 교환 하고 모든 요소 의 Next 지침 을 업데이트 한다.처음에 구덩이 에 들 어 갔 는데 모든 요소 가 링크 의 요소 가 아니 라 일부 입력 요 소 는 소 용이 없 었 다.
코드 는 다음 과 같 습 니 다:
#include
#include
#include
//
typedef struct Node {
char s[6];
int data;
char next[6];
} Node;
//
void swap (Node *Array, int index1, int index2) {
Node temp;
if (index1 == index2) {
return ;
}
memcpy(&temp, Array + index1, sizeof(Node));
memcpy(Array + index1, Array + index2, sizeof(Node));
memcpy(Array + index2, &temp, sizeof(Node));
}
int main () {
int num;
int changeNum;
char baseAd[6];
Node *Array = NULL;
int i, j;
int mid;
scanf("%s %d %d", baseAd, &num, &changeNum);
if (0 == strcmp("-1", baseAd)) {
return 1;
}
Array = malloc (num * sizeof(Node));
if (NULL == Array) {
printf("Malloc Failed!
");
return 1;
}
//
for (i = 0; i < num; i++) {
scanf("%s %d %s", Array[i].s, &(Array[i].data), Array[i].next);
}
// 0
for (i = 0; i < num; i++) {
if (0 == strcmp(Array[i].s, baseAd)) {
swap(Array, 0, i);
break;
}
}
// 0 ， Next ， Next -1 ，
for (i = 0; i < num - 1; i++) {
for (j = i + 1; j < num; j++) {
if (0 == strcmp(Array[i].next, Array[j].s)) {
swap(Array, i + 1, j);
break;
}
}
if (0 == strcmp(Array[i + 1].next, "-1")) {
num = i + 2;
break;
}
}
// reverse
mid = changeNum / 2;
for (i = 0; i < num; i += changeNum) {
if ((i + changeNum) > num) { // changeNum reverse
break;
}
for (j = 0; j < mid; j++) {
swap(Array, i + j, i + changeNum - j - 1);
}
}
for (i = 0; i < num; i++) {
if (i != (num -1)) { // Next
strcpy(Array[i].next, Array[i + 1].s);
} else {
strcpy(Array[i].next, "-1");
}
printf("%s %d %s", Array[i].s, Array[i].data, Array[i].next); //
if (i != (num - 1)) {
printf("
");
}
}
free(Array); //
return 0;
}
2. 일원 다항식 가이드
설계 함 수 는 일원 다항식 의 도 수 를 구한다.(주: xn (n 은 정수) 의 1 단계 도 수 는 n * xn - 1 이다.) 입력 형식: 지수 하락 방식 으로 다항식 비 0 항 계수 와 지수 (절대 치 는 모두 1000 을 초과 하지 않 는 정수) 를 입력 한다.숫자 사 이 를 빈 칸 으로 나누다.출력 형식: 입력 과 같은 형식 으로 도체 다항식 비 0 항목 의 계수 와 지 수 를 출력 합 니 다.숫자 사 이 는 빈 칸 으로 구분 되 지만 끝 에 빈 칸 이 있어 서 는 안 된다.'0 여 항 식' 의 지수 와 계 수 는 모두 0 이지 만 '0' 이 라 고 표시 합 니 다.
입력 샘플: 3, 4 - 5, 2, 6, 1 - 20 출력 샘플: 12, 3 - 10, 1, 6, 0
사고: 이 문 제 는 비교적 간단 하 다. 사실은 링크 를 사용 하지 않 아 도 출력 할 수 있 지만 많이 쓰 고 연습 하 는 마음 에 따라 링크 로 완전 하 게 썼 다.주의해 야 할 것 은 도체 가 0 일 때 '0 0' 을 출력 해 야 한 다 는 것 이다.
코드 는 다음 과 같 습 니 다:
#include
#include
typedef struct Node {
int co;
int power;
struct Node *next;
} Node;
int main () {
int co;
int power;
int flag = 0;
Node *head, *newNode, *tempNode;
head = malloc (sizeof (Node));
if (NULL == head) {
return 1;
}
head->co = 0;
head->power = 0;
head->next = NULL;
tempNode = head;
// scanf input
while (EOF != (scanf("%d %d", &co, &power))) {
newNode = malloc (sizeof (Node));
if (NULL == newNode) {
return 1;
}
newNode->co = co;
newNode->power = power;
newNode->next = NULL;
tempNode->next = newNode;
tempNode = newNode;
}
// cal result
tempNode = head->next;
if (NULL != tempNode) {
tempNode->co = tempNode->co * tempNode->power;
tempNode->power--;
if (0 != tempNode->co) {
flag = 1; // 0
printf("%d %d", tempNode->co, tempNode->power);
}
tempNode = tempNode->next;
while (NULL != tempNode) {
tempNode->co = tempNode->co * tempNode->power;
tempNode->power--;
if (0 != tempNode->co) {
printf(" %d %d", tempNode->co, tempNode->power);
}
tempNode = tempNode->next;
}
}
// 0， 0 0
if (!flag) {
printf("0 0");
}
// free memory
tempNode = head;
while (NULL != tempNode) {
head = tempNode->next;
free(tempNode);
tempNode = head;
}
return 0;
}
3. 접두사 표현 식 의 값 구하 기
산술 표현 식 은 접두사 표현법, 접두사 표현법 과 접두사 표현법 등 형식 이 있다.접두사 표현 식 은 이원 연산 자가 두 연산 수 앞 에 있 는 것 을 말한다. 예 를 들 어 2 + 3 * (7 - 4) + 8 / 4 의 접두사 표현 식 은 + + 2 * 3 - 7 4 / 84 이다.접두사 표현 식 의 결과 값 을 계산 하 는 프로그램 을 설계 하 십시오.
입력 형식 설명: 한 줄 에 30 자 를 넘 지 않 는 접두사 표현 식 을 입력 하 십시오. +, -, *, \ 및 연산 수 만 포함 하고 서로 다른 대상 (연산 수, 연산 기호) 사 이 를 빈 칸 으로 구분 합 니 다.
출력 형식 설명: 출력 접두사 표현 식 의 연산 결 과 는 소수점 뒤의 1 자리 까지 정확 하거나 오류 정보 인 'ERROR' 입 니 다.
샘플 입 출력
사고방식: 접두사, 접두사, 접두사 표현 식 등에 대해 기본적으로 창고 구 조 를 사용 해 야 한다.접두사 표현 식 을 살 펴 보면 하나의 연산 자 를 읽 은 후에 두 개의 조작 수 라면 계산 할 수 있 습 니 다. 따라서 왼쪽 에서 오른쪽으로 표현 식 을 읽 을 때 연산 자 를 읽 을 때 스 택 에 눌 러 넣 고 작업 수 를 읽 을 때 스 택 꼭대기 도 조작 수 인지 판단 할 수 있 습 니 다. 조작 수 라면 pop 은 이 조작 수 를 operand 1 로 하고 읽 은 조작 수 는 operand 2 로 합 니 다.스 택 상단 의 연산 자 를 계속 팝 니 다.결 과 를 얻 은 후에 스 택 지붕 이 조작 수 인지 계속 판단 하고 똑 같은 연산 을 반복 하 며 조작 수가 아 닌 후에 결 과 를 스 택 에 넣 고 다음 수 를 계속 읽 습 니 다.알고리즘 사고방식 은 문제 가 되 지 않 았 지만 문자열 의 조작 에 문제 가 생 겼 습 니 다. 그리고 C / C + + 의 디 버 깅 환경 도 없 었 습 니 다. 마지막 으로 자바 로 썼 습 니 다. 자바 가 문자열 에 대한 조작 은 비교적 간단 합 니 다. 특히 문자열 과 숫자 간 의 변환 을 처리 합 니 다.
코드 는 다음 과 같 습 니 다:
import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
DecimalFormat decimalFormat = new DecimalFormat(".#");
Scanner in = new Scanner(System.in);
String line = in.nextLine(); //
String[] array = line.split(" "); // split
LinkedList stack = new LinkedList();
String temp;
String op;
double operand1, operand2;
for (int i = 0; i < array.length; i++) {
temp = array[i];
if (!isOperator(temp)) {
operand2 = Double.parseDouble(temp);
while (!stack.isEmpty() && !isOperator(stack.peek())) { // ，
operand1 = Double.parseDouble(stack.pop());
op = stack.pop();
if (op.equals("/") && operand2 == 0) { // 0， ERROR
System.out.print("ERROR");
System.exit(0);
} else {
operand2 = calculate(operand1, operand2, op);
}
}
stack.push(String.valueOf(operand2)); // ，
} else {
stack.push(temp); // ，
}
}
operand1 = Double.parseDouble(stack.pop());
System.out.print(decimalFormat.format(operand1));
}
//
public static double calculate (double opr1, double opr2, String op) {
double result = 0;
char c = op.charAt(0);
switch (c) {
case '+': result = opr1 + opr2; break;
case '-': result = opr1 - opr2; break;
case '*': result = opr1 * opr2; break;
case '/': result = opr1 / opr2; break;
}
return result;
}
//
public static boolean isOperator (String s) {
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
return true;
}
return false;
}
}
4. Pop Sequence
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification: Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification: For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
Sample Input: 5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2 Sample Output: YES NO NO YES NO
사고: 스 택 에 들 어가 서 스 택 작업 을 모 의 합 니 다.수 는 1 부터 작은 것 에서 큰 것 으로 스 택 에 들 어 갔 습 니 다. 스 택 시퀀스 에 어떤 숫자 가 나 오 면 이 숫자 보다 작은 숫자 가 먼저 스 택 에 들 어 갔 을 것 입 니 다.따라서 알고리즘 사 고 는 마지막 스 택 에 있 는 디지털 lastInt 를 기록 하고 스 택 시퀀스 의 숫자 를 읽 을 때마다 이 숫자 가 스 택 꼭대기 요소 와 같 으 면 pop 스 택 꼭대기 요 소 를 기록 하고 다음 스 택 시퀀스 의 숫자 를 계속 읽 는 것 입 니 다.이 숫자 가 스 택 상단 요소 와 같 지 않 으 면 last Int + 1 부터 현재 스 택 숫자 에 눌 릴 때 까지 계속 숫자 를 누 르 고 과정 에서 스 택 요소 가 최대 용량 을 초과 하면 이 스 택 시퀀스 가 불가능 하 다 는 것 을 나타 낸다. 그렇지 않 으 면 스 택 을 계속 누 르 고 pop 현재 스 택 숫자 를 나타 낸다.모든 스 택 숫자 를 읽 고 스 택 이 비어 있 는 지 여 부 를 판단 합 니 다. 비어 있 지 않 으 면 스 택 시퀀스 가 불가능 합 니 다.
코드 는 다음 과 같 습 니 다:
#include
#include
using namespace std;
// pop
bool isPopSeq (int array[], int n, int m) {
stack stack;
int curInt;
int lastOut = 0; //
for (int i = 0; i < n; i++) {
curInt = array[i];
if (!stack.empty() && stack.top() == curInt) { // ，
stack.pop();
continue;
}
if (stack.empty() || stack.top() < curInt) { // ，
for (int j = lastOut + 1; j <= curInt; j++) {
stack.push(j);
if (stack.size() > m) { // ，
return false;
}
}
lastOut = stack.top(); // lastOut
stack.pop(); // pop
}
}
if (!stack.empty()) {
return false;
}
return true;
}
int main () {
int m, n, k;
cin >> m >> n >> k;
int *pop = new int[n];
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
cin >> pop[j];
}
if (isPopSeq(pop, n, m)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
