线性表
线性表是线性结构的抽象，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
数据元素之间的位置关系是一个接一个的排列：
1.除第一个位置的数据元素外，其他数据元素位置的前面都只有一个数据元素。
2.除最后一个位置的外，其他数据元素位置的后面都只有一个元素。
线性表通常表示为：L=(D,R)
D是数据元素的有限集合
R是数据元素之间关系的有限集合
线性表的基本操作：
1 public interface IListDS<T> {
2 int GetLength(); //求长度
3 void Clear(); //清空
4 bool IsEmpty(); //判空
5 void Append(T item); //附加
6 void Insert(T item, int i); //插入
7 T Delete(int i); //删除
8 T GetElement(int i); //取表元素
9 int Locate(T value); //按值查找
10 }
顺序表
顺序表是线性表的顺序存储(Sequence Storage)，是指在内存中用一块地址连续的空间依次存放线性表的数据元素(Sequence List)，具有随机存取的特点。
w: 每个数据元素占w个存储单元
A1:顺序表的基地址(Base Address)
Loc(Ai)=Loc(A1)+(i-1)*w 1<=i<=n
为了理解顺序表，闪电学习了这样一个例题，有兴趣的朋友可以在自己的机器上写一下。
有数据类型为整型的顺序表La和Lb，其数据元素均按从小到大的升序排列，编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。
算法思路：
依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。
思路图示：
1 public class SeqList<T> : IListDS<T> {
2 private int maxsize; //顺序表的容量
3 private T[] data; //数组，用于存储顺序表中的数据元素
4 private int last; //指示顺序表最后一个元素的位置
5
6 //构造器
7 public SeqList(int size)
8 {
9 data = new T[size];
10 maxsize = size;
11 last = -1; //如果顺序表为空，last=-1
12 }
13 //索引器
14 public T this[int index]
15 {
16 get { return data[index]; }
17 set { data[index] = value; }
18 }
19 //最后一个元素的位置属性
20 public int Last
21 {
22 get { return last; }
23 }
24 //容量属性
25 public int Maxsize
26 {
27 get { return maxsize; }
28 set { maxsize = value; }
29 }
30 //判断顺序表是否为空
31 public bool IsEmpty()
32 {
33 if (last == -1)
34 return true;
35 else
36 return false;
37 }
38 //判断顺序表是否为满
39 public bool IsFull()
40 {
41 if (last == maxsize - 1)
42 return true;
43 else
44 return false;
45 }
46 //求顺序表的长度
47 public int GetLength()
48 {
49 return last + 1;
50 }
51 //清空顺序表
52 public void Clear()
53 {
54 last = -1;
55 }
56 //在顺序表末尾添加新元素
57 public void Append(T item)
58 {
59 if (IsFull())
60 {
61 Console.WriteLine("List is full.");
62 return;
63 }
64 data[++last] = item;
65 }
66
67 //在顺序表第i个数据元素位置插入一个数据元素
68 public void Insert(T item, int i)
69 {
70 if (IsFull())
71 return;
72 if (i < 1 || i > last + 2)
73 return;
74 if (i == last + 2)
75 data[last + 1] = item;
76 else
77 {
78 for (int j = last; j >= i - 1; --j)
79 {
80 data[j + 1] = data[j];
81 }
82 data[i - 1] = item;
83 }
84 ++last;
85 }
86 //删除顺序表的第i个数据元素
87 public T Delete(int i)
88 {
89 T tmp = default(T);
90 if (IsEmpty())
91 return tmp;
92 if (i < 1 || i > last + 1)
93 return tmp;
94 if (i == last + 1)
95 tmp = data[last--];
96 else
97 {
98 tmp = data[i - 1];
99 for (int j = i; j <= last; ++j)
100 data[j] = data[j + 1];
101 }
102 --last;
103 return tmp;
104 }
105 //获得顺序表的第i个数据元素
106 public T GetElement(int i)
107 {
108 if (IsEmpty() || (i < 1) || (i > last + 1))
109 return default(T);
110 return data[i-1];
111 }
112 //在顺序表中查找值为value的数据元素
113 public int Locate(T value)
114 {
115 if (IsEmpty())
116 return -1;
117 int i = 0;
118 for (i = 0; i <= last; ++i)
119 {
120 if (value.Equals(data[i]))
121 break;
122 }
123 if (i > last)
124 return -1;
125 return i;
126 }
127 }
1 public class GenericList
2 {
3 public GenericList()
4 { }
5 public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb)
6 {
7 SeqList<int> Lc = new SeqList<int>(La.Maxsize+Lb.Maxsize);
8 int i = 0;
9 int j = 0;
10 int k = 0;
11
12 //两个表中元素都不为空
13 while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1)))
14 {
15 if (La[i] < Lb[j])
16 Lc.Append(La[i++]);
17 else
18 Lc.Append(Lb[j++]);
19 }
20 //a表中还有数据元素
21 while (i <= (La.GetLength() - 1))
22 Lc.Append(La[i++]);
23 //b表中还有数据元素
24 while (j <= (Lb.GetLength() - 1))
25 Lc.Append(Lb[j++]);
26 return Lc;
27
28 }
29 }
客户端代码：
1 static void Main(string[] args)
2 {
3 SeqList<int> sl1 = new SeqList<int>(4);
4 sl1.Append(1);
5 sl1.Append(3);
6 sl1.Append(4);
7 sl1.Append(7);
8
9 SeqList<int> sl2 = new SeqList<int>(6);
10 sl2.Append(2);
11 sl2.Append(5);
12 sl2.Append(6);
13 sl2.Append(8);
14 sl2.Append(11);
15 sl2.Append(14);
16
17 GenericList gl = new GenericList();
18 SeqList<int> sl3 = gl.Merge(sl1, sl2);
19 Console.WriteLine("length:" + sl3.GetLength());
20 for (int i = 0; i < sl3.GetLength(); i++)
21 {
22 Console.WriteLine(i + ":" + sl3[i]);
23 }
24 }
好了，下一次学习链表。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。