关键词不能为空

当前您在: 主页 > 英语 >

数据结构整理完整版

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-02-01 22:06
tags:

-

2021年2月1日发(作者:cusa)


第二章线性表



一、



顺序表和链表的优缺点



1.



顺序表




定义:


用一组连续的存储单元


(地址连续)


依次存放线性表的各个数据元素。


即:在顺序表中逻辑结构上相邻的数据元素,其物理位置也是相邻的。



?



优点



?



逻辑相邻,物理相邻



?



可随机存取任一元素



?



存储空间使用紧凑



?



缺点



?



插入、


删 除操作需要移动大量的元素


(平均约需移动一半结点,



n


很大时,


算法的效率较低)



?



预先分配空间需按最大空间分配,利用不充分



?



表容量难以扩充



2.



链式存储结构



定义:


由分别表示


a


1

< p>
,a


2


,



,a


i-1


,a


i


,



,a


n

< p>


N


个结点依次相链构成的链表,


称为


线性表的链式存储表示




优势:



(1)


能有效利用存储空间;



动态存储分配的结构,


不需预先为线性表分配足够大的空间,


而是向系统




用随取



,在删除元素时可同时释放空间。



(2)




指 针



指示数据元素之间的后继关系,


便 于进行



插入





删除



等操作;



插入或删除时只需要修改指针,而不需要元素移动。



劣势:



(1)


不能随机存取数据元素;



(2)


丢失了一些顺序表的长处,如线性表的



表长



和数据元素在线性表中的< /p>



位序



,在单 链表中都看不见了。如,不便于在表尾插入元素,需遍历整个


表才能找到插入的位置。< /p>



二、



单链表中删除一个节点和插入一个节点的语句操作,


p29


1.



插入元素操作







算法基 本思想:


首先找到相应结点,然后修改相应指针。


< p>
假定在


a



b

< p>
之间插入结点


X



s


指向


X, p


指向


a


,指针修改语句为:



s->next=p->next; p->next =s;



2.



删除元素操作





算法基本思想


:

首先找到第



i-1


个结点,然后修改相应指针。



删除< /p>


b


结点,其中,


P


指向


a


,指针修改语句为:



p->next=p->next->next




三、



单链表的就地逆置习题集


2.22



算法的基本思想:


以单链表作存储结构进行就地逆置的正确做法 应该是:将


原链表的头结点和第一个元素结点断开(令其指针域为空)

< br>,先构成一个新的空


表,然后将原链表中各结点,从第一个结点起,依次插入这个 新表的头部(即令


每个插入的结点成为新的第一个元素结点)





算法思路:


依次取原链表中的每个结点,将其作为第一个结点插入到新链表


中去,指针

< p>
p


用来指向当前结点,


p


为空时结束。




void



reverse (Linklist H){



LNode



*p;



p=H->next;



/*p


指向第一个数据结点


*/



H->next=NULL;



/*


将原链表置为空表


H*/





while (p){




q=p;




p=p->next;




q->next=H->next;




/*


将当前结点插到头结点的后面


*/




H->next=q;



}


}


第三章栈和队列



一、



栈和队列的特性



1.



特点



栈必须按



后进先出

< br>”



LIFO


)的规则进行操作 ,仅限在表尾进行插入和删


除的操作。



队列(


FIFO


)必须按



先进先出



的规则进行操作,队尾插入,队头删 除。



二、



循环队列为空和满的判定方法,


p63


队空条件:


front == rear;


队满条件:


(rear + 1) % maxSize == front



第四章串



一、模式匹配的改进算法




Next


数组



1)



Next[j]


的定义




2)



求解


next[j]


示例



j


模式串



Next[j]


1


a


0


2


b


1


3


a


1


4


a


2


5


b


2


6


c


3


7


a


1


8


c


2


第五章数组与广义表



一、对称矩阵和上(下)三角矩阵的压缩存储



1.



对称矩阵的压缩存储




若一个


n


阶方阵


A


中的元素满足


a


i,j


=a


j,i


(1≤i,j≤n),


则 称其为


n


阶对称矩阵






1

)只存储对称矩阵中上三角或下三角中的元素





2


)将


n

< p>
2


个元素压缩存储到


n(n+1)/2

< p>
个元素的空间中,以一个一维数组作



A


的存储空间。



?


i< /p>


(


i


?


1)



?


j


?


1,



i


?

< p>
j


?


?


2



k


?


?



?


j


(


j


?


1)


?


i

< p>
?


1,



i


?


j


?


?

< br>2



2.



下三角矩阵的压缩存储


B[n(n+1)/2+1]







?


i


(


i


?


1)


?


j


?


1,



i


?


j


?


?


2


k


?

< br>?


?


n


(


n


?


1)


,



i


?


j


?< /p>


?


