简单数据结构

数据结构是程序储存，组织数据的一种方式，是程序中处理数据的基本单位。主要讲解简单的数据结构的基本操作。线性表是最简单也是最常用的一种数据结构。例如，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={ai,ai-1}基本操作：操作函数实现}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个元素。下面详细讲解这些基本操作。在对顺序表操作之前我们必须先对顺序表初始化。对顺序表的初始化的算法如图14.8所示。SeqList*init_SeqList(){SeqList*L;/*定义L为指向Seqlist类型的指针*/L=(SeqList*)malloc(sizeof(SeqList));/*用malloc动态获得线性表的存储空间*/L-length=0;/*当前线性表最后一个元素*/returnL;/*L为线性表的长度*/}初始化的顺序表为空表求顺序表长度所用到的函数为Length()，该算法的实现如图14.9所示。intlength_List(SqListL){returnL.length;/*返回表的长度*/}在顺序表初始化时已设定length的值为顺序表的长度。如果顺序表的长度为0，则顺序表为空表。判断顺序表是否为空的算法具体实现如图14.10所示。intEmpty_List(SqListL){if(L.length==0)/*判断顺序表的长度*/{return1;}else{return0;}}通过函数的返回值是否为1来判断顺序表是否为空清空顺序表也就是删除顺序表中的所有数据元素，清空之后的顺序表的长度length为0。清空顺序表的算法如图14.11所示。voidClear_List(SqListL){L.length=0;/*删除所有数据元素*/}把顺序表中的数据元素的个数置为0取顺序表数据元素运算是返回顺序表中第i个数据元素，注意i取值范围是1≤i≤length。如果i的取值正确，运算的时间复杂度为O(1)。取顺序表数据元素的算法实现如图14.12所示。voidGet_List(SqListL,inti){if(Empty_List(L)||i1||iLength_List(L))/*判断表是否为空或输入位置是否合法*/{printf(表空或者输入的位置不对!);return;}returnL.data[i-1];/*返回第i个数据元素*/}根据位置i可以直接找到数据元素，所以时间复杂度为1对顺序表初始化后，我们需要向顺序表中插入我们所需的数据，然后才能对其进行其它的操作。对顺序表的插入前与插入后数据元素的位置改变如图14.13所示。a6a5a4a3a2a1插入前的顺序表L：a6a5a4xa3a2a1向顺序表L中第4个位置插入元素x后，顺序表的数据元素位置的变化如下：a4后的元素位置依次往后移动了1位，线性表的长度增1顺序表是一种随机存取结构。所以，在顺序表中按位置查找元素非常容易，只有查找位置合法，可直接返回对应的数据元素。按位置查找元素算法实现如图14.16所示。DataTypeLocate_List(SqListL,inti){DataTypee;if(i1||iLength_List(L))/*判断表输入的位置是否正确*/{printf(输入的位置非法!);return0;}e=L.data[i-1];return(e);/*返回对应位置为i的数据元素*/DataType用户自定义的数据类型，便于用户修改数据元素的数据类型按值查找元素是在顺序表中进行的，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；如果顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。顺序表按值查找元素算法实现如图14.17所示。intLocate_List(SqListL,DataTypex){inti=0;while(iL.length&&L.data[i]!=x)i++;if(iL.length)return(i+1);/*返回数据元素的位置*/elsereturn0;/*查找失败*/}datanx…x…mn返回首次出现x值的序列号，所以返回值是m，不是n注意返回值是首次出现x元素的位置效率主要是从时间复杂度和空间复杂度来看的，由于现在计算机的内存足够用程序实现，所以我们这里只考虑时间复杂度。按位置查找数据元素的时间复杂度分析如图14.18所示。DataTypeLocate_List(SqListL,inti){……return(L.dara[i-1]);}无循环直接根据位置i返回数据元素时间复杂度O(1)字母O大写时间复杂度和顺序表长度无关x的位置为1循环次数1x的位置为2循环次数2x的位置为3循环次数3x的位置为n-1循环次数n-1x的位置为n循环次数n……n种情况的和1+2+…+n-1+n=(n+1)/2O(n)时间复杂度字母O大写时间复杂度和顺序表长度无关如果对顺序表的第i个元素删除操作，那么低i+1个元素以及其后面的元素都会向前移动一个位置，并且顺序表的长度减1，具体算法以及算法分析如图14.20所示。intDelete_Seqlist(Seqlist*L,inti){intj;if(i1||iL-last+1){printf(不存在第i个元素)；return(0)}for(j=1;j=L-last;j++)L-data[j-1]=L-data[j];/*向前移动*/L-last--/*顺序表的长度减1*/return(1);/*删除成功*/}datan......dataidatai-1datan...datai+1datai删除的元素删除a1元素移动元素个数n-1删除a2元素移动元素个数n-2删除a3元素移动元素个数n-3删除an-1元素移动元素个数1删除n元素移动元素个数0……平均移动元素个数n1idl21ni)(nn1E线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。在链式存储中，结点不仅包含数据元素的基本信息内容，而且包含数据元素之间的逻辑关系，如图14.24所示。链表L：L(结点1,节点2,…,结点n-1,结点n)链表L：L(结点1,节点2,…,结点n-1,结点n)结点包含两方面结点包含两方面数据域：数据元素本身信息数据域：数据元素本身信息指针域：元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息指针域：元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息一般链表中的结点包含一个或者多个指针域typedefstructnode{intdata;structnode*next;}LNode，*LinkList;LNodeL;/*定义了只有一个元素的单链表*/LinkListH;/*定义头指针变量H*/H=&L;单链表定义形式说明datanextH指向其后继元素L头结点nexthead开始结点data[0]nextdata[1]next…终端结点data[n]NULL头结点的数据域中一般存储单链表的长度终端结点的next指针是不指向任何数据的，所以为NULL在单链表中只能通过指针域访问后继结点，无法访问其前驱结点初始化链表主要完成头结点空间的申请和赋值。在以后的算法中不加说明则默认为单链表是带头结点的。初始化链表实现算法如图14.27所示。intInit_List(LinkList&L){L=(LNode*)malloc(sizeof(LNode));/*申请结点空间*/if(L){L-next=NULL;/*置为空表*/return1;}elsereturn0;}单链表初始化算法初始化形成的单链表dataNULLHL清空操作是指清除单链表中的所有结点使单链表为空，并释放空间。此时，头指针变为空。清空链表实现算法如图14.28所示。intClear_List(LinkList&L){while(L!=NULL)/*判断链表是否为空*/{LinkListp;p=L;L=L-next;free(p);/*释放结点存储空间*/}return1;}清空单链表的算法使用while循环逐点释放使用free()函数释放单链表结点的存储空间，从而这一段空间又可以被其它数据利用如果单链表的头指针所指的第一个结点为空，那么单链表就为空，返回1，否则返回0。判断单链表是否为空的算法实现如图14.29所示。intIsEmpty(LinkListL){if(L-next==NULL)/*判断链表是否为空*/return1;elsereturn0;}判断单链表是否为空算法说明dataNULLHLdatanextLHL-next为NULL，则单链表为空，返回1L-next为notNULL，则单链表为非空，返回0算法思路：设一个移动指针ｐ和计数器k