设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › 数据结构求助
返回列表 发新帖
查看: 1119|回复: 8

[已解决]数据结构求助

[复制链接]
乔治爱啃脚趾
发表于 2023-10-3 14:51:03 | 显示全部楼层 |阅读模式
2鱼币
1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致;

2. 在链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值;

3. 删除链表中第i个元素，并输出被删除的元素值和删除后的链表中各元素值;

4. 在链表中查找第i个数据元素结点，如果查找成功，则显示“查找成功！”和该元素的值，否则显示“查找失败！”;

5. 根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1，并输出有序链表中各元素值;

6. 根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2，并输出有序链表中各元素值;

7. 将有序链表L1和L2合并到单链表L1中，要求使用原链中的结点，并使L1保持其原有序性，最后输出合并后的有序链表中各结点的元素值。

8.  已知两个一元多项式A(x)=a1xe1+ a2xe2+……+ amxem，B(x)= b1xe1+ b2xe2+……+ bmxen，其中ei为整数指数且递增有序。要求编写算法实现两个一元多项式A和B的加法运算A(x)= A(x)+ B(x)，并编写程序测试其正确性。
这是我目前写的
  1. #include <stdio.h>;
  2. #include <stdlib.h>;
  3. typedef int elemtype;
  4. typedef struct lnode{
  5.         elemtype date;
  6.         struct lnode *next;
  7. }lnode,*linklist;
  8. void initlist(linklist &l)
  9. {
  10.         int n;
  11.         elemtype e;
  12.         l=(linklist)malloc(sizeof(lnode));
  13.         l->next=NULL;
  14.         printf("请输入你想建立的长度：\n");
  15.         scanf("%d",&n);
  16.         printf("请输入数字：\n");
  17.         for(int i=0;i<n;i++){
  18.                 scanf("%d",&e);
  19.                 linklist p=(linklist)malloc(sizeof(lnode));
  20.                 p->date=e;
  21.                 l->next=p;
  22.                 p->next=NULL;
  23.         }
  24. }
  25. void output(linklist l)
  26. {
  27.         linklist p=l->next;
  28.         while(p){
  29.                 printf("%d",p->date);
  30.                 p=p->next;
  31.         }
  32.         printf("\n");
  33. }
  34. void delete1(linklist &l)
  35. {
  36.         int n,j;
  37.         linklist p=l,q;
  38.         printf("请输入你要删除的位置：\n");
  39.         scanf("%d",&n);
  40.         for(j=0;j<n-1;j++)
  41.         {
  42.                 p=p->next;
  43.         }
  44.         if((p->next))
  45.         {
  46.                 printf("error\n");
  47.         }
  48.         q=p->next;
  49.         p->next=q->next;
  50.         free(q);
  51. }
  52. int main()
  53. {
  54.         linklist l;
  55.         initlist(l);
  56.         delete1(l);
  57.         output(l);
  58. }
复制代码
最佳答案
月排行榜 / 总排行榜
陶远航
2023-10-3 14:51:04
你的问题包含了多个子问题，我将按照顺序为你解答。首先，我会对你提供的代码进行分析和修改，然后针对你的问题提供解决方案。

首先，你的代码有一些问题，我将对其进行修改。以下是修改后的代码：

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

  4. typedef int elemtype;
  5. typedef struct lnode {
  6.     elemtype date;
  7.     struct lnode *next;
  8. } lnode, *linklist;

  10. void initlist(linklist *l) {
  11.     int n;
  12.     elemtype e;
  13.     *l = (linklist)malloc(sizeof(lnode));
  14.     (*l)->next = NULL;
  15.     printf("请输入你想建立的长度：\
  16. ");
  17.     scanf("%d", &n);
  18.     printf("请输入数字：\
  19. ");
  20.     linklist tail = *l;
  21.     for (int i = 0; i < n; i++) {
  22.         scanf("%d", &e);
  23.         linklist p = (linklist)malloc(sizeof(lnode));
  24.         p->date = e;
  25.         p->next = NULL;
  26.         tail->next = p;
  27.         tail = p;
  28.     }
  29. }

  31. void output(linklist l) {
  32.     linklist p = l->next;
  33.     while (p) {
  34.         printf("%d ", p->date);
  35.         p = p->next;
  36.     }
  37.     printf("\
  38. ");
  39. }

  41. void delete1(linklist *l) {
  42.     int n, j;
  43.     linklist p = *l, q;
  44.     printf("请输入你要删除的位置：\
  45. ");
  46.     scanf("%d", &n);
  47.     for (j = 0; j < n - 1; j++) {
  48.         p = p->next;
  49.     }
  50.     if (!(p->next)) {
  51.         printf("error\
  52. ");
  53.     } else {
  54.         q = p->next;
  55.         p->next = q->next;
  56.         free(q);
  57.     }
  58. }

  60. int main() {
  61.     linklist l;
  62.     initlist(&l);
  63.     delete1(&l);
  64.     output(l);
  65. }
