1、数据结构知识点部分整理1. 数据结构的产生（1）计算机的发展：速度快计算机存储容量大应用范围不断拓宽价格降早期计算机主要用于科学计算处理对象：纯数值性的信息。（2）计算机的应用：情报检索60 年代后企业管理乃至人类社会活动的一切领系统工程（3）计算机的处理对象：数值性和非数值性（包括字符、图像、声音）算法（还是要掌握好的一部分）1. 概念：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。2. 算法的特性（1） 有穷性：指有穷的步数，以及有穷的时间（2） 确定性：每条指令必须有确切的含义，且算法只有唯一的一条执行路径，相同的输入只能是相同的输出（3） 可行性
2、：可以通过已经实现的基本运算执行有限次来实现的。（4） 输入：一个算法有零个或多个的输入。（5） 输出：有一个或者多个的输出，输出的是同输入有着某些特定关系的量。3. 算法的描述方法：自然语言、程序流程图、伪代码（又有自然语言又有程序语言）、程序设计语言。4. 算法的设计目标（1） 正确性：明确的无歧义的描述（2） 可读性：便于阅读理解（3） 健壮性：输入数据非法时，算法也能做出处理，而不产生不可预料的结果（4） 高时间效率：算法时间尽量短（5） 低储存量需求：指算法执行过程中所需要的最大存储空间要低。5. 算法效率的度量（1） 时间复杂度：算法的执行时间是指根据该算法编制的程序在计算机上运行
3、时所消耗的时间总量。基本语句：执行次数与整个算法的执行次数成正比的语句，多数情况下它是最深层循环内的语句。T(n)= O(f(n)Eg：语句的执行次数（就是循环的次数）为n2+1，则算法的时间复杂度为T（n）=）O（n2）（2） 空间复杂度：算法的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，它也是衡量算法有效性的一个指标。算法的空间复杂度是对算法的执行过程需要的辅助空间进行度量。通常记作S(n)=O(f(n)其中n为问题的规模（或大小），表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。线性表（重点掌握）1.线性表的定义：线性表(linearlist
4、)是n(n0)个相同类型的数据元素构成的有限序列。其中称n为线性表的长度，当n=0时，表示线性表是一个空表，即表中不包含任何元素。一个有n个数据元素的线性表常表示为：（a1，a2，an）则常把线性表中使用的元素类型用一种通用数据类型标识符ElemType进行抽象，实际使用时可以通过typedef语句把它定义为任何一种具体类型。若线性表中的元素为整数，则可通过下列语句把它定义为整数类型：typedef int ElemType2. 线性表的定义：（1） 序列的顺序性，限制顺序，第一个元素无前期，最后一个无后继，其他元素有且仅有一个前驱和后继（2） 有限性：元素个数的有限，计算机处理的对象是有限的
5、（3） 相同性：元素取自同一个数据对象，每个元素占相同数量的存储单元。（4） 抽象性：元素的类型是抽象的、不具体的，看具体问题。（5） 线性表的逻辑结构：元素之前的前驱后继关系A1称为ai+1的前驱，后者是前者的后继3. 抽象数据类型（掌握）InitList（&L，maxsize，incresize）构造一个容量为maxsize的空线性表LClearList（&L）线性表L存在的前提下将线性表重置为空表ListEmpty（L）在线性表存在的前提下，若L为空表，则返回true，否则返回falseListLength（L）在线性表L存在的前提下，返回L中元素的个数，即线性表的长度LocateEle
6、m（L，e）在表中找到与e相等的第一个值的位序PriorElem（L，cure，&pre-e）cur-e是L的元素，但不是第一个，就用pre-e返回它的前驱，若操作失败，则pre-e无定义。NextElem（L，cur-e，&next_e）cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义ListInsert（&L，i，e）线性表L已存在且1iLengthList(L)，操作结果是在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete（&L，i，e）线性表L已存在且非空，1iLengthList(L)，操作结果是删除L的第i个元
7、素，并用e返回其值，L的长度减1。GetElem(L ，i，&e)线性表L已存在，且1iLengthList(L)，操作结果是用e返回L中第i个元素的值。ListTraverse(L)线性表L已存在，操作结果是依次输出L中的每个数据元素。DestroyList(&L)线性表L已存在，操作结果是撤销线性表L。4. 顺序表（重点掌握）（1）顺序表的定义：用一组地址连续的存储单元一次存储线性表里各个元素的存储结构称为线性表的顺序存储结构。（常用程序设计语言中的一维数组来描述顺序表中数据元素的存储区域，也就是把线性表中相邻的元素存储在数组中相邻的位置）特点:逻辑上相邻的数据元素，其物理位置上也是相邻的
8、。（2）顺序表中程序的存储首址假设每个数据元素占用k个存储单元，loc(ai)表示数据元素ai的存储首址，则线性表中相邻的两个元素ai与ai+1的存储首址1oc(ai)与loc(ai+1)满足下面的关系：loc(ai+1)=1oc(ai)+k (1i n)线性表中第i个元素ai的存储首址为：1oc(ai)=1oc(a1)+(i-1)*k (1i n)由于表中每个元素的存储首址都可由上面的公式计算求得，且计算所需的时间也是相同的，所以访问表中任意元素的时间都相等，具有这一特点的存储结构称为随机存取结构。（3）拓展：ElemType(也有的书上称之为elemtp)是数据结构的书上为了说明问题而用的
9、一个词。它是element type（“元素的类型”）的简化体，ElemType的默认是int型。Incrementsize貌似是增加线性表空间大小的意思Lelem表示访问L结构体中的成员elem，L_elem表示的是一个变量或者结构体的名字静态存储分配的顺序表：# define LIST_INIT_SIZE 100typedef struct ElemType elem LIST_INIT_SIZE; int length; SSqList; 动态存储分配的顺序表：# define LISTINCREMENT 10 typedef struct ElemType *elem; int len
10、gth; int listsize; int incrementsize; SqList; 辨析A线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的；数组的长度是存放线性表的存储空间的长度，一旦存储空间分配后，这个量确定不变。存储结构是数据及其逻辑结构在计算机中的表示存取结构是在某种数据结构上对访问操作时间性能的描述 B顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行访问操作，其时间性能为O(1)。顺序存储：顺序表（重点掌握）sqlist随机存储结构（1） 初始化void InitList_Sq( SqList &L, int xsize=
11、LIST_INIT_SIZE, int incresize=LISTINCREMENT ) L.elem=(ElemType *)malloc(maxsize*sizeof(ElemType); /(这里是某种数据结构，就假设这是一个线性表，它储存的元素的数据类型为ElemType（就像整型，浮点型，或者是自定义型等等），表长为LIST-INIT-SIZE，L是一个线性表，L的elem成员是这个线性表的首元素的地址，这个表达式的意思就是分配一个长度为LIST-INIT-SIZE个ElemType长度的空间并强制转换为ElemType类型的指针，将该指针的地址赋给L.elem。这样L就是一个已经
12、分配过空间的线性表了，它已经有了一个空的存储空间，可以放LIST-INIT-SIZE个ElemType类型的数据) if(!L.elem) exit(1); L.length=0; L.listsize=maxsize; L.incrementsize=incresize; / InitList_Sq（2）求表长（O(1)）int ListLength_Sq(SqList L) return L.length;/ ListLength_Sq（3）查找（O(n)）int LocateElem_Sq( SqList L, ElemType e) for(int i=0;iL. length;i+)
13、 if(L.elemi=e) return i; return -1;（因为C/C+中数组的下标是从0开始，所以当查找失败时不能返回0，而应该返回一个有效下标之外的整数）/LocateElem_Sq（4）前插（时间复杂度为O(n)）bool ListInsert_Sq(SqList &L, int i, ElemType e) int j;if(iL.length) return false; if(L.length=L.listsize) L.elem=(ElemType *)realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemTyp
14、e);if(!L.elem) exit(1); L.listsize+=L.incrementsize; for(j=L.length;ji;j-) L.elemj=L.elemj-1;L.elemi=e; L.length+; return true; / ListInsert_Sq（拓展：A：realloc动态内存调整先判断当前的指针是否有足够的连续空间，如果有，扩大，并且将mem_address返回，如果空间不够，先按照newsize指定的大小分配空间。B：malloc 动态内存分布向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针
15、。C,C+规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针C：sizeof C语言中判断数据类型或者表达式长度符D：incrementsize增量大小，增补一段空间）E：calloc动态内存分配并清零：功能：在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULLF:_alloca，内存分配函数，与malloc,calloc,realloc类似，但是注意一个重要的区别，_alloca是在栈(stack)上申请空间，用完马上就释放。（5）删除（时间复杂度为O(n)）bool ListDelete_Sq(SqList
16、&L,int i, ElemType &e) int j;if(i=L.length) return false; if(L.length=0) return false; （首先判断删除的位置是否合理）e=L.elemi; for(j=i+1;j=L.length-1;j+) L.elem j-1=L.elem j;（元素依次向前移，同时线性表长度减1）L.length-; return true; / ListDelete_Sq（6）取数据元素bool GetElem_Sq(SqList L,int i, ElemType &e) if(iL.length) return false; i
17、f(L.length=0) return false; e=L.elemi; return true; / GetElem_Sq（7）顺序表的遍历（O(n)，n为顺序表的长度，遍历就是打印出这个表里的所有数据元素）Traverse横穿（拓展：coutsetw(10)是给下一个输出的量，设定输出场宽为10个字符，输出量不足10个字符时在左面填空白，输出量宽于10个字符，则按实际需要全部输出，eg，A：coutsetfill(*)setw(5)aendl;则输出：*a 4个*和字符a共占5个位置）B：char x=12345678;char y=123456789abcd;coutsetw(10)
18、xendl; /输出：白白12345678coutxendl; /输出：12345678 coutsetw(10)ynext=NULL;/ InitList_L（2） 求表长int ListLength_L( LinkList L ) LinkList p;int k=0;p=L-next; while(p) k+; p=p-next; return k;/ ListLength_L-运算符叫做“指向结构体成员运算符”，是C语言和C+语言的一个运算符，用处是使用一个指向结构体或对象的指针访问其内成员。（3）查找LNode *LocateElem_L(LinkList L,ElemType e)
19、 LinkList p;p=L-next;while(p&p-data!=e )（意思就是p != NULL的意思，先判断p不为NULL，否则直接p-data，当p为NULL的时候会出异常。）p=p-next;return p;/ LocateElem_L（4）插入两个语句顺序不可以改变，否则不可以进行插入操作bool ListInsert_L( LinkList L, int i, ElemType e)LinkList p,s;int j;p=L; j=0;while(p-next&jnext; j+; if(j!=i-1) return false;if(s=(LNode *)mallo
20、c(sizeof(LNode)=NULL)exit(1);s-data=e;s-next=p-next; p-next=s;return true;/ ListInsert_L（&两边都要是true才会true，逻辑运算符；&与运算，eg：1&0=0,1&1=1,0&0=0,0&1=0；|逻辑或运算，一个满足则true）（5）删除bool ListDelete_L( LinkList L, int i, ElemType &e)LinkList p,q;int j;p=L; j=0;while(p-next&p-next-next&jnext; j+; if(j!=i-1) return fa
21、lse;q=p-next;p-next=q-next;e=q-data; free(q);return true;/ ListDelete_L（while 中的条件表达式中的“p-next-next”是为了保证第i个结点存在）（6） 取元素bool GetElem_L(LinkList L,int i, ElemType &e)LinkList p;int j;p=L; j=0;while(p-next&jnext; j+; if(j!=i) return false;e=p-data;return true;/ GetElem_L取元素操作与删除元素操作基本类同，主要差别是取数据元素时指针定
22、位在第 i个结点，并且不删除ai结点（7） 创建单链表尾插法void CreateList_L_Rear(LinkList &L,ElemType a,int n )LinkList p,q; int i;L=(LinkList)malloc(sizeof(LNode);q=L;for(i=0;idata=ai;q-next=p;q=p;q-next=NULL;/ CreateList_L_Rear头插法void CreateList_L_Front(LinkList &L,ElemType a,int n )LinkList p; int i;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n-1;i=0;i-)p=(LinkList)malloc(sizeof(LNode);p-data=ai;p-next=L-next;L-next=p;/ CreateList_L_Front（8） 单链表的遍历void ListTraverse_L(LinkList L)LinkList p=L-next;while(p) cout setw(6)data;p=p-next;coutnext;free(p1);L=NULL;/ DestroyList_L
