文档库

最新最全的文档下载
当前位置:文档库 > C语言学习资料

C语言学习资料

算法一般具有4个基本特征:可行性、确定性、有穷性、拥有足够的情报。

算法的基本结构是:顺序结构、选择结构、循环结构。

算法的复杂度分为时间复杂度和空间复杂度。

时间复杂度,执行算法所需要的计算工作量(次数)。

空间复杂度,执行算法所需要的内存空间。

数据的逻辑结构:是指反映数据元素之间逻辑关系,而与它们在计算机中的存储位置无关

数据的存储结构(物理结构):数据的逻辑结构在计算机存储空间中的存放形式,数据元素在计算机存储空间的位置关系可能与逻辑关系不同。

数据结构:线性结构(线性表、栈、队列、链表)和非线性结构(树)。

线性表:1 有且只有一个根结点,它无前件。

2 有且只有一个终端结点,它无后件。

3 其他结点,只一个前件,一个后件。

线性表的顺序存储结构特点:

1线性表中所有元素所占的存储空间是连续的;

2线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

栈:(一种特殊的线性表)只允许在一端插入,删除,改写数据。

原则为先进后出。

进栈出栈顺序。

例:进栈顺序:ABCD123

出栈顺序:321DCBA

队列:允许在一端进行插入,而另一端进行删除的线性表。

允许插入一端,尾指针。允许删除的一端,头指针。

原则为先进先出。

循环队列中元素的个数是由队头指针和队尾指针共同决定。循环队列的头指针为front,尾指针为rear,容量为maxSize,则循环队列中元素的个数是【(rear-front+maxSize) mod maxSize】。

一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有多少个元素?(3个) 若头<尾,元素个数=尾-头;若头>尾,元素个数=15+(尾-头)

线性链表:一个存储结点分为两部分。一部分用来存储数据元素的值(数据域),另一部分用来下一个数据元素的存储地址(指针域)。

线性链表是线性表的链式存储结构。用链表表示线性表的优点是便于插入和删除操作。

线性链表的存储空间不一定连续,且个元素的存储顺序是任意的

树(非线性结构)

特征:每一个结点只有一个前件,该前件称为父结点。无前件的结点,根结点。一个结点所拥有的后件个数称为该结点的度。树的最大层次称为树的深度。没有后件的结点称为叶子结点。

二叉树:

特点:1 非空的二叉树只有一个根结点。

2 每一个结点最多有两棵子树,分别左子树,右子树。

性质:1 在二叉树第K层上,最多有2k-1个结点。

2 深度为m的二叉树最多有2m-1个结点。

3 在任意一棵二叉树中,叶子结点总是比度为2的结点多一个。

C语言学习资料

(共6页)