数据结构——线性表作业-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——线性表作业。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

选择题和填空题

编程题

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

单链表

双指针

2. 数组元素移动

3. 多项式相加

4. 数组的循环左移

选择题和填空题

数据结构——线性表作业,数据结构学习总结,数据结构,算法,学习,笔记,c语言,娱乐,青少年编程

编程题

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

【问题描述】

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

【输入形式】

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

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

【样例输入】

3 13 45 54 32 1 4 98 2

【样例输出】

【样例说明】

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 Found\n");
    } else {
        p = head;
        for (int i = 0; i < count - k; i++) {
            p = p->next;
        }
        printf("%d\n", p->num);
    }
    p = head;
    while (p != NULL) {
        LinkList temp = p;
        p = p->next;
        free(temp);
    }
    return 0;
}

双指针

#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;
    LinkList temp=head;
    if (k <= 0) {
        printf("Not Found\n");
    } else {
        p = head;
        temp=head;
        while(k && temp){
            temp=temp->next;
            k--;
        }
        while(temp){
            temp=temp->next;
            p=p->next;
            }
        if(k > 0){
           printf("Not Found\n");
            return 0;
        }
        printf("%d\n", p->num);
    }
    return 0;
}

2. 数组元素移动

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

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

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

【评分标准】

必须用链表实现

#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 %d\n", 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

【样例说明】

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

除了提交之后自动判分之外，还会根据代码的时间复杂度酌情给分，请大家尽量降低空间、时间复杂度文章来源地址https://www.toymoban.com/news/detail-714691.html

#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;
}

到了这里，关于数据结构——线性表作业的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！