十月份就要考数据结构了，为了这次考试能顺利通过。同时数据结构在开发过程中也是相当重要的，但是以前从来就没有系统地学习过。所以正好借此机会好好地学习下数据结构，一方面是为了通过考试，另一方面也把数据结构和算法这一块的基础打牢一点，真是一举两得啊。
我打算把这一部分写成一个系列，分为C#和C语言两个版本，每周发布两篇。从线性表开始，这一篇主要总结线性表之顺序表的相关操作，主要分以下几个部分来总结。
1，什么是线性表？
2，线性表的两种存储结构？ 3，顺序表的存储结构表示？ 4，顺序表的常见操作和代码实现？1，什么是线性表
线性表就是关系中的一对一的关系，如果是一对多就用树来表示，如果多对多就用网状来表示。
线性表具有以下四个特征：
1> 有且只有一个“首”元素
2> 有且只有一个“尾”元素 3> 除“首”元素外，其余元素都有唯一的后继元素。 4> 除“尾”元素外，其余元素都有唯一的前驱元素。2，线性表的两种存储结构
1> 顺序表，即线性表用顺序存储结构保存数据，数据是连续的。这一篇文章总结的就是顺序表
2> 链表，即线性表用链式存储结构保存数据，数据不连续。3，顺序表的存储结构表示
注：C#和C语言中的数组下标都是从0开始的。
4，顺序表的常见操作和代码实现
顺序表主要有以下常见操作，我们一般用数组来保存数据
1，初始化
思路：将数组的长度length设为0，时间复杂度为O(1)。
2，求顺序表的长度
思路：获取数组的length值，时间复杂度为O(1)。
3，插入元素
思路：分两种情况，一种是插入位置在数组的末尾，这种情况与添加元素相同。另一种情况是插入位置在数组的开始，这时候被插入元素的后续元素都要依次向后移动一位，也就是说整个数组都会移动，所以时间复杂度为O(n)。
4，删除元素
思路：同样分两种情况，一种是删除位置在数组的末尾，不用移动任何元素，因此时间复杂度为O(1);另一种情况是删除位置在数组的开始，这时被删除元素的后续元素都要依次向前移动一位，因此时间复杂度为O(n)。
5，按序号查找元素
思路：因为顺序表的存储地址是连续的，所以第n个元素的地址公式为：(n-1)*单元存储长度，不用移动任何元素，因此时间复杂度为O(1)。
6，按关键字查找元素
思路：一般用for循环，调用IComparable接口的CompareTo()方法去比较，因此时间复杂度为O(n)。
项目结构：
实现代码：
C#版
namespace DS.Model{ /// /// 学生实体 /// public class Student { public int ID { get; set; } public string Name { get; set; } public int Age { get; set; } }}namespace DS.BLL{ /// /// 顺序表操作业务逻辑类 /// public class SeqListBLL { /// /// 初始化 /// /// (SeqListType seqList) { seqList.ListLen = 0; } /// /// 获取顺序表的长度 /// /// (SeqListType seqList) { return seqList.ListLen; } /// /// 插入元素(在第n个元素之前的位置插入新元素) /// /// (SeqListType seqList, int n, T data) { //检查数组是否已满 if (seqList.ListLen >= seqList.MaxSize) return false; //检查n的位置是否超出范围 if (n < 1 || n > seqList.ListLen + 1) return false; //若插入数据位置不在表尾 if (n <= seqList.ListLen) { //将要插入位置之后元素依次向后移动一位 for (int i = seqList.ListLen - 1; i >= n-1; i--) { seqList.ListData[i + 1] = seqList.ListData[i]; } } //将数据插入到位置为n的位置并将数组的长度加1 seqList.ListData[n-1] = data; seqList.ListLen++; return true; } /// /// 删除元素(删除第n个元素) /// /// (SeqListType seqList, int n) { //判断数组是否为空 if (seqList.ListLen == 0) return false; //判断n的位置是否合法 if (n < 1 || n > seqList.ListLen) return false; //如果删除不是最后位置 if (n < seqList.ListLen) { //将删除位置后继元素依次前移 for (int i = n; i < seqList.ListLen; i++) { seqList.ListData[i-1] = seqList.ListData[i]; } } //表长减1 seqList.ListLen--; return true; } /// /// 查找第n个元素 /// /// (SeqListType seqList, int n) { //检查位置是否超出范围 if(n<1||n>seqList.ListLen) return default(T); return seqList.ListData[n-1]; } /// /// 按关键字查找元素 /// /// (SeqListType seqList,string key,Func where) where W : IComparable { for (int i = 0; i < seqList.ListLen; i++) { if (where(seqList.ListData[i]).CompareTo(key) == 0) { return seqList.ListData[i]; } } return default(T); //值类型返回0，引用类型返回null } } /// /// 封装顺序表 /// /// { private const int maxSize = 100; public int MaxSize { get { return maxSize; } }//表的最大长度 //初始化长度为100的数组保存数据 public T[] ListData = new T[maxSize]; //顺序表的长度 public int ListLen { get; set; } }}namespace SeqList.CSharp{ class Program { static void Main(string[] args) { //定义一个顺序表实例 SeqListType seqList = new SeqListType (); //初始化 Console.WriteLine("****************初始化**********************\n"); SeqListBLL.InitSeqList (seqList); Console.WriteLine("初始化后表的长度为：{0}",SeqListBLL.GetSeqListLen (seqList)); //插入数据 Console.WriteLine("\n****************插入三条数据**********************\n"); if (!SeqListBLL.Insert (seqList, 1, new Student { ID = 1, Name = "james", Age = 28 })) Console.WriteLine("插入失败"); else Console.WriteLine("插入成功"); if (!SeqListBLL.Insert (seqList, 1, new Student { ID = 2, Name = "kobe", Age = 33 })) Console.WriteLine("插入失败"); else Console.WriteLine("插入成功"); if (!SeqListBLL.Insert (seqList, 1, new Student { ID = 3, Name = "wade", Age = 31 })) Console.WriteLine("插入失败"); else Console.WriteLine("插入成功"); Display(seqList); //删除数据 Console.WriteLine("\n****************删除一条数据**********************\n"); SeqListBLL.Delete (seqList,1); Console.WriteLine("删除成功"); Display(seqList); //查找元素 Console.WriteLine("****************查找元素by位置**********************\n"); Console.WriteLine("查找第{0}个元素",2); Student student= SeqListBLL.GetDataByIndex (seqList,2); if (student != null) Console.WriteLine("ID:" + student.ID + ",Name:" + student.Name + ",Age:" + student.Age); else Console.WriteLine("没有找到数据"); //查找元素by关键字 Console.WriteLine("****************查找元素by关键字**********************\n"); Console.WriteLine("查找关键字为{0}的元素", "kobe"); Student student1 = SeqListBLL.GetDataByKey (seqList,"kobe",p=>p.Name); if (student1 != null) Console.WriteLine("ID:" + student1.ID + ",Name:" + student1.Name + ",Age:" + student1.Age); else Console.WriteLine("没有找到数据"); //获取表的长度 Console.WriteLine("****************获取表的当前长度**********************\n"); int currentLen= SeqListBLL.GetSeqListLen (seqList); Console.WriteLine("当前表中有{0}个元素", currentLen); Display(seqList); Console.ReadKey(); } /// /// 显示数据 /// /// 顺序表对象 private static void Display(SeqListType seqList) { Console.WriteLine("****************展示数据**********************"); if (seqList == null || seqList.ListLen == 0) { Console.WriteLine("没有数据"); return; } for (int i = 0; i < seqList.ListLen; i++) { Console.WriteLine("ID:" + seqList.ListData[i].ID + ",Name:" + seqList.ListData[i].Name + ",Age:" + seqList.ListData[i].Age); } } }} 运行结果：
C语言版
/*包含头文件*/#include "stdio.h"#include "stdlib.h" #include "io.h"#include "math.h" #include "time.h"/*定义常量，类似于C#中的const*/#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20/*定义类型的同义字*/typedef int Status;typedef int ElemType;typedef struct //定义顺序表{ ElemType data[MAXSIZE]; int length;}SeqList;/*初始化*/Status InitSeqList(SeqList *seqList) //*L表示指向顺序表SeqList的指针{ seqList->length=0; return OK;}/*求顺序表的长度*/int GetSeqListLen(SeqList *seqList){ return seqList->length;}/*插入元素(在第n个元素之前的位置插入新元素)*/Status Insert(SeqList *seqList,int n,ElemType e){ int k; //检查数组是否已满 if (seqList->length>=MAXSIZE) return ERROR; //检查n的位置是否超出范围 if (n<1||n>seqList->length+1) return ERROR; //若插入数据位置不在表尾 if (n<=seqList->length) { //将要插入位置之后元素依次向后移动一位 for (k=seqList->length-1;k>=n-1;k--) { seqList->data[k+1]=seqList->data[k]; } } //将新元素插入到腾出的位置，并将表长加1 seqList->data[n-1]=e; seqList->length++; return OK;}/*删除元素(删除第n个元素)*/Status Delete(SeqList *seqList,int n,ElemType *e){ int k; //判断数组是否为空 if (seqList->length==0) return ERROR; //判断n的位置是否合法 if (n<1||n>seqList->length) return ERROR; *e=seqList->data[n-1]; //如果删除不是最后位置 if (n length) { //将删除位置后继元素依次前移 for (k=n;k length;k++) { seqList->data[k-1]=seqList->data[k]; } } //表长减1 seqList->length--; return OK;}/*查找第n个元素*/int GetDataByIndex(SeqList *seqList,int n){ //检查位置是否超出范围 if (n<1||n>seqList->length) return ERROR; return seqList->data[n-1];}/*打印结果*/void Display(SeqList *seqList){ int i; printf("\n********展示数据********\n"); for (i=0;i length;i++) { Visit(seqList->data[i]); } printf("\n");}Status Visit(ElemType c){ printf("%d\n",c); return OK;}void main(){ //声明变量 SeqList seqList; //创建顺序表 int j,k; Status i; ElemType elem; printf("\n*****************初始化************************\n"); i=InitSeqList(&seqList);//&表示地址 printf("初始化后表的长度为：%d\n",seqList.length); printf("\n*****************插入五条数据************************\n"); for (j=1;j<=5;j++) { i=Insert(&seqList,1,j);//在表头依次插入1~5 } Display(&seqList); printf("\n*****************删除一条数据************************\n"); i=Delete(&seqList,1,&elem); if (i==OK) printf("删除成功\n"); Display(&seqList); printf("\n*****************查找元素by位置************************\n"); k=GetDataByIndex(&seqList,2); printf("第2个元素为%d\n",k); printf("\n*****************获取表的当前长度************************\n"); k=GetSeqListLen(&seqList); printf("当前表中有%d个元素\n",k); getchar();} 运行结果：