算法总结

2.1

void Union(List &La, List Lb) { // 算法2.1

// 将所有在线性表Lb中但不在La中的数据元素插入到La中

int La_len,Lb_len,i;

ElemType e;

La_len = ListLength(La); // 求线性表的长度

Lb_len = ListLength(Lb);

for (i=1; i<=Lb_len; i++) {

GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e

if (!LocateElem(La, e, equal)) // La中不存在和e相同的数据元素 ListInsert(La, ++La_len, e); // 插入

} } // union

2.2

void MergeList(List La, List Lb, List &Lc) { // 算法2.2 // 已知线性表La和Lb中的元素按值非递减排列。

// 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。

int La_len, Lb_len;

ElemType ai, bj;

int i=1, j=1, k=0;

InitList(Lc);

La_len = ListLength(La);

Lb_len = ListLength(Lb);

while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, ai);

GetElem(Lb, j, bj);

if (ai <= bj) {

ListInsert(Lc, ++k, ai);

…… …… 余下全文

数据结构和算法设计与分析

谈到计算机方面的专业课程，我觉得数据结构算是一门必不可少的课了，它是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不得不讲数据结构,谈数据结构也不可避免的要了解算法,好的算法一定有一个好的数据结构，很多算法实际上是对某种数据结构实行的一种变换,研究算法也就是研究在实行变换过程中数据的动态性质。这两门课程分别是我在大二和研一的时候学的，因为它们密切的联系，这里将其放在一起总结如下。

什么是数据结构呢？研究数据的逻辑结构和存储结构（物理结构）以及它们之间的关系，且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构，也称为物理结构，它有4类基本的存储映射方法：1.顺序的方法；2.链接的方法；3.索引的方法；4.散列的方法。在程序设计语言中，数据结构直接反映在数据类型上，比如一个整型变量就是一个节点，根据类型给他分配内存单元。抽象数据类型：一组值以及在这些值上定义的操作集合，它是描述数据结构的一种理论工具，其特点是把数据结构作为独立于应用程序的一种抽象代数结构。

线性表结构：由一系列元素组成的有序的序列，除了第一个元素和最后一个元素外，每个元素都只有一个直接前趋和直接后继，元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优点是存储单元是连续的，适合快速访问元素内容，链表的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱关系把一个个结点链接起来，这样可以动态地根据需要分配内存空间，经常用于插入新结点或删除节点的需要，链表还可以根据结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类特别的线性表：栈和队列。栈是一种限制访问端口的线性表，常称为后进先出表。正是这种特殊的性质使得栈的用途非常广泛，比如在计算表达式的值时处理运算符的先后次序，另外一个大的用处就是递归了，hanoi 塔就是最典型的用了递归的思想，在算法中，也有很多运用递归思想的例子。队列也属于限制访问点的线性表，它的特点就是加入和删除元素都只能在队列的一端进行，即队列首出，队列尾进，最大的特点是先来先服务，先进先出。因

…… …… 余下全文

《数据结构与算法》课程学习总结报告

10040120xx 10计本（4）班 章兴春

本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。 一、《数据结构与算法》知识点：

学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。

第一章主要介绍了相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。

第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。

链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。

第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。 算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。

…… …… 余下全文

**大学

算法与数据结构课程设计

课 程：

专 业：

班 级：

学 号：

姓 名： **

2010 年 11 月 18日

本次算法与数据结构实践课中我们小组主要选择了两个课题，一个是迷宫的创建及求解问题，另一个是停车场管理系统问题，还选做了一个敢死队的问题。

在迷宫创建及求解这个问题中，我主要负责的是求解迷宫这个模块。迷宫求解采用的是课本中的回溯法，其求解过程就是沿着一个方向进行探索，若能走通，则继续向前走；否则原路返回，换一个方向在进行探索，直到找到了出口，或者所有可能的探索都失败而告终。

在探索过程中，可以用一个栈来保存探索的序列。其算法框架如下：

创建一个（保存探索过程的）空栈：

把入口位置压入栈中：

While 栈不空时{

取栈顶位置并设置为当前位置；

While 当前位置存在试探可能{

取下一个试探位置；

If（下一个位置是出口）

打印栈中保存的探索过程然后返回

If （下一个位置是通道）

把下一个位置进栈并且设置为当前位置；

}

}

这个模块在程序中对应的代码段是：

Status InitStack(Stack *s) /*创建栈s并初始化为空栈*/ {

s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); /*分配内存空间*/

if(!s->base) Error("Overflow");

s->top=s->base;

s->stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestroyStack(Stack *s) /*销毁栈*/

{

s->top=NULL;

…… …… 余下全文

《数据结构与算法》课程学习总结报告

0704013015 07计本（3）班 张浩

本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。

一、《数据结构与算法》知识点

在课本的第一章便交代了该学科的相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。

第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念，重点在于串的模式匹配。

链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。

堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。

第六章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。

…… …… 余下全文

数据结构与算法实验学期总结

我的数据结构

   班级：09计本一班    学号：2009810020     姓名：吴伟    

摘要

数据结构实验的目的是为了加深对课堂知识的理解，培养实验者的动手能力和思维能力。实验中，能体会到了算法和源程序之间的区别，理解到要实现算法要做的事情，解决编写源程序时遇到的各类问题。

关键字：算法、源程序、算法实现、解决问题

一、    数据结构与算法课程实验的主要意义的目的

    数据结构课程的实践性很强，许多内容如果只进行单纯的课堂讲授是根本不能够深刻认识的。例如，第二章线性表的多种存储结构的对比分析，如不上机练习，就只能靠自己背，但这样就不能有更直观、形象的认识了。因此，实验是数据结构课程的一个重要环节。

首先，在实验的过程中，可以会体会到源程序与算法的区别。

算法是一种算法描述语言。它不是一种现实存在的编程语言。使用算法的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。它可能综合使用多种编程语言中语法、保留字，甚至会用到自然语言。 因此，算法必须结构清晰，代码简单，可读性好，并且类似自然语言。

源程序(source code)是指未编译的按照一定的程序设计语言规范书写的，一系列人类可读的计算机语言指令。其实现起来，有时并不像算法那样看起来那么简单。例如，希尔排序的算法：

void ShellSort(SSTable &L, int dlta[], int t) {

   // 按增量序列dlta[0...t-1]对顺序表L做希尔排序

   for (int k=0; k<t; ++k)

…… …… 余下全文

1 算法

算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：

（1）可行性；

（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；

（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；

（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

2 数据结构的基本基本概念

数据结构研究的三个方面：

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：

（1）表示数据元素的信息；

（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

3 线性表及其顺序存储结构

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

…… …… 余下全文