简单数据结构数据结构是程序储存，组织数据的一种方式，是程序中处理数据的基本单位。主要讲解简单的数据结构的基本操作。线性表线性表是最简单也是最常用的一种数据结构。例如，C语言中的数组就是线性表应用的一个典型代表。线性表的基本概念线性表是由n（n≥0）个类型相同的数据元素（结点）组成的有限序列。通常线性表的表示形式以及说明如图14.1所示。线性表的表示形式如下：L(a1,a2,a3,…ai,…,an)L：L为线性表名称，习惯用大写书写；ai：ai为该线性表的数据元素，也称为节点，习惯用小写书写n：线性表的长度，表示数据元素的个数。当n为0时，线性表为空，即空线性表线性表的基本概念a1a2…ai-1aiai+1an…如果有前驱元素，那么它是唯一的唯一的表头元素唯一的表尾元素如果有后继元素，那么它是唯一的线性表的基本概念L(1,3,5,7,8,10,12,34,67)L(1,3,5,7,8,10,12,34,67)线性表L中的数据元素类型为int型，长度为9线性表L中的数据元素类型为int型，长度为9线性表的基本操作线性表的基本操作通过以下函数可以实现，有关于这些函数的形式以及功能如表14-3。函数实现功能MakeEmpty(L)将线性表L变为空表Length(L)返回表L的长度，即表中元素个数Get(L,i)获得线性表L中位置i处的元素（1≤i≤n）Prev(L,i)取i位置数据元素的前趋元素Next(L,i)取i位置数据元素的后继元素Locate(L,x)函数的返回值为数据元素x在L中的位置Insert(L,I,x)在线性表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置Delete(L,p)从表L中删除位置p处的元素IsEmpty(L)如果表L为空表(长度为0)则返回true，否则返回falseClear(L)清除所有元素Init(L)同MakeEmpty(L)，初始化线性表为空Traverse(L)遍历输出所有元素Find(L,x)查找线性表L中元素x首次出现的位置，如果成功返回出现的位置，否则返回0Update(L,x)更新元素Sort(L)对所有元素重新按给定的条件排序rstr(string1,string2)用于字符数组的求string1中出现string2的首地址线性表的基本操作ADTList{数据对象：D={ai,i=1,2,3,…,n}数据关系：R={
}基本操作：操作函数实现}ADTlistADT为抽象数据类型数据对象中的每个元素都有一个固定的值相邻的数据元素之间有序偶关系线性表的顺序存储结构线性表的顺序存储结构的含义如图14.5所示。线性表的顺序存储结构用一组连续的存储单元依次存储线性表中的每个数据元素。含义线性表的顺序存储结构逻辑地址1数据元素物理地址内存单元23i……nana1a2a3…ai………Loc(a1)a2a3…ai……ana1Loc(a1)+sumLoc(a1)+2sumLoc(a1)+(i-1)sumLoc(a1)+(n-1)sum为线性表分配的存储单元是连续的sum为每个数据元素占的存储单元个数线性表的顺序存储结构#defineMAXSIZE100/*线性表的最大长度*/typedefstruct{/*数据元素ai存储在L.data[i]中*/intdata[MAXSIZE];/*last记录线性表的最后一个元素的位置*/intlast;}SeqList;SeqlistL;/*定义一个顺序表L*/当顺序表为空Last为-1当顺序表非空Last的值等于L的长度减1顺序表的基本操作顺序表的基本操作包括初始化、求顺序表的长度、判断顺序表是否为空、清空顺序表、获取顺序表中第i个元素。下面详细讲解这些基本操作。1.初始化顺序表L在对顺序表操作之前我们必须先对顺序表初始化。对顺序表的初始化的算法如图14.8所示。SeqList*init_SeqList(){SeqList*L;/*定义L为指向Seqlist类型的指针*/L=(SeqList*)malloc(sizeof(SeqList));/*用malloc动态获得线性表的存储空间*/L->length=0;/*当前线性表最后一个元素*/returnL;/*L为线性表的长度*/}初始化的顺序表为空表2.求顺序表的长度求顺序表长度所用到的函数为Length()，该算法的实现如图14.9所示。intlength_List(SqListL){returnL.length;/*返回表的长度*/}在顺序表初始化时已设定length的值为顺序表的长度。3.判断顺序表是否为空如果顺序表的长度为0，则顺序表为空表。判断顺序表是否为空的算法具体实现如图14.10所示。intEmpty_List(SqListL){if(L.length==0)/*判断顺序表的长度*/{return1;}else{return0;}}通过函数的返回值是否为1来判断顺序表是否为空4.清空顺序表清空顺序表也就是删除顺序表中的所有数据...
