空安

用户名：KongAn

访问量：5858

签　名：

等　　级
排　　名	3428
经　　验	1932
参赛次数	0
文章发表	27
年　　龄	0
在职情况	学生
学　　校	哈尔滨商业大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高-能量项链-题解(C++代码)-----×
浏览：285

Cylinder-题解(C++代码)-----×
浏览：174

蓝桥杯基础练习VIP-时间转换-题解(C++代码)
浏览：116

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

空安---《数据结构》第一章复习

　　作者: 空安　　　　发表时间：2020-04-22 20:47:59 浏览：244　|　评论：0　

### 1.1绪论
1、数据 ：所有能够输入到计算机中，且能被计算机处理的符号的集合。
2、数据元素 ：是数据（集合）中的一个“个体”，它是数据的基本单位。
3、数据项 ：**是数据的最小单位，**用来描述数据元素的。
4、数据对象 ：具有相同性质的若干个数据元素的集合，如整数数据对象是所有整数的集合。

““ ”数据结构 = 数据对象 + 结构

5、元素关系包括 ：相邻关系和邻接关系

**1.1.1 数据结构的构成 ：逻辑关系 --> 存储结构 --> 数据运算 **

1、数据的逻辑结构表示
（1）表格 
（2）二元组  B =（ D ，R ）
   B--数据结构 
   D--元素集合 
   R--二元关系的集合
   序偶< x , y > : x 为 y 的前驱元素；y 为 x 的后继元素。
** * ** 注 ：序偶< x , y >是有向的，序偶（ x , y ）是无向的。
 (3)图形
 
2、数据的存储结构表示
存储结构：数据在计算机中的存储方式

（1）结构体数组
```cpp
struct {
	int no;
	char name[8];
	char sex[2];
	char class[4];
}stud[7]={{1,"张斌","男","9901"},
		 ……
		  {5,"王萍","女","9901"}}
```
特点：
①所有占用一整块内存空间
②逻辑上相邻的元素，物理上也相邻
 -----即 顺序存储结构
 
（2）链表
```cpp
typedef struct studnode{
	int no;
	char name[8];
	char sex[2];
	char class[4];
	struct studnode *next;
}studType;
```
特点：
①一个逻辑元素用一个结点存储，每个结点单独分配，故有结点的地址不一定是连续的。
②用指针来表示逻辑关系。
-----即 链式存储结构

3、数据运算
运算描述和运算实现

总结：
①同一逻辑结构可以对应多种存储结构，
②同样的运算，在不同的存储结构中，其实现过程是不同的。

**1.1.2逻辑结构类型**
1、集合
（1）元素之间关系：无
（2）特点：数据元素之间除了“属于同一集合”的关系外，别无其他逻辑关系。

2、线性结构
（1）元素之间关系：一对一
（2）特点：开始元素和终端元素唯一，其余元素有且仅有一个前驱元素和后继元素。

3、树形结构
（1）元素之间关系：一对多
（2）特点：开始元素唯一，终端元素不唯一。

4、图形结构
（1）元素之间关系:多对多
（2）特点：所有元素都可能有多个前驱元素和多个后继元素。

**1.1.3存储结构类型**
1、顺序存储结构
2、链式存储结构
3、索引存储结构
4、哈希（散列）存储结构

**1.1.4数据类型和抽象数据类型**
1、数据类型：一个值的集合定义在此集合上的一组操作的总称
2、抽象数据类型：逻辑结构+抽象运算

### 1.2算法及其描述
数据元素之间的关系有逻辑关系和物理关系，对应的算法有基于逻辑结构的运算描述和基于存储结构的运算实现。

**算法的特性：(考点：给一个程序问你违反了哪些特性 或者 直接考简答题)**
（1）有穷性：在有穷步之后结束，算法能够停机。
（2）确定性：无二义性。
（3）可行性：通过基本运算有限次执行来实现。 （比如除零错误等等）
（4）有输入
（5）有输出

**C++中提供了一种引用运算符“&”用于描述输出型参数：**
```cpp
int a=10；
int &b=a;  //a为b的引用
//两个变量共享内存空间 --> a,b同时发生改变
//无论是改变实参a还是改变实参b 最后两者的结果都一样 是相互影响的
```
**1、编写swap（x,y）函数**
第一种：
```cpp
void swap1(int *x,int *y)
{
	int tmp;
	tmp=*x;
	*x=*y;
	*y=tmp;
}

//函数调用时写为：swap1(&a,&b);
```

