[已解决]数据结构求助

isdkz

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
20. 
    
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. }
    
29. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
20. 
    
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. }
    
29. 
    
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. }
    
40. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
20. 
    
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. }
    
29. 
    
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. }
    
40. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
20. 
    
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. }
    
29. 
    
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. }
    
41. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
24. 
    
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. }
    
33. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
24. 
    
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. }
    
33. 
    
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>
   
3. 
   
4. typedef int elemtype;
   
5. typedef struct lnode{
   
6.     elemtype date;
   
7.     struct lnode *next;
   
8. }lnode,*linklist;
   
9. 
   
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. }
    
24. 
    
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. }
    
43. 
    
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. }
    
52. 
    
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