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

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

新老客户大回馈,云服务器低至5折

?注:未经博主同意,不得转载。

线性表(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)) 

以上代码中关于自增运算用++i而不用i++,想要了解请转至http://www.cnblogs.com/tenjl-exv/p/7469016.html
如要更加追求效率可写为 i+=1。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:拨开字符编码的迷雾--编译器如何处理文件编码

下一篇:C到C++的升级_2