首页 > > 程序设计 > C/C++ >

数据结构第一篇——线性表的逻辑结构

2018-06-17 21:58:27来源：未知阅读 ()

?注：未经博主同意，不得转载。

线性表（linear list）是最常用且最简单的数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。例如，26个英文字母的字母表：

（A,B,C,D,......Z）

线性表的抽象数据类型定义如下：

 1 ADT List
 2 {
 3     Data: D={Ai|Ai<DataSet,i=1,2,...,n, n>=0}
 4     //称n为线性表的表长
 5     //称n=0时的线性表为空表
 6     Structure: R={<A(i-1),Ai>|A(i-1),Ai∈D,i=1,2,...,0}
 7     //设线性表为（A1,A2,...,Ai,...,An）
 8     //称i为Ai在线性表中的位序
 9     
10     Operation:
11     {
12         List();                            //构造一个空的线性表 
13         Length();                        //求线性表的长度 
14         Locate(Data x);                //查找值为x的元素 
15         Insert(Data x ,int i);        //在i的位置上插入元素x 
16         Delete(int i);                    //删除第i个元素 
17         Next (Data x);                    //求值为x的前驱元素 
18         Prior(Data x);                    //求值为x的后继元素 
19         IsEmpty();                        //判断线性表是否为空 
20         IsFull();                        //判断线性表是否为满 
21         GetElem(int i);                //查找第i个元素 
22         Print();                            //输出所有元素 
23     } 
24 }

对上述定义了抽象数据类型的线性表，还可进行一些更复杂的操作，比如：
1.将两个或两个以上的线性表合并成一个线性表：

 1 void Union(List LA, List LB)
 2 {
 3     int i=0;
 4     while(i<LB.size)
 5     {
 6         x=LB.GetElem(i);   //在LB中取一元素 
 7         k=LA.Locate(x);        //在LA中搜索它 
 8         if(k==-1)                //未找到，将它插入到LA中 
 9         {
10             LA.Insert(x,i);
11         }
12         else ++i;
13     }
14 }
15 //此算法时间复杂度为O（LA.size*LB.size）

2.已知线性表LA和LB中的元素按值递增有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素值仍递增排列。例如，设
LA=（2,3,5,8,11,15）

LB=（4,5,6,9,15,20,24）

则

LC=（2,3,4,5,5,6,8,9,11,15,15,20,24）

 1 void MergeList()
 2 {
 3     int i=j=1;        //跟随LA和LB 
 4     int k=1;            //跟随LC 
 5     while((i<LA.size)&&(j<LB.size))    //LA和LB长度范围内    
 6     {
 7         x=LA.GetElem(i);        //获取LA中元素 
 8         y=LB.GetElem(j);        //获取LB中元素 
 9         if(x<=y)
10         {
11             LC.Insert(x,k);
12             ++i;
13             ++k;
14         }
15         else
16         {
17             LC.Insert(y.k);
18             ++j;
19             ++k;
20         }
21     }
22     while(i<LA.size)        //LB已经添加完毕 
23     {
24         x=LA.GetElem(i);
25         LC.Insert(x,k);
26         ++i;
27         ++k; 
28     }
29     while(j<LB.size)        //LB已经添加完毕 
30     {
31         y=LB.GetElem(j);
32         LC.Insert(y,k);
33         ++j;
34         ++k; 
35     }    
36 }
37 //算法复杂度为O（Length（LA）+Length（LB））