2022年数据结构知识点部分整理.docx

《2022年数据结构知识点部分整理.docx》由会员分享，可在线阅读，更多相关《2022年数据结构知识点部分整理.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 1.数据结构的产生学习必备欢迎下载（1）运算机的进展：速度快运算机储备容量大应用范畴不断拓宽 价格降 早期运算机主要用于科学运算处理对象：纯数值性的信息；（2）运算机的应用：情报检索60 岁月后企业治理乃至人类社会活动的一切领系统工程（3）运算机的处理对象：数值性和非数值性（包括字符、图像、声音）名师归纳总结 - - - - - - -第 1 页,共 11 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载算法（仍是要把握好的一部分）1. 概念：是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个

2、操作；2. 算法的特性（1）有穷性：指有穷的步数,以及有穷的时间（2）确定性：每条指令必需有准确的含义,且算法只有唯独的一条执行路径,相同的输入只能是相同的输出3.（3）可行性：可以通过已经实现的基本运算执行有限次来实现的；、程（4）输入：一个算法有零个或多个的输入；（5）输出：有一个或者多个的输出,输出的是同输入有着某些特定关系的量；算法的描述方法：自然语言、程序流程图、伪代码（又有自然语言又有程序语言）序设计语言；4. 算法的设计目标（1）正确性：明确的无歧义的描述（2）可读性：便于阅读懂得（3）健壮性：输入数据非法时,算法也能做出处理,而不产生不行预料的结果（4）高时间效率：算法时间尽量

3、短（5）低储存量需求：指算法执行过程中所需要的最大储备空间要低；5. 算法效率的度量（1）时间复杂度：算法的执行时间是指依据该算法编制的程序在运算机上运行时所消耗的时间总量；基本语句：执行次数与整个算法的执行次数成正比的语句,多数情形下它是最深层循环内的语句；Tn= Ofn n2+1,就算法的时间复杂度为Eg：语句的执行次数（就是循环的次数）为T（n）=）O（n2）（2）空间复杂度：算法的空间复杂度是对一个算法在运行过程中暂时占用储备空间大小的度量,它也是衡量算法有效性的一个指标；算法的空间复杂度是对算法的执行过程需要的帮助空间进行度量；通常记作Sn=Ofn 其中 n 为问题的规模（或大小）

4、,表示随着问题规模 储量的增长率与 fn的增长率相同；线性表（重点把握）n 的增大,算法运行所需存1.线性表的定义：线性表 linearlist 是 nn0个相同类型的数据元素构成的有限序列；其中称 n 为线性表的长度,当 n=0 时,表示线性表是一个空表,即表中不包含任何元素；一个有 n 个数据元素的线性表常表示为：（a1,a2, , an）就常把线性表中使用的元素类型用一种通用数据类型标识符ElemType 进行抽象,实际使用时可以通过 typedef 语句把它定义为任何一种详细类型；如线性表中的元素为整数,就可通过以下语句把它定义为整数类型：typedef int ElemType 名师

5、归纳总结 2.线性表的定义：第 2 页,共 11 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载（1）序列的次序性,限制次序,第一个元素无前期,最终一个无后继,其他元素有且仅有一个前驱和后继（2）有限性：元素个数的有限,运算机处理的对象是有限的（3）相同性：元素取自同一个数据对象,每个元素占相同数量的储备单元；（4）抽象性：元素的类型是抽象的、不详细的,看详细问题；（5）线性表的规律结构：元素之前的前驱后继关系A1称为 ai+1的前驱,后者是前者的后继3.抽象数据类型（把握）maxsize 的空线性表L InitList（ &L,maxsize

6、,incresize）构造一个容量为ClearList（&L）线性表 L 存在的前提下将线性表重置为空表ListEmpty（L）在线性表存在的前提下,如 L 为空表,就返回 true ,否就返回 false ListLength（L）在线性表 L存在的前提下,返回 L 中元素的个数,即线性表的长度LocateElem（L,e）在表中找到与 e 相等的第一个值的位序PriorElem（L, cure,&pre -e）cur -e 是 L 的元素,但不是第一个,就用 pre-e 返回它的前驱,如操作失败,就 pre-e 无定义；NextElem（L,cur-e,&next_e ）cur_e 是 L

7、 的元素,但不是最终一个,就用 next_e 返回它的后继,否就操作失败,next_e 无定义ListInsert（&L,i,e）线性表 L 已存在且 1iLengthListL,操作结果是在 L 的第 i 个元素之前插入新的元素 e, L的长度增 1；ListDelete（&L,i,e）线性表 L 已存在且非空,1iLengthListL,操作结果是删除 L的第 i 个元素,并用 e 返回其值, L 的长度减 1；GetElemL ,i, &e线性表 L 已存在,且 1 iLengthListL,操作结果是用 e 返回 L 中第 i 个元素的值；ListTraverseL线性表 L 已存在,

