内容发布更新时间 : 2024/12/22 10:13:46星期一 下面是文章的全部内容请认真阅读。

资料收集于网络，如有侵权请联系网站删除

第一章 绪论

1.1数据、数据元素、数据项、数据结构等基本概念

1.数据（data）：客观事物的符号表示，在计算机科学中指所有能输入计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声音、图像。

2.数据元素（dataelement）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3.一个数据元素可能由若干个数据项（dataitem）组成。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段）。故不是组成数据的最小单位。数据项是构成数据的最小单位。

4.数据对象（dataobject）：性质相同的数据元素的集合，是数据的一个子集。 5.数据结构（datastructure）：数据元素以及数据元素之间存在的关系。

6.数据结构主要描述：数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算，即数据的逻辑结构、存储结构和数据的操作集合

1.2数据结构的逻辑结构、存储结构的含义及其相互关系

1.数据的逻辑结构：用形式化方式描述数据元素间的关系。数据的逻辑结构独立于计算机，是数据本身所固有的。用于算法的设计。

两大类逻辑结构：线性结构（线性表、栈、队列、数组和串），非线性结构（树和图）。 2.数据的物理结构（也称存储结构）：数据在计算机中的具体表示。包括数据元素的表示和关系的表示。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。用于算法的实现。

数据的存储方式可分为如下两类：顺序存储、链接存储。

1.3算法

1.算法的定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列。 2.算法的特性：

有穷性——算法必须在执行有穷步之后结束，而且每一步都可在有穷时间内完成 确定性——每条指令无二义性。并且，相同的输入只能得到相同的输出； 可行性——算法中描述的每一操作，都可以通过已实现的基本运算来实现。 输入——算法有零至多个输入。输出——算法有一个至多个输出 3.算法效率的度量：时间复杂度和空间复杂度及计算。

word可编辑

资料收集于网络，如有侵权请联系网站删除

第二章 线性表

2.1线性表的逻辑结构特征

存在唯一的一个被称作第一个的数据元素；存在唯一的一个被称作最后一个的数据元素；除第一个元素之外，集合中的每个数据元素均只有一个前驱；除最后一个元素之外，集合中的每个数据元素均只有一个后继。

2.2线性表的顺序存储结构

1.用一组连续的存储单元依次存储线性表的数据元素。在线性表的顺序存储表示中，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的顺序存储结构是一种随机存取的存储结构。

LOC(ai+1)=LOC(ai)+1 LOC(ai+1)=LOC(a1)+i*1

LOC(ai)表示元素ai的存储位置；LOC(a1)表示第一个数据元素的存储位置，通常称为线性表的起始位置或基地址每个数据元素占用1个存储单元。

2.线性顺序表上的插入是指在第i(1≤i≤n+1)个位置插入一个新的数据元素，需将第i至第n共(n-i+1)个元素后移 注意：

? ? ?

顺序表中数据区域有listSize个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。

要检验插入位置的有效性，这里i的有效范围是：1<=i<=n+1，其中n为原表长。 注意数据的移动方向

算法时间复杂度 移动元素个数：n-i+1 平均移动元素个数：n/2 T（n）=O（n）；

3.线性顺序表上的删除是指第i(1≤i≤n)个数据元素删除掉，需将第i+1至第n共（n-i)个元素前移 注意：

? ? ?

删除第i个元素，i的取值为1<=i<=n,否则第i个元素不存在，因此，要检查删除位置的有效性。

当表空时不能做删除。

删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。

算法时间复杂度： 移动元素个数：n-i

平均移动元素个数：（n-1）/2 T（n）=O（n）； 4.线性表的顺序存储。

优点：逻辑相邻，物理相邻可以实现数据元素的随机存取；

word可编辑

资料收集于网络，如有侵权请联系网站删除

缺点：在作插入或是删除操作时，需要移动大量数据元素

2.3线性表的链式存储结构

1.线性表链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素。在线性表的链式存储中，在进行插入或是删除操作时，不需要进行数据元素的移动，但不能实现数据元素的随机存取。

2.线性链表的表示：数据元素、数据元素之间的关系；数据域存储数据元素，指针域存储数据元

素之间的关系：直接后继的存储位置，线性链表：每个节点只包含一个指针域

3.假定指针p指向线性链表中的第i个数据元素，则p->next为指向线性链表中第i+1个数据元素的指针。即p->data为ai，p->next->data为ai+1。

(*p)表示p所指向的结点 (*p).data(*p).next

p->data表示p指向结点的数据域 p->next表示p指向结点的指针域

4.在单链表中查找第i个元素

StatusgetElem_L(LinkListL,inti,ElemType&e){ //获取线性链表中的第i个数据元素

p=L->next;j=1; while(p&&j

p=p->next;++j; }

if(!p‖j>i)returnERROR; returnp->data; }//GetElem_L

5.在单链表中插入数据元素

S->next=P->next； P->next=S;

StatuslistInsert_L(LinkList&L,inti,ElemTypee){

p=L;j=0;

while(p&&jnext;++j； }

if(!p‖j>i-1)returnERROR;

s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next=p->next;p->next=s; return

OK;

word可编辑