数据结构精华版

1一、线性表：（一）、线性结构的特点（有序，有限）：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后继。（二）、线性表的定义：线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。概念有：(1)第一个元素叫首节点，最后一个叫尾节点。(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_array)returnERROR;else{L-length=0;returnOK;}}(2)、顺序线性表的插入：*实现思想❶将线性表L中的第i个至第n个结点后移一个位置。❷将结点e插入到结点ai-1之后。❸线性表长度加1。*算法实现：StatusInsert_SqList(Sqlist*L，inti，ElemTypee){intj;if(i0||iL-length-1)returnERROR;if(L-length=MAX_SIZE){printf(“线性表溢出!\n”);returnERROR;}for(j=L-length–1;j=i-1;--j)L-Elem_array[j+1]=L-Elem_array[j];/*i-1位置以后的所有结点后移*/L-Elem_array[i-1]=e;/*在i-1位置插入结点*/2L-length++;returnOK;}顺序表的插入操作平均时间复杂度为O(n)(3)、顺序表的删除：*实现思想：❶将线性表L中的第i+1个至第n个结点依此向前移动一个位置。❷线性表长度减1。*算法实现：ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;if(L-length==0){printf(“线性表L为空!\n”);returnERROR;}elseif(i1||iL-length){printf(“要删除的数据元素不存在!\n”);returnERROR;}else{x=L-Elem_array[i-1];/*保存结点的值*/for(k=i;kL-length;k++)L-Elem_array[k-1]=L-Elem_array[k];/*i位置以后的所有结点前移*/L-length--;return(x);}}线性表的删除操作平均时间复杂度为O(n)。(4)、顺序线性表的查找定位删除：*实现思想：❶在线性表L查找值为x的第一个数据元素。❷将从找到的位置至最后一个结点依次向前移动一个位置。❸线性表长度减1。*算法实现：StatusLocate_Delete_SqList(Sqlist*L，ElemTypex)/*删除线性表L中值为x的第一个结点*/{inti=0,k;while(iL-length)/*查找值为x的第一个结点*/{if(L-Elem_array[i]!=x)i++;else{for(k=i+1;kL-length;k++)L-Elem_array[k-1]=L-Elem_array[k];L-length--;break;}}if(iL-length){printf(“要删除的数据元素不存在!\n”);returnERROR;}3returnOK;}顺序线性表的查找定位删除平均时间复杂度O(n).（四）、线性表的链式存储：1、定义：用一组任意的存储单元存储线性表中的数据元素。2、特点：存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。3、注意：为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。4、单链表：（1）头插入法：LNode*create_LinkList(void)/*头插入法创建单链表,链表的头结点head作为返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head-next=NULL;/*创建链表的表头结点head*/while(1){scanf(“%d”,&data);if(data==32767)break;p=(LNode*)malloc(sizeof(LNode));p–data=data;/*数据域赋值*/p–next=head–next;head–next=p;/*钩链，新创建的结点总是作为第一个结点*/}return(head);}*注意：头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。（2）尾插入法：LNode*create_LinkList(void){Intdata;LNode*head,*p,*q;Head=p=(LNode*)mallpc(sizeof(LNode));p-next=null;while(1){Scanf(“%d”,&data);If(data==32767)break;q=(LNode*)malloc(sizeof(LNode));4q-data=data;q-next=p-next;p-next=q;p=q;}Return(head);}注意：头插入法和尾插入法的时间复杂度都是O(n).(3)单链表的查找：❶按序号查找：单链表只能从链表的头节点出发，沿链域next逐个查询，直到找到第i个节点为止。*算法步骤：ElemTypeGetElem(LNode*L,inti){Intj;LNode*p;P=L-next;j=1;While(p!=null&&ji){P=p-next;j++;}If(j!=i)return(-32768);Elsereturn(p-data);}*注意：当i1时，移动指针p的频率是0次；i在[1,n],是（i-1）次；in时，为n时间复杂度是O（n）。❷按值查询：思想：查找是否有节点值等于给定的值Key的节点？若有，则返回首次找到值为Key的节点的存储位置；否则，返回Null.查找是从开始节点沿着链表逐个与给定值Key比较。算法步骤：LNode*Locate_Node(LNode*L,intKey){//在以L为头节点的单链表中查找值为Key的第一个节点LNode*p=L-next;While(p!=null&&p-data!=key)P=p-next;If(p-data==key)returnp;Else{Printf(“您所要查找的值不存在！\n”);Return(null);}}该算法的时间复杂度是O(n)。（4）单链表的插入：VoidInsert_LNode(LNode*L,intI,ElemTypee){Intj=0;LNode*p,*q;P=L-next;While(p!=null&&ji-1){5P=p-next;j++;}If(ji-1)printf(“i太大或为0”);Else{Q=(LNode*)malloc(sizeof(Lnode));q-data=e;q-next=p-next;p-next=q;}}单链表的插入操作的时间复杂度是O(n).(5)单链表的删除：❶按序号删除：思想：为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p–next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。*算法实现：VoidDelete_LinkList(LNode*L,inti){Intj=1;LNode*p,*q;P=L;q=l-next;While(p-next!=null&&ji){P=q;q=q-next;j++}If(j!=i){Printf(“i太大或等于0”);}else{P-next=q-next;free(q);}}❷按值删除：思想：删除单链表中值为Key的第一个节点。算法：VoidDelete_LinkList(LNode*L,intKey){LNode*p=L,*q=L-next;While(q!=null&&q-data!=Key){P=q;q=q-next;}If(q-data==Key){p-next=q-next;free(q);}Elseprintf(“所要删除的值不存在”);}单链表的删除操作时间复杂度是O（n）。6二、循环链表：1、单循环链表：和单线性链表初链表的合并外其他一致，只不过在语法上要加上两点：❶判断是否是空链表：head-next==head;❷判断是否是表尾结点：p-next==head;2、双向链表：（一）定义：指的是构成链表的每个结点中设立两个指针：一个指向其直接前趋的指针域prior，一个纸箱其直接后继的指针域next。将头节点和尾节点连接起来并称是双向循环链表。（二）特点：*带头节点的双向链表的形式：TypedefstructDulnode{ElemTypedata;StructDulnode*prior,*next;}Dulnode;（三）双向链表的插入：（先右后左顺序）*算法如下：S=（Dulnode*）malloc(sizeof(Dulnode));S-data=e;S-next=p-next;p-next-prior=S;p-next=S;S-prior=p;(四)双向链表的删除：设要删除的结点为p，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。部分语句组如下：p-prior-next=p-next;p-next-prior=p-prior;7free(p);*注意：双向链表与单链表相比，双向链表的操作要同时对某一节点的直接前趋和直接后继进行操作。三、栈：（一）定义：是限制在表的一端进行插入和删除操作的线性表。（二）特点：先进后出。（三）元素：栈顶：运行进行插入、删除的一端；又叫表尾。栈底：又叫表头。（四）栈的顺序表示：指栈的顺序存储结构；用一维数组表示；根据是否可以根据需求增大，分为：静态顺序栈、动态顺序栈。空栈：top=bottom。*栈的动态存储操作：（五）栈的基本操作：——进栈#defineSTACK_SIZE100/*栈初始向量大小*/#defineSTACKINCREMENT10/*存储空间分配增量*/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*栈不存在时值为NULL*/ElemType*top;/*栈顶指针*/intstacksize;/*当前已分配空间，以元素为单位*/}SqStack;(六)栈的操作：——栈的初始化：StatusInit_Stack(void){SqStackS;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));if(!S.bottom)returnERROR;S.top=S.bottom;/*栈空时栈顶和栈底指针相同*/S.stacks