8、操作结果是依次输出L 中的每个数据元素；4.DestroyList&L线性表 L 已存在,操作结果是撤销线性表L；次序表（重点把握）（1）次序表的定义：用一组地址连续的储备单元一次储备线性表里各个元素的储备结 构称为线性表的次序储备结构；（常用程序设计语言中的一维数组来描述次序表中数据 元素的储备区域,也就是把线性表中相邻的元素储备在数组中相邻的位置）特点 :规律上相邻的数据元素,其物理位置上也是相邻的；（2）次序表中程序的储备首址假设每个数据元素占用k 个储备单元, locai表示数据元素ai 的储备首址,就线性表中相邻的两个元素ai 与 ai+1 的储备首址1ocai与 locai+1满意

9、下面的关系：locai+1=1ocai+k 1i n 线性表中第 i 个元素 ai 的储备首址为：1ocai=1oca1+i-1*k 1i n 由于表中每个元素的储备首址都可由上面的公式运算求得,且运算所需的时间也是相同名师归纳总结 的,所以拜访表中任意元素的时间都相等,具有这一特点的储备结构称为随机存取结构；第 3 页,共 11 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载（3）拓展： ElemType也有的书上称之为elemtp 是数据结构的书上为了说明问题而用的一个词；它是 element type （“ 元素的类型”）的简化体, El

10、emType 的默认是 int 型；Incrementsize 貌似是增加线性表空间大小的意思Lelem 表示拜访 L 结构体中的成员 静态储备安排的次序表：# define LIST_INIT_SIZE 100 typedef struct elem ,L_elem 表示的是一个变量或者结构体的名字ElemType elem LIST_INIT_SIZE; int length; SSqList; 动态储备安排的次序表：# define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; int

11、incrementsize; SqList; 辨析A 线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个 量是变化的； 数组的长度是存放线性表的储备空间的长度,一旦储备空间安排后,这个量确定不变；储备结构是数据及其规律结构在运算机中的表示 存取结构是在某种数据结构上对拜访操作时间性能的描述B 次序表是一种随机存取的储备结构” 的含义为：在次序表这种储备结构上进行拜访 操作,其时间性能为 O1；次序储备：次序表（重点把握）sqlist 随机储备结构（1）初始化void InitList_Sq SqList &L, int xsize=LIST_INIT_SIZE, int

12、 incresize=LISTINCREMENT L.elem=ElemType *mallocmaxsize*sizeofElemType; / 这里是某种数据结构,就假设这是一个线性表,它储存的元素的数据类型为ElemType（就像整型,浮点型,或者是自定义型等等）,表长为LIST-INIT-SIZE, L 是一个线性表, L 的 elem 成员是这个线性表的首元素的地址,这个表达式的意思就是安排一个长度为LIST-INIT-SIZE个 ElemType 长度的空间并强制转换为ElemType 类型的指针,将该指针的地址赋给L.elem；这样 L就是一个已经安排过空间的线性表了,它已经有了

13、一个空的储备空间,可以放 LIST-INIT-SIZE个 ElemType 类型的数据 if.L.elem exit1; L.length=0; L.listsize=maxsize; 名师归纳总结 L.incrementsize=incresize; / InitList_Sq 第 4 页,共 11 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载（2）求表长（ O1）int ListLength_SqSqList L return L.length; / ListLength_Sq （3）查找（ On）int LocateElem_Sq Sq

14、List L, ElemType e forint i=0;iL. length;i+ ifL.elemi=e return i; 0 开头,所以当查找失败时不能返回0,return -1;（ 由于 C/C+中数组的下标是从而应当返回一个有效下标之外的整数）/LocateElem_Sq （4）前插（时间复杂度为 On）bool ListInsert_SqSqList &L, int i, ElemType e int j; ifiL.length return false; ifL.length=L.listsize L.elem=ElemType *reallocL.elem,L.lists

15、ize+L.incrementsize*sizeofElemType; if.L.elem exit1; L.listsize+=L.incrementsize; forj=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 个字节的内存

