数据结构C语言版讲义.doc

第一章 绪论

第一节 什么是数据结构？

估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。

　　数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象

的行为、特性基本一致。

信息模型：信息处理领域中的数学模型。

　　数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。

数据元素：数据的基本单位。相当于"记录"。

一个数据元素由若干个数据项组成，相当于"域"。

数据对象：性质相同的数据元素的集合。

数据结构：相互之间存在特定关系的数据集合。

四种结构形式：集合、线性、树形、图(网)状

形式定义：(D，S，P)

D：数据元素的集合(数据对象)

S：D 上关系的有限集

P：D 上的基本操作集

逻辑结构：关系 S 描述的是数据元素之间的逻辑关系。

二、有关数据类型的概念

　　数据类型：值的集合和定义在该值集上的一组操作的总称。

　　 包括：原子类型、结构类型。

　　抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。

核心：是逻辑特性，而非具体表示、实现。

课程任务：

实践指导：

如：C 中的头文件、C++中的类

算法：

void add(int a,int b,int &c) { c=a+b; }

程序：

void add(int a,int b,int *p_c){ *p_c=a+b; }

第四节 算法的描述及分析

一、有关算法的概念

算法：特定问题求解步骤的一种描述。

1)有穷性　 2)确定性　 3)可行性

二、算法设计的要求

　f(n)：基本操作执行的次数　

T(n)=O(f(n)) 渐进时间复杂度(时间复杂度)

例：求两个方阵的乘积 C＝A*B

void MatrixMul(float a[][n],float b[][n],float c[][n])

{ int i,j,k;

for(i=0; i<n; i++) // n+1

for(j=0; j<n; j++) // n(n+1)

{ c[i][j]=0; // n*n

for(k=0; k<n; k++) // n*n*(n+1)

c[i][j]+ = a[i][k] * b[k][j]; // n*n*n

}

环体中步长加 1、终值判断、控制转移等成分。

for(i=0; i<n-1; i++)

if(A[i]==k) return i;

四、常见时间复杂度

按数量级递增排序：

<

<

<

<

<

<

将指数时间算法改进为多项式时间算法：伟大的成就。

五、空间复杂度

　　实现算法所需的辅助存储空间的大小。

　　S(n)=O(f(n)) 按最坏情况分析。

if(A[i]>max) max=A[i];

else if(A[i]<min) min=A[i];

}

若数组为递减排列，比较次数是多少？

if(A[i]>max)：n-1 次

if(A[i]<min): n-1 次

若数组为递增排列，比较次数是多少？

if(A[i]>max)：n-1 次

if(A[i]<min): 0 次

解法一：先将 x 的幂存于 power[]，再分别乘以相应系数。

for(f=0,i=0;i<=n;i++)

f+=coef[i]*power[i];

return(f);

}

解法二：f(x)=a

0

+(a

1

+(a

2

+……+(a

n

0

+(a

1

+(a

2

+(a

+a

5

float eval(float coef[],int n,float x)

{ int i; float f;

for(f=coef[n],i=n-1;i>=0;i--)

f=f*x+coef[i];

for(j=5*i;j<=n;j++)

s=s+i*j;

2、问：“a[i][j]=x;”的执行次数？时间复杂度？

for(i=0; i<n; i++)

for(j=0; j<=i; j++) a[i][j]=x;

第二章 线性表

线性结构：在数据元素的非空集中，

①存在唯一的一个首元素，

②存在唯一的一个末元素，

④除末元素外每个元素均只有一个直接后继。

i

i

i-1

i

　　<a

i-1

,a

i

>为序偶，表示前后关系

基本操作 P：

{ int La_len, Lb_len;

La_len=ListLength(La); // 计算表长

Lb_len=ListLength(Lb);