数据结构C语言版讲义

1 第一章 绪论

第一节 什么是数据结构？

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

数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。

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

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

忽略数据的具体含义，研究信息模型的结构特性、处理方法。

第二节 概念、术语

一、有关数据结构的概念

数据：对客观事物的符号表示。

例：生活中还有什么信息没有被数字化？

身份证，汽车牌号，电话号码，条形代码……

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

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

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

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

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

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

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

S：D上关系的有限集

P：D上的基本操作集

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

存储结构：数据结构在计算机中的存储形式。

顺序映象、非顺序映象、索引存储、哈希存储

逻辑结构与存储结构的关系：

逻辑结构：描述、理解问题，面向问题。

存储结构：便于机器运算，面向机器。

程序设计中的基本问题：逻辑结构如何转换为存储结构？

二、有关数据类型的概念

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

包括：原子类型、结构类型。 2 抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。

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

课程任务：

学习ADT、实践ADT。

如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……

实践指导：

为了代码的复用性，采用模块结构。

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

第三节 ADT的表示与实现

本教材中，算法书写习惯的约定。

数据元素类型ElemType：int,float,char, char[] ……

引用参数 &

算法：

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)可行性

二、算法设计的要求

好算法：

1)正确性 2)可读性 3)健壮性 4)高效，低存储

三、时间复杂度

事前估算：问题的规模，语言的效率，机器的速度

时间复杂度：在指定的规模下，基本操作重复执行的次数。

n：问题的规模。

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

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

例：求两个方阵的乘积 C＝A*B 3 void MatrixMul(float a[][n],float b[][n],float c[][n])

{ int i,j,k;

for(i=0; i

for(j=0; j

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

for(k=0; k

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

}

}

时间复杂度： )(1232)(323nOnnnnT

一般情况下，对循环语句只需考虑循环体中语句的执行次数，可以忽略循环体中步长加1、终值判断、控制转移等成分。

最好/最差/平均时间复杂度的示例：

例：在数组A[n]中查找值为k的元素。

for(i=0; i

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

四、常见时间复杂度

按数量级递增排序：

)1(O < )(log2nO < )(nO < )log(2nnO < )(2nO < )(3nO

< )2(nO < )!(nO < )(nnO

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

五、空间复杂度

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

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

六、算法举例

例1：以下程序在数组中找出最大值和最小值

void MaxMin(int A[], int n)

{ int max, min, i;

max=min=A[0];

for(i=1; i

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

else if(A[i]

printf("max=%d, min=%d\n", max, min); 4 }

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

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

if(A[i]

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

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

if(A[i]

例2：计算f(x)=a0+a1x+a2x2+....+anxn

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

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

{ float power[MAX], f;

int i;

for(power[0]=1,i=1;i<=n;i++)

power[i]=x*power[i-1];

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

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

return(f);

}

解法二：f(x)=a0+(a1+(a2+……+(an-1+anx)x)… x)x

f(x)=a0+(a1+(a2+(a3+(a4+a5x)x)x)x)x

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];

return(f);

}

五、思考题

1、问：“s=s+i*j;”的执行次数？时间复杂度？

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

if(5*i<=n)

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

s=s+i*j;

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

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

第二章 线性表

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

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

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

③除首元素外每个元素均只有一个直接前驱，

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

第一节 逻辑结构

形式定义：

Linear_list=(D，S，P)

D = {ai| ai∈ElemSet, i=0,1,2,…,n-1}

S = {| ai-1,ai∈D, i=1,2,…,n-1}

为序偶，表示前后关系

基本操作P：

①插入、删除、修改，存取、遍历、查找。

void ListAppend(List L, Elem e) ;

void ListDelete(List L, int i) ;

int SetElem(List L, int i, Elem e);

int GetElem(List L, int i, Elem &e);

int ListLength(List L);

void ListPrint(List L);

int LocateElem(List L, Elem e);

②合并、分解、排序

基本操作的用途：

集合的并、交、差运算

有序线性表的合并、多项式的运算

例：利用线性表LA和LB分别表示集合A和B，求A=A∪B。

void union(List &La，List Lb)

{ int La_len, Lb_len;

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

Lb_len=ListLength(Lb); 6 for(i=1; i<=Lb_len; i++)

{ GetElem(Lb, i, e); // 取Lb的第i个元素

if(!LocateElem(La, e)) // 在La中查找e

ListAppend(La, e); // 在La中插入e

}

}

第二节 顺序存储结构

一、概念

逻辑结构中的“前后关系”：物理结构中的“相邻关系”

loc(ai)=loc(a0)+i*sizeof(单个数据元素)

静态顺序存储结构：一维数组。

注意：第i个元素的下标是i-1

动态顺序存储结构：

#define LIST_INIT_SIZE 100

#define LIST_INCREMENT 10 // 存储空间的分配增量

typedef struct

{ ElemType *elem;

int length; //当前表长

int listsize; //当前已分配的存储空间

}SqList;

二、基本操作：

1、在ai之前插入x：

a0 a1 … ai-1 ai … … an-1

 如何移动元素？

a0 a1 … ai-1 x ai … … an-1

void SqList_Insert(SqList A, int i, ElemType e)

{ for(j=A.length-1; j>=i; j--)

A.elem[j+1] = A.elem[j];

A.elem[i]=e; A.length++;

}

2、删除ai：

a0 a1 … ai-1 ai ai+1 … … an-1