数据结构大全

一、概论

二、线性表

三、栈和队列

四、串

五、多维数组和广义表

十、文件

六、树

七、图

八、排序

九、查找

一、概论

1、　评价一个算法时间性能的主要标准是(　算法的时间复杂度　)。  
2、　算法的时间复杂度与问题的规模有关外，还与输入实例的(　初始状态　)有关。

3、　一般，将算法求解问题的输入量称为(　问题的规模　)。

4、　在选择算法时，除首先考虑正确性外，还应考虑哪三点?

答：选用的算法首先应该是"正确"的。此外，主要考虑如下三点：① 执行算法所耗费的时间；② 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③ 算法应易于理解，易于编码，易于调试等等。

6、　下列四种排序方法中，不稳定的方法是(　D )  
A、直接插入排序　B、冒泡排序　C、归并排序　D、直接选择排序

7、　按增长率由小至大的顺序排列下列各函数：
　　2¹⁰⁰, (3/2)ⁿ，(2/3)ⁿ，nⁿ  ,n^0.5 , n! ，2ⁿ ，lgn ,　n^lgn, n^3/2

答：常见的时间复杂度按数量级递增排列,依次为: 常数0(1)、对数阶0(log₂n)、线形阶0(n)、线形对数阶0(nlog₂n)、平方阶0(n²)立方阶0(n³)、…、k次方阶0(n^k)、指数阶0(2ⁿ)。显然，时间复杂度为指数阶0(2ⁿ)的算法效率极低，当n值稍大时就无法应用。先将题中的函数分成如下几类：
常数阶：2¹⁰⁰
对数阶：lgn
K次方阶：n^0.5、n^3/2

指数阶 (按指数由小到大排)：n^lgn、(3/2)ⁿ、2ⁿ、 n!、 nⁿ
注意：(2/3)ⁿ由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 
根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)ⁿ <2¹⁰⁰ < lgn < n^0.5< n^3/2 < n^lgn <(3/2)ⁿ < 2ⁿ < n! < nⁿ 

…… …… 余下全文

题 目： C语言顺序结构通讯录程序 班 级： 学生学号： 学生姓名： 时 间：

2级 金融 1 20xx年10月14日

1．问题描述

此程序要求开发一个具有如下功能：

（1）录入通讯信息（包含姓名、性别、学号、电话、qq、Email）；

（2）添加通讯录记录，逐个添加联系人；

（3）删除通讯录记录，输入人名删除相应的信息

（4）显示：显示通讯录记录，显示所有的联系人。

（5）查询：按人名查询通讯录记录；

（6）修改：修改通讯录记录，选择性修改。

（7）保存：将信息保存到文件，以文件形式保存到硬盘。

（8）读取：将信息从文件读取到内存中。

(9)退出：退出程序。

另外要求用顺序结构来存储通讯录的信息并实现增删功能。

2．开发平台及工具介绍

开发平台为windows 7

开发工具为 visual studio 2012

3.程序中构造以及使用的函数 int shuru(ADDRESS t[]); /*输入记录*/

void xianshi(ADDRESS t[], int n); /*显示记录*/

void chazhao(ADDRESS t[], int n); /*按姓名查找显示记录*/ int shanchu(ADDRESS t[], int n);

int charu(ADDRESS t[], int n);

void baocun(ADDRESS t[], int n); /*记录保存为文件*/

int duqu(ADDRESS t[]); /*从文件中读记录*/

void display(ADDRESS t[]); /*按序号显示所有记录*/ void sort(ADDRESS t[], int n); /*按姓名排序*/

…… …… 余下全文

顺序结构程序设计复习题

一．选择题

1． 已有定义：int a,b; float x,y;,以下正确的赋值语句是：（ ） a) a=1,b=2, b) y=(x%2)/10; c) x*=y+8; d) a+b=x;

2. 有以下程序：

main()

{ int y=1111;

printf(“y=%6d\n”,y);

printf(“y=%+06d\n”,y);

}

程序运行的结果是：（ ）

a) y= 1111 b) y= 1111 c)

y=001111 y=+01111

3. 有以下程序：

main()

{ int y=456;

printf(“*y=%7o*\n”,y);

printf(“*y=%-7o*\n”,y);

printf(“*y=%07o*\n”,y);

}

程序运行的结果是：（ ）

a) *y= 710* b) y=1111 d) y=+01111 *y= 456* y= 1111 y=1111

*y=710 * *y=456 *

*y=0000710* *y=0000456* c) *y=710* d) *y=456*

*y=-710* *y=-456*

*y=0710* *y=0456*

4. 有以下程序：

main()

{ float y=3.667;

printf(“*%f*\n”,y);

printf(“*%7.2f*\n”,y);

printf(“*%8.0f*\n”,y);

}

程序运行的结果是：（ ）

…… …… 余下全文

编写顺序结构程序--万能公式

1.考虑定义几个变量；

2.考虑变量定义成神马类型；

3.变量初始化；

4.摆公式；

5.输出结果。

.............................................................................................

一.已知任意矩形的两条边长，编写程序求他的面积。 ........................................................................................... #include <stdio.h>

void main()

{

float a,b;

double s;

printf("please enter the value of a and b:\n"); scanf("%f,%f",&a,&b);

s=a*b;

printf("矩形的面积s=%5.2f\n",s);

}

.........................................................................................

二.已知圆的半径，求圆的面积。s=pai*r*r;

..........................................................................................

#include <stdio.h>

#define pai 3.14159

void main()

