西北大学计算机科学系第1章绪论1.1数据结构的基本概念（定义）数据（Data）数据元素（DataElement）数据对象（DataObject）数据结构（DataStructure）数据结构（DataStructure）数据类型(DataType)数据类型(DataType)数据抽象与抽象数据类型1.2数据结构的内容逻辑结构集合结构线性结构树型结构图状结构或网状结构综上所述，数据的逻辑结构可概括为：存储结构逻辑结构与存储结构的关系为：运算集合数据结构的内容1.3算法算法（Algorithm）定义算法的特性算法设计的要求1.4算法描述的工具算法、语言、程序的关系设计实现算法过程步骤类描述算法的语言选择3.赋值语句对C语言作以下描述：4.条件选择语句情况语句对C语言作以下描述：while语句1.5对算法作性能评价性能评价有关数量关系计算关于算法执行时间语句频度算法的时间复杂度常用的时间复杂度频率计数常用的时间复杂度频率计数最坏时间复杂度voidbubble(inta[],intlength){将a中整数数组重新排序，达到递增有序}inti=0,j,temp;intchange;do{change=false;for(j=1;j<length-i;j++)if(a[j]>a[j+1])算法的空间复杂度1.6数据结构与C语言表示程序示例1-1：根据测试次数与测试成绩的关系，采用数组结构存储测验成绩，提高了程序的适用范围。main(){intsum，erage；inti;intt[10]=80，85，77，56，68，83，90，92，80，98}/*分别赋值*/sum=0;/*总分置初值*/for(i=0;i<10;i++)sum=sum+t[i];average=sum/10;/*计算平均分*/printf(“总分=%d\n”,sum);printf(“平均分=%d\n”,average);}1.6.2结构化程序设计与函数的模块化①结构化程序设计目的1.6.3面向对象与抽象数据类型面向对象程序设计的特点是封装性、继承性和多态性结构化与面向对象开发方法的不同点数学模型数据的抽象抽象数据类型抽象数据类型实现ADT的表示与实现关于参数传递：1.6.4算法描述规范与设计风格1.6.4算法描述规范与设计风格2.算法描述要点避免可能出现的二义性表达3.与参数传递的相关技术#include<stdio.h>viodswap1(inta,intb){intc;c=a;a=b;b=c;printf(“swap1中的a=%d,b=%d”,a,b);}viodswap2(int*a,int*b){intc;c=*a,*a=*b,*b=c;}voidmain(){intx=100,y=800;swap1(x,y);/*调用函数swap1()*/printf(“\n调用swap1后x=%d,y=%d”,x,y);/*输出调用swap1后的数据*/x=100;y=800;swap2(&x,&y);/*调用函数swap2()*/printf(“\n调用swap2后x=%d,y=%d”,x,y);/*输出调用swap2后的数据*/}4.函数结果的带出方式①全局变量方式：int*fun2(inta[],intn)/*将最大、最小值放到数组b中，通过return返回*/{staticintb[2];b[0]=b[1]=a[0];//给最大值最小值赋初值inti;for(i=1;i<n;i++){if(a[i]>b[0])b[0]=a[i];if(a[i]<b[1])b[1]=a[i];}return(b);}Data*fun3(inta[],intn)/*将最大、最小值放到结构体指针p中，通过return返回*/{Data*p;inti;p=(Data*)malloc(sizeof(Data*));//指针初始化p->max=p->min=a[0];//给最大值最小值赋初值for(i=1;i<n;i++){if(a[i]>p->max)p->max=a[i];if(a[i]<p->min)p->min=a[i];}return(p);}Datafun4(inta[],intn)/*将最大、最小值放到结构体p中，通过结构体p带回返回值*/{Datap;inti;p.max=p.min=a[0];//给最大值最小值赋初值for(i=1;i<n;i++){if(a[i]>p.max)p.max=a[i];if(a[i]<p.min)p.mi