大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说什么是数据结构？_数据结构主要研究什么,希望您对编程的造诣更进一步.

一、数据结构与算法官方定义

“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”——Sartaj Sahni，《数据结构、算法与应用》
“数据结构是ADT（抽象数据类型 Abstract DataType）的物理实现。”—— Clifford A.Shaffer，《数据结构与算法分析》
“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。”
——中文维基百科

综上：从上面的三种官方定义可以看出，数据结构和算法通常是一起出现的。

二、例1：如何在书架上（存储空间）摆放图书（数据）

只有事先得知数据规模的问题，才能得到处理数据的方法

2.1 方法1：随便放

哪里有空放哪里，查找图书困难

2.2 方法2：按照书名的拼音字母顺序排放

二分查找，通过书名的拼音字母不断缩小查找图书的范围，新书来了插入会成为一个问题

2.3 方法3：综合方法1和2

把书架划分成几块区域，每块具区指定摆放各种类别的书；每块区域内，按照书名的拼音字母顺序排放，斟酌类的分法

综上：解决问题方法的效率，和数据的组织方式有关

三、例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印1到N的全部正整数

3.1 方法1：循环实现

/* c语言实现 */
void PrintN (int N)
{int i;
 for (i=1; i<=N; i++)(
 printf("%d\n", i);
 )
 return;
}
# python语言实现
def print_n(n: int):
 for i in range(n):
 print(n)

3.2 方法2：递归实现

N过大，代码会直接罢工

/* c语言实现 */
void PrintN (int N)
{if (N){
 PrintN(N - 1);
 printf("%d\n", N);
}
 return;
}
# python语言实现
def print_n(n: int):
 if n:
 print_n(n - 1)
 print(n)

综上：解决问题方法的效率，和空间的利用效率有关

四、例3：写程序计算给定多项式在给定点x处的值

4.1 方法1

对于上述的多项式，我们可以使用以下代码实现：

/* c语言实现 */
double f(int n, double a[], double x)
{int i;
 double p = a[0]
 for (i=1; i<=n; i++)
 p += (a[i] * pow(x, i));
 return p;
}
# python语言实现
def f(n: int, a_list: list, x: float):
 p = a_list[0]
 for i in range(1, n):
 p += (a_list[i] * pow(x, i))
 return p

4.2 方法2

但是上述的方法极其复杂，我们可以对多项式进行如下化简：

/* c语言实现 */
double f(int n, double a[], double x)
{int i;
 double p = a[n];
 for (i=n; i>0; i--)
 p = a[i-1] + x*p;
 return p
}
# python语言实现
def f(n: int, a_list: list, x: float):
 p = a_list[n]
 for i in range(0,n,-1):
 p = a_list[i-1] + x*p
 return p

五、程序运行时间捕捉方法-clock()

clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。

常数CLK_TCK：机器时钟每秒所走的时钟打点数。

/* c语言实现 */
#include <stdio.h>
#include <time.h>
clock_t start, stop;
/* clock_t是clock()函数返回的变量类型 */
double duration;
/* 记录被测函数运行时间，以秒为单位 */
int main()
{/* 不在测试范围内的准备工作写在clock()调用之前*/
 start = clock(); /* 开始计时 */
 MyFunction(); /* 把被测函数加在这里 */ 
 stop = clock(); /* 停止计时 */
 duration = ((double)(stop -start))/CLK_TCK;
 /* 计算运行时间 */
 /* 其他不在测试范围的处理写在后面，例如输出duration的值 */
 return 0;
}
# python语言实现
import time
def main():
 start = time.clock() # start = time.process_time()
 my_function()
 stop = time.clock() # stop = time.process_time()
 t = stop - start # 以秒为单位
 
 return t

对于一个九项式的测试程序，运行一次，效果微乎其微，因此可以让被测函数重复运行充分多次，使得测出的总的时钟打点

间隔充分长，最后计算被测函数平均每次运行的时间即可!

综上：解决问题方法的效率，和算法的巧妙程度有关

六、说到底，什么是数据结构？

数据对象在计算机中的组织方式
逻辑结构
物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

七、抽象数据类型（Abstract Data Type）

数据类型
数据对象集：数据本身
数据集合相关联的操作集：类（数据和方法的集合）
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题，即可以理解为伪代码

八、例4：“矩阵”的抽象数据类型定义

类型名称：矩阵（Matrix
Matrix）
数据对象集：一个M×N
M×N的矩阵A
M×N
=(a
ij
)(i=1,…,M;j=1,…,N)
AM×N=(aij)(i=1,…,M;j=1,…,N) （不考虑矩阵A
A是二维数组、一维数组、十字链表）由M×N
M×N个三元组<a,i,j>
<a,i,j>构成，其中a
a是矩阵元素的，i
i是元素所在的行号，j
j是元素所在的列号。
操作集：对于任意矩阵A、B、C∈Matrix
A、B、C∈Matrix，以及整数i、j、M、N
i、j、M、N
Matrix Create( int M, int N )：返回一个M×N
M×N的空矩阵；
int GetMaxRow( Matrix A )：返回矩阵A
A的总行数；
int GetMaxCol( Matrix A )：返回矩阵A
A的总列数；
ElementType GetEntry( Matrix A, int i, int j )：返回矩阵A
A的第i
i行、第j
j列的元素；
Matrix Add( Matrix A, Matrix B )：如果A
A和B
B的行、列数一致，则返回矩阵C=A+B
C=A+B （不考虑先按行加、先按列加、什么语言实现），否则返回错误标志；
Matrix Multiply( Matrix A, Matrix B )：如果A的列数等于B的行数，则返回矩阵C=AB
C=AB，否则返回错误标志；
……

综上：抽象不需要关心具体的细节

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/11793.html

什么是数据结构？_数据结构主要研究什么