数据结构复习--线性表归并算法（c语言实现）

PROC union(VAR LA:Linear_list; LB:Linear_list);
{将所有在线性表LB中存在而线性表LA中不存在的数据元素插入到线性表LA中去}
 n := LENGTH(LA); {确定线性表LA的长度}
 FOR i:=1 TO LENGTH(LB) DO
 [
  x:=GET(LB,i);{取得LB中第i个数据元素}
  k:=LOCATE(LA,x);{在LA中进行搜索}
  IF k=0 THEN
  [
   INSERT(LA,n+1,x);
   n:=n+1;
  ]
  {将LA中不存在的元素插入到LA中，同时修改n的值}
 ]
ENDP;{union}

 

C语言实现--顺序存储结构

 

#include <iostream>
using namespace std;

struct sqlist//顺序存储结构
{
    int elem[10];
    int last;
};
void Union (struct sqlist *LA, struct sqlist *LB);
int Locate (struct sqlist *temp, int x);

/********************************************/
//    name:        main                     //
//    parameter:    none                    //
//    return :    none                      //
//    details:                              //
/********************************************/
void main()
{
    sqlist LA,LB;

    //init LA
    LA.elem[0] = 1;
    LA.elem[1] = 2;
    LA.elem[2] = 3;
    LA.last = 3;


    //init LB
    LB.elem[0] = 2;
    LB.elem[1] = 3;
    LB.elem[2] = 4;
    LB.last = 3;
    
    Union(&LA, &LB);//归并
}

/********************************************/
//    name:       Union                     //
//    parameter:  sqlist LA, sqlist LB      //
//    return :    none                      //
//    details:    归并两个线性表LA,LB         //
/********************************************/

void Union (struct sqlist *LA, struct sqlist *LB)
{
    int i;
    int x;
    int k;

    for (i=0; i<(*LB).last; i++)
    {
        x = (*LB).elem[i];
        k = Locate(LA, x);


        if (k==-1)
        {
            (*LA).elem[(*LA).last] = x;
            (*LA).last++;
        }
    }
}

/********************************************/
//    name:       Locate                    //
//    parameter:  sqlist *temp (struct),    //
//                int x (need to find)      //
//    return :    i                         //
//    details:   查找线性表temp中是否有x,如   //
//               存在则返回序号，否则返回-1   //
/*******************************************/
int Locate (struct sqlist *temp, int x)
{
    int i = 0;
    for (i=0; i<(*temp).last; i++)
    {
        if ((*temp).elem[i] == x)
            return i;
    }
    return -1;
}

 

PROC merge_linklist(la，lb：linkisttp；VAR lc：linkisttp)；
｛la和lb为参与归并的两个有序表，lc为结果有序表｝
    pa：=la↑．next；pb：=lb↑．next；lc：=la；pc：=lc；
    WHILE (pa<>NIL AND pb<>NIL) DO 
        IF pa↑．data<=pb↑．data
            THEN [ pc↑．next：=pa；pc：=pa；pa：=pa↑．next]
            ELSE  [ pc↑．next：=pb；pc：=pb；pb：=pb↑．next]；
    IF (pa<>NIL)
        THEN pc↑．next：=pa
        ELSE  pc↑．next：=pb；
    dispose(lb)
ENDP；{merge_linklist}

 

#include <iostream>
using namespace std;

struct linklist
{
    int data;
    struct linklist *next;
};

void create(int elements[], int num, struct linklist*);
void Union(struct linklist* la, struct linklist* lb, struct linklist*);
void Free(struct linklist* l);

/********************************************/
// name: main                               //
// parameter: none                          //
// return : none                            //
// details:                                 //
/********************************************/

void main()
{
    //初始化链表时用到的数组
    int elements_1[10] = {1,2,3,4,5,6,7,8,9,10};
    int elements_2[5] = {9,10,11,12,13};
    //两个链表la,lb和归并结果链表lc
    struct linklist *la = (struct linklist*)malloc(sizeof(linklist));
    struct linklist *lb = (struct linklist*)malloc(sizeof(linklist));
    struct linklist *lc = (struct linklist*)malloc(sizeof(linklist));
    //创建链表
    create (elements_1, 10, la);
    create (elements_2, 5, lb);
    //归并
    Union(la, lb, lc);
    Free(lc);
    free(la);
    free(lb);
    elements_1[1]=2;
}
/********************************************/
// name: Free                               //
// parameter: *linklist                     //
// return : none                            //
// details: 归并                            //
/********************************************/

void Free(struct linklist* l)
{
    struct linklist* p;
    struct linklist* q;
    p = (*l).next;

    while (p!=NULL)
    {
        q = p;
        p = (*p).next;
        free(q);
    }
    free(l);
}

/********************************************/
// name: Union                              //
// parameter: linklist,linklist             //
//                ,*linklist                //
// return : none                            //
// details: 归并                            //
/********************************************/

void Union(struct linklist *la, struct linklist *lb, struct linklist* lc)
{
    //建立移动指针
    struct linklist *pa;
    struct linklist *pb;
    struct linklist *pc;
    pa = (*la).next;
    pb = (*lb).next;
    pc = lc;


    while(pa!=NULL && pb!=NULL)
    {
        if ((*pa).data <= (*pb).data)
        {
            (*pc).next = pa;
            pc = pa;
            pa = (*pa).next;
        }
        else
        {
            (*pc).next = pb;
            pc = pb;
            pb = (*pb).next;
        }
    }
    if (pa!=NULL)
        (*pc).next = pa;
    else
        (*pc).next = pb;
}

/********************************************/
// name: create                             //
// parameter: array,max,*linklist           //
// return : none                            //
// details: 将给定的数组制成链表              //
/********************************************/

void create(int elements[], int num, struct linklist* l)
{
    struct linklist* p;
    int i = 0;
    //先建立一个空表

    (*l).next = NULL;
    for (i=num-1; i>=0; i--)
    {
        p = (struct linklist*)malloc (sizeof(linklist));
        (*p).data = elements[i];
        //前插式创建

        (*p).next = (*l).next;
        (*l).next = p;
    }
}