算法计算量的大小是指算法的复杂性.doc

1. 算法计算量的大小是指算法的复杂性2. 计算机算法指的是解决问题的步骤序列，特性：有穷性，确定性，可执行性3. 同一个算法，实现语言的级别越高。执行效率越低4. 与数据的存储结构无关的是栈；5. 数据的物理结构包括数据元素的表示和数据元素之间关系的表示6. 集合；线性结构；树形结构；图状或网状结构7. 数据的逻辑结构是指数据的组织形式。即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称邻接关系。8. 一个数据结构在计算机中表示（又称映像）称为存储结构。9. 抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_计算机内部如何实现与表示_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。10. 数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度 11. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的_算法；12. 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出。13. ，希尔和简单选择和堆排序是不稳定的；归并和冒泡；直接插入；二分法插入排序；折半插入是稳定的第六章：树和二叉树1.已知前缀表达式和中缀表达式，可以得出唯一的后缀表达式，同理，已知中缀和后缀表达式可以得出唯一的前缀表达式；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层上，最多有2(k-1)个结点；若满二叉树的深度为h，则总结点个数为2h-1；若完全二叉树的总结点个数为n；则其深度为log2n（下取整）+1；# include# include# include# define OVERFLOW -1typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void InitList(LinkList &L)L=(LinkList)malloc(sizeof(LNode);if(!L)exit(OVERFLOW);L-next=NULL;void CreateList(LinkList &L,int n)int i;LinkList p,q;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表q=L;printf(请输入%d个数据:n,n);for(i=0;idata);q-next=p;q=q-next;p-next=NULL;void ListTrave(LinkList L)LinkList p=L-next;while(p)printf(%4d,p-data);p=p-next;printf(n);void GetElem(LinkList L,int i,ElemType &e)int j=1;LinkList p=L-next;while(p&jnext;j+;if(!p|ji)exit(OVERFLOW);e=p-data;printf(%d,p-data);void ListInsert(LinkList &L,int i,ElemType e)int j=0;LinkList p=L,s;while(p&jnext;j+;if(!p|ji-1)exit(OVERFLOW);s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;void ListDelete(LinkList &L,int i,ElemType &e)int j=0;LinkList p=L,q;while(p-next&jnext;j+;if(!p-next|ji-1)exit(OVERFLOW);q=p-next;p-next=q-next;e=p-data;free(q);int ListLength(LinkList L)int i=0;LinkList p=L-next;while(p)i+;p=p-next;return i;void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)LinkList pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);void main()int n;LinkList La,Lb,Lc;InitList(La);InitList(Lb);InitList(Lc);printf(please input the number of n:n);scanf(%d,&n);CreateList(La,n);printf(please input the number of n:n);scanf(%d,&n);CreateList(Lb,n);MergeList(La,Lb,Lc);printf(Lc=);ListTrave(Lc);# include# include# include# define TRUE 1# define FALSE 0# define OVERFLOW -1typedef char Status;typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针BiTNode,*BiTree;void InitBiTree(BiTree &T)/构造空二叉树TT=NULL;void CreateBiTree(BiTree &T)/按先序次序输入二叉树中结点的值（可为字符型或整型，在主程序中定义）/构造二叉链表的二叉树TTElemType ch;scanf(%c,&ch);if(ch=#) T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);/生成根结点if(!T) exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);/构造左子树CreateBiTree(T-rchild);/构造右子树void PreOrder(BiTree T)/先序遍历二叉树Tif(T)printf(%2c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void InOrder(BiTree T)/中序遍历二叉树Tif(T)InOrder(T-lchild);printf(%2c,T-data);InOrder(T-rchild);void PostOrder(BiTree T)/后续遍历二叉树Tif(T)PostOrder(T-lchild);PostOrder(T-rchild);printf(%2c,T-data);void main()BiTree T;Ini