从拾数据结构.doc

从拾《数据结构》 线性表最简单的存储结构:所以我想首先从线性表说起。线性——很明显，肯定是满足某种关系的才能称作线性( ⊙ o ⊙ )！ 不错，线性表有几个很明显的特征 （1）:存在唯一的一个数据元素被称为表头 （2）：除表头之外其余数据元素都拥有一个“前驱” （3）：存在唯一的一个数据元素被称为表尾 （4）：出表尾之外其余数据元素都拥有一个“后继” （5）：数据元素存在一个有限的集合中 以上五个点，可以说是线性表最具有代表性的特征。 但是光有这些特征是不够的，要进一步了解线性表，还需要自己去实践中慢慢总结和积累。其实，线性表在计算机上可以理解为一块连续的内存。那神马是连续的内存呢!？ 我们可以类比于连续的寝室。每栋寝室楼都有自己的区（也就是逻辑地址），而寝室楼里面又包含寝室单元，每个独立的寝室单元都有自己的门牌号（也就是偏移地址）。学过汇编语言的人都知道什么是逻辑地址和偏移地址，也就是计算机访问每个内存都是通过逻辑地址加偏移地址实现的。比如我要找你的寝室，我就要首先知道你是几栋，然后是你的寝室门牌号。通过这些信息当然我几可以轻而易举的找到你。不是吗！ 呵呵，扯远了。。。其实，线性表就是这么一回事。无非就是一个巨大的容器，不过在ta容纳数据之前已经为数据分好了“家”，并且这些“家”的“门牌号”都是连续的。 好吧，如果还有耐心就看下面的代码吧！（个人风格趋向于C++，代码有点小长）。重点是删除和插入操作哦！ #includeiostream #includestdlib.h #define False 0 #define True 1 #define Error 0 #define Ok 1 typedef status; using namespace std; template class T class Sqlist { private: int Listsize; int Length; T *elem;//表头指针 public: Sqlist(int size); ~Sqlist(); void Print1() const;//遍历输出所有元素的值 bool ListEmpty() const;//判断表是否为空 int ListLength() const;//返回线性表的表长 int LocateElem(T e) const;//返回e元素的位置 int GetElem(int x) const;//返回i位置元素的值 int Insert(int i,T e);//在i位置插入元素 int Delete(int c);//选择i位置删除元素 }; //函数的实现 template class T SqlistT::Sqlist(int size)//构造函数 { int j; elem=new T[size];//申请新的空间 if(elem==NULL) { cout内存申请失败endl; exit(1); } Length=0; Listsize=size; srand(size); for(j=0;jsize;j++) { elem[j]=rand()%100; Length++; } } template class T SqlistT::~Sqlist() { delete [] elem; } template class T void SqlistT::Print1() const//输出函数 { int k; for(k=0;kLength;k++) { coutelem[k] ; } coutendl; } template class T bool SqlistT::ListEmpty() const//判断是否为空 { if(Length==0) return true; else return false; } template class T int SqlistT::ListLength() const//返回表长 { cout表的长度为 : Lengthendl; return Ok; } template class T int SqlistT::LocateElem(T e) const//判断e元素的位置 { int l; for(l=0;lLength;l++) { if(elem[l]==e) { cout位置是: l+1endl; return Error; } } cout元素不存在 endl; return Ok; } template class T in