数据结构复习总结..doc

数据结构复习总结 绪论 数据：是对客观事物的符合表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符合的总成。 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项：是数据的不可分割的最小单位。（一个数据元素可由若干个数据项组成） 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 数据的逻辑结构（即数据之间的相互关系）：线性结构、树形结构、图状结构、集合。（4种） 数据的存储结构（物理结构）：顺序存储结构、链式存储结构。（2种） 数据的四种基本的存储方法：顺序存储方法、链式存储方法、索引存储方法、散列存储方法。 数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 存取结构：与存储结构是两个不同的概念。存取结构是在一个数据结构上对查找操作的时间性能的一种描述，通常有两种存取结构：随机存取结构（例如顺序表）和顺序存取结构（例如单链表） 算法的特征：有穷性、确定性、可行性、输入和输出。 算法的时间复杂度（计算） 线性表 线性结构（这里指线性表的逻辑结构）的特点：在数据元素的非空有限集中，（1）存在唯一的“第一元素”（2）存在唯一的“最后元素”（3）除“第一元素”外，集合中的每个元素均只有一个前驱（4）除“最后元素”外，集合中的每个元素均只有一个后继 线性表：是具有相同数据类型的n(n=0)个数据元素的有限序列，是最简单、最基本、也是最常用的一种线性结构。 （1）表中元素具有逻辑上的顺序性； （2）表中元素个数有限； （3）表中元素都是数据元素； （4）表中元素的数据类型都相同； （5）表中元素具有抽象性。 线性表的长度：线性表中元素的个数n(n=0)定义为线性表的长度，n=0时成为空表。 线性表的存储结构（物理结构）有 顺序存储结构：顺序表（具有按数据元素的序号随机存取的特点，时间复杂度为O(1)） 链式存储结构：单链表（数据的存取方式为顺序存取） 其它存储结构：循环链表、双向链表、静态链表 顺序表（线性表的顺序存储表示）的形式描述： 静态分配： #define LISTSIZE 100 //线性表存储空间的初始分配量 Typedef struct{ ElemType elem[LISTSIZE]; int length; }Sqlist; 动态分配： #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 Typedef struct{ ElemType *elem; //存储空间基址，指示线性表的基地址 int length; //当前长度，实际已存元素个数 int listsize; //当前分配的存储容量,以sizeof(ElemType)为单位 } Sqlist; 构造一个空的顺序表 Status InitList Sq(SqList L){ L.elem=(ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } 在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0 int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){ i=1; p=L.elem; while(i=L.length!(*compare)(*p++,e)) ++i; if(i=Length) return I; else return 0; } 算法的时间复杂度为O( ListLength(L) ) 顺序表中插入元素 Status ListInsert_Sq(SqList L,int i,ElemType e){ // 在顺序表L的第 i 个元素之前插入新的元素e, // i 的合法范围为 1≤i≤L.length+1if (i 1 || i L.length+1) return ERROR; // 插入位置不合法 if (L.length = L.listsize) { // 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (Ele