数据结构精华版.doc

《数据结构精华版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、线性表：（一）、线性结构的特点（有序，有限）：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继。（二）、线性表的定义：线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。概念有：(1)第一个元素叫首节点，最后一个叫尾节点。(2)后继；直接后继；前驱，直接前驱。（三）、线性表的顺序存储：

2、1、定义：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。2、特点：若用L表示每个元素所占的存储单元，log(ai+1)表示第（i+1）个元素的存储地址，则有：（用数组形式表示）Log(ai+1)=log(ai)+L;Log(ai)=log(a1)+(i-1);4、线性表的基本操作：(1)、顺序线性表初始化：StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem

3、_array)returnERROR;else{L->length=0;returnOK;}}(2)、顺序线性表的插入：*实现思想❶将线性表L中的第i个至第n个结点后移一个位置。❷将结点e插入到结点ai-1之后。❸线性表长度加1。*算法实现：StatusInsert_SqList(Sqlist*L，inti，ElemTypee){intj;if(i<0

4、

5、i>L->length-1)returnERROR;if(L->length>=MAX_SIZE){printf(“线性表溢出!”);returnERROR;}for(j=L->length

6、–1;j>=i-1;--j)L->Elem_array[j+1]=L->Elem_array[j];/*i-1位置以后的所有结点后移*/L->Elem_array[i-1]=e;/*在i-1位置插入结点*/L->length++;returnOK;}顺序表的插入操作平均时间复杂度为O(n)(3)、顺序表的删除：*实现思想：❶将线性表L中的第i+1个至第n个结点依此向前移动一个位置。❷线性表长度减1。*算法实现：ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;if(L->length==0){

7、printf(“线性表L为空!”);returnERROR;}elseif(i<1

8、

9、i>L->length){printf(“要删除的数据元素不存在!”);returnERROR;}else{x=L->Elem_array[i-1];/*保存结点的值*/for(k=i;klength;k++)L->Elem_array[k-1]=L->Elem_array[k];/*i位置以后的所有结点前移*/L->length--;return(x);}}线性表的删除操作平均时间复杂度为O(n)。(4)、顺序线性表的查找定位删除：*实现思想：

10、❶在线性表L查找值为x的第一个数据元素。❷将从找到的位置至最后一个结点依次向前移动一个位置。❸线性表长度减1。*算法实现：StatusLocate_Delete_SqList(Sqlist*L，ElemTypex)/*删除线性表L中值为x的第一个结点*/{inti=0,k;while(ilength)/*查找值为x的第一个结点*/{if(L->Elem_array[i]!=x)i++;else{for(k=i+1;klength;k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--

11、;break;}}if(i>L->length){printf(“要删除的数据元素不存在!”);returnERROR;}returnOK;}顺序线性表的查找定位删除平均时间复杂度O(n).（四）、线性表的链式存储：1、定义：用一组任意的存储单元存储线性表中的数据元素。2、特点：存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。3、注意：为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。4、单链表：（

12、1）头插入法：LNode*create_LinkList(void)/*头插入法创建单链表,链表的头结点head作为返回值*/{intd