自考数据结构重点(２０１4整理）第一章概论１、瑞士计算机科学家沃思提出：算法+数据结构=程序。
算法就是对数据运算得描述，而数据结构包括逻辑结构与存储结构。
由此可见，程序设计得实质就是针对实际问题选择一种好得数据结构与设计一个好得算法,而好得算法在很大程度上取决于描述实际问题得数据结构。
２、数据就是信息得载体。
数据元素就是数据得基本单位。
一个数据元素可以由若干个数据项组成，数据项就是具有独立含义得最小标识单位.数据对象就是具有相同性质得数据元素得集合。
3、数据结构指得就是数据元素之间得相互关系，即数据得组织形式。
数据结构一般包括以下三方面内容：数据得逻辑结构、数据得存储结构、数据得运算①数据得逻辑结构就是从逻辑关系上描述数据,与数据元素得存储结构无关，就是独立于计算机得。
数据得逻辑结构分类:线性结构与非线性结构②数据元素及其关系在计算机内得存储方式，称为数据得存储结构(物理结构）。
数据得存储结构就是逻辑结构用计算机语言得实现，它依赖于计算机语言。
③数据得运算。
最常用得检索、插入、删除、更新、排序等。
4、数据得四种基本存储方法：顺序存储、链接存储、索引存储、散列存储(１）顺序存储:通常借助程序设计语言得数组描述。
(2）链接存储：通常借助于程序语言得指针来描述。
（3）索引存储：索引表由若干索引项组成。
关键字就是能唯一标识一个元素得一个或多个数据项得组合。
(4）散列存储：该方法得基本思想就是:根据元素得关键字直接计算出该元素得存储地址.5、算法必须满足5个准则：输入,０个或多个数据作为输入;输出，产生一个或多个输出；有穷性，算法执行有限步后结束;确定性，每一条指令得含义都明确;可行性，算法就是可行得。
算法与程序得区别:程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定得符号语言来描述。
目前常用得描述算法语言有两类:类Pascaｌ与类C.６、评价算法得优劣:算法得"正确性＂就是首先要考虑得.此外,主要考虑如下三点：ﻫ①执行算法所耗费得时间，即时间复杂性；②执行算法所耗费得存储空间，主要就是辅助空间，即空间复杂性；③算法应易于理解、易于编程，易于调试等，即可读性与可操作性。
以上几点最主要得就是时间复杂性,时间复杂度常用渐进时间复杂度表示。
7、算法求解问题得输入量称为问题得规模,用一个正整数n表示.8、常见得时间复杂度按数量级递增排列依次为：常数阶０（1）、对数阶0(ｌog2n)、线性阶0（n）、线性对数阶0(nl ｏg2n）、平方阶0(n2）立方阶０（n3)、…、ｋ次方阶0（nｋ）、指数阶０(2ｎ)与阶乘阶0（ｎ！)。
９、一个算法得空间复杂度Ｓ(ｎ）定义为该算法所耗费得存储空间，它就是问题规模ｎ得函数,它包括存储算法本身所占得存储空间、算法得输入输出数据所占得存储空间与算法在运行过程中临时占用得存储空间。
第二章线性表1、数据得运算就是定义在逻辑结构上得，而运算得具体实现就是在存储结构上进行得.2、只要确定了线性表存储得起始位置,线性表中任意一个元素都可随机存取,所以顺序表就是一种随机存取结构。
3、常见得线性表得基本运算：(1)置空表ＩnｉtLiｓt（L) 构造一个空得线性表L。
（2）求表长ＬistLｅngtｈ（L)求线性表L中得结点个数,即求表长。
（3)GetＮｏde(L,ｉ）取线性表L中得第i个元素.ﻫ（4)LoｃateNode(L，x）在L中查找第一个值为x 得元素，并返回该元素在L中得位置。
若L中没有元素得值为x ,则返回0值。
ﻫ(5）ＩnｓerｔList(L,ｉ，x)在线性表Ｌ得第i个元素之前插入一个值为x 得新元素,表Ｌ得长度加１.（6)DeletｅＬｉｓt(L，i)删除线性表L得第i个元素,删除后表L得长度减1.4、顺序存储方法：把线性表得数据元素按逻辑次序依次存放在一组地址连续得存储单元里得方法。
顺序表(Sequeｎtial Lisｔ):用顺序存储方法存储得线性表称为顺序表.顺序表就是一种随机存取结构，顺序表得特点就是逻辑上相邻得结点其物理位置亦相邻。
5、顺序表上实现得基本运算:（1）插入:该算法得平均时间复杂度就是Ｏ（ｎ),即在顺序表上进行插入运算,平均要移动一半结点（n/２）。
（2）删除：顺序表上做删除运算，平均要移动表中约一半得结点（n-1)/2,平均时间复杂度也就是Ｏ(n）。
6、采用链式存储结构可以避免频繁移动大量元素。
一个单链表可由头指针唯一确定，因此单链表可以用头指针得名字来命名.①生成结点变量得标准函数 p＝( ＬisｔNｏde ＊)malloc（siｚeｏf(LiｓtNｏde））；//函数mａｌlｏc分配一个类型为ListNode得结点变量得空间，并将其首地址放入指针变量p中②释放结点变量空间得标准函数fｒee(p)；//释放p所指得结点变量空间③结点分量得访问方法二:p-﹥data与ｐ—﹥ｎｅxt④指针变量p与结点变量＊p得关系：指针变量p得值——结点地址，结点变量*p得值——结点内容７、建立单链表:(1) 头插法建表：算法：p=（LｉstNode ＊）ｍalloｃ(ｓizeof（LisｔNode））;①／/生成新结点p-〉ｄata=ch；②／／将读入得数据放入新结点得数据域中p－〉ｎext=head；③ﻫｈｅad＝p;④ﻫ(2) 尾插法建表:算法: p=（LｉsｔNodｅ *）maｌloc(sizeｏｆ(LｉstNode)）; ①／/生成新结点ﻫ p-〉data=ch; ②/／将读入得数据放入新结点得数据域中if （hｅaｄ=＝NULＬ)heａd＝ｐ;//新结点插入空表ﻫ eｌｓｅｒｅaｒ—>next＝p;③//将新结点插到＊r之后ﻫ re ａr=p;④//尾指针指向新表尾（3）尾插法建带头结点得单链表：头结点及作用：头结点就是在链表得开始结点之前附加一个结点.它具有两个优点:⒈由于开始结点得位置被存放在头结点得指针域中,所以在链表得第一个位置上得操作就与在表得其它位置上操作一致,无须进行特殊处理；ﻫ⒉无论链表就是否为空，其头指针都就是指向头结点得非空指针（空表中头结点得指针域空)，因此空表与非空表得处理也就统一了.头结点数据域得阴影表示该部分不存储信息.在有得应用中可用于存放表长等附加信息。
具体算法:r＝hｅad；// 尾指针初值也指向头结点ﻫ while（(ch=gｅtcｈar（）)！=’\n＇）｛ﻫｓ＝（ListNode ＊)malloc（ｓｉｚeof(ＬistNodｅ））；/／生成新结点ﻫｓ－＞data=ｃｈ；//将读入得数据放入新结点得数据域中r—>ｎeｘt=s；r=s；}ｒ—〉next=NULL;/／终端结点得指针域置空,或空表得头结点指针域置空以上三个算法得时间复杂度均为O(n)。
8、单链表上得查找：（带头结点)（1)按结点序号查找：序号为0得就是头结点。
算法：p=head;j=０;//从头结点开始扫描ｗhiｌe（p—>nｅxt＆＆ｊ<i）{//顺指针向后扫描，直到p—＞ｎｅxｔ为NULL或i=j为止ﻫp=p—>nｅｘt；ﻫｊ＋＋；}if（i=＝j）ﻫreｔuｒｎ p;//找到了第i个结点eｌsｅｒｅｔurn NULL;//当ｉ＜0或ｉ＞０时,找不到第i个结点时间复杂度:在等概率假设下，平均时间复杂度为：为n／２=O(ｎ)(2)按结点值查找：具体算法：LｉstＮoｄe *p＝heａd—>next；/／从开始结点比较.表非空，p初始值指向开始结点whｉle（ｐ&＆p－＞ｄata!=key）//直到p为ＮULＬ或p－〉ｄatａ为key为止p=ｐ->next；//扫描下一结点rｅtuｒn ｐ；//若p=NULL,则查找失败，否则p指向值为ｋey得结点时间复杂度为:O（ｎ）９、插入运算：插入运算就是将值为x得新结点插入到表得第i个结点得位置上,即插入到ａi－１与a i之间。
ﻫs=（ListNoｄe *）malloc(ｓｉzeｏf(LisｔNoｄｅ））；②ｓ－>data=ｘ；③s－>next=p—>nｅxt④；p—>next=s;⑤算法得时间主要耗费在查找结点上，故时间复杂度亦为O（n）。
10、删除运算ﻫｒ=p—＞nexｔ;②／/使r指向被删除得结点a iﻫ p—＞next=r—>ｎext③；//将a i从链上摘下ﻫfreｅ(ｒ）;④//释放结点ａｉ得空间给存储池算法得时间复杂度也就是O（n). ｐ指向被删除得前一个结点。
ﻫ链表上实现得插入与删除运算,无须移动结点,仅需修改指针。
11、单循环链表—在单链表中，将终端结点得指针域NＵLL改为指向表头结点或开始结点即可。
判断空链表得条件就是hｅad＝=head->nexｔ；12、仅设尾指针得单循环链表:用尾指针reａr表示得单循环链表对开始结点ａ1与终端结点a n查找时间都就是O（1)。
而表得操作常常就是在表得首尾位置上进行，因此,实用中多采用尾指针表示单循环链表。
判断空链表得条件为rear ＝=rｅar->nｅxt；13、循环链表:循环链表得特点就是无须增加存储量,仅对表得链接方式稍作改变，即可使得表处理更加方便灵活.若在尾指针表示得单循环链表上实现,则只需修改指针，无须遍历,其执行时间就是O（1)。
具体算法：LinkList Connect（ＬinkＬisｔ A，ＬinkList Ｂ） {//假设Ａ,B为非空循环链表得尾指针LinkＬist p=Ａ—>ｎeｘt；//①保存A表得头结点位置Ａ－〉next=B-〉next－>next；//②B表得开始结点链接到Ａ表尾ﻫ free(B-＞next）；/／③释放B表得头结点B－>next=p;／/④ﻫ return B；／/返回新循环链表得尾指针循环链表中没有ＮULL指针。
涉及遍历操作时,其终止条件就不再就是像非循环链表那样判别p或p—〉ｎexｔ就是否为空，而就是判别它们就是否等于某一指定指针,如头指针或尾指针等。
在单链表中,从一已知结点出发，只能访问到该结点及其后续结点,无法找到该结点之前得其它结点。
而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现.1４、双向链表：双(向)链表中有两条方向不同得链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋得指针域pｒior.①双链表由头指针hｅad惟一确定得。
ﻫ②带头结点得双链表得某些运算变得方便。
③将头结点与尾结点链接起来，为双（向）循环链表.15、双向链表得前插与删除本结点操作①双链表得前插操作void DＩｎserｔBeｆoｒe(DLisｔNoｄe ＊p，DａｔaTyｐe x){//在带头结点得双链表中，将值为ｘ得新结点插入*p之前,设ｐ≠NＵＬLDListNｏｄe ＊s=ｍａllｏc（sizeof(DLisｔNｏdｅ）)；//①s—〉ｄatａ=ｘ；//②s-〉prioｒ=ｐ-〉priｏr；//③s—〉neｘt=ｐ;//④ﻫ p—〉prｉｏｒ－〉ｎexｔ=ｓ;/／⑤p->prior=ｓ；//⑥ﻫ}ﻫ②双链表上删除结点＊p自身得操作voｉd DDeleteNoｄｅ（DListNode ＊ｐ）{／/在带头结点得双链表中,删除结点*p，设*p为非终端结点ﻫ p-〉pｒｉor-＞next=ｐ—〉ｎext;/／①p-〉next—＞prior=p－〉ｐriｏr;/／②free（p）;／／③｝与单链表上得插入与删除操作不同得就是,在双链表中插入与删除必须同时修改两个方向上得指针。