第二种：
```cpp
void swap2(int &x,int &y)
{
	int tmp=x;
	x=y;
	y=tmp;
}

//函数调用时写为：swap2(a,b) 实际上就是 x与a，y与b共享存储空间
```

**2、下面来分析 普通的参数传递 和 引用类型的参数传递**
```cpp
//普通的参数传递
void fun1(int n)
{
	int m=2;
	fun2(m);
	printf("%d\n",m);
}

void fun2(int x)
{
	x++;
	printf("%d\n",x);
}
//从fun1（m）----> fun2（x）是实参到形参单向值传递
//运行结果为fun2里面的x为3 func1里面的m为2 并没有改变
```

```cpp
void fun1(int n)
{
	fun2(n);
	cout<<n<<endl;
}

void fun2(int &x)
{
	x++;
	cout<<x<<endl;
}
//从fun1（m）--->fun2（x） 实参到形参的单向值传递
//从fun2（x）--->fun1（m） 形参回传给实参，实参给形参同步发生改变
//结果都为3 fun2先输出
```
-
-
-
例题：求一元二次方程的解
？？无法运行暂不贴代码

### 1.3算法分析基础
分析算法占用的资源：
①CPU时间  --> 时间性能分析
②内存空间  --> 空间性能分析

**1.3.1时间复杂度**
算法=控制语句+原操作
```cpp
for(int i=0;i<n;i++)     //频度n+1，执行n次 （循环了n+1次但只执行了n次）
	for(int j=0;j<n;j++)    //频度n（n+1）
		C[i][j]=A[i][j]+B[i][j];  //频度n*n=n^2
//综上T（n）= n+1 + n(n+1) +n^2 = 2n^2+2n+1 = O(n)
```

**O(1)< O(log2N) < O(N) < O(Nlog2N) < O(N^2) < O(N^3) < O(2^N) < O(N!)

```cpp
void fun(int a[],int n,int k)
{
	int i;
	if(k==n-1)
		for(i=0;i<n;i++)    	//n次
			printf("%d\n",a[i]);
	else
	{
		for(i=k;i<n;i++)      //n-k次
			a[i]=a[i]+i*i;
		fun(a,n,k+1);
	}
}
 T1（n，k）=n         当k=n-1时
 T(n)=n-k+T1(n,k+1)   其他情况
综上：T（n）= T1（n，0）= n + T1（n，1）
			= n +（n-1）+ T1（n，2）
			= ……… = n +（n-1）+ (n - 2) + …… + 2 + T1 (n , n - 1)
			= n + (n - 1) + …… + 2 + n = O(n^2)
```

**1.3.2空间复杂度**
上个例题：
S1（n，k）= 1              当k = n-1时
S1（k）= 1 + S1（n，k + 1） 其他情况
-->S(n)=s1(n,0)=1+S1(n,1)=1+1+S1(n,2)=……=1+1+……+1=O（n）

### 1.4最好、最坏和平均时间复杂度分析
递归算法分析 -- 也称变长时空分析
非递归算法分析 -- 也称定长时空分析

```cpp
设计一个算法，求含n个整数元素的序列中前i（1<=i<=n）个元素的最大值时，需要元素比较（i-1）-1+1=i-1次。在等概率情况下：T（n）= ∑ 1/n ×（i-1）= 1/n ∑（i-1）=（n-1）/2 = O(n)-----平均时间复杂度
	该算法的最坏复杂度：W（n）=O（n） （当i=n时）
	该算法的最好复杂度：B（n）=O（1）  (当i=1时)
	
	int fun(int a[],int n,int i)
	{
		int j,maxx=a[0];
		for(j=1;j<=i-1;j++)
			if(a[j]>maxx)maxx=a[j];
		return(maxx);
	}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

空安

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【数组的距离】（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

空安---《数据结构》第一章复习

评论区

精彩推荐

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯历届试题-九宫重排（C++代码）

打水问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）

一元一次方程（C语言代码）

空安

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【数组的距离】 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

空安---《数据结构》第一章复习

评论区

精彩推荐

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯历届试题-九宫重排 （C++代码）

打水问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C二级辅导-同因查找 （C语言代码）

妹子杀手的故事 （C语言代码）

一元一次方程 （C语言代码）

【数组的距离】（C语言代码）

C二级辅导-进制转换（C语言代码）

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

打水问题（C语言代码）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）

一元一次方程（C语言代码）