算法计算量大小是指算法复杂性

《算法计算量大小是指算法复杂性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.算法计算量的大小是指算法的复杂性2.计算机算法指的是解决问题的步骤序列，特性：有穷性，确定性，可执行性3.同一个算法，实现语言的级别越高。执行效率越低4.与数据的存储结构无关的是栈；5.数据的物理结构包括数据元素的表示和数据元素之间关系的表示6.集合；线性结构；树形结构；图状或网状结构7.数据的逻辑结构是指数据的组织形式。即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称邻接关系。8.一个数据结构在计算机中表示（又称映像）称为存储结构。9.抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_计算机内部如何实现与表示_无关，

2、即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。10.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度11.数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的_算法；12.一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。13.，希尔和简单选择和堆排序是不稳定的；归并和冒泡；直接插入；二分法插入排序；折半插入是稳定的第六章：树和二叉树1.已知前缀表达式和中缀表达式，可以得出唯一的后缀表达式，同理，已知中缀

3、和后缀表达式可以得出唯一的前缀表达式；2.在二叉树中，根结点表示运算符号，左右子树分别表示运算量，其位置不可互换；3.设度为0,1,2,3的结点数分别为n0,n1,n2,n3；则总结点数为n=n0+n1+n2+n3；总分子树B=0*n0+1*n1+2*n2+3*n3；且满足关系B=n-1；即在二叉树中有性质n0=n2+1；4.节点的度（次数）：指结点的分支数；而数的度：指节点的度的最大值；正如：在二叉树中，二叉树的度不一定为25.丰满树，查找树，平衡树，完全树6.赫夫曼树：若给定n个结点，则构成赫夫曼树的结点总数为2n-1；7.二叉树的第k层上，最

4、多有2(k-1)个结点；若满二叉树的深度为h，则总结点个数为2h-1；若完全二叉树的总结点个数为n；则其深度为{log2n}（下取整）+1；#include#include#include#defineOVERFLOW-1typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidInitList(LinkList&L){L=(LinkList)malloc(sizeof(L

5、Node));if(!L)exit(OVERFLOW);L->next=NULL;}voidCreateList(LinkList&L,intn){inti;LinkListp,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表q=L;printf("请输入%d个数据:",n);for(i=0;idata);q->next=p;q=q->next;}p->

6、next=NULL;}voidListTrave(LinkListL){LinkListp=L->next;while(p){printf("%4d",p->data);p=p->next;}printf("");}voidGetElem(LinkListL,inti,ElemType&e){intj=1;LinkListp=L->next;while(p&&jnext;j++;}if(!p

7、

8、j>i)exit(OVERFLOW);e=p->data;printf("%d",p->data);}voidListInsert(L

9、inkList&L,inti,ElemTypee){intj=0;LinkListp=L,s;while(p&&jnext;j++;}if(!p

10、

11、j>i-1)exit(OVERFLOW);s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;}voidListDelete(LinkList&L,inti,ElemType&e){intj=0;LinkListp=L,q;while(p->next&&jnext;j++;

12、}if(!p->next

13、

14、j>i-1)exit(OVERFLOW);q=p->next;p->next=q->next;