数据结构C语言版mdashmdash线.doc

数据结构 C 语言版 mdash mdash 线线性表线性表(List)：由n(n=0)个相同类型的数据元素构成的有限序列。简记L=(D，R)D：数据元素的有限集合；R：数据元素之间关系的有限集合。线性表的基本操作：求长度、清空操作、判断线性表是否为空、附加操作、插入操作、删除操作、取表元。1：/summary 2：/线性表的基本操作接口3：/线性表(List)：由n(n=0)个相同类型的数据元素构成的有限序列。4：/简记L=(D，R)D：数据元素的有限集合；R：数据元素之间关系的有限集合。5：/summary 6：/typeparam name=T元素类型/typeparam 7：public interface IList T：IEnumerable T8：/summary 9：/列表长度10：/summary 11：int Countget；12：13：/summary 14：/清空列表15：/summary 16：void Clear()；17：18：/summary 19：/判断是否为空20：/summary 21：bool IsEmptyget；22：23：/summary 24：/添加一个数据项至列表尾部25：/summary 26：/param name=value插入项/param 27：void Add(T value)；28：29：/summary 30：/在指定位置插入一个数据项31：/summary 32：/param name=value数据项/param 33：/param name=index位置/param 34：void Insert(T value,int index)；35：36：/summary 37：/删除指定位置的数据项38：/summary 39：/param name=index位置/param 40：void Delete(int index)；41：42：/summary 43：/获取指定位置的数据项44：/summary 45：/param name=index位置/param 46：/returns数据项/returns 47：T thisint indexget；set；48：顺序表在内存中用一块地址连续的空间依次存放线性表的数据元素，这种方式存储的线性表叫顺序表。顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻。因此，在顺序表中查找任何一个位置上的数据元素非常方便，这是顺序存储的优点。但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率。顺序表实现：1：public class SequenceList T：IList T2：private const int Step=16；3：private int _capacity；4：private T_datas；5：private int _last=-1；6：7：public SequenceList()：this(Step)8：9：public SequenceList(int capacity)10：this._capacity=capacity；11：this._datas=new Tcapacity；12：13：14：#region Implementation of IEnumerable 15：16：public IEnumerator TGetEnumerator()17：int index=0；18：while(index=this._last)19：yield return this._datasindex+；20：21：22：23：IEnumerator IEnumerable.GetEnumerator()24：return GetEnumerator()；25：26：27：#endregion 28：29：#region Implementation of IList T30：31：/summary 32：/列表长度33：/summary 34：public int Count35：getreturn this._last+1；36：37：38：/summary 39：/清空列表40：/summary 41：public void Clear()42：this._last=-1；43：44：45：/summary 46：/判断是否为空47：/summary 48：public bool IsEmpty49：getreturn this._last=-1；50：51：52：/summary 53：/添加一个数据项至列表尾部54：/summary 55：/param name=value插入项/param 56：public void Add(T value)57：if(this._last+1=this._capacity)58：Reassign()；59：60：this._last+；61：this._datasthis._last=value；62：63：64：private void Reassign()65：this._capacity+=Step；66：T newDatas=new Tthis._capacity；67：int index=0；68：while(index=this._last)69：newDatasindex=this._datasindex；70：index+；71：72：this._datas=newDatas；73：74：75：/summary 76：/在指定位置插入一个数据项77：/summary 78：/param name=value数据项/param 79：/param name=index位置/param 80：public void Insert(T value,int index)81：CheckIndex(index)；82：if(this._last+1=this._capacity)83：Reassign()；84：85：this._last+；86：int tempIndex=this._last；87：while(tempIndex index)88：this._datastempIndex=this._datastempIndex-1；89：tempIndex-；90：91：this._datastempIndex=value；92：93：94：private void CheckIndex(int index)95：if(index 0|index this._last)96：throw new ArgumentException(不正确的位置。)；97：98：99：100：/summary 101：/删除指定位置的数据项102：/summary 103：/param name=index位置/param 104：public void Delete(int index)105：CheckIndex(index)；106：int tempIndex=index；107：while(tempIndex this._last)108：this._datastempIndex=this._datastempIndex+1；109：tempIndex+；110：111：this._last-；112：113：114：/summary 115：/获取指定位置的数据项116：/summary 117：/param name=index位置/param 118：/returns数据项/returns 119：public Tthisint index120：get121：CheckIndex(index)；122：return this._datasindex；123：124：set125：CheckIndex(index)；126：this._datasindex=value；127：128：129：130：#endregion 131：顺序表测试：1：TestClass2：public class SequenceListTest3：/summary 4：/已知顺序表L，写一算法将其倒置5：/11，23，36，45，80，60，40，6 6：/summary 7：TestMethod8：public void Revers()9：SequenceList int l=new SequenceList int()；10：l.Add(11)；11：l.Add(23)；12：l.Add(36)；13：l.Add(45)；14：l.Add(80)；15：l.Add(60)；16：l.Add(40)；17：l.Add(6)；18：19：for(int i=0；i l.Count/2；i+)20：int temp=li；21：li=ll.Count-1-i；22：ll.Count-1-i=temp；23：24：25：foreach(var iin l)26：Console.WriteLine(i)；27：28：29：30：31：/summary 32：/有数据类型为整形的顺序表La和Lb，其数据元素均按从小到大的升序排列。33：/编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。34：/1,2,5,7 35：/3,4,6,8,9 36：/summary 37：TestMethod38：public void Merge()39：SequenceList int la=new SequenceList int()；40：la.Add(1)；41：la.Add(2)；42：la.Add(5)；43：la.Add(7)；44：45：SequenceList int lb=new SequenceList int()；46：lb.Add(3)；47：lb.Add(4)；48：lb.Add(6)；49：lb.Add(8)；50：lb.Add(9)；51：52：int aIndex=0；53：int bIndex=0；54：55：SequenceList int lc=new SequenceList int()；56：57：while(aIndex la.Count&bIndex lb.Count)58：if(laaIndex=lbbIndex)59：lc.Add(laaIndex)；60：aIndex+；61：62：else63：lc.Add(lbbIndex)；64：bIndex+；65：66：67：68：while(aIndex la.Count)69：lc.Add(laaIndex)；70：aIndex+；71：72：73：while(bIndex lb.Count)74：lc.Add(lbbIndex)；75：bIndex+；76：77：78：foreach(var iin lc)79：Console.WriteLine(i)；80：81：82：83：/summary 84：/已知一个存储整数的顺序表La，试构造顺序表Lb，要求顺序表Lb中只包含顺序表La中所有值不相同的数据元素。85：/11，23，23，36，45，36，80，11，60，40，6,6 86：/summary 87：TestMethod88：public void Purge()89：SequenceList int la=new SequenceList int()；90：la.Add(11)；91：la.Add(23)；92：la.Add(23)；93：la.Add(36)；94：la.Add(45)；95：la.Add(36)；96：la.Add(80)；97：la.Add(11)；98：la.Add(60)；99：la.Add(40)；100：la.Add(6)；101：la.Add(6)；102：103：SequenceList int lb=new SequenceList int()；104：lb.Add(la0)；105：for(int i=1；i la.Count；i+)106：int j=0；107：for(；j lb.Count；j+)108：if(lai=lbj)109：break；110：111：112：if(j=lb.Count)113：lb.Add(lai)；114：115：116：117：foreach(var iin lb)118：Console.WriteLine(i)；119：120：121：122：链表链式存储，这样的线性表叫链表(Lnked List)。链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此，在对链表进行插入和删除时不需要移动数据元素，但同时也失去了顺序表可随机存储的优点。单链表实现：1：public class OneWayNode T2：private OneWayNode T_next；3：private T_value；4：5：public OneWayNode()：this(default(T),null)6：7：8：public OneWayNode(T value)：this(value,null)9：10：11：public OneWayNode(T value,OneWayNode Tnext)12：this._value=value；13：this._next=next；14：15：16：public OneWayNode TNext17：getreturn this._next；18：setthis._next=value；19：20：21：public TValue22：getreturn this._value；23：setthis._value=value；24：25：1：public class OneWayLinkList T：IList T2：private OneWayNode T_head；3：4：#region Implementation of IEnumerable 5：6：public IEnumerator TGetEnumerator()7：OneWayNode Tnode=this.Head；8：while(node！=null)9：yield return node.Value；10：node=node.Next；11：12：13：14：IEnumerator IEnumerable.GetEnumerator()15：return GetEnumerator()；16：17：18：#endregion 19：20：#region Implementation of IList T21：22：/summary 23：/列表长度24：/summary 25：public int Count26：get27：int count=0；28：OneWayNode Tnode=this._head；29：while(node！=null)30：count+；31：node=node.Next；32：33：return count；34：35：36：37：/summary 38：/清空列表39：/summary 40：public void Clear()41：this._head=null；42：43：44：/summary 45：/判断是否为空46：/summary 47：public bool IsEmpty48：getreturn this.Head=null；49：50：51：public OneWayNode THead52：getreturn this._head；53：setthis._head=value；54：55：56：/summary 57：/添加一个数据项至列表尾部58：/summary 59：/param name=value插入项/param 60：public void Add(T value)61：if(this.Head=null)62：this.Head=new OneWayNode T(value)；63：return；64：65：OneWayNode Tnode=this.Head；66：while(node.Next！=null)67：node=node.Next；68：69：node.Next=new OneWayNode T(value)；70：71：72：/summary 73：/在指定位置插入一个数据项74：/summary 75：/param name=value数据项/param 76：/param name=index位置/param 77：public void Insert(T value,int index)78：CheckIndex(index)；79：if(index=0)80：this._head=new OneWayNode T(value,this._head)；81：return；82：83：84：OneWayNode Tprev=this._head；85：OneWayNode Tnext=this._head.Next；86：int tempIndex=1；87：while(tempIndex index)88：prev=next；89：next=next.Next；90：tempIndex+；91：92：prev.Next=new OneWayNode T(value,next)；93：94：95：private void CheckIndex(int index)96：if(index 0|index=Count)97：throw new ArgumentException(不正确的位置。)；98：99：100：101：/summary 102：/删除指定位置的数据项103：/summary 104：/param name=index位置/param 105：public void Delete(int index)106：if(index=0)107：this._head=this._head.Next；108：return；109：110：OneWayNode Tprev=this._head；111：OneWayNode Tnext=this._head.Next；112：int tempIndex=1；113：while(tempIndex index)114：prev=next；115：next=next.Next；116：tempIndex+；117：118：prev.Next=next.Next；119：120：121：/summary 122：/获取指定位置的数据项123：/summary 124：/param name=index位置/param 125：/returns数据项/returns 126：public Tthisint index127：get128：OneWayNode Tcurrent=GetItem(index)；129：return current.Value；130：131：set132：OneWayNode Tcurrent=GetItem(index)；133：current.Value=value；134：135：136：137：private OneWayNode TGetItem(int index)138：OneWayNode Tcurrent=this.Head；139：int tempIndex=0；140：while(tempIndex index)141：current=current.Next；142：tempIndex+；143：144：return current；145：146：147：#endregion 148：单链表测试：1：TestClass2：public class OneWayLinkListTest3：/summary 4：/已知顺序表L，写一算法将其倒置5：/11，23，36，45，80，60，40，6 6：/summary 7：TestMethod8：public void Revers()9：OneWayLinkList int l=new OneWayLinkList int()；10：l.Add(11)；11：l.Add(23)；12：l.Add(36)；13：l.Add(45)；14：l.Add(80)；15：l.Add(60)；16：l.Add(40)；17：l.Add(6)；18：19：OneWayNode int node=l.Head；20：l.Head=null；21：while(node！=null)22：OneWayNode int next=node.Next；23：node.Next=l.Head；24：l.Head=node；25：node=next；26：27：28：foreach(var iin l)29：Console.WriteLine(i)；30：31：32：33：34：/summary 35：/有数据类型为整形的顺序表La和Lb，其数据元素均按从小到大的升序排列。36：/编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。37：/1,2,5,7 38：/3,4,6,8,9 39：/summary 40：TestMethod41：public void Merge()42：OneWayLinkList int la=new OneWayLinkList int()；43：la.Add(1)；44：la.Add(2)；45：la.Add(5)；46：la.Add(7)；47：48：OneWayLinkList int lb=new OneWayLinkList int()；49：lb.Add(3)；50：lb.Add(4)；51：lb.Add(6)；52：lb.Add(8)；53：lb.Add(9)；54：55：OneWayNode int aNode=la.Head；56：OneWayNode int bNode=lb.Head；57：58：OneWayLinkList int lc=new OneWayLinkList int()；59：60：61：while(aNode！=null&bNode！=null)62：if(aNode.Value=bNode.Value)63：lc.Add(aNode.Value)；64：aNode=aNode.Next；65：66：else67：lc.Add(bNode.Value)；68：bNode=bNode.Next；69：70：71：72：while(aNode！=null)73：lc.Add(aNode.Value)；74：aNode=aNode.Next；75：76：77：while(bNode！=null)78：lc.Add(bNode.Value)；79：bNode=bNode.Next；80：81：82：foreach(var iin lc)83：Console.WriteLine(i)；84：85：86：87：/summary 88：/已知一个存储整数的顺序表La，试构造顺序表Lb，要求顺序表Lb中只包含顺序表La中所有值不相同的数据元素。89：/11，23，23，36，45，36，80，11，60，40，6,6 90：/summary 91：TestMethod92：public void Purge()93：OneWayLinkList int la=new OneWayLinkList int()；94：la.Add(11)；95：la.Add(23)；96：la.Add(23)；97：la.Add(36)；98：la.Add(45)；99：la.Add(36)；100：la.Add(80)；101：la.Add(11)；102：la.Add(60)；103：la.Add(40)；104：la.Add(6)；105：la.Add(6)；106：107：OneWayLinkList int lb=new OneWayLinkList int()；108：109：lb.Add(la.Head.Value)；110：OneWayNode int aNode=la.Head.Next；111：112：while(aNode！=null)113：OneWayNode int bNode=lb.Head；114：while(bNode！=null)115：if(aNode.Value=bNode.Value)116：break；117：118：bNode=bNode.Next；119：120：if(bNode=null)121：lb.Add(aNode.Value)；122：123：aNode=aNode.Next；124：125：126：foreach(var iin lb)127：Console.WriteLine(i)；128：129：130：双链表实现：1：public class TwoWayNode T2：private TwoWayNode T_next；3：private TwoWayNode T_prev；4：private T_value；5：6：public TwoWayNode()：this(default(T),null,null)7：8：9：10：public TwoWayNode(T value)11：this(value,null,null)12：13：14：15：public TwoWayNode(T value,TwoWayNode Tprev,TwoWayNode Tnext)16：this._value=value；17：this._prev=prev；18：this._next=next；19：20：21：public TwoWayNode TNext22：getreturn this._next；23：setthis._next=value；24：25：26：public TwoWayNode TPrevious27：getreturn this._prev；28：setthis._prev=value；29：30：31：public TValue32：getreturn this._value；33：setthis._value=value；34：35：1：public class TwoWayLinkList T：IList T2：private TwoWayNode T_head；3：4：#region Implementation of IEnumerable 5：6：public IEnumerator TGetEnumerator()7：TwoWayNode Tnode=this.Head；8：while(node！=null)9：yield return node.Value；10：node=node.Next；11：12：13：14：IEnumerator IEnumerable.GetEnumerator()15：return GetEnumerator()；16：17：18：#endregion 19：20：#region Implementation of IList T21：22：/summary 23：/列表长度24：/summary 25：public int Count26：get27：int count=0；28：TwoWayNode Tnode=this._head；29：while(node！=null)30：count+；31：node=node.Next；32：33：return count；34：35：36：37：/summary 38：/清空列表39：/summary 40：public void Clear()41：this._head=null；42：43：44：/summary 45：/判断是否为空46：/summary 47：public bool IsEmpty48：getreturn this.Head=null；49：50：51：public TwoWayNode THead52：getreturn this._head；53：setthis._head=value；54：55：56：/summary 57：/添加一个数据项至列表尾部58：/summary 59：/param name=value插入项/param 60：public void Add(T value)61：if(this.Head=null)62：this.Head=new TwoWayNode T(value)；63：return；64：65：TwoWayNode Tnode=this.Head；66：while(node.Next！=null)67：node=node.Next；68：69：node.Next=new TwoWayNode T(value,node,null)；70：71：72：/summary 73：/在指定位置插入一个数据项74：/summary 75：/param name=value数据项/param 76：/param name=index位置/param 77：public void Insert(T value,int index)78：CheckIndex(index)；79：if(index=0)80：this._head=new TwoWayNode T(value,null,this._head)；81：return；82：83：84：TwoWayNode Tcurrent=this.GetItem(index)；85：current.Previous.Next=current.Next.Previous=new TwoWayNode T(value,current.Previous,current.Next)；86：87：88：private void CheckIndex(int index)89：if(index 0|index=Count)90：throw new ArgumentException(不正确的位置。)；91：92：93：94：/summary 95：/删除指定位置的数据项96：/summary 97：/param name=index位置/param 98：public void Delete(int index)99：if(index=0)100：this._head=this._head.Next；101：return；102：103：TwoWayNode Tcurrent=this.GetItem(index)；104：current.Previous.Next=current.Next；105：current.Next.Previous=current.Previous；106：107：108：/summary 109：/获取指定位置的数据项110：/summary 111：/param name=index位置/param 112：/returns数据项/returns 113：public Tthisint index114：get115：TwoWayNode Tcurrent=GetItem(index)；116：return current.Value；117：118：set119：TwoWayNode Tcurrent=GetItem(index)；120：current.Value=value；121：122：123：124：private TwoWayNode TGetItem(int index)125：TwoWayNode Tcurrent=this.Head；126：int tempIndex=0；127：while(tempIndex index)128：current=current.Next；129：tempIndex+；130：131：return current；132：133：134：#endregion 135：双链表测试：1：TestClass2：public class TwoWayLinkListTest3：/summary 4：/已知顺序表L，写一算法将其倒置5：/11，23，36，45，80，60，40，6 6：/summary 7：TestMethod8：public void Revers()9：TwoWayLinkList int l=new TwoWayLinkList int()；10：l.Add(11)；11：l.Add(23)；12：l.Add(36)；13：l.Add(45)；14：l.Add(80)；15：l.Add(60)；16：l.Add(40)；17：l.Add(6)；18：19：TwoWayNode int node=l.Head；20：l.Head=null；21：while(node！=null)22：TwoWayNode int next=node.Next；23：node.Next=l.Head；24：l.Head=node；25：node=next；26：27：28：foreach(var iin l)29：Console.WriteLine(i)；30：31：32：33：34：/summary 35：/有数据类型为整形的顺序表La和Lb，其数据元素均按从小到大的升序排列。36：/编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。37：/1,2,5,7 38：/3,4,6,8,9 39：/summary 40：TestMethod41：public void Merge()42：TwoWayLinkList int la=new TwoWayLinkList int()；43：la.Add(1)；44：la.Add(2)；45：la.Add(5)；46：la.Add(7)；47：48：TwoWayLinkList int lb=new TwoWayLinkList int()；49：lb.Add(3)；50：lb.Add(4)；51：lb.Add(6)；52：lb.Add(8)；53：lb.Add(9)；54：55：TwoWayNode int aNo