[数据结构]线性表合并
- 格式：pdf
- 大小：152.51 KB
- 文档页数：7
[数据结构]线性表合并
⼀、问题描述
线性表合并是程序设计语⾔编译中的⼀个最基本的问题，现在有两个线性表LA和LB，其中的元素都是按照⾮递减有序排列的，要将两个LA
和LB归并为⼀个新的线性表LC，使得LC中的元素仍然是⾮递减有序的。
本实验的合并⽅式有两种。第⼀种是分别取LA和LB的第⼀个元素，即各⾃的最⼩的元素进⾏⽐较，选择较⼩的元素加⼊LC尾部，然后重复
以上步骤；当LA表空了或者LB表空了的时候，将另⼀个表剩下的元素按照顺序加⼊LC的尾部，从⽽保证LC中元素有序。第⼆种⽅式是以
LA为母表，将LB中的元素向LA中插⼊，直到LB表空，得到的新的LA表就是最终需要的LC表。
本实验采⽤线性表实现，采⽤了链式表⽰和顺序表⽰两种实现⽅式。根据各⾃的特点，链式表⽰对应了第⼆种合并⽅式，⽽顺序表⽰对应了
第⼀种合并⽅式。
⼆、数据结构——线性表
1、链式表⽰：
链式表⽰的特点是⽤⼀组任意的存储单元存储线性表的数据元素，每个元素包括两个域——数据域和指针域。其中数据域是存储数据信息的
域，本实验中默认所处理的数据元素都是在整型（int）范围内的数据；指针域中存储⼀个指针，指向当前元素的下⼀个元素的地址。n个结
点按照如上关系连接起来，形成⼀个链表，就是线性表的链式表⽰。
由于链式表⽰对于数据的插⼊、删除操作⽐较⽅便，⽽查找⼀个元素的效率⽐较低下，于是选择⽤第⼆种合并⽅式，即以LA为母表，将LB
中的元素⼀个⼀个插⼊LA中。
⾸先，每个结点的是⼀个node型的变量，包含⼀个int型变量Num和⼀个node*型的指针变量next。正如上⽂所描述，Num保存该结点的数
值，next保存逻辑上下⼀个结点的地址。然后定义了⼀个名叫MyList的类，其中有private型的变量包含线性表⾃⾝的基本变量，⽐如元素个
数、⾸地址等等；还包括public型的线性表的基本操作函数，⽐如初始化（InitList）、清除（ClearList）、打印(PrintList)等等。
2、顺序表⽰：
顺序表⽰是指的⽤⼀段地址连续的区域存储⼀个线性表，⽤物理存储位置的连续表⽰线性表的顺序关系。这就要求元素之间维持严格的物理
位置关系，在访问变得简单的同时，对线性表的修改操作给线性表的维护带来了很⼤的⿇烦。
由于顺序表⽰对于数据的操作⽐较⽅便，⽽对线性表的数据进⾏操作⽐较⿇烦且效率低下，故选择第⼀种合并⽅式，即将LA和LB合并到⼀
个新的线性表LC中。
⾸先，申请⼀段连续的空间，当空间不够时申请⼀个更⼤的空间，再把之前的数据搬过去。基本功能与链式表⽰基本相同，实现上略有差
别。
三、算法的设计和实现
1、第⼀种合并⽅式
（1）建⽴线性表LA和LB，并读⼊数据。
（2）建⽴空线性表LC。
（3）分别选取LA中未读过的最⼩的元素和LB中未读过的最⼩的元素，进⾏⽐较，将较⼩的元素加⼊新的线性表LC中，较⼤元素视作未读
过的元素。
（4）重复步骤（2）直到LA或者LB的元素都被读过了。若LA中的元素都被度过了，则将LB中剩下未读的元素按顺序依次添加到LC的尾
部；否则，将LA中的剩下未读的元素按顺序依次添加到LC的尾部。
（5）得到的LC就是最终结果。
2、第⼆种合并⽅式
（1）建⽴线性表LA和LB，并读⼊数据。
（2）⽤aIndex标记LA中读到元素的位置，将其位置的元素与LB中第⼀个元素进⾏⽐较。
（3）若LA中当前元素较⼩，则aIndex向后移，重复（2）直到LB为空或者LA到末端；否则将LB中的第⼀个元素插⼊LA的当前位
置，aIndex向后移，删除LB中的第⼀个元素，重复（2）直到LB为空或者LA到末端。
（4）若LB为空，则LA已经是最终结果；否则，将LB剩下的元素按顺序依次加⼊LA的末端，得到最终结果。
四、预期结果和实验中的问题
1、预期结果是程序可以正确地合成两个线性表LA和LB，如LA={1,1,2}，LB={1,2,2,3}，则得到的结果应该是{1,1,1,2,2,2,3}。2、实际运⾏中曾遇到的问题：
（1）使⽤顺序结构表⽰线性表的时候，可能会出现初始申请的空间不够的情况，需要额外申请⼀个更⼤的空间，把之前的元素全部复制过
去，然后把之前的空间释放掉。
（2）由于链式表⽰和顺序表⽰各有特点，在MyList类中的函数有些细节不⼀样，⽐如有两个函数，分别是PriorElem(e,&Pre_e)：若e是L中
的元素，则返回e的前躯，以及NextElem(e,&Next_e)：若e是L中的元素，则返回e的后继。由于顺序表⽰的访问上的便利，我多写了⼀个函
数ElemPos(e,&Pos)：若e是L中的元素，则返回e的位置。借助这个函数，之前两个函数的实现简单了许多。⽽这对于链式表⽰是没有太⼤
的必要的。
（3）我第⼀次写顺序表⽰的链表时，我的合并函数是每合并⼀个元素，则将其从原表中删去。⽽顺序表⽰在删除数据上的笨拙之处⽴刻显
现出来，时间复杂度变到了O(n^2)，这是⾮常不明智的。修改之后的实现时间复杂度为O(n)。下⾯是修改前的合并函数：
1 void MergeList(MyList La, MyList Lb, MyList &Lc)
2 {
3 int aElem, bElem, cLen = 0;
4 Lc.InitList();
5 while((!La.ListEmpty()) && (!Lb.ListEmpty()))
6 {
7 La.GetElem(1, aElem);
8 Lb.GetElem(1, bElem);
9 if(aElem <= bElem)
10 {
11 Lc.ListInsert(++cLen, aElem);
12 La.ListDelete(1, aElem);
13 }
14 else
15 {
16 Lc.ListInsert(++cLen, bElem);
17 Lb.ListDelete(1, bElem);
18 }
19 }
20 while(!La.ListEmpty())
21 {
22 La.ListDelete(1, aElem);
23 Lc.ListInsert(++cLen, aElem);
24 }
25 while(!Lb.ListEmpty())
26 {
27 Lb.ListDelete(1, bElem);
28 Lc.ListInsert(++cLen, bElem);
29 }
30 }
附：c++源代码：
1、第⼀种合并⽅式，顺序表⽰
1 #include
2 #include
3 #include
4
5 using namespace std;
6
7 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
8 #define LISTINCREMENT 10 //线性表存储空间的分配增量
9
10 class MyList
11 {
12 private:
13 int *Elem; //存储空间基址
14 int Len; //当前元素个数
15 int ListSize; //当前分配的储存容量
16
17 public:
18 void InitList() //构造⼀个空的线性表
19 {
20 Elem = new int(LIST_INIT_SIZE);
21 Len = 0;
22 ListSize = LIST_INIT_SIZE;
23 }
24 void ClearList() //重置为空表
25 {
26 delete Elem;
27 Len = 0;
28 }
29 bool ListEmpty() //判断L是否为空表
30 {
31 return Len == 0; 32 }
33 int ListLength() //返回L中数据元素个数
34 {
35 return Len;
36 }
37 bool GetElem(int Pos, int &RetElem) //返回第Pos个元素，出错返回true
38 {
39 if(Pos < 1 || Pos > Len)
40 {
41 printf("Wrong position!\n");
42 return true;
43 }
44 RetElem = Elem[Pos - 1];
45 return false;
46 }
47 //LocateElem(L, e, compare()) //返回L中第⼀个与e满⾜关系compare()的元素的位序，不存在返回0
48 bool ElemPos(int El, int &Pos) //若El是L中的元素，返回e的位置，失败时返回true
49 {
50 int i;
51 for(i = 0; i < Len; i++)
52 if(El == Elem[i])
53 break;
54 if(i < Len)
55 {
56 Pos = i + 1;
57 return false;
58 }
59 printf("Cannot find the element!\n");
60 return true;
61 }
62 bool PriorElem(int El, int &Pre_e) //若El是L中的元素，返回e的前躯，失败时返回true
63 {
64 int Pos;
65 bool flag = ElemPos(El, Pos);
66 if(flag)
67 {
68 printf("Cannot find the element!\n");
69 return true;
70 }
71 else
72 {
73 if(Pos == 1)
74 {
75 printf("Cannot find the precursor!\n");
76 return true;
77 }
78 else
79 Pre_e = Elem[Pos - 2];
80 }
81 return false;
82 }
83 bool NextElem(int El, int &Next_e) //若El是L中的元素，返回e的后继，错误时返回true
84 {
85 int Pos;
86 bool flag = ElemPos(El, Pos);
87 if(flag)
88 {
89 printf("Cannot find the element!\n");
90 return true;
91 }
92 else
93 {
94 if(Pos == Len)
95 {
96 printf("Cannot find the successor!\n");
97 return true;
98 }
99 Next_e = Elem[Pos];
100 }
101 return false;
102 }
103 bool ListInsert(int Pos, int El) //在Pos位置插⼊元素El，失败时返回true
104 {
105 if(Pos < 1 || Pos > Len + 1)
106 {
107 printf("Wrong position!\n");
108 return true;
109 }
110 if(Len + 1 > ListSize) //当前存储空间不够，需要增加分配
