数据结构——线性表作业

目录

1. 输出单链表倒数第K个结点值

2. 数组元素移动

3. 多项式相加

4. 数组的循环左移


1. 输出单链表倒数第K个结点值

【问题描述】

输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第1个节点。

【输入形式】

输入第一位为K值,其后接一串以空格分隔的整型值。
【输出形式】

输出为倒数第K个结点的值,若无,则输出Not Found

【样例输入】

3 13 45 54 32 1 4 98 2

【样例输出】

4

【样例说明】

K值为3,则输出链表倒数第3个结点的值,为4;数据输入间以空格隔开
【评分标准】

本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int num;
    struct Node* next;
} Node, * LinkList;

int main() {
    LinkList head = NULL;
    LinkList tail = NULL;
    int k;
    scanf("%d", &k);
    int n;
    while (scanf("%d", &n) != EOF) {
        LinkList newNode = (LinkList)malloc(sizeof(Node));
        newNode->num = n;
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = tail->next;
        }
    }
    LinkList p = head;
    int count = 0;
    while (p != NULL) {
        count++;
        p = p->next;
    }
    if (k <= 0 || k > count) {
        printf("Not Foundn");
    } else {
        p = head;
        for (int i = 0; i < count - k; i++) {
            p = p->next;
        }
        printf("%dn", p->num);
    }
    p = head;
    while (p != NULL) {
        LinkList temp = p;
        p = p->next;
        free(temp);
    }
    return 0;
}
2. 数组元素移动

【问题描述】
 将整数数组A[0..n],将其分为两部分,左边所有元素为奇数,右边所有元素为偶数。数组元素个数不超过1000。
【输入形式】
 以逗号隔开的所有元素
【输出形式】
 依次打印调整后的数组元素,元素间以逗号隔开。奇数序列和偶数序列分别按原序列中的顺序依次输出
【样例输入】

1,2,33,8,5

【样例输出】

1,33,5,2,8

【评分标准】

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    int arr[1000];
    int size = 0;
    while (scanf("%d,", &n) != EOF) {
        arr[size] = n;
        size++;
    }

    int *arr1 = (int*) malloc(size * sizeof(int));
    int *arr2 = (int*) malloc(size * sizeof(int));
    int size1 = 0, size2 = 0;

    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 != 0) {
            arr1[size1] = arr[i];
            size1++;
        } else {
            arr2[size2] = arr[i];
            size2++;
        }
    }

    for (int i = 0; i < size1; i++) {
        printf("%d", arr1[i]);
        if (i < size1 - 1) {
            printf(",");
        }
    }
    if(size1>=1&&size2!=0){
        printf(",");
    }
    
    for (int i = 0; i < size2; i++) {
        printf("%d", arr2[i]);
        if (i < size2 - 1) {
            printf(",");
        }
    }

    free(arr1);
    free(arr2);
    return 0;
}
3. 多项式相加

【问题描述】

编写一个程序用单链表存储多项式,并实现两个一元多项式A与B相加的函数。A,B刚开始是无序的,A与B之和按降序排列。例如:

多项式A:  1.2X^0  2.5X^1  3.2X^3  -2.5X^5

多项式B:  -1.2X^0  2.5X^1  3.2X^3   2.5X^5   5.4X^10
多项式A与B之和:5.4X^10  6.4X^3  5X^1
【输入形式】

任意两个多项式A和B
【输出形式】

多项式中某一项的系数与指数,系数保留一位小数

【输入样例】

1.2 0 2.5 1 3.2 3 -2.5 5
-1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
2

【输出样例】

6.4 3

【样例说明】
第一个多项式的系数与指数对,以空格隔开
第二个多项式的系数与指数对,以空格隔开
输出第2项的系数与指数,系数与指数间用空格隔开,系数保留一位小数

【评分标准】

必须用链表实现

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    float coef; 
    int exp; 
    struct Node* next;
} Node;

Node* createNode(float coef, int exp) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->coef = coef;
    newNode->exp = exp;
    newNode->next = NULL;
    return newNode;
}

void insertNode(Node** head, float coef, int exp) {
    Node* newNode = createNode(coef, exp);
    if (*head == NULL || (*head)->exp < exp) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL && temp->next->exp >= exp) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

Node* addPolynomials(Node* poly1, Node* poly2) {
    Node* result = NULL;
    while (poly1 && poly2) {
        if (poly1->exp > poly2->exp) {
            insertNode(&result, poly1->coef, poly1->exp);
            poly1 = poly1->next;
        } else if (poly1->exp < poly2->exp) {
            insertNode(&result, poly2->coef, poly2->exp);
            poly2 = poly2->next;
        } else {
            float sum = poly1->coef + poly2->coef;
            if (sum) {
                insertNode(&result, sum, poly1->exp);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    while (poly1 || poly2) {
        if (poly1) {
            insertNode(&result, poly1->coef, poly1->exp);
            poly1 = poly1->next;
        } 
        if (poly2) {
            insertNode(&result, poly2->coef, poly2->exp);
            poly2 = poly2->next;
        }
    }
    return result;
}


int main() {
    Node* poly1 = NULL;
    Node* poly2 = NULL;
    float coef;
    int exp;
    char ch;
    while (scanf("%f %d%c", &coef, &exp, &ch)) {
        insertNode(&poly1, coef, exp);
        if (ch == 'n') break; 
    }
    while (scanf("%f %d%c", &coef, &exp, &ch)) {
        insertNode(&poly2, coef, exp);
        if (ch == 'n') break;
    }
  
    Node* result = addPolynomials(poly1, poly2);

    int pos;
    scanf("%d", &pos);
    int i;
    for (i = 1; i < pos; i++) {
        if (result) {
            result = result->next;
        }
    }
    if (result) {
        printf("%.1f %dn", result->coef, result->exp);
    }
    return 0;
}
4. 数组的循环左移

【问题描述】

设将n(n>1)个整数存放在一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移P(P>0)个位置。
例如,假设P<n,将R中的数据(X0,X1,..Xn-1)循环左移P个位置后,变换为(Xp, XP+1,..Xn-1,X0,X1,..Xp-1)
【输入形式】

循环移动的位数,数组中数据的个数,循环前的数组
【输出形式】

循环后的数组
【样例输入】

3 5 1 2 3 4 5

【样例输出】

4 5 1 2 3

【样例说明】

请大家注意,循环位移的位数可能超过数组中元素个数;输入与输出的数据均以空格分割,其中输入的数据中第一个是循环移位的位数,第二个是数组中数据的个数,后面的是数组中的数据。
【评分标准】

除了提交之后自动判分之外,还会根据代码的时间复杂度酌情给分,请大家尽量降低空间、时间复杂度

#include <stdio.h>
#include <stdlib.h>

void reverseArr(int *arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

void leftRotate(int *arr, int p, int n) {
    reverseArr(arr, 0, p - 1);
    reverseArr(arr, p, n - 1);
    reverseArr(arr, 0, n - 1);
}

int main() {
    int p, num, i;
    scanf("%d", &p);
    scanf("%d", &num);
    p = p % num;
    int *arr = (int *)malloc(num * sizeof(int));
    for (i = 0; i < num; i++) {
        scanf("%d", &arr[i]);
    }

    leftRotate(arr, p, num);

    for (i = 0; i < num; i++) {
        printf("%d", arr[i]);
        if (i < num - 1) {
            printf(" ");
        }
    }
    printf("n");

    free(arr);
    return 0;
}