自考02142《数据结构导论》串讲笔记.docx
《自考02142《数据结构导论》串讲笔记.docx》由会员分享,可在线阅读,更多相关《自考02142《数据结构导论》串讲笔记.docx(30页珍藏版)》请在冰点文库上搜索。
自考02142《数据结构导论》串讲笔记
:
第一张概论
引言
两项基本任务:
数据表示,数据处理
软件系统生存期:
软件计划,需求分析,软件设计,软件编码,软件测试,软件维护
由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型,这种数学模型的建立,选择和实现是数据结构的核心问题。
机外表示------逻辑结构------存储结构
~
处理要求-----基本运算和运算-------算法
数据,逻辑结构和运算
数据:
凡是能够被计算机存储,加工的对象通称为数据
数据元素:
是数据的基本单位,在程序中作为一个整体加以考虑和处理。
又称元素,顶点,结点,记录。
数据项:
数据项组成数据元素,但通常不具有完整确定的实际意义,或不被当做一个整体对待。
又称字段或域,是数据不可分割的最小标示单位。
—
1.2.2数据的逻辑结构
逻辑关系:
是指数据元素之间的关联方式,又称“邻接关系”
逻辑结构:
数据元素之间逻辑关系的整体称为逻辑结构。
即数据的组织形式。
四种基本逻辑结构:
1集合:
任何两个结点间没有逻辑关系,组织形式松散
2线性结构:
结点按逻辑关系依次排列成一条“锁链”
3树形结构:
具有分支,层次特性,形态像自然界中的树
{
4.图状结构:
各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接。
注意点:
1.逻辑结构与数据元素本身的形式,内容无关。
2.逻辑结构与数据元素的相对位置无关
3.逻辑结构与所含结点个数无关。
运算:
运算是指在任何逻辑结构上施加的操作,即对逻辑结构的加工。
。
加工型运算:
改变了原逻辑结构的“值”,如结点个数,结点内容等。
引用型运算:
不改变原逻辑结构个数和值,只从中提取某些信息作为运算的结果。
引用:
查找,读取
加工:
插入,删除,更新
同一逻辑结构S上的两个运算A和B,A的实现需要或可以利用B,而B的实现不需要利用A,则称A可以归约为B。
假如X是S上的一些运算的集合,Y是X的一个子集,使得X中每一运算都可以规约为Y中的一个或多个运算,而Y中任何运算不可规约为别的运算,则称Y中运算(相对于X)为基本运算。
@
将逻辑结构S和在S上的基本运算集X的整体(S,X)称为一个数据结构。
数据结构包括逻辑结构和处理方式。
存储实现和运算实现
由于逻辑结构是设计人员根据解题需要选定的数据组织形式,因此存储实现建立的机内表示应遵循选定的逻辑结构。
另一方面,由于逻辑结构不包括结点内容即数据元素本身的表示,因此存储实现的另一主要内容是建立数据元素的机内表示。
按上述思路建立的数据的机内表示称为数据的存储结构。
存储结构包括三部分:
1.存储结点,每个存储结点存放一个数据元素。
2.数据元素之间关联方式的表示,也就是逻辑结构的机内表示。
3.%
4.附加设施,如方便运算实现而设置的“哑结点”等。
四种基本存储方式:
1.顺序存储方式:
每个存储结点只含一个数据元素。
所有存储结点相继存放在一个连续的存储区里。
用存储结点间的位置关系表述数据元素之间的逻辑关系。
2.链式存储方式:
每个存储结点不仅含有一个数据元素,还包含一组指针。
每个指针指向一个与本结点有逻辑关系的结点,即用附加的指针表示逻辑关系。
3.索引存储方式:
每个存储结点只含一个数据元素,所有存储结点连续存放。
此外增设一个索引表,索引指示各存储结点的存储位置或位置区间端点。
4.散列存储方式:
每个结点含一个数据元素,各个结点均匀分布在存储区里,用散列函数指示各结点的存储位置或位置区间端点。
-
1.3.2运算实现
运算只描述处理功能,不包括处理步骤和方法;运算实现的核心是处理步骤的规定,即算法设计。
算法:
算法规定了求解给定问题所需的所有处理步骤及其执行顺序,使得给定类型的任何问题能在有限时间内被机械的求解。
算法分类:
1:
运行终止的程序可执行部分:
又称为程序
2:
伪语言算法:
不可以直接在计算机上运行,但容易编写和阅读。
!
3:
非形式算法:
用自然语言,同时可能还使用了程序设计语言或伪语言描述的算法。
算法分析
算法质量评价指标:
1.正确性:
能够正确实现处理要求
2.易读性:
易于阅读和理解,便于调试,修改和扩充
3.健壮性:
当环境发生变化,算法能够适当做出反应或处理,不会产生不需要的运行结果
4.高效率:
达到所需要的时空性能。
;
如何确定一个算法的时空性能,称为算法分析
一个算法的时空性能是指该算法的时间性能和空间性能,前者是算法包含的计算量,后者是算法需要的存储量。
算法在给定输入下的计算量:
1.根据该问题的特点选择一种或几种操作作为“标准操作”。
2.确定每个算法在给定输入下共执行了多少次标准操作,并将此次数规定为该算法在给定输入下的计算量。
[
若无特殊说明,将默认以赋值语句作为标准操作。
最坏情况时间复杂性:
算法在所有输入下的计算量的最大值作为算法的计算量
平均时间复杂性:
算法在所有输入下的计算量的加权平均值作为算法的计算量。
算法的输入规模(问题规模)是指作为该算法输入的数据所含数据元素的数目,或与此数目有关的其他参数。
常见时间复杂性量级:
1.)
2.常数阶:
O
(1)即算法的时间复杂性与输入规模N无关或N恒为常数。
3.对数阶:
Olog2N
4.线性阶:
O(N)
5.平方阶:
O(N2)
6.指数阶:
O(2N次方)
通常认为指数阶量级的算法实际是不可计算的,而量级低于平方阶的算法是高效率的
第二章线性表
}
线性表的基本概念
线性结构:
线性结构是N(N大于等于0)个结点的有穷序列。
AI称为Ai+1的直接前趋,Ai+1称为Ai的直接后继。
为满足运算的封闭性,通常允许一种逻辑结构出现不含任何结点的情况。
不含任何结点的线性结构记为()或
线性结构的基本特征:
若至少含有一个结点,则除起始节点没有直接前趋外,其他结点有且只有一个直接前趋,除终端结点没有直接后继外,其他结点有且只有一个直接后继。
2.1.2线性表
线性表的逻辑结构是线性结构。
所含结点个数称为线性表的长度(表长)。
表长为0的是空表。
<
线性表的基本运算:
1.初始化initiate(L):
加工型运算,其作用是建立一个空表L=。
2.求表长length(L):
引用型运算,其结果是线性表L的长度。
3.读表元get(L,i):
引用型运算。
若1小于等于i小于等于length(L),其结果是L的第i个结点,否则为一特殊值。
4.定位(按值查找)locate(L,X):
引用型运算。
若L中存在一个或多个值与X相等,结果为这些结点的序号最小值,否则,运算结果为0。
5.插入insert(L,X,i):
加工型运算。
在L的第i个位置上增加一个值为X的新结点,参数i的合法取值范围是1---L+1。
6.删除delete(L,i):
加工型运算。
撤销L的第i个结点ai,i的合法取值范围是1---N。
|
线性表的顺序实现
2.2.1顺序表
顺序表是线性表的顺序存储结构,即按顺序存储方式构造的存储结构。
顺序表基本思想:
顺序表的一个存储结点存储线性表的一个结点的内容,即数据元素(不含其他信息),所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列。
顺序表的特点:
逻辑结构中相邻的结点在存储结构中仍相邻。
【
顺序表的类C语言描述:
p17
Constmaxsize=顺序表的容量
Typedefstruct
{datatypedate[maxsize]
Intlast;
}sqlist;
SqlistL;
(
L表示线性表的长度,last-1是终端结点在顺序表中的位置。
常数maxsize为顺序表的容量。
表长,终端结点[]
2.2.2基本运算在顺序表上的实现
1.插入
Voidinset_sqlist(sqlistL,datatypex,inti)
{if==maxsize)error(‘表满’);/*溢出*/
If(((i<1)!
!
(i>+1))error(‘非法位置’);
>
For(j=;j=I;j--)
[j]=[j-1];/*依次后移*/
[i-1]=x;/*置入*/
=+1/*修改表长*/
}
2.删除
Voiddelete_sqlist(sqlistL,intI)/*删除顺序表L中第i个位置上的结点*/
~
{
If((i<1)!
!
(I>)error(‘非法位置’);
For(j=i+1;j=;j++)
[j-2]=[j-1];/*依次前移,注意第一个[j-2]存放ai*/
=/*修改表长*/
3.定位
Intlocate_sqlist(sqlistL,datatypeX)
@
/*在顺序表中从前往后查找第一个值等于X的结点。
若找到则回传该结点序号,否则回传0*/
{
I=1;
While((i<=&&[i-1]!
=x))/*注意:
ai在[i-1]中*/
i++;/*从前往后查找*/
if(i<=return(i)
elsereturn(0)
}
【
2.2.3顺序实现的算法分析
插入:
平均时间复杂性:
=n/2
平均时间复杂性量级为O(n)
删除:
平均时间复杂性:
n-1/2
平均时间复杂性量级:
O(n)
定位:
平均时间复杂性量级:
O(n)
求表长,读表元:
量级O
(1)
…
以上分析得知:
顺序表的插入,删除算法的时间性能方面是不理想的。
线性表的链接实现
顺序表的优缺点:
优点:
1。
无需为表示结点间的逻辑关系而增加额外的存储空间。
2.可以方便地随机存取表中的任一结点。
缺点:
1。
插入,删除运算不方便,除表尾位置外,其他位置上进行插入和删除操作都必须移动大量结点,效率较低。
2.由于顺序表要求占用连续的空间,存储分配职能预先进行(静态分配),因此当表长变化较大时,可能造成空间长期闲置或空间不够而溢出。
`
链表:
采用链接方式存储的线性表称为链表
一种数据结构的链接实现是指按链式存储方式构建其存储结构,并在此链式存储结构上实现其基本运算。
2.3.1单链表
单链表表示法的基本思想:
用指针表示结点间的逻辑关系。
一个存储结点包含两部分:
!
data部分:
称为数据域,用于存储线性表的一个数据元素。
Next部分:
称为指针域或链域,用于存放一个指针,指向本结点所含数据元素的直接后继所在的结点
终端结点的指针NULL称为空指针,不指向任何结点,只起标志作用。
Head称为头指针变量,指向单链表的第一个结点的,称为头指针。
头指针具有标识单链表的作用,故常用头指针变量来命名单链表。
单链表的类C语言描述:
:
Typedefstructnode*pointer;
Structnode
{datatypedata;
Pointernext;
};
Typedefpointerlklist;
2.3.2单链表的简单操作
为了便于实现各种运算,通常在单链表第一个结点前增设一个类型相同的结点,称为头结点。
其他结点称为表结点。
表结点中第一个和最后一个称为首结点和尾结点。
头结点的数据域可以不存储任何信息,也可以存放一个特殊标志或表长。
1初始化:
Lklistinitiate_lklist()/*建立一个空表*/
{
t=malloc(size);
t->next=NULL;
return(t);}
"
此算法说明的问题:
1.语句t=malloc(size);有双重作用:
1由malloc自动生成一个类型为node的新结点。
2指针型变量t得到一个值即指针,该指针指向上述新结点。
2.要生成新结点必须通过调用malloc才能实现。
3.语句t->next=NULL的作用是将头结点*t的链域置为NULL。
4.为了建立一个空表,可定义一个lklist类型的变量head,并通过调用head=initiate_lklist()使head成为指向一个空表的头指针。
2求表长
Intlength_lklist(lklisthead)/*求表head的长度,P是pointer类型的变量*/
…
{p=head;
J=0;
While(p->next!
=NULL)
{p=p->next;
J++;}
Return(j);}
3按序号查找
?
Pointerfind_lklist(lklisthead,intI)/*在单链表head中查找第i个结点。
若找到则回传指向该结点的指针,否则回传null*/
{p=head;j=0;
While(p->next!
=NULL)&&(j
{p=p->next;j++;}
If(i==j)return(p);
Elsereturn(NULL);}
4定位
/
Intlocate_lklist(lklisthead,datatypex)
{p=head;j=0;
While((p->next!
=NULL)&&(p->data!
=x))
{p=p->next;j++;}
Ifp->data==xreturn(j);
Elsereturn(0);
}
^
5删除
Voiddelete_lklist(lklisthead,inti)
{p=find_lklist(head,i-1);/*调用按序号查找算法*/
If((p!
=NULL)&&(p->next!
=NULL))
{q=p->next;
p->next=q->next;
free(q);}
elseerror(‘不存在第i个结点’)}
…
free是库函数,结果是释放q所指结点占用的内存空间,同时q的值变成无定义。
6插入
Voidinsert_lklist(lklisthead,datatypedx,inti)
{
P=find_lklist(head,i-1);
If(p==NULL)
Error(‘不存在第i个位置’)
-
Else
{s=malloc(size);s->data=x;
s->next=p->next;
p->next=s;}
其他链表
循环链表
尾结点的链域值不是NULL,而是指向头结点的指针。
优点是从任一结点出发都能通过后移操作而扫描整个循环链表。
·
但为找到尾结点,必须从头指针出发扫描表中所有结点。
改进的方法是不设头指针而改设尾指针。
这样,头结点和尾结点的位置为:
rear->next->next和rear.
双链表:
在每个结点中增加一个指针域,所含指针指向前趋结点。
双链表的摘除*P的操作:
p->prior->next=p->next;
p->next->prior=p->prior;
链入操作:
P后面链入*q:
q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
顺序实现与链接实现的比较
·
空间性能的比较:
存储结点中数据域占用的存储量与整个存储结点占用存储量之比称为存储密度。
顺序表=1,链表<1,所有顺序表空间利用率高。
但顺序表要事先估计容量,有时造成浪费。
时间性能的比较:
一种实现的时间性能是指该实现中包含的算法的时间复杂性。
定位:
顺序表和链表都是O(n)
读表元:
顺序表O
(1),链表O(n),故当需要随机存取时,不宜采用链表。
摘除,链入:
顺序表O(n),链表O
(1),经常需要插入删除时不宜采用顺序表。
@
串
串是由零个或多个字符组成的又穷序列。
含零个字符的串称为空串。
串中所含字符的个数称为该串的长度。
两个串完全一样时称为相等的。
串中任意个连续字符组成的子序列称为该串的子窜,该窜称为主窜。
字符串常量按字符数组处理,它的值在执行过程中不能改变。
串变量与其他变量不一样,不能由赋值语句赋值。
串的基本运算:
1.…
2.赋值:
ASSIGN(S,T):
加工型运算。
将串变量或串常量的值传给串变量。
3.判等:
EQUAL(S,T):
引用型运算,若相等返回1,否则返回0。
4.求长:
LENGTH(S):
引用型运算
5.联接:
CONCAT(S,T):
引用型运算。
运算结果是联接在一起形成的新串。
6.求子串:
SUBSTR(S,I,j):
引用型运算:
结果是串S中从第i个字符开始,由连续j个字符组成的子串。
当I,j参数超过范围时,运算不能执行,也没有结果。
7.插入:
INSERT(S1,I,S2):
加工型运算。
将串2整个插到S1的第i个字符之后从而产生一个新串。
8.删除DELETE(S,I,J)加工型运算。
从串S中删去第I个字符开始的长度为J的子串。
9.定位:
INDEX(S,T):
引用型运算。
若串S中存在一个与T相等的子串。
则结果为S中第一个这样的子串的第一个字符在S中的位置,否则,结果为0。
(要求T不是空串)
10.,
11.替换:
REPLACE(S,T,R)加工型运算。
在S中处处同时以串R置换T的所有出现所得的新串。
串的存储:
1.串的顺序存储:
紧缩格式,非紧缩格式
2.串的链接存储:
将串中每个存储结点存储的字符个数称为结点大小。
结点为1时存储密度低但操作方便,大于1时存储密度高但操作不方便。
第三章栈,队列和数组
栈
}
栈是一种特殊的线性表,栈上的插入删除操作限定在表的某一端进行,称为栈顶。
另一端称为栈底。
不含任何元素的栈称为空栈。
栈又称为先进后出线性表。
在栈顶进行插入运算,被称为进栈,删除被称为出栈。
栈的基本运算:
1.初始化:
InitStack(S):
加工型运算,设置一个空栈S.
2.进栈:
push(S,X)加工型运算,将元素X插入S中,使X称为栈顶元素。
3.退栈:
pop(S)加工型运算,当栈不空时,从栈中删除当前栈顶。
4.读栈顶:
top(S):
引用型运算,若S不空,由X返回栈顶元素,S为空时,结果为一特殊标志。
5.)
6.判栈空empty(S):
引用型运算,若S为空栈,结果为1,否则为0
3.1.2栈的顺序实现
顺序栈由一个一维数组和一个记录栈顶位置的变量组成。
空栈中进行出栈操作,发生下溢,满栈中进行入栈操作,发生上溢。
类C语言定义:
#definesqstack_maxsize6/*6是栈的容量*/
Typedefstructsqstack
—
{DataTypedada[sqstack_maxsize];
Inttop;
}SqStackTP;
栈的基本运算的实现:
1.初始化
IntInitStack(InitStackTp*sq)
{sq->top=0;
】
Return
(1);}
2.进栈
Intpush(sqstackTp*sq,datatypex)
{if(s->top==sqstack_maxsize-1)
{error(“栈满”);return0;}
Else{sq-top++;
Sq->data[sq->top]=x;
Return
(1);}
—
3退栈
Intpop(sqstackTp*sq,datatype*x)
{if(sq->top==0)
{error(“下溢”);return(0);}
Else{*x=sq->data[sq->top];
Sq->top--;
Return
(1);}
…
4判栈空
Intemptystack(stackTp*sq)
{ifsq->top==0}
Return
(1);
Elsereturn(0);}
5取栈顶元素
Intgettop(sqstackTp*sq,datatype*x)
&
{if(sq->top=0)return(0);
Else{*x=sq->data[sq->top];
Return
(1);}
栈的链接实现
链栈由栈顶指针ls唯一确定。
栈中其他结点通过他们的next域链接起来。
栈底结点的next域为NULL。
因为链栈本身没有容量限制,所以不会出现栈满情况。
·
3.栈的简单应用和递归
栈与函数调用:
函数调用时,先保存的位置后返回,后保存的位置先返回。
所以每遇到一个函数调用便立刻将相应的返回位置进栈,调用结束时,栈顶元素正好是此函数的返回位置。
递归与栈:
满足递归的条件:
1.被定义项在定义中的应用具有更小的尺度。
2.被定义项在最小尺度上的定义不是递归的。
\
3.2队列
队列也可以看成一种受限的线性表,插入限定在表的某一端进行(队尾),删除限定在另一端进行(队头)
队列又称先进先出线性表。
队列的基本运算:
1.队列初始化initQueue(Q)加工型运算,设置一个空队列Q
2.入队列enQueue(Q,X)加工型运算,将X插入到队列Q的队尾。
若原队列为空,则X为原队尾结点的后继,同时是新队列的队尾结点。
3.,
4.出队outQueue(Q,X)加工型运算,若队列Q不空,则将队头元素赋给X,并删除队头结点,其后继成为新的队头结点。
5.判队列空emptyQueue(Q)引用型运算,若队列Q为空,则返回1,否则为0
6.读队头gethead(Q,x)引用型运算,Q不空时由参数X返回队头结点的值,否则给一特殊标志。
队列的顺序实现:
队列的顺序实现由一个一维数组及两个分别指示队头和队尾的变量组成,称为队头指针和队尾指针。
约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置。
如果按=+1;[]=x和=+1分别进行入队和出队操作,则会造成“假溢出。
”
;
循环队列的入队操作:
=+1)%maxsize;[]=x
出队操作:
=+1)%maxsize;
判断循环队列队满的条件:
(+1)%maxsize)==
队空的条件:
==
3.3数组
二维数组可以看成是一个被推广的线性表,这种线性表的每一个数据元素本身也是一个线性表。
&
数组只有两种基本运算:
1.读:
给定一组下标,读取相应的数据元素
2.写:
给定一组下标,修改相应的数据元素
数组元素的存储位置是下标的线性函数,计算存储位置所需的时间取决于乘法的时间,因此,存取任一元素的时间相等。
通常将具有这一特点的存储结构成为随机存储结构。
矩阵的压缩存储
(
压缩存储的基本思想:
值相同的多个元素只分配一个存储空间,零元素不分配空间。
要压缩的矩阵分为两种
1.特殊矩阵:
对称矩阵,三角矩阵。
值相同的元素或零元素的分布有一定规律叫特殊矩阵。
对称矩阵通常存储下三角,n阶方阵需要n*(n+1)/2个存储单元
三角矩阵需要n*(n+1)/2+1个存储单元,最后一个单元存储相同的常数。
2.稀疏矩阵:
零元素远多于非零元素,且非零元素的分布没有规律。