数据结构复习笔记.doc

数据结构复****笔记一、:能被计算机表示、存储和加工处理的一切信息(数值型和非数值型):::::指数据之间的逻辑关系,:::按照某种逻辑关系组织起来的一批数据,按一定的存储方法把它存储在计算机中,:线性结构、集合、树形结构、:仅一个开始结点、仅一个终端结点;其它都是内部结点,且都有且仅有一个前驱和一个后驱(一对一):结构中数据元素只具有“同属于一个集合”:有且仅有一个根结点,其它结点有且仅有一个前驱结点,对于非根结点都存在从根到该结点的一条路径(一对多)::顺序存储结构、::存储空间不连续,:有穷性、确定性、可行性、输入、:程序不一定满足有穷性;:正确、简单、可读、健壮、:事后统计和事前分析、:输入规模、算法效率、输入顺序、机器、(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<…<O(2n)<O(n!)二、:唯一第一数据元素、唯一最后数据元素、:无需为表示数据元素之间的逻辑关系而增加额外存储空间;:预先为数据元素分配空间;:newnode→next=p→next;p→next=:p→next=q→next;:current->prior->next=current->next;current->next->prior=current->prior;:p->prior=current;p->next=current->next;current->next->prior=p;current->next=:顺序表结点总数大概确定,表中结点数目稳定(插删操作少);链表结点数目不预知且动态变化三、:允许插入和删除的一端称为栈顶,另一端称为栈底,:若abc顺序入栈,:在一端进行插入操作(队尾),而另一端进行删除操作的线性表(队头),:(rear+1)%QueueSize==:rear==front6递归算法设计方法:最小规