2


3.



上三角矩阵的压缩存储


B[n(n+1)/2+1]








?


(


i


?


1)(2


n< /p>


?


i


?


2)


?


j


?


i


,



i


?


j


?


?


2

< br>k


?


?


n


(


n


?


1)


?


,



i


?< /p>


j


?


?


2


二、理解广义表的取表头和表尾的操作



1.



广义表的表头

< br>(Head)


和表尾


(Tail)





当广义表

LS=(a


1


,a


2


,…,a


i


,…,a


n


)


非空时,


称第一个元素

< br>a


1


为广义表的表头,


其余


元素组成的表


(a


2


, a


3


, …,a


n


)


称为广义表的表尾。


表头可能是原子,

< p>
也可能是广义表,


但表尾一定是广义表。



2.



取表头


GetHead(LS) = a


1




3.



取表尾


GetTail(LS) =



(a


2


,a


3


,…,a


n


)




4.



取表头表尾示例




B=(e)









GetHead(B) = e;



GetTail(B) = ( ).



A=(a, ((b, c), d, e))


GetTail(A)=(((b, c), d, e))


GetHead( GetTail(A))=((b, c), d, e)


GetHead( GetHead( GetTail(A))) = (b, c).



A=( );





B = ( ( ) )


A


空表,长度


0


,深 度


1


,无表头和表尾;



B


长度


1


,深度

< p>
2


,表头


( )


,表尾


( )




第六章树和二叉树



一、



二叉树先序、中序和后序的关系


p154



1.


二叉树遍历的概念



二叉树的遍历是指按照一定次序访问树中所有结点


,


并且每个结点仅被访问一次


的过程。它是最基本的运算


,


是二叉树中所有其他运算的基础。



2.


先序遍历(


DLR


)操作过程:

< p>


若二叉树为空,则空操作,否则




(1)


访问根结点;




(2)


按先序遍历左子树;




(3)


按先序遍历右子树。



3.

< p>
中序遍历(


LDR


)操作过程:

< br>


若二叉树为空,则空操作,否则:






(1)


按中序遍历左子树;






(2)


访问根结点;






(3)


按中序遍历右子树。



4.

< p>
后序遍历(


LRD


)操作过程:

< br>


若二叉树为空,则空操作,否则:






(1)


按后序遍历左子树;






(2)


按后序遍历右子树;






(3)


访问根结点。



5.


遍历示例:




6.


强调:


给定结点的前序序列和中序序列可以唯一确定一棵二叉树。



P 154



6-5


,必须掌握。




二、



二叉树向森林的转换



1.

< p>
将一棵二叉树还原为树或森林,具体方法如下:




1


)若某结点是其双亲的左孩子,则把该结点的右孩子、右孩 子的右孩



……


都与该结点的双亲结点 用线连起来。




2

< br>)删掉原二叉树中所有双亲结点与右孩子结点的连线。




3


)整理由(


1




2


)两步所得到的树或森林,使之结构层次分明。




2.


二叉树到森林的转换示例









C










A


E


F


D


H


I


J


(a)


添加连线


G


B


C


A


E


F


D


H


I


J


(b)


删除右孩 子结点的连线


G


A


E

< br>B


B


C


D


G


F


H


I


J


(c)


整理


三、



算法:




题 目要求:


实现一次遍历二叉树即可求得根结点到树中每个叶结点的路径,


试用


C


语言描述该算法。


以二 叉链表存储表示二叉树,


结点的结构为


(lchild, data,


rchild)




————树节点结构——————



Typedef




struct




BInode{




TElemType



data;




Struct



Binode



*lchild,rchild;


} Binode,*BiTree;


void AllPath(Bitree T, Stack &S)//


输出二叉树上从根到所有叶子结点的路径