复制代码


接下来，我将针对你的问题提供解决方案：

1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

   这部分已经在上面的代码中实现了，initlist 函数用于创建链表，output 函数用于输出链表中的元素。

2. 在链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。

   你可以添加一个名为 insert 的函数来实现这个功能：

  
  1.    void insert(linklist *l, int i, elemtype x) {
  2.        linklist p = *l;
  3.        int j;
  4.        for (j = 0; j < i - 1; j++) {
  5.            p = p->next;
  6.            if (!p) {
  7.                printf("插入位置错误\
  8. ");
  9.                return;
  10.            }
  11.        }
  12.        linklist new_node = (linklist)malloc(sizeof(lnode));
  13.        new_node->date = x;
  14.        new_node->next = p->next;
  15.        p->next = new_node;
  16.    }
  17.    
复制代码


   在 main 函数中调用 insert 函数：

  
  1.    int main() {
  2.        linklist l;
  3.        initlist(&l);
  4.        insert(&l, 2, 42); // 在第2个元素之前插入值为42的元素
  5.        output(l);
  6.        delete1(&l);
  7.        output(l);
  8.    }
  9.    
复制代码


3. 删除链表中第i个元素，并输出被删除的元素值和删除后的链表中各元素值。

   这部分已经在上面的代码中实现了，delete1 函数用于删除链表中的元素。

4. 在链表中查找第i个数据元素结点，如果查找成功，则显示“查找成功！”和该元素的值，否则显示“查找失败！”。

   你可以添加一个名为 find 的函数来实现这个功能：

  
  1.    void find(linklist l, int i) {
  2.        linklist p = l->next;
  3.        int j;
  4.        for (j = 1; j < i; j++) {
  5.            if (!p) {
  6.                break;
  7.            }
  8.            p = p->next;
  9.        }
  10.        if (p) {
  11.            printf("查找成功！第%d个元素的值为：%d\
  12. ", i, p->date);
  13.        } else {
  14.            printf("查找失败！\
  15. ");
  16.        }
  17.    }
  18.    
复制代码


   在 main 函数中调用 find 函数：

  
  1.    int main() {
  2.        linklist l;
  3.        initlist(&l);
  4.        insert(&l, 2, 42);
  5.        output(l);
  6.        find(l, 3); // 查找第3个元素
  7.        delete1(&l);
  8.        output(l);
  9.    }
  10.    
复制代码


接下来的问题涉及到有序链表的合并和一元多项式的加法运算，由于篇幅原因，我将在下一个回答中为你解答。
如果问题已经解决，请设置最佳答案

最佳答案

陶远航

查看完整内容

你的问题包含了多个子问题，我将按照顺序为你解答。首先，我会对你提供的代码进行分析和修改，然后针对你的问题提供解决方案。 首先，你的代码有一些问题，我将对其进行修改。以下是修改后的代码： 接下来，我将针对你的问题提供解决方案： 1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。 这部分已经在上面的代码中实现了，initl ...
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

陶远航
发表于 2023-10-3 14:51:04 | 显示全部楼层    本楼为最佳答案   
你的问题包含了多个子问题，我将按照顺序为你解答。首先，我会对你提供的代码进行分析和修改，然后针对你的问题提供解决方案。

首先，你的代码有一些问题，我将对其进行修改。以下是修改后的代码：

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

  4. typedef int elemtype;
  5. typedef struct lnode {
  6.     elemtype date;
  7.     struct lnode *next;
  8. } lnode, *linklist;

  10. void initlist(linklist *l) {
  11.     int n;
  12.     elemtype e;
  13.     *l = (linklist)malloc(sizeof(lnode));
  14.     (*l)->next = NULL;
  15.     printf("请输入你想建立的长度：\
  16. ");
  17.     scanf("%d", &n);
  18.     printf("请输入数字：\
  19. ");
  20.     linklist tail = *l;
  21.     for (int i = 0; i < n; i++) {
  22.         scanf("%d", &e);
  23.         linklist p = (linklist)malloc(sizeof(lnode));
  24.         p->date = e;
  25.         p->next = NULL;
  26.         tail->next = p;
  27.         tail = p;
  28.     }
  29. }

  31. void output(linklist l) {
  32.     linklist p = l->next;
  33.     while (p) {
  34.         printf("%d ", p->date);
  35.         p = p->next;
  36.     }
  37.     printf("\
  38. ");
  39. }

  41. void delete1(linklist *l) {
  42.     int n, j;
  43.     linklist p = *l, q;
  44.     printf("请输入你要删除的位置：\
  45. ");
  46.     scanf("%d", &n);
  47.     for (j = 0; j < n - 1; j++) {
  48.         p = p->next;
  49.     }
  50.     if (!(p->next)) {
  51.         printf("error\
  52. ");
  53.     } else {
  54.         q = p->next;
  55.         p->next = q->next;
  56.         free(q);
  57.     }
  58. }

  60. int main() {
  61.     linklist l;
  62.     initlist(&l);
  63.     delete1(&l);
  64.     output(l);
  65. }
