计算机备考资料：数据结构基本概念(三)

《计算机备考资料：数据结构基本概念(三)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：基本概念(三)Ø栈的定义栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。Ø栈的操作特性栈的操作具有后进先出的特性。Ø队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。Ø队列的操作特性队列的操作具有先进先出的特性。Ø循环队列中解决队空队满的判断条件方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；

2、方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是front=rear，队满的条件是(rear+1)%QueueSize=front，队列长度为(rear-front+QueueSize)%QueueSize。方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。Ø串的定义串是零个或多个字符组成的有限序列。Ø空格串和空串的定义只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为0的串称空串

3、，记作""。Ø串的比较串的比较是通过组成串的字符之间的比较来进行的。给定两个串：X="x1x2…xn"Y="y1y2…ym"则当n=m且x1=y1，…，xn=ym时，称X=Y；当下列条件之一成立时，称X＜Y：⑴n＜m，且xi=yi（i=1，2，…，n）；⑵存在某个k≤min(m，n)，使得xi=yi（i=1，2，…，k-1），xk＜yk。Ø改进的模式匹配算法中next[j]的求法用next[j]表示tj对应的k值（1≤j≤m），其定义如下：0j=1max{k

4、1≤k＜j且＂t1t2…tk-1＂=＂t

5、j-k+1tj-k+2…tj-1＂}1其它情况next[j]=Ø数组的基本操作数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。因此，在数组中通常只有两种操作：⑴读取：给定一组下标，读取相应的数组元素；⑵修改：给定一组下标，存储或修改相应的数组元素。Ø二维数组的寻址按行优先，设二维数组的行下标与列下标的范围分别为［l1，h1］与［l2，h2］，则任一元素aij的存储地址可由下式确定：LOC(aij)＝LOC(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2)

6、)×cØ特殊矩阵的定义特殊矩阵是指矩阵中有很多值相同的元素并且它们的分布有一定的规律。Ø矩阵压缩存储的基本思想压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。Ø对称矩阵的压缩存储中：下三角元素aij（i≥j）在一个数组SA中的下标为：k=i×(i-1)/2+j-1。上三角中的元素aij（i＜j），则访问和它对应的下三角中的元素aji即可，即：k=j×(j-1)/2+i-1。Ø三角矩阵的压缩存储中：下三角矩阵中任一元素aij在一个数组SA中的下标k与i、j的对应

7、关系为：k=i×(i-1)/2+j-1当i≥jn×(n＋1)/2当i＜j上三角矩阵元素aij在SA中的下标为：k=(i-1)×(2n-i+2)/2+(j-i)。Ø稀疏矩阵的压缩存储方式三元组顺序表和十字链表Ø三元组的定义structelement{introw,col;ElemTypeitem};文后寄语：book118是一个专注于电子文档的在线分享平台，用户在此平台上不但可以自由交换文档，还可以分享最新的行业资讯。book118制定了严格的文档审核策略，以保证文档来源的合法性，对有可能引起知识产权

8、纠纷的文档，网站不予收录。同时，道客巴巴采用了行业领先的文档加密及保护技术，最大程度上保证用户上传的文档的版权不被非法侵犯。注册1、会员信息是您在book118网站的身份标识，注册后，您可以浏览文档、在线阅读或下载，建立并管理自己的文档信息库;2、打开网站的首页，点击页面上方的信息条文字"【免费注册】"，在用户注册页面，输入用户名、密码、电子邮件、验证码，阅读"服务协议"，并选中"同意"复选框，最后点击"注册"按钮;3、也可以在"登录"页面，点击"新用户注册"按钮，进入用户注册页面;