{




if(T)




{






Push(S,T->data);






if(!T->Left&&!T->Right)//


如果左指针 和右指针同时为空,才说明该节点为


叶子节点







PrintStack(S);






else






{








AllPath(T->Left,S);








AllPath(T->Right,S);






}






Pop(S);




}


四、



哈夫曼树



1.


构造哈夫曼树


(


哈夫曼算法


)




由给定的


n


个权值


{W


1


,W


2


,...,W


n


},


构造


n


棵只有一个叶子 结点的二叉树


,



而得到一个二叉树的 集合


F={T


1


,T

< br>2


,...,T


n


};





F


中选取根结点的权值最小和次小的两棵二叉树作为左、


右子树构造一


棵新的二叉树


,


这棵新的二叉树根结点 的权值为其左、右子树根结点权值


之和


;




在集合


F


中删除作为左、右子树的两棵二叉树


,


并将新建立的二叉树加入


到集合


F


中< /p>


;




重复< /p>


(2)



(3)


两步


,



F


中 只剩下一棵二叉树时


,


这棵二叉树便是所要建立的


哈夫曼树。



2.


哈夫曼构造示例:




3.


哈夫曼编码(最优前缀编码)



16





前缀编码:任一字符的编码都不是另一个字符的编码的前缀。


0


1



d


9



右图对应的哈夫曼编码如下:



1


0



a



000



b



001



c



01



d



1


4


c



0


1




a


b




哈夫曼编码树中没有度为


1


的结点。


n


个叶子结 点,共有


2n-1


个结点。




强调


:建立的哈弗曼树不唯一,编码 也不唯一,但是不同哈弗曼编码的树的


带权路径长度都是一样的,都是最小的。



第七章图




.



图邻接矩阵的表示方法



1.


邻接矩阵表示法(数组表示法)



?




G


是一个具有


n


个顶点的无权图,

< p>
G


的邻接矩阵是具有如下性质的


n×n

< p>
矩阵


A





?


?


1,


< /p>



(


v


i


,


v


j


)

< p>


?


v


i


,


v


j


??

< br>V



A


[


i


,


j


]


?


?


?



?


0,



其它


?



若图


G


是一个有


n


个顶点的网,则它的邻接矩阵是具有如下性质的


n×n


矩阵


A





?


?


w


ij

< p>
,




(


v


i


,


v

j


)



?


v


i


,


v


j< /p>


??


V



A


[


i


,


j


]


?


?


?


?


?


,



其它



邻接矩阵表示法示例:




1




?< /p>


0


1


0


1


1


?


?


1

< p>
0


1


1


0


?



2


3


0


?


?


< /p>


A


1


?


?


0


1


0


1

< p>
1


?


?


?



4


1


1

< br>1


0


1


?


?



?


(a)

?


1


0


1


1


0


?


?


< /p>


?


0


1


0


1


0


?



1


?


0


0< /p>


1


1


0


?



?


?


2


3


0



A


2


?


?


0


0


0


1


1


?


?


?



0


0


0


0

< br>0


?


?


4



?


?


1


0


0


1


0


?


?



(b)



邻接矩阵表示法类型描述?




define



MAX_VERTEX_NUM




20













//


最多顶点个数?




define



INFINITY




INT_MAX















//


表示极大值∞?



typedef



enum{DG,



DN,



UDG,



UDN}



GraphKind;






typedef



struct



ArcCell{


?










VRType





adj;










InfoType




*info;


?



} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];



typedef



struct{








VertexType



vexs< /p>



MAX_VERTEX_NUM];



//


顶点向量









AdjMatrix




arcs;


? //


邻接矩阵









int




vexnum,




arcnum;



//


图的顶点数和弧数?









GraphKind



kind;




//


图的种类标志?


-


-


-


-


-


-


-


-



本文更新与2021-02-01 22:06,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/595430.html

数据结构整理完整版的相关文章

  • 余华爱情经典语录,余华爱情句子

    余华的经典语录——余华《第七天》40、我不怕死,一点都不怕,只怕再也不能看见你——余华《第七天》4可是我再也没遇到一个像福贵这样令我难忘的人了,对自己的经历如此清楚,

    语文
  • 心情低落的图片压抑,心情低落的图片发朋友圈

    心情压抑的图片(心太累没人理解的说说带图片)1、有时候很想找个人倾诉一下,却又不知从何说起,最终是什么也不说,只想快点睡过去,告诉自己,明天就好了。有时候,突然会觉得

    语文
  • 经典古训100句图片大全,古训名言警句

    古代经典励志名言100句译:好的药物味苦但对治病有利;忠言劝诫的话听起来不顺耳却对人的行为有利。3良言一句三冬暖,恶语伤人六月寒。喷泉的高度不会超过它的源头;一个人的事

    语文
  • 关于青春奋斗的名人名言鲁迅,关于青年奋斗的名言鲁迅

    鲁迅名言名句大全励志1、世上本没有路,走的人多了自然便成了路。下面是我整理的鲁迅先生的名言名句大全,希望对你有所帮助!当生存时,还是将遭践踏,将遭删刈,直至于死亡而

    语文
  • 三国群英单机版手游礼包码,三国群英手机单机版攻略

    三国群英传7五神兽洞有什么用那是多一个武将技能。青龙飞升召唤出东方的守护兽,神兽之一的青龙。玄武怒流召唤出北方的守护兽,神兽之一的玄武。白虎傲啸召唤出西方的守护兽,

    语文
  • 不收费的情感挽回专家电话,情感挽回免费咨询

    免费的情感挽回机构(揭秘情感挽回机构骗局)1、牛牛(化名)向上海市公安局金山分局报案,称自己为了挽回与女友的感情,被一家名为“实花教育咨询”的情感咨询机构诈骗4万余元。

    语文