复制代码


接下来，我将针对你的问题提供解决方案：

1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

   这部分已经在上面的代码中实现了，initlist 函数用于创建链表，output 函数用于输出链表中的元素。

2. 在链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。

   你可以添加一个名为 insert 的函数来实现这个功能：

  
  1.    void insert(linklist *l, int i, elemtype x) {
  2.        linklist p = *l;
  3.        int j;
  4.        for (j = 0; j < i - 1; j++) {
  5.            p = p->next;
  6.            if (!p) {
  7.                printf("插入位置错误\
  8. ");
  9.                return;
  10.            }
  11.        }
  12.        linklist new_node = (linklist)malloc(sizeof(lnode));
  13.        new_node->date = x;
  14.        new_node->next = p->next;
  15.        p->next = new_node;
  16.    }
  17.    
复制代码


   在 main 函数中调用 insert 函数：

  
  1.    int main() {
  2.        linklist l;
  3.        initlist(&l);
  4.        insert(&l, 2, 42); // 在第2个元素之前插入值为42的元素
  5.        output(l);
  6.        delete1(&l);
  7.        output(l);
  8.    }
  9.    
复制代码


3. 删除链表中第i个元素，并输出被删除的元素值和删除后的链表中各元素值。

   这部分已经在上面的代码中实现了，delete1 函数用于删除链表中的元素。

4. 在链表中查找第i个数据元素结点，如果查找成功，则显示“查找成功！”和该元素的值，否则显示“查找失败！”。

   你可以添加一个名为 find 的函数来实现这个功能：

  
  1.    void find(linklist l, int i) {
  2.        linklist p = l->next;
  3.        int j;
  4.        for (j = 1; j < i; j++) {
  5.            if (!p) {
  6.                break;
  7.            }
  8.            p = p->next;
  9.        }
  10.        if (p) {
  11.            printf("查找成功！第%d个元素的值为：%d\
  12. ", i, p->date);
  13.        } else {
  14.            printf("查找失败！\
  15. ");
  16.        }
  17.    }
  18.    
复制代码


   在 main 函数中调用 find 函数：

  
  1.    int main() {
  2.        linklist l;
  3.        initlist(&l);
  4.        insert(&l, 2, 42);
  5.        output(l);
  6.        find(l, 3); // 查找第3个元素
  7.        delete1(&l);
  8.        output(l);
  9.    }
  10.    
复制代码


接下来的问题涉及到有序链表的合并和一元多项式的加法运算，由于篇幅原因，我将在下一个回答中为你解答。
如果问题已经解决，请设置最佳答案
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

isdkz
发表于 2023-10-3 14:52:33 | 显示全部楼层
1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         p->next = l->next;
  17.         l->next = p;
  18.     }
  19. }

  21. void output(linklist l) {
  22.     linklist p = l->next;
  23.     while(p) {
  24.         printf("%d ", p->date);
  25.         p = p->next;
  26.     }
  27.     printf("\n");
  28. }

  30. int main() {
  31.     int n;
  32.     printf("请输入你想建立的长度：\n");
  33.     scanf("%d", &n);
  34.     linklist l;
  35.     initlist(l, n);
  36.     output(l);
  37.     return 0;
  38. }
复制代码


2. 在链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         p->next = l->next;
  17.         l->next = p;
  18.     }
  19. }

  21. void output(linklist l) {
  22.     linklist p = l->next;
  23.     while(p) {
  24.         printf("%d ", p->date);
  25.         p = p->next;
  26.     }
  27.     printf("\n");
  28. }

  30. void insert(linklist &l, elemtype x, int i) {
  31.     linklist p = l;
  32.     for(int j = 0; j < i - 1; j++) {
  33.         p = p->next;
  34.     }
  35.     linklist q = (linklist)malloc(sizeof(lnode));
  36.     q->date = x;
  37.     q->next = p->next;
  38.     p->next = q;
  39. }

  41. int main() {
  42.     int n, i, x;
  43.     printf("请输入你想建立的长度：\n");
  44.     scanf("%d", &n);
  45.     linklist l;
  46.     initlist(l, n);
  47.     output(l);
  48.     printf("请输入你想插入的位置和数值：\n");
  49.     scanf("%d %d", &i, &x);
  50.     insert(l, x, i);
  51.     output(l);
  52.     return 0;
  53. }
复制代码