{

float r;

double s;

printf("请输入圆的半径r:\n");

…… …… 余下全文

C语言排序方法

学的排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排序，快速排序，计数排序，基数排序，桶排序（没有实现）。比较一下学习后的心得。

我不是很清楚他们的时间复杂度，也真的不知道他们到底谁快谁慢，因为书上的推导我确实只是小小了解，并没有消化。也没有完全理解他们的精髓，所以又什么错误的还需要高手指点。呵呵。

1.普及一下排序稳定，所谓排序稳定就是指：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1，第二个1就是排序前第二个1，第三个1就是排序前的第三个

1。同理2也是一样。这里用颜色标明了。不稳定呢就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。

2.普及一下原地排序：原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。

3.感觉谁最好，在我的印象中快速排序是最好的，时间复杂度：n*log(n)，不稳定排序。原地排序。他的名字很棒，快速嘛。当然快了。我觉得他的思想很不错，分治，而且还是原地排序，省去和很多的空间浪费。速度也是很快的，n*log(n)。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n,不过在加入随机的情况下这种情况也得以好转，而且他可以做任意的比较，只要你能给出两个元素的大小关系就可以了。适用范围广，速度快。

4.插入排序：n*n的时间复杂度，稳定排序，原地排序。插入排序是我学的第一个排序，速度还是很快的，特别是在数组已排好了之后，用它的思想来插入一个数据，效率是很高的。因为不用全部排。他的数据交换也很少，只是数据后移，然后放入要插入的数据。（这里不是指调用插入排序，而是用它的思想）。我觉得，在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。

…… …… 余下全文

总结C语言循环结构相应知识点

1、什么叫循环结构？

当条件成立的时候，执行循环体的代码，当条件不成立的时候，跳出循环，执行循环结构后面的代码。

2、循环结构中使用的语句在C语言中有哪些？

C语言循环控制语句提供了 while语句、do-while语句和for语

句来实现循环结构。

3、循环的选用原则是什么？

同一个问题，往往既可以用 while语句解决，也可以用 do-while或者for语句来解决，但在实际应用中，应根据具体情况来选用不同的循环语句。选用的一般原则是：

(1) 如果循环次数在执行循环体之前就已确定，一般用 for语句。如果循环次数是由循环体的执行情况确定的，一般用 while语句或者do- while语句。

(2) 当循环体至少执行一次时，用 do-while语句，反之，如果循环体可能一次也不执行，则选用while语句。

C++/C循环语句中，for语句使用频率最高，while语句其次，do语句很少用。

三种循环语句for、while、do-while可以互相嵌套自由组合。但要注意的是，各循环必须完整，相互之间绝不允许交叉。

4、for语句中的1、2、3、4都是指的什么？

for语句的格式为：

for (初始化语句; 条件语句; 控制语句)

{

语句1 ;

语句2 ;

....

语句n ;

}

for 语句的执行顺序是：首先执行“初始化语句”；然后测试“条件语句”；若条件成立，则执行语句1到语句n；然后执行“控制”语句；接着再测试条件语句是否成立，如果成立则重复执行以上过程，直至条件不成立时才结束for循环。如：

for(i=0;i<10;i++)......;

int i,a[]=new int[10];

for (i=0,i<10;i++) a[i]= 0;

这段代码把整型数组a中的所有元素都赋成0。

…… …… 余下全文

《C语言程序设计》教学基本知识点

第一章 C语言基本知识

1.C源程序的框架

尽管各个C源程序的功能千变万化，但框架是不变的，主要有：编译预处理、主函数()、函数n()等，主函数的位置不一定在最前面，可以在程序的中部或后面，主函数的名字固定为main。

2.C语言源程序的书写规则：

(1)C源程序是由一个主函数和若干个其它函数组成的。

(2)函数名后必须有小括号，函数体放在大括号内。

(3)C程序必须用小写字母书写。

(4)每句的末尾加分号。

(5)可以一行多句。

(6)可以一句多行。

(7)可以在程序的任何位置加注释。

3.语句种类

语句是程序的基本成分，程序的执行就是通过一条条语句的执行而得以实现的，根据表现形式及功能的不同，C语言的基本语句可以分为五大类。

(1)流程控制语句

流程控制语句的功能是控制程序的走向，程序的流程有三种基本结构：顺序结构、分支结构和循环结构，任何复杂的程序都可以由这三种基本结构复合而成。其中后两种结构要用特定的流程控制语句实现。

(2)表达式语句

表达式语句的形式是：表达式；，即表达式后跟一分号“；”，分号是语句结束符，是一个语句必不可少的成分。表达式和表达式语句的区别在于表达式代表的是一个数值，而表达式语句则代表一种动作。最常见的表达式语句是赋值语句。

(3)函数调用语句

函数调用语句实际上也是一种表达式语句，形式为：在一次函数调用的小括号后面加上一个分号。

(4)空语句

空语句的形式就是一个分号，它不代表任何动作，常常作为一个意义转折点使用。

(5)复合语句

复合语句从形式上看是多个语句的组合，但在语法意义上它只相当于一个语句，在任何单一语句存在的地方都可以是复合语句。注意复合语句中最后一个语句末尾的分号不能少。复合语句右大括号后面没有分号。

4.运算符

用来表示数据各种操作的符号称为运算符。运算符实际上代表了一种类型数据的运算规则。不同的运算符具有不同的运算规则，其操作的数据类型必须符合该运算符的要求，运算结果的数据类型也是固定的。

…… …… 余下全文