第一章

1、数据元素是数据的基本单位；数据项是数据的不可分割的最小单位。

2、数据结构：4种基本结构为：集合， 线性结构，树状结构，图状结构或网状结构 DS 组成：逻辑结构（结构定义中的关系描述是数据元素之间的逻辑关系），物理结构（数据结构在计算机中的表示）;常用的逻辑结构分为四种：线性结构、层次/树形结构、网状/图结构、集合结构

3、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象。由此得到两种不同的存储结构：顺序存储结构和链式存储结构

4、计算算法的时间复杂度

5、数据的四种基本存储方法：顺序、链式、索引、散列存储方法

6、算法的五个重要特征：有穷、确定、可行性、有输入、有输出。算法的设计原则：正确、可读、健壮性、高效率与低存储量需求

7、给出一个小程序计算算法的时间复杂度

8、O(1) ≦O(log2n) ≦ O(n) ≦ O(nlog2n) ≦ O(n2) ≦ O(n3) ≦… ≦ O(nk) ≦ O(2n)

9、算法执行时间的增长率和 f(n) 的增长率相同，T (n) = O(f(n)) ，称T (n) 为算法的(渐近)时间复杂度；空间复杂度是指计算机执行操作时所占的内存开销规模，S(n) = O(g(n)) 表示算法执行所需存储量的增长率与g(n)的增长率相同

…… …… 余下全文

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

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

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

第一章是这门学科的基础章节，从整体方面介绍了“数据结构和算法”，同时引入相关的学术概念和术语，如数据、数据元素、数据类型以及数据结构的定义。重点是数据结构的括逻辑结构、存储结构和运算集合的含义及其相互联系。数据结构和两大逻辑结构的4四种常用存储方法；逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。难点是算法复杂度的分析方法和性能的分析。

第二章详细地分析了顺序表。介绍了顺序表的相关概念及其有关运算。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等，在各种算法思想的先分析后，要弄清各种算法的时间复杂度与空间性能的优点和缺点，在什么特定的场合适合哪种算法思想。最后介绍了顺序串的概念，顺序串是顺序表的一个特例；区别在于组成顺序串的数据元素是一组字符，其重点在于串的模式匹配。

…… …… 余下全文

一，基础知识

数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。

数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所

① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

② 线性结构：结构中的数据元素之间存在一对一的关系。 ③ 树型结构：结构中的数据元素之间存在一对多的关系。

④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

数据结构的形式定义

数据结构的形式定义是一个二元组： Data-Structure=(D，S)

…… …… 余下全文

package datastructtest;

import java.io.File;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

import java.util.LinkedList;

import java.util.Scanner;

import javax.swing.JFrame;

public class Testbase {

public static void main(String[] args) throws IOException{

//100之内被3或7整除的数的个数

// int m=0,n=0;

// for (int i=0;i<100;i++){

// if(i%3==0){

// m++;

// }

// if(i%7==0){

// n++;

// }

// }

// System.out.println("m="+m+" ；");

…… …… 余下全文

本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。一、《数据结构与算法》知识点在课本的第一章便交代了该学科的相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念，重点在于串的模式匹配。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了

…… …… 余下全文

第四章排序程序设计初步

本章介绍线性表的一个主要应用——排序，讲解了排序相关的基本概念和排序算法的一般思路，包括直接插入排序、简单选择排序、冒泡排序以及静态链表插入排序，并给出了其程序设计源码，通过程序设计技巧和线性表的联合来体会数据结构的作用。

计算级程序设计中，最常用的一个功能就是对数据的排序，因为无序的数据和有序的数据之间实际上是有信息差异的。如运动会上需要求出20运动员在200米短跑中的冠军、亚军。季军。在输入数据后，因为数据是无序的。所以该算法需要求出最小值，次小值和第三个最小值。但是如果先做一次从小到大的排序操作，那么不光前三名的次序出来了，其他运动员的排名同时全部出来了，而许多其他功能可能会有一个前提，即要求数据是有序的。 由于计算机程序的“点式思维”和人的“面式思维”不同，设计排序程序时通常第一步就是把数据组成线性结构，也就是前面提到的线性表。排序是线性表中涉及的几百呢操作之为最常用的其他操作。它是程序设计中非常重要的应用之一，吸引看世界上很多科学家研究这个课题，推出饿的排序方法也是精彩纷呈。

本章内容中涉及到程序设计中一些重要的概念和设计基础，所以程序设计初步对以后我们完成程序设计有这重要作用。最基本的四种排序方法，并给出四种排序方法的可执行的程序，通过多个案例介绍了排序操作的用途。排序是许多其他功能实现的前提，排序后的数据增加了位序信息，所以有些科学家一生都把排序技术最为重要的研究课题。认真努力学习本章理解到排序的重要性。

…… …… 余下全文

二级C公共基础知识总结

二级C公共基础知识总结数据结构与算法

1 算法

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

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

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

（1） 可行性； （2） 确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；

（3） 拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

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

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

…… …… 余下全文

单链表：list Sqlist

//---------------------------------创建 void Create(Sqlist** _head) {

int i, n;

Sqlist *q, *s; q = *_head;

printf("请输入单链表的长度："); scanf("%d",&n); getchar();

for (i=0; i<n; i++){ s = (Sqlist*)malloc(sizeof(Sqlist)); s->next = NULL;

printf("输入第 %d 个结点：", i+1); scanf("%d", &s->data); getchar(); q->next = s; q = s; } }

//--------------------------------输出 void Output(Sqlist* head) {

…… …… 余下全文