3. 删除链表中第i个元素，并输出被删除的元素值和删除后的链表中各元素值;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         p->next = l->next;
  17.         l->next = p;
  18.     }
  19. }

  21. void output(linklist l) {
  22.     linklist p = l->next;
  23.     while(p) {
  24.         printf("%d ", p->date);
  25.         p = p->next;
  26.     }
  27.     printf("\n");
  28. }

  30. void delete1(linklist &l, int i) {
  31.     linklist p = l, q;
  32.     for(int j = 0; j < i - 1; j++) {
  33.         p = p->next;
  34.     }
  35.     q = p->next;
  36.     p->next = q->next;
  37.     printf("被删除的元素值为：%d\n", q->date);
  38.     free(q);
  39. }

  41. int main() {
  42.     int n, i;
  43.     printf("请输入你想建立的长度：\n");
  44.     scanf("%d", &n);
  45.     linklist l;
  46.     initlist(l, n);
  47.     output(l);
  48.     printf("请输入你想删除的位置：\n");
  49.     scanf("%d", &i);
  50.     delete1(l, i);
  51.     output(l);
  52.     return 0;
  53. }
复制代码


4. 在链表中查找第i个数据元素结点，如果查找成功，则显示“查找成功！”和该元素的值，否则显示“查找失败！”;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         p->next = l->next;
  17.         l->next = p;
  18.     }
  19. }

  21. void output(linklist l) {
  22.     linklist p = l->next;
  23.     while(p) {
  24.         printf("%d ", p->date);
  25.         p = p->next;
  26.     }
  27.     printf("\n");
  28. }

  30. bool search(linklist l, int i, elemtype &e) {
  31.     linklist p = l;
  32.     for(int j = 0; j < i; j++) {
  33.         p = p->next;
  34.         if(p == NULL) {
  35.             return false;
  36.         }
  37.     }
  38.     e = p->date;
  39.     return true;
  40. }

  42. int main() {
  43.     int n, i;
  44.     elemtype e;
  45.     printf("请输入你想建立的长度：\n");
  46.     scanf("%d", &n);
  47.     linklist l;
  48.     initlist(l, n);
  49.     output(l);
  50.     printf("请输入你想查找的位置：\n");
  51.     scanf("%d", &i);
  52.     if(search(l, i, e)) {
  53.         printf("查找成功！该元素的值为：%d\n", e);
  54.     } else {
  55.         printf("查找失败！\n");
  56.     }
  57.     return 0;
  58. }
复制代码


5. 根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1，并输出有序链表中各元素值;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         linklist q = l;
  17.         while(q->next && q->next->date < p->date) {
  18.             q = q->next;
  19.         }
  20.         p->next = q->next;
  21.         q->next = p;
  22.     }
  23. }

  25. void output(linklist l) {
  26.     linklist p = l->next;
  27.     while(p) {
  28.         printf("%d ", p->date);
  29.         p = p->next;
  30.     }
  31.     printf("\n");
  32. }

  34. int main() {
  35.     int n;
  36.     printf("请输入你想建立的长度：\n");
  37.     scanf("%d", &n);
  38.     linklist l;
  39.     initlist(l, n);
  40.     output(l);
  41.     return 0;
  42. }
复制代码


6. 根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2，并输出有序链表中各元素值;

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         linklist q = l;
  17.         while(q->next && q->next->date < p->date) {
  18.             q = q->next;
  19.         }
  20.         p->next = q->next;
  21.         q->next = p;
  22.     }
  23. }

  25. void output(linklist l) {
  26.     linklist p = l->next;
  27.     while(p) {
  28.         printf("%d ", p->date);
  29.         p = p->next;
  30.     }
  31.     printf("\n");
  32. }

  34. int main() {
  35.     int m;
  36.     printf("请输入你想建立的长度：\n");
  37.     scanf("%d", &m);
  38.     linklist l;
  39.     initlist(l, m);
  40.     output(l);
  41.     return 0;
  42. }
复制代码


7. 将有序链表L1和L2合并到单链表L1中，要求使用原链中的结点，并使L1保持其原有序性，最后输出合并后的有序链表中各结点的元素值。

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

  4. typedef int elemtype;
  5. typedef struct lnode{
  6.     elemtype date;
  7.     struct lnode *next;
  8. }lnode,*linklist;

  10. void initlist(linklist &l, int n) {
  11.     l = (linklist)malloc(sizeof(lnode));
  12.     l->next = NULL;
  13.     for(int i = 0; i < n; i++) {
  14.         linklist p = (linklist)malloc(sizeof(lnode));
  15.         scanf("%d", &(p->date));
  16.         linklist q = l;
  17.         while(q->next && q->next->date < p->date) {
  18.             q = q->next;
  19.         }
  20.         p->next = q->next;
  21.         q->next = p;
  22.     }
  23. }

  25. void merge(linklist &l1, linklist l2) {
  26.     linklist p1 = l1->next, p2 = l2->next, q = l1;
  27.     while(p1 && p2) {
  28.         if(p1->date <= p2->date) {
  29.             q = p1;
  30.             p1 = p1->next;
  31.         } else {
  32.             q->next = p2;
  33.             p2 = p2->next;
  34.             q = q->next;
  35.             q->next = p1;
  36.         }
  37.     }
  38.     if(p2) {
  39.         q->next = p2;
  40.     }
  41.     free(l2);
  42. }

  44. void output(linklist l) {
  45.     linklist p = l->next;
  46.     while(p) {
  47.         printf("%d ", p->date);
  48.         p = p->next;
  49.     }
  50.     printf("\n");
  51. }

  53. int main() {
  54.     int n, m;
  55.     printf("请输入L1的长度：\n");
  56.     scanf("%d", &n);
  57.     linklist l1;
  58.     initlist(l1, n);
  59.     printf("请输入L2的长度：\n");
  60.     scanf("%d", &m);
  61.     linklist l2;
  62.     initlist(l2, m);
  63.     merge(l1, l2);
  64.     output(l1);
  65.     return 0;
  66. }
