线性表——顺序存储结构实现字符串类型（四）实现顺序表的合并

目录

• • • • merge合并
      • main
      • 其他部分代码
      • • 思考

merge合并

/*
**m是一个空表，将表a，表b，都赋给表m
* 按照从小到大的顺序
*/
void merge(string* m,string* a,string* b){
    (*m).length=(*a).length+(*b).length;            //更新m表长
    (*m).size=(*a).size+(*b).size;                  //更新m表size
    (*m).data=(elemType*)malloc(sizeof(elemType)*(*m).size);//给m足够的开辟空间
    elemType *pa=&((*a).data[0]);
    elemType *pb=&((*b).data[0]);              //分别获取表a和表b的表头指针
    elemType *pa_last=&((*a).data[(*a).length-1]);
    elemType *pb_last=&((*b).data[(*b).length-1]); //分别获取表a表b的表尾指针
    elemType *pc = & ((*m).data[0]);
    if(!((*m).data)){
        printf("ERROR in function merge()");
        exit(0);
    }
    while(pa<=pa_last&&pb<=pb_last){
        if(*pa<=*pb) *(pc++)=*(pa++);
        else
            *(pc++)=*(pb++);
    }
    while(pa<=pa_last){
        *(pc++)=*(pa++);//插入剩余元素
    }
    while(pb<pb_last){
        *(pc++)=*(pb++);//插入剩余元素
    }


}
           

main

int main(){
 string s1=newString(4);
    add(&s,'1');
    add(&s,'2');
    add(&s,'3');
    add(&s1,'4');
    add(&s1,'5');
    add(&s1,'6');
    string s3;
    merge(&s3,&s1,&s);
    printf("合并结果：%s\n",s3.data);
    printf("合并长度：%d\n",s3.length);
    }
           

其他部分代码

//add
void add(string* s,elemType e){
    //空间不够，则重新分配空间
    if(s->length>=s->size){
        elemType* newbase=(elemType*)realloc((*s).data,sizeof(elemType)*(s->size+extension));
        if(newbase==NULL){
            printf("OVErFlow in function add()");
        }
        s->data=newbase;
        s->size+=extension; 
    }
    // 将元素e添加到表尾
    (*s).data[s->length]=e;
    printf("添加的字符：%c\n",s->data[s->length++]);
}
           

#include<stdio.h>
#include<stdlib.h>
#define elemType char
#define extension 10
/*
** 定义一个实现顺序存储结构的字符串类型的线性表
*/
typedef struct string{
    elemType * data;//
    int size;
    int length;
}string;
//初始化string
string newString(int size){
    string s;
    s.data=(elemType*)malloc(sizeof(elemType)*size);
    if(s.data!=NULL){
        s.size=size;
        s.length=0;
        return s;
    }
    exit(0);
}
           

使用时先复制方法，最后复制main。

思考

刚开始觉得无从下手，看了看书上代码，觉得也挺简单的。

首先是将空表更新长度、size，并为她开辟存储空间，使得它能够存储数据。

接着，获取要被复制的表a、表b的表首、表尾指针（第一个元素），表m只需要获取表首指针。

这样做的目的是可以让首指针自增并与尾指针比较得到是否到达表尾的信息。

通过比较大小来将元素添加到表m的步骤我觉得可有可无，原因是我的顺序表不一定存储的是数字或字符。

如果没有顺序的要求，直接通过两个while循环，将元素添加到表m。应该是这样的结果：

/*
**m是一个空表，将表a，表b，都赋给表m
* 按照从小到大的顺序
*/
void merge(string* m,string* a,string* b){
    (*m).length=(*a).length+(*b).length;            //更新m表长
    (*m).size=(*a).size+(*b).size;                  //更新m表size
    (*m).data=(elemType*)malloc(sizeof(elemType)*(*m).size);//给m足够的开辟空间
    elemType *pa=&((*a).data[0]);
    elemType *pb=&((*b).data[0]);              //分别获取表a和表b的表头指针
    elemType *pa_last=&((*a).data[(*a).length-1]);
    elemType *pb_last=&((*b).data[(*b).length-1]); //分别获取表a表b的表尾指针
    elemType *pc = & ((*m).data[0]);
    if(!((*m).data)){
        printf("ERROR in function merge()");
        exit(0);
    }
  //  while(pa<=pa_last&&pb<=pb_last){
    //    if(*pa<=*pb) *(pc++)=*(pa++);
      //  else
        //    *(pc++)=*(pb++);
    //}
    while(pa<=pa_last){
        *(pc++)=*(pa++);//插入剩余元素
    }
    while(pb<pb_last){
        *(pc++)=*(pb++);//插入剩余元素
    }


}