16、空间；返回类型是 void* 类型； void* 表示未确定类型的指针；过类型转换强制转换为任何其它类型的指针C,C+规定, void* 类型可以通C：sizeof C语言中判定数据类型或者表达式长度符D：incrementsize增量大小,增补一段空间）E：calloc 动态内存安排并清零：功 能：在内存的动态储备区中安排 n 个长度为 size 的连续空间, 函数返回一个指向安排起始地址的指针；假如安排不胜利,返回 NULL F: _alloca,内存安排函数,与 malloc,calloc,realloc 类似 ,但是留意一个重要的区分, _alloca 是在栈 stack上申请空间,用

17、完立刻就释放；名师归纳总结 - - - - - - -第 5 页,共 11 页精选学习资料 - - - - - - - - - （5）删除（时间复杂度为On）学习必备欢迎下载bool ListDelete_SqSqList &L,int i, ElemType &e int j;ifi=L.length return false; ifL.length=0 return false; （第一判定删除的位置是否合理）e=L.elemi; forj=i+1;j=L.length-1;j+ L.elem j-1=L.elem j;（元素依次向前移,同时线性表长度减 1）L.length-; retu

18、rn true; / ListDelete_Sq （6）取数据元素bool GetElem_SqSqList L,int i, ElemType &e ifiL.length return false; ifL.length=0 return false; e=L.elemi; return true; / GetElem_Sq （7）次序表的遍历（On,n 为次序表的长度,遍历就是打印出这个表里的全部数据元 素）Traverse横穿（拓展： coutsetw10 是给下一个输出的量,设定输出场宽为 10 个字符,输出量不足 10 个字符时在左面填空白,输出量宽于 10 个字符,就按实际需要

19、全部输出, eg,A：coutsetfill*setw5aendl; 就输出： *a 4 个* 和字符 a 共占 5 个位置）B：char x=12345678; char y=123456789abcd; coutsetw10xendl; / 输出：白白12345678 coutxendl; / 输出： 12345678 coutsetw10ynext=NULL; / InitList_L （2）求表长 int ListLength_L LinkList L LinkList p;int k=0;p=L-next; whilep k+; p=p-next; return k; / ListL

20、ength_L -运算符叫做“ 指向结构体成员运算符”,是 C语言和 C+语言的一个运算符,用处是使用一个指向结构体或对象的指针拜访其内成员；（3）查找LNode *LocateElem_LLinkList L,ElemType e LinkList p; p=L-next; whilep&p-data.=e （意思就是p .= NULL的意思,先判定p 不为 NULL,否就直接p-data,当 p 为 NULL的时候会出反常； ）p=p-next; return p; / LocateElem_L 名师归纳总结 - - - - - - -第 8 页,共 11 页精选学习资料 - - - -

21、- - - - - 学习必备 欢迎下载（4）插入两个语句次序不行以转变,否就不行以进行插入操作bool ListInsert_L LinkList L, int i, ElemType e LinkList p,s; int j; p=L; j=0; whilep-next&jnext; j+; ifj.=i-1 return false; ifs=LNode *mallocsizeofLNode=NULL exit1; s-data=e; s-next=p-next; p-next=s; return true; / ListInsert_L （ & 两 边 都 要 是 true 才 会 t

22、rue , 逻 辑 运 算 符 ； & 与 运 算 , 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; 名师归纳总结 - - - - - - -第 9 页,共 11 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载whilep-next&p-next-next&jnext; j+; ifj.=i-1 return false; q=p-next; p-nex

23、t=q-next; e=q-data; freeq; return true; / ListDelete_L（while 中的条件表达式中的“p-next-next ” 是为了保证第i 个结点存在）（6）取元素bool GetElem_LLinkList L,int i, ElemType &e LinkList p; int j; p=L; j=0; whilep-next&jnext; j+; ifj.=i return false; e=p-data; return true; / GetElem_L （7）取元素操作与删除元素操作基本类同,主要差别是取数据元素时指针定位在第i个结点,并

24、且不删除ai 结点创建单链表尾插法void CreateList_L_RearLinkList &L,ElemType a,int n LinkList p,q; int i; L=LinkListmallocsizeofLNode; q=L; fori=0;idata=ai; q-next=p; q=p; q-next=NULL; / CreateList_L_Rear 头插法void CreateList_L_FrontLinkList &L,ElemType a,int n LinkList p; int i; L=LinkListmallocsizeofLNode; L-next=NU

25、LL; fori=n-1;i=0;i- 名师归纳总结 - - - - - - -第 10 页,共 11 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载 p=LinkListmallocsizeofLNode; p-data=ai; p-next=L-next; L-next=p; / CreateList_L_Front （8）单链表的遍历void ListTraverse_LLinkList L LinkList p=L-next; whilep cout setw6data; p=p-next; coutnext; freep1; L=NULL; / DestroyList_L 名师归纳总结 - - - - - - -第 11 页,共 11 页