复制代码


8. 已知两个一元多项式A(x)=a1xe1+ a2xe2+……+ amxem，B(x)= b1xe1+ b2xe2+……+ bmxen，其中ei为整数指数且递增有序。要求编写算法实现两个一元多项式A和B的加法运算A(x)= A(x)+ B(x)，并编写程序测试其正确性。

```c++
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int coef;
    int expn;
    struct node *next;
}node, *linklist;

void initlist(linklist &l, int n) {
    l = (linklist)malloc(sizeof(node));
    l->next = NULL;
    for(int i = 0; i < n; i++) {
        linklist p = (linklist)malloc(sizeof(node));
        scanf("%d %d", &(p->coef), &(p->expn));
        linklist q = l;
        while(q->next && q->next->expn > p->expn) {
            q = q->next;
        }
        if(q->next && q->next->expn == p->expn) {
            q->next->coef += p->coef;
            free(p);
        } else {
            p->next = q->next;
            q->next = p;
        }
    }
}

void output(linklist l) {
    linklist p = l->next;
    while(p) {
        printf("%dx^%d", p->coef, p->expn);
        if(p->next) {
            printf("+");
        }
        p = p->next;
    }
    printf("\n");
}

void add(linklist &A, linklist B) {
    linklist p = A->next, q = B->next, r = A;
    while(p && q) {
        if(p->expn < q->expn) {
            r->next = p;
            r = p;
            p = p->next;
        } else if(p->expn == q->expn) {
            p
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

陶远航
发表于 2023-10-3 14:53:53 | 显示全部楼层
isdkz 发表于 2023-10-3 14:52
1. 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与 ...

没写完
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

Mike_python小
发表于 2023-10-3 14:54:22 | 显示全部楼层
问题1: 根据输入表的长度n和各个数据元素值建立一个带头结点的单链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度n和各个数据元素值，并逐个插入到链表中。
4. 遍历链表，输出链表中各元素值。

以下是修改后的代码实现：
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int elemtype;
  7. typedef struct lnode{
  8.     elemtype date;
  9.     struct lnode *next;
  10. } lnode, *linklist;
  12. void initlist(linklist &l) {
  13.     int n;
  14.     elemtype e;
  15.    
  16.     l = (linklist)malloc(sizeof(lnode));
  17.     l->next = NULL;
  18.    
  19.     printf("请输入你想建立的长度：\n");
  20.     scanf("%d", &n);
  21.    
  22.     printf("请输入数字：\n");
  23.     for (int i = 0; i < n; i++) {
  24.         scanf("%d", &e);
  25.         
  26.         linklist p = (linklist)malloc(sizeof(lnode));
  27.         p->date = e;
  28.         p->next = l->next;
  29.         l->next = p;
  30.     }
  31. }
  33. void output(linklist l) {
  34.     linklist p = l->next;
  35.    
  36.     while (p) {
  37.         printf("%d ", p->date);
  38.         p = p->next;
  39.     }
  40.     printf("\n");
  41. }
  43. int main() {
  44.     linklist l;
  45.    
  46.     initlist(l);
  47.     output(l);
  48.    
  49.     return 0;
  50. }
复制代码

问题2: 在链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度n和各个数据元素值，并逐个插入到链表中。
4. 获取要插入的位置i和值x。
5. 遍历链表，找到第i-1个节点，然后在其后插入一个新的节点，值为x。
6. 遍历链表，输出插入后的链表中各元素值。

以下是修改后的代码实现：
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int elemtype;
  7. typedef struct lnode{
  8.     elemtype date;
  9.     struct lnode *next;
  10. } lnode, *linklist;
  12. void initlist(linklist &l) {
  13.     int n;
  14.     elemtype e;
  15.    
  16.     l = (linklist)malloc(sizeof(lnode));
  17.     l->next = NULL;
  18.    
  19.     printf("请输入你想建立的长度：\n");
  20.     scanf("%d", &n);
  21.    
  22.     printf("请输入数字：\n");
  23.     for (int i = 0; i < n; i++) {
  24.         scanf("%d", &e);
  25.         
  26.         linklist p = (linklist)malloc(sizeof(lnode));
  27.         p->date = e;
  28.         p->next = l->next;
  29.         l->next = p;
  30.     }
  31. }
  33. void output(linklist l) {
  34.     linklist p = l->next;
  35.    
  36.     while (p) {
  37.         printf("%d ", p->date);
  38.         p = p->next;
  39.     }
  40.     printf("\n");
  41. }
  43. void insert(linklist &l, int i, elemtype x) {
  44.     int j = 0;
  45.     linklist p = l;
  46.    
  47.     while (p && j < i - 1) {
  48.         p = p->next;
  49.         j++;
  50.     }
  51.    
  52.     if (!p || j > i - 1) {
  53.         printf("插入位置无效！\n");
  54.         return;
  55.     }
  56.    
  57.     linklist s = (linklist)malloc(sizeof(lnode));
  58.     s->date = x;
  59.     s->next = p->next;
  60.     p->next = s;
  61. }
  63. int main() {
  64.     linklist l;
  65.     int i, x;
  66.    
  67.     initlist(l);
  68.    
  69.     printf("请输入要插入的位置：\n");
  70.     scanf("%d", &i);
  71.    
  72.     printf("请输入要插入的元素值：\n");
  73.     scanf("%d", &x);
  74.    
  75.     insert(l, i, x);
  76.    
  77.     output(l);
  78.    
  79.     return 0;
  80. }
复制代码

问题3: 删除链表中第i个元素，并输出被删除的元素值和删除后的链表中各元素值。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度n和各个数据元素值，并逐个插入到链表中。
4. 获取要删除的位置i。
5. 遍历链表，找到第i-1个节点，并记录下要删除的节点以及其后一个节点。
6. 修改指针，将第i-1个节点指向第i+1个节点，释放要删除的节点内存。
7. 输出被删除的元素值和删除后的链表中各元素值。

以下是修改后的代码实现：
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int elemtype;
  7. typedef struct lnode{
  8.     elemtype date;
  9.     struct lnode *next;
  10. } lnode, *linklist;
  12. void initlist(linklist &l) {
  13.     int n;
  14.     elemtype e;
  15.    
  16.     l = (linklist)malloc(sizeof(lnode));
  17.     l->next = NULL;
  18.    
  19.     printf("请输入你想建立的长度：\n");
  20.     scanf("%d", &n);
  21.    
  22.     printf("请输入数字：\n");
  23.     for (int i = 0; i < n; i++) {
  24.         scanf("%d", &e);
  25.         
  26.         linklist p = (linklist)malloc(sizeof(lnode));
  27.         p->date = e;
  28.         p->next = l->next;
  29.         l->next = p;
  30.     }
  31. }
  33. void output(linklist l) {
  34.     linklist p = l->next;
  35.    
  36.     while (p) {
  37.         printf("%d ", p->date);
  38.         p = p->next;
  39.     }
  40.     printf("\n");
  41. }
  43. void deleteNode(linklist &l, int i) {
  44.     linklist p = l;
  45.     int j = 0;
  46.    
  47.     while (p && j < i - 1) {
  48.         p = p->next;
  49.         j++;
  50.     }
  51.    
  52.     if (!p || j > i - 1 || !p->next) {
  53.         printf("删除位置无效！\n");
  54.         return;
  55.     }
  56.    
  57.     linklist q = p->next;
  58.     p->next = q->next;
  59.     int deletedValue = q->date;
  60.     free(q);
  61.    
  62.     printf("被删除的元素值为：%d\n", deletedValue);
  63. }
  65. int main() {
  66.     linklist l;
  67.     int i;
  68.    
  69.     initlist(l);
  70.    
  71.     printf("请输入要删除的位置：\n");
  72.     scanf("%d", &i);
  73.    
  74.     deleteNode(l, i);
  75.    
  76.     output(l);
  77.    
  78.     return 0;
  79. }
复制代码

问题4: 在链表中查找第i个数据元素结点，如果查找成功，则显示“查找成功！”和该元素的值，否则显示“查找失败！”。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度n和各个数据元素值，并逐个插入到链表中。
4. 获取要查找的位置i。
5. 遍历链表，找到第i个节点，打印其元素值并显示“查找成功！”；如果找不到节点，则显示“查找失败！”。

以下是修改后的代码实现：
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int elemtype;
  7. typedef struct lnode{
  8.     elemtype date;
  9.     struct lnode *next;
  10. } lnode, *linklist;
  12. void initlist(linklist &l) {
  13.     int n;
  14.     elemtype e;
  15.    
  16.     l = (linklist)malloc(sizeof(lnode));
  17.     l->next = NULL;
  18.    
  19.     printf("请输入你想建立的长度：\n");
  20.     scanf("%d", &n);
  21.    
  22.     printf("请输入数字：\n");
  23.     for (int i = 0; i < n; i++) {
  24.         scanf("%d", &e);
  25.         
  26.         linklist p = (linklist)malloc(sizeof(lnode));
  27.         p->date = e;
  28.         p->next = l->next;
  29.         l->next = p;
  30.     }
  31. }
  33. void findNode(linklist l, int i) {
  34.     linklist p = l->next;
  35.     int j = 1;
  36.    
  37.     while (p && j < i) {
  38.         p = p->next;
  39.         j++;
  40.     }
  41.    
  42.     if (!p || j > i) {
  43.         printf("查找失败！\n");
  44.         return;
  45.     }
  46.    
  47.     printf("查找成功！元素值为：%d\n", p->date);
  48. }
  50. int main() {
  51.     linklist l;
  52.     int i;
  53.    
  54.     initlist(l);
  55.    
  56.     printf("请输入要查找的位置：\n");
  57.     scanf("%d", &i);
  58.    
  59.     findNode(l, i);
  60.    
  61.     return 0;
  62. }
复制代码

问题5: 根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1，并输出有序链表中各元素值。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度n和递增的有序数据，并逐个插入到链表L1中。
4. 遍历链表L1，输出有序链表中各元素值。

以下是修改后的代码实现：
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int elemtype;
  7. typedef struct lnode{
  8.     elemtype date;
  9.     struct lnode *next;
  10. } lnode, *linklist;
  12. void initlist(linklist &l) {
  13.     int n;
  14.     elemtype e;
  15.    
  16.     l = (linklist)malloc(sizeof(lnode));
  17.     l->next = NULL;
  18.    
  19.     printf("请输入你想建立的长度：\n");
  20.     scanf("%d", &n);
  21.    
  22.     printf("请输入有序数据：\n");
  23.     for (int i = 0; i < n; i++) {
  24.         scanf("%d", &e);
  25.         
  26.         linklist p = (linklist)malloc(sizeof(lnode));
  27.         p->date = e;
  28.         
  29.         linklist pre = l;
  30.         linklist q = l->next;
  31.         
  32.         while (q && q->date < e) {
  33.             pre = q;
  34.             q = q->next;
  35.         }
  36.         
  37.         p->next = q;
  38.         pre->next = p;
  39.     }
  40. }
  42. void output(linklist l) {
  43.     linklist p = l->next;
  44.    
  45.     while (p) {
  46.         printf("%d ", p->date);
  47.         p = p->next;
  48.     }
  49.     printf("\n");
  50. }
  52. int main() {
  53.     linklist l;
  54.    
  55.     initlist(l);
  56.     output(l);
  57.    
  58.     return 0;
  59. }
复制代码

问题6: 根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2，并输出有序链表中各元素值。

为了实现这个问题，可以按照以下步骤进行：

1. 定义一个带头节点的单链表结构体lnode，其中包括数据元素值date和指向下一个节点的指针next。
2. 创建一个头结点并初始化链表为空。
3. 获取输入的长度m和递增的有序数据，并逐个插入到链表L2中。
4. 遍历

球一个最佳答案谢谢啦！这对我非常重要！
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

乔治爱啃脚趾
 楼主| 发表于 2023-10-3 15:50:14 | 显示全部楼层
陶远航 发表于 2023-10-3 14:52
你的问题包含了多个子问题，我将按照顺序为你解答。首先，我会对你提供的代码进行分析和修改，然后针对你的 ...

后续出了吗
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

陶远航
发表于 2023-10-3 15:55:47 | 显示全部楼层
乔治爱啃脚趾 发表于 2023-10-3 15:50
后续出了吗

抱歉，我之前的回答没有包含后续问题的解答。现在我将继续回答你的问题。

5. 根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1，并输出有序链表中各元素值;

6. 根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2，并输出有序链表中各元素值;

你可以使用以下函数创建有序链表：

  1. void create_ordered_list(linklist *l, int n) {
  2.     *l = (linklist)malloc(sizeof(lnode));
  3.     (*l)->next = NULL;
  4.     linklist tail = *l;
  5.     elemtype e;
  6.     for (int i = 0; i < n; i++) {
  7.         scanf("%d", &e);
  8.         linklist p = (linklist)malloc(sizeof(lnode));
  9.         p->date = e;
  10.         p->next = NULL;
  11.         tail->next = p;
  12.         tail = p;
  13.     }
  14. }
复制代码


在main函数中创建两个有序链表L1和L2：

  1. int main() {
  2.     linklist L1, L2;
  3.     int n, m;
  4.     printf("请输入L1的长度：\n");
  5.     scanf("%d", &n);
  6.     printf("请输入L1的有序数据：\n");
  7.     create_ordered_list(&L1, n);
  8.     output(L1);

  10.     printf("请输入L2的长度：\n");
  11.     scanf("%d", &m);
  12.     printf("请输入L2的有序数据：\n");
  13.     create_ordered_list(&L2, m);
  14.     output(L2);
  15. }
复制代码


7. 将有序链表L1和L2合并到单链表L1中，要求使用原链中的结点，并使L1保持其原有序性，最后输出合并后的有序链表中各结点的元素值。

你可以使用以下函数合并两个有序链表：

  1. void merge_ordered_lists(linklist *L1, linklist L2) {
  2.     linklist p1 = *L1, p2 = L2->next, temp;
  3.     while (p1->next && p2) {
  4.         if (p1->next->date > p2->date) {
  5.             temp = p2->next;
  6.             p2->next = p1->next;
  7.             p1->next = p2;
  8.             p2 = temp;
  9.         } else {
  10.             p1 = p1->next;
  11.         }
  12.     }
  13.     if (p2) {
  14.         p1->next = p2;
  15.     }
  16.     free(L2);
  17. }
复制代码

在main函数中合并L1和L2：

  1. int main() {
  2.     linklist L1, L2;
  3.     int n, m;
  4.     printf("请输入L1的长度：\n");
  5.     scanf("%d", &n);
  6.     printf("请输入L1的有序数据：\n");
  7.     create_ordered_list(&L1, n);
  8.     output(L1);

  10.     printf("请输入L2的长度：\n");
  11.     scanf("%d", &m);
  12.     printf("请输入L2的有序数据：\n");
  13.     create_ordered_list(&L2, m);
  14.     output(L2);

  16.     merge_ordered_lists(&L1, L2);
  17.     printf("合并后的链表：\n");
  18.     output(L1);
  19. }
复制代码

8. 已知两个一元多项式A(x)=a1xe1+ a2xe2+……+ amxem，B(x)= b1xe1+ b2xe2+……+ bmxen，其中ei为整数指数且递增有序。要求编写算法实现两个一元多项式A和B的加法运算A(x)= A(x)+ B(x)，并编写程序测试其正确性。

你可以使用以下结构体表示一元多项式的项：

  1. typedef struct term {
  2.     int coef;
  3.     int exp;
  4.     struct term *next;
  5. } term, *polynomial;
复制代码


然后，你可以创建一个函数来创建一元多项式：

  1. void create_polynomial(polynomial *p, int n) {
  2.     *p = (polynomial)malloc(sizeof(term));
  3.     (*p)->next = NULL;
  4.     term *tail = *p;
  5.     int coef, exp;
  6.     for (int i = 0; i < n; i++) {
  7.         scanf("%d%d", &coef, &exp);
  8.         term *new_term = (term *)malloc(sizeof(term));
  9.         new_term->coef = coef;
  10.         new_term->exp = exp;
  11.         new_term->next = NULL;
  12.         tail->next = new_term;
  13.         tail = new_term;
  14.     }
  15. }
复制代码


接下来，创建一个函数来实现一元多项式的加法运算：

  1. void add_polynomials(polynomial *A, polynomial B) {
  2.     term *p1 = *A, *p2 = B->next, *temp;
  3.     while (p1->next && p2) {
  4.         if (p1->next->exp > p2->exp) {
  5.             temp = p2->next;
  6.             p2->next = p1->next;
  7.             p1->next = p2;
  8.             p2 = temp;
  9.             p1 = p1->next;
  10.         } else if (p1->next->exp == p2->exp) {
  11.             p1->next->coef += p2->coef;
  12.             if (p1->next->coef == 0) {
  13.                 temp = p1->next;
  14.                 p1->next = temp->next;
  15.                 free(temp);
  16.             } else {
  17.                 p1 = p1->next;
  18.             }
  19.             temp = p2;
  20.             p2 = p2->next;
  21.             free(temp);
  22.         } else {
  23.             p1 = p1->next;
  24.         }
  25.     }
  26.     if (p2) {
  27.         p1->next = p2;
  28.     }
  29.     free(B);
  30. }
复制代码


最后，在main函数中创建两个一元多项式A和B，并执行加法运算：

  1. int main() {
  2.     polynomial A, B;
  3.     int n, m;
  4.     printf("请输入A的项数：\n");
  5.     scanf("%d", &n);
  6.     printf("请输入A的项：\n");
  7.     create_polynomial(&A, n);

  9.     printf("请输入B的项数：\n");
  10.     scanf("%d", &m);
  11.     printf("请输入B的项：\n");
  12.     create_polynomial(&B, m);

  14.     add_polynomials(&A, B);
  15.     printf("A(x) + B(x) = ");
  16.     output_polynomial(A);
  17. }
复制代码

注意：你需要创建一个名为output_polynomial的函数来输出一元多项式。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

乔治爱啃脚趾
 楼主| 发表于 2023-10-3 16:00:55 | 显示全部楼层
陶远航 发表于 2023-10-3 15:55
抱歉，我之前的回答没有包含后续问题的解答。现在我将继续回答你的问题。

5. 根据输入的n和n个递增的 ...

好的好的，谢谢你
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

乔治爱啃脚趾
 楼主| 发表于 2023-10-3 21:20:09 | 显示全部楼层
陶远航 发表于 2023-10-3 15:55
抱歉，我之前的回答没有包含后续问题的解答。现在我将继续回答你的问题。

5. 根据输入的n和n个递增的 ...

你好，我想问问为什么在创建链表的时候最后要有一个tail=p，这行有什么含义吗
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-5-9 21:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表