데이터 구조 재 미 있 는 문제 - 원 표 공간 에서 링크 의 병합 을 진행 합 니 다.

   1: #include <stdio.h>

   2: #include <stdlib.h>

   3:  

   4: /*  int ElemType  */

   5: typedef int ElemType;

   6:  

   7: /*         */

   8: typedef struct node {

   9:     ElemType data;   /*   */

  10:     struct node *next;  /*   */

  11: } LNode, *LinkList;

  12:  

  13: /*       n   ，     */

  14: LinkList GreatLinkList(int n) {

  15:     LinkList p, r, list = NULL;

  16:     ElemType e;

  17:     int i;

  18:  

  19:     for(i = 1; i <= n; i++) {

  20:         scanf("%d", &e);

  21:         p = (LinkList)malloc(sizeof(LNode));

  22:         p->data = e;

  23:         p->next = NULL;

  24:  

  25:         if(!list)

  26:             list = p;

  27:         else

  28:             r->next = p;

  29:  

  30:         r = p;

  31:     }

  32:  

  33:     return list;

  34: }

  35:  

  36: /*        ，              e*/

  37: void insertList(LinkList *list, LinkList q, ElemType e) {

  38:     LinkList p;

  39:     p = ( LinkList)malloc(sizeof(LNode));

  40:     p->data = e;

  41:  

  42:     if(!*list) {

  43:         *list = p;

  44:         p->next = NULL;

  45:     }

  46:     else {

  47:         p->next = q->next;

  48:         q->next = p;

  49:     }

  50: }

  51:  

  52: void insertNode(LinkList *q1, LinkList *q2, LinkList *p, LinkList *l2) {

  53:     if(*q1 == *q2)

  54:     {

  55:         (*p)->next = *q2;

  56:         *l2 = *q2 = *q1 = *p;

  57:  

  58:     }

  59:     else

  60:     {

  61:         (*q2)->next = *p;

  62:         (*p)->next = *q1;

  63:         (*q2) = (*q2)->next;

  64:     }

  65: }

  66:  

  67: void MergeLink(LinkList l1, LinkList l2 , LinkList *l3)

  68: {

  69:     /*   l1,l2    ，l3         */

  70:     LinkList p, q1, q2;

  71:     q1 = q2  = l2; /*l3  l2*/

  72:     p = l1;

  73:  

  74:     while(p != NULL && q1 != NULL) {

  75:         if(p->data >= q1->data) {

  76:             q2 = q1;

  77:             q1 = q1->next;

  78:         }

  79:         else {

  80:             l1 = l1->next ;

  81:             insertNode(&q1, &q2, &p, &l2);  /* p       q2  q1  */

  82:             // q2 = q2->next;

  83:             p = l1;

  84:         }

  85:     }

  86:  

  87:     if(q1 == NULL) q2->next = p;

  88:  

  89:     *l3 = l2;

  90:  

  91:  

  92: }

  93:  

  94: int main()

  95: {

  96:     ElemType e;

  97:     LinkList  l1, l2, l3, q;

  98:  

  99:     printf("Please input the contents of Link1
");

 100:     q = l1 = GreatLinkList(1); /*        ，q l     */

 101:  

 102:     scanf("%d", &e);

 103:  

 104:     while(e)             /*       ，          */

 105:     {

 106:         insertList(&l1, q, e) ;

 107:         q = q->next;

 108:         scanf("%d", &e);

 109:     }

 110:  

 111:     printf("Please input the contents of Link2
");

 112:     q = l2 = GreatLinkList(1); /*        ，q l     */

 113:  

 114:     scanf("%d", &e);

 115:  

 116:     while(e)             /*       ，          */

 117:     {

 118:         insertList(&l2, q, e) ;

 119:         q = q->next;

 120:         scanf("%d", &e);

 121:     }

 122:  

 123:     MergeLink(l1, l2, &l3); /*  l2,l2  l3        */

 124:  

 125:     q = l3;

 126:  

 127:     printf("The merge of link1 and link 2 is
");

 128:  

 129:     while(q)            /*         */

 130:     {

 131:         printf("%d ", q->data) ;

 132:         q = q->next;

 133:     }

 134: }