数据结构知识点整理(清华大学出版社).doc
《数据结构知识点整理(清华大学出版社).doc》由会员分享，可在线阅读，更多相关《数据结构知识点整理(清华大学出版社).doc（12页珍藏版）》请在冰点文库上搜索。
第一章绪论
1.数据结构:
主要研究非数值计算问题中计算机的操作对象有哪些结构（逻辑结构）、这些结构在计算机中的表示及其操作的定义和实现问题。
2.逻辑结构：
不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。
通常说的数据结构即此义。
分类：
如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则（一对多）形成一个树形数据结构，城市间据通路（多对多）形成图状结构，此外还有集合结构（除同属一个集合外，无其它关联），共四类
3.数据结构（数据元素及关系/结构）在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。
4.顺序存储结构：
关系采取顺序映像表示，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。
此时物理结构对应一个数组。
优点:
可根据起始地址随机访问各元素。
缺点:
需事先分配一足够大空间，且插入删除结点需移动大量数据。
链式存储结构：
关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。
优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。
5.度量指标：
算法运行时间主要取决于基本操作的执行次数（频度），执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。
6.时间复杂度：
频度函数的增长率基本与函数中“关键项”（去掉低次项和常数项）的增长率相同，故可用“关键项”反映算法效率。
假设关键项为f（n），用T（n）=O（f（n））表示算法时间增长率与f（n）增长率同阶。
称O（f（n））为算法的渐近时间复杂度，简称时间复杂度。
f（n）的增长率为f（n+1）/f（n），如对复杂度为O（n）的算法其运行时间随问题规模增长率为1+1/n,复杂度为O
（1）的算法时间增长率为1。
7.按增长率由小至大的顺序排列下列各函数 （2/3）n-2100-㏒2n-n1/2-n-n㏒2n-n3/2-2n-n!
-nn
第二章线性表
1.顺序表：
借助元素在存储器中位置上的”相邻”关系表示数据元素间具有的关系，如此存储的线性表称为顺序表。
顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动（表尾除外）；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。
2.线性链表:
采用链式存储结构的线性表对应一个链表。
结点包含数据域和指针域两部分。
链表名指向第一个结点（头指针），尾结点指针域值为NULL。
链表优点是空间利用好,插入删除不移动数据,表头表尾操作快（改进的单链表）,位置概念强；缺点是需要顺序访问各元素，位序概念弱。
顺序表相关程序：
#defineLIST_INIT_SIZE100//…
#defineLISTINCREMENT10//…
typedef*****ElemType;
typedefstruct{
ElemType*elem;//存储空间基址
intlength;//…
intlistsize;//……
}SqList；
SqListLa,Lb,Lc;
StatusInitList_Sq（SqList&L）
{//构造空线性表L
L.elem=（ElemType*）malloc（LIST_INIT_SIZE
*sizeof（ElemType））
if（L.elem==0） exit（OVERFLOW）;
L.length=0;//初始化表长为0，“空”表
L.listsize=LIST_INIT_SIZE;//初始化存储容量
return（OK）;
}//InitList_Sq
voidListDelete（SqList&L,inti,ElemType&e）
{//在顺序表L中删除第ｉ个元素，用ｅ返回其值．
//i的合法值是[1，ListLength（L）]
if（i<1||i>L.length）returnERROR;//删除位置不合理
ElemType*p=&L.elem[i-1],*q=L.elem+L.length-1;
e=*p;
while（p --L.length;
returnOk;
}//ListDelete_Sq
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{//在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1
if（i<1||i>L.length+1）returnERROR;//插入不合法
if（L.length>=L.listsize）
{//表满，增加存储容量
ElemType*newbase=（ElemType*）realloc
（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））
if（!
newbase） exit（OVERFLOW）;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
ElemType*q=&L.elem[i-1],*p=&L.elem[L.length-1];
while（p>=q）
{*（p+1）=*p;--p;}//插入位置后的元素右移
*q=e;
++L.length;
returnOK;
}//ListInsert_S
线性表相关程序：
typedef*****ElemType;
typedefstructLNode{
ElemTypedata;//数据域
structLNode*next;//指针域
}LNode,*LinkList;//默认带头结点,需说明
LNodenode1;LinkListLa；
StatusGetElem_L（LinkListL,inti,ElemType&e）
{//L为带头结点的单链表的头指针。
第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
LNode*p=L->next;//p指向”第1个”结点，
intj=1; //j为指向结点的位序
while（p&&j{//顺序查找，只要p不空且未到第i结点就前进
p=p->next;
++j;
}
if（!
p）returnERROR;//第i个元素不存在
e=p->data;//取第i个元素
returnOK；
}
StatusListInsert_L（LinkList&L,inti,ElemTypee）
{//向链表L中第i个位置插入e
LNode*p=L;intj=0;/*p始终指向第j个结点*/
while（p&&jnext;++j;}//寻找第i-1个结点
if（!
p）returnERROR;
LNode*temp;
temp=（LNode*）Malloc（sizeof（LNode））;
if（!
temp） exit（OVERFLOW）;
temp->data=e;
temp->next=p->next;
p->next=temp;
return（OK）;
}//ListInsert_L
StatusListDelete_L（LinkList&L,inti,ElemType&e）
{
LNode*p=L,*q;intj=0;/*p始终指向第j个结点*/
while（p&&jnext;++j;}//寻找第i-1个结点，j最终为i-1,除非到表尾p空
if（!
p||!
p->next）
returnERROR;//第i个或更前结点不存在
q=p->next;
e=q->data;
p->next=q->next;
free（q）;
return（OK）;
}//ListDelete_L
StatusCreateList_L（LinkList&L,intn）
{//逆位序输入n个元素的值，建立带头结点的单链表L。
LNode*p;
L=（LinkList）malloc（sizeof（LNode））;L->next=NULL;
for（inti=1;i<=n;++i）
{
p=（LNode*）malloc（sizeof（LNode））;//LNode*等同LinkList
scanf（“…”,&p->data）;
p->next=L->next;
L->next=p;//插入到表头
}
}//CreateList_L
相关两表的归并
voidMergeList_Sq（SqListLa,SqListLb,Sqlist&Lc）
{//归并非降顺序表La与Lb构成非降顺序表Lc
Lc.listsize=Lc.length=La.length+Lb.length;
Lc.elem=（ElemType*）
malloc（Lc.listsize*sizeof（ElemType））;
If（!
Lc.elem） exit（OVERFLOW）;//存储分配失败
ElemType*pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;
ElemType*pa_last=La.elem+La.listsize-1;
ElemType*pb_last=Lb.elem+La.listsize-1;
while（pa<=pa_last&&pb<=pb_last）
{//归并
if（*pa<=*pb） *pc++=*pa++;
else *pc++=*pb++;
}
while（pawhile（pb}//MergeList_Sq
StatusListMerge_SortedL
（SortedSqListLa,SortedSqListLb,SortedSqList&Lc）
{//将两个有序顺序表La与Lb归并为有序顺序表Lc
intla_len=ListLength_Sq（La）;
intlb_len=ListLength_Sq（Lb）;
inti=1,j=1,k=1;
ElemTypea,b;
InitList_Sq（Lc）;
while（i<=la_len&&j<=lb_len）
{//归并
GetElem_Sq（La,i,a）;GetElem_Sq（Lb,j,b）;
if（aelse{ListInsert_Sq（Lc,k++,b）;++j;}
}
while（i<=la_len）//插入La的剩余元素
{GetElem_Sq（La,i++,a）;ListInsert_Sq（Lc,k++,a）;}
while（j<=lb_len）//插入Lb的剩余元素
{GetElem_Sq（Lb,j++,b）;ListInsert_Sq（Lc,k++,b）;}
returnOK;
}//复杂度O（ListLength（La）+ListLength（Lb）,因只在表尾插入）
3.注意链表中next指针的应用，如插入，删除等操作各个元素的链接。
4.顺序表的就地逆置思路：
分别设两个指针p与q指向第一个和最后一个元素，当p单链表的就地逆置思路：
令指针p指向首元结点,头结点断开,{将p所指结点插入到表头后,p后移,直至p为空}
StatusListInverse_Sq（SqList&L）
{//顺序表就地逆置
ElemType*p,*q;
ElemTypee;
p=L.elem;q=L.elem+L.length-1;
while（p{
temp=*p;
*p=*q;
*q=temp;
++p;--q;
}
returnOK;
}
StatusListInverse_L（LinkList&L）
{
//思路:
令指针p指向首元结点,头结点断开,{将p所指结点插入到表头后,p后移,至p空}
LNode*p,*q;
p=L->next;
L->next=NULL;
while（p!
=NULL）
{
q=p->next;//令q指向p的后继结点，以便以后p后移接下来两句将p所指向节点插入到头结点后
p->next=L->next;
L->next=p;
p=q;//q后移
}
returnOK;
}
有序顺序表插入
StatusListInsert_SortedSq（SqList&L,ElemTypee）
{//在非降顺序表L中插入元素e,使得L中各元素仍然非降。
注意插入位置据e求得
//思路：
从最后一个元素开始，只要它比待插入元素大就后移。
条件不成立时退出循环，将e插入当前位置后即可。
顺序表插入操作莫忘表满的处理。
只要是顺序表的插入操作就需要判断是否表满，对于链表则无此要求
if（L.length>=L.listsize）
{//表满，增加存储容量
ElemType*newbase=（ElemType*）
realloc（L.elem,（L.listsize+LISTINCREMENT）
*sizeof（ElemType））;
if（!
newbase）exit（OVERFLOW）;
L.elem=newbase;L.listsize+=LISTINCREMENT;
}
//下面从最后一个元素开始，只要大于e就后移，最后插入当前位置后
p=L.elem+L.length-1;
while（p>=L.elem&&*p>e）{*（p+1）=*p;--p;}
*（p+1）=e;
++L.length;//表长加1
returnOK;
}
5.循环链表、双向链表、双向循环链表的特点和基本操作。
主要是插入删除的相关指针操作。
//---线性表的双向（循环）链表存储结构---
typedefstructDuLNode
{
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
}DuLNode,*DuLinkList;
StatusListInsert_DuL（DuLinkList&L,inti,ElemType&e）
{//在带头结点的双向链表L的第i个位置插入e,1≤i≤表长+1
DuLNode*p=L;intj=0;
while（jnext;++j;}
if（!
p）returnERROR;
s=（DuLNode*）malloc（sizeof（DuLNode））;
if（!
s）exit（OVERFLOW）;
s->data=e;
s->prior=p;
s->next=p->next;//记:
注意分析指针改变
p->next->prior=s;
p->next=s;//次序对结果的影响
returnOK;
}
另外看下多项式的相关课件，老师复习提纲上有写这方面的代码。
第三章栈和队列
1.栈（Stack）是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行，为形象起见，称允许操作端为栈顶（Top），另一端为栈底（base），注意Top指向待插入位置。
特性:
LastInFirstOut后进先出//总是访问最近插入的一个//按插入顺序倒着访问。
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedef?
?
SElemType;//栈元素类型
typedefstruct{
SElemType*base;//栈底指针
SElemType*top;//栈顶指针
intstacksize;//栈容量
}SqStack
StatusInitStack（SqStack&S）
{//构造空栈S
S.base=（SElemType*）
malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;//空栈
S.stacksize=STACK_INIT_SIZE;
return（OK）;
}//InitStack复杂度”O
（1）”
StatusDestroyStack（SqStack&S）
{//销毁栈S
free（S.base）;
S.base=NULL;
S.top=NULL;
S.stacksize=0;
returnOK;
}//复杂度O
（1）
StatusClearStack（SqStack&S）
{//置S为空栈
S.top=S.base;returnOK;
}//复杂度O
（1）
StatusPush（SqStack&S,SElemTypee）
{//插入e为栈顶元素
if（S.top-S.base==S.stacksize）//判断栈满
{//栈满则应重新分配空间
S.base=（SElemType*）realloc（S.base,
（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base） exit（OVERFLOW）;
S.top=（S.base+S.stacksize）;//使得S.top重新指向栈顶,因realloc
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;//top指向待插入位置
return（OK）;
}//Push,复杂度O
（1）
StatusPop（SqStack&S,SElemType&e）
{//若栈不空则栈顶元素出栈并用e带回其值
if（S.top==S.base） returnERROR;//判断栈空
e=*（--S.top）;//栈顶元素为*（S.top-1）
returnOK;
}//复杂度O
（1）
StatusStackEmpty（SqStackS）
{
if（S.top==S.base） returnTRUE;
else returnFALSE;
}
intStackLength（SqStackS）{return（S.top-S.base）;}
StatusGetTop（SqStackS,SElemType&e）
{
if（S.top==S.base） returnERROR;
e=*（S.top-1）;//注意top指向待插入位置
returnOK;
}
栈的遍历一直没用到，可以自己找找课件看。
2.队列类似线性表和栈,也是定义在线性结构上的ADT,与线性表和栈的区别在于，元素的插入和删除分别在表的两端进行。
类似日常生活中排队,允许插入的一端为队尾（rear）,允许删除端称队头（front）。
特性:
FirstInFirstOut先进先出，如操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。
#define***QElemType
typedefstructQNode{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
}LinkQueue;//链队列
StatusInitQueue（LinkQueue&Q）
{//构造一个空队列Q
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front） exit（OVERFLOW）;
Q.front->next=NULL;//莫忘！
！
returnOK;
}//时间复杂度O
（1）
StatusDestroyQueue（LinkQueue&Q）
{//销毁队列Q，此处不同于教材,先清空元素结点，后释放头结点
QueuePtrp=Q.front->next;
while（p）
{//依次释放首元素至最后一个元素
Q.front->next=p->next;
free（p）;
p=Q.front->next;
}
free（Q.front）;
Q.front=NULL;Q.rear=NULL;
returnOK;
}//去掉下划线部分为置空操作,复杂度O（n）
StatusEnQueue（LinkQueue&Q,QElemTypee）
{//插入元素e为Q的新的队尾元素
QueuePtrp;
p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p） exit（OVERFLOW）;//存储分配失败
p->data=e;p->next=NULL;//
升级会员 