• 数据结构——线性表作业

    目录

    选择题和填空题

    编程题

    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；数据输入间以空格隔开
    【评分标准】

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

    单链表

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int num;
    6.     struct Node* next;
    7. } Node, * LinkList;
    8.  
    9. int main() {
    10.     LinkList head = NULL;
    11.     LinkList tail = NULL;
    12.     int k;
    13.     scanf("%d", &k);
    14.     int n;
    15.     while (scanf("%d", &n) != EOF) {
    16.         LinkList newNode = (LinkList)malloc(sizeof(Node));
    17.         newNode->num = n;
    18.         newNode->next = NULL;
    19.         if (head == NULL) {
    20.             head = newNode;
    21.             tail = newNode;
    22.         } else {
    23.             tail->next = newNode;
    24.             tail = tail->next;
    25.         }
    26.     }
    27.     LinkList p = head;
    28.     int count = 0;
    29.     while (p != NULL) {
    30.         count++;
    31.         p = p->next;
    32.     }
    33.     if (k <= 0 || k > count) {
    34.         printf("Not Found\n");
    35.     } else {
    36.         p = head;
    37.         for (int i = 0; i < count - k; i++) {
    38.             p = p->next;
    39.         }
    40.         printf("%d\n", p->num);
    41.     }
    42.     p = head;
    43.     while (p != NULL) {
    44.         LinkList temp = p;
    45.         p = p->next;
    46.         free(temp);
    47.     }
    48.     return 0;
    49. }

    双指针

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int num;
    6.     struct Node* next;
    7. } Node, * LinkList;
    8.  
    9. int main() {
    10.     LinkList head = NULL;
    11.     LinkList tail = NULL;
    12.     int k;
    13.     scanf("%d", &k);
    14.     int n;
    15.     while (scanf("%d", &n) != EOF) {
    16.         LinkList newNode = (LinkList)malloc(sizeof(Node));
    17.         newNode->num = n;
    18.         newNode->next = NULL;
    19.         if (head == NULL) {
    20.             head = newNode;
    21.             tail = newNode;
    22.         } else {
    23.             tail->next = newNode;
    24.             tail = tail->next;
    25.         }
    26.     }
    27.     LinkList p = head;
    28.     LinkList temp=head;
    29.     if (k <= 0) {
    30.         printf("Not Found\n");
    31.     } else {
    32.         p = head;
    33.         temp=head;
    34.         while(k && temp){
    35.             temp=temp->next;
    36.             k--;
    37.         }
    38.         while(temp){
    39.             temp=temp->next;
    40.             p=p->next;
    41.             }
    42.         if(k > 0){
    43.            printf("Not Found\n");
    44.             return 0;
    45.         }
    46.         printf("%d\n", p->num);
    47.     }
    48.     return 0;
    49. }

    2. 数组元素移动

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

    1,2,33,8,5

    【样例输出】

    1,33,5,2,8

    【评分标准】

    1. #include 
    2. #include 
    3.  
    4. int main() {
    5.     int n;
    6.     int arr[1000];
    7.     int size = 0;
    8.     while (scanf("%d,", &n) != EOF) {
    9.         arr[size] = n;
    10.         size++;
    11.     }
    12.  
    13.     int *arr1 = (int*) malloc(size * sizeof(int));
    14.     int *arr2 = (int*) malloc(size * sizeof(int));
    15.     int size1 = 0, size2 = 0;
    16.  
    17.     for (int i = 0; i < size; i++) {
    18.         if (arr[i] % 2 != 0) {
    19.             arr1[size1] = arr[i];
    20.             size1++;
    21.         } else {
    22.             arr2[size2] = arr[i];
    23.             size2++;
    24.         }
    25.     }
    26.  
    27.     for (int i = 0; i < size1; i++) {
    28.         printf("%d", arr1[i]);
    29.         if (i < size1 - 1) {
    30.             printf(",");
    31.         }
    32.     }
    33.     if(size1>=1&&size2!=0){
    34.         printf(",");
    35.     }
    36.     
    37.     for (int i = 0; i < size2; i++) {
    38.         printf("%d", arr2[i]);
    39.         if (i < size2 - 1) {
    40.             printf(",");
    41.         }
    42.     }
    43.  
    44.     free(arr1);
    45.     free(arr2);
    46.     return 0;
    47. }

    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

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

    【评分标准】

    必须用链表实现

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     float coef; 
    6.     int exp; 
    7.     struct Node* next;
    8. } Node;
    9.  
    10. Node* createNode(float coef, int exp) {
    11.     Node* newNode = (Node*)malloc(sizeof(Node));
    12.     newNode->coef = coef;
    13.     newNode->exp = exp;
    14.     newNode->next = NULL;
    15.     return newNode;
    16. }
    17.  
    18. void insertNode(Node** head, float coef, int exp) {
    19.     Node* newNode = createNode(coef, exp);
    20.     if (*head == NULL || (*head)->exp < exp) {
    21.         newNode->next = *head;
    22.         *head = newNode;
    23.     } else {
    24.         Node* temp = *head;
    25.         while (temp->next != NULL && temp->next->exp >= exp) {
    26.             temp = temp->next;
    27.         }
    28.         newNode->next = temp->next;
    29.         temp->next = newNode;
    30.     }
    31. }
    32.  
    33. Node* addPolynomials(Node* poly1, Node* poly2) {
    34.     Node* result = NULL;
    35.     while (poly1 && poly2) {
    36.         if (poly1->exp > poly2->exp) {
    37.             insertNode(&result, poly1->coef, poly1->exp);
    38.             poly1 = poly1->next;
    39.         } else if (poly1->exp < poly2->exp) {
    40.             insertNode(&result, poly2->coef, poly2->exp);
    41.             poly2 = poly2->next;
    42.         } else {
    43.             float sum = poly1->coef + poly2->coef;
    44.             if (sum) {
    45.                 insertNode(&result, sum, poly1->exp);
    46.             }
    47.             poly1 = poly1->next;
    48.             poly2 = poly2->next;
    49.         }
    50.     }
    51.     while (poly1 || poly2) {
    52.         if (poly1) {
    53.             insertNode(&result, poly1->coef, poly1->exp);
    54.             poly1 = poly1->next;
    55.         } 
    56.         if (poly2) {
    57.             insertNode(&result, poly2->coef, poly2->exp);
    58.             poly2 = poly2->next;
    59.         }
    60.     }
    61.     return result;
    62. }
    63.  
    64.  
    65. int main() {
    66.     Node* poly1 = NULL;
    67.     Node* poly2 = NULL;
    68.     float coef;
    69.     int exp;
    70.     char ch;
    71.     while (scanf("%f %d%c", &coef, &exp, &ch)) {
    72.         insertNode(&poly1, coef, exp);
    73.         if (ch == '\n') break; 
    74.     }
    75.     while (scanf("%f %d%c", &coef, &exp, &ch)) {
    76.         insertNode(&poly2, coef, exp);
    77.         if (ch == '\n') break;
    78.     }
    79.   
    80.     Node* result = addPolynomials(poly1, poly2);
    81.  
    82.     int pos;
    83.     scanf("%d", &pos);
    84.     int i;
    85.     for (i = 1; i < pos; i++) {
    86.         if (result) {
    87.             result = result->next;
    88.         }
    89.     }
    90.     if (result) {
    91.         printf("%.1f %d\n", result->coef, result->exp);
    92.     }
    93.     return 0;
    94. }

    4. 数组的循环左移

    【问题描述】

    设将n（n>1）个整数存放在一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移P（P>0）个位置。
    例如，假设P 【输入形式】

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

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

    3 5 1 2 3 4 5

    【样例输出】

    4 5 1 2 3

    【样例说明】

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

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

    1. #include 
    2. #include 
    3.  
    4. void reverseArr(int *arr, int start, int end) {
    5.     while (start < end) {
    6.         int temp = arr[start];
    7.         arr[start] = arr[end];
    8.         arr[end] = temp;
    9.         start++;
    10.         end--;
    11.     }
    12. }
    13.  
    14. void leftRotate(int *arr, int p, int n) {
    15.     reverseArr(arr, 0, p - 1);
    16.     reverseArr(arr, p, n - 1);
    17.     reverseArr(arr, 0, n - 1);
    18. }
    19.  
    20. int main() {
    21.     int p, num, i;
    22.     scanf("%d", &p);
    23.     scanf("%d", &num);
    24.     p = p % num;
    25.     int *arr = (int *)malloc(num * sizeof(int));
    26.     for (i = 0; i < num; i++) {
    27.         scanf("%d", &arr[i]);
    28.     }
    29.  
    30.     leftRotate(arr, p, num);
    31.  
    32.     for (i = 0; i < num; i++) {
    33.         printf("%d", arr[i]);
    34.         if (i < num - 1) {
    35.             printf(" ");
    36.         }
    37.     }
    38.     printf("\n");
    39.  
    40.     free(arr);
    41.     return 0;
    42. }

  • 相关阅读:
    nodejs+express+mysql简单博客搭建
    sora生成高质量视频的原理
    主流开发语言与环境介绍
    经典的CNN网络模型概述
    Android 高版本 packageManager.getPackageArchiveInfo 总是返回null
    【JavaScript】过了一年，懒癌患者终于整理了一下『手写Promise A+』
    全渠道电商 | 国内知名的药妆要如何抓住风口实现快速增长？
    MakeSense中文版使用手册【图像标注神器】
    ZYNQ_project:test_fifo_255X8
    2022谷粒商城学习笔记（二十二）rabbitＭＱ学习
  • 原文地址：https://blog.csdn.net/timberman666/article/details/133828201