一、会：基本概念，基本思想 二、懂：思想证明 三、写：C代码
第一章 引论
一、算法：若干指令组成的有限序列。
五个特征：输入、输出、确定性、有限性、可行性。
二、数据结构=逻辑结构，物理结构
数据逻辑结构(顶层)：三种，线性、层次（树）、图，
逻辑结构是： 成分数据 +成分数据之间关系 数据元素（成分数据）：一个同学档案 数据项：姓名、生日、学号....
数据物理结构(底层，存储结构)：两种，顺序（数组）、非顺序（链表）
同一个逻辑结构可以在不同的物理结构中实现， 但是各种操作算法的具体实现代码不同
（比如在数组插入，在链表中插入算法不同）
涉及题目：
05年 二(1,3)
三、复杂度=占用资源的多少，时间、空间
O(...)，表示数量级
O(1) 1、时间复杂度 相对时间，一条指令（语句）运行时间 为1计算： 非递归=主要循环（最费时）执行的次数 递归= 结果中的常数(0)和系数(1)，低阶全 部去掉(0) 3n+7+0.5*n*n=O(n*n) 复杂度类型：最好、最坏、平均 2、空间复杂度：辅助数据空间,如果没 有,则是O(1) 涉及题目： 08年 2,3,9,12 07年 15 四、结构类型、变量、指针 （抽象数据类型不会考）： 1、什么是类型？类型是模板，用于定义变量 int double float char ... 如果不定义变量，类型没用 int x; x占2字节 double y; y占8字节 说法：int占2字节，double占8字节 实际上x,y占字节 生活模板 C语言 ======＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 二居室模板 图纸规划 类型 int double 主卧20平方 小卧10平方 客厅20平方 厨房10 厕所4 阳台4 总计68平方 －－－－－－－－－－－－－－－－－－－－－－ 房子盖好 int x; 张三家是二居室 x是整型变量 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 类型：名字，大小，不占内存 变量：名字，大小，占内存 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ C语言允许程序员自己定义类型？ 因为C语言原来的类型太少！ 比如要存储处理学生档案数据 学号：整数 姓名：字符串8个字符 性别：字符,M,F 地址：字符串40个字符 分数：浮点数组[30] －－－－－－－－－－－－－－ 定义结构类型 int num; char name[8]; char sex; char addr[40]; float score; typedef struct student{ int num; 2 成员 char name[8]; 8 char sex; 1 char addr[40]; 40 float score; 4 }STUDENT; 定义一个结构类型！ 名字sturct student或者STUDENT,大小55字节 －－－－－－－－－－－－－ 定义结构变量 struct student student1, student2，stu[100],*p; 或者 STUDENT student1, student2，stu[100],*p; p自己占4个字节，管65字节 p里只存一个地址，; int x,y; x=8; 注意： 类型名不能用作变量名 以下代码大错！！ scanf(\，%s，%c，%s, %f\； printf(\，%s，%c，%s, %f\； ---------------------------------- 引用结构体变量中成员的方式为 结构体变量名.成员名 student1.num=101; student1.name[0]='T'; student1.name[1]='o'; student1.name[2]='m'; student1.name[3]='\\0'; student1.sex='M'; student1.score=80.5; 张三家.厨房 李四家.厨房 student2.score=student1.score; sum=student1.score+student2.score; student1.age++; ++student2.age; scanf(\，%s，%c，%s, %f\ &student1.num, &student1.name, &student1.sex, &student1.addr, &student1.score)； printf(\，%s，%c，%s, %f\ student1.num, student1.name, student1.sex, student1.addr, student1.score)； stu[0].num=103; 数组名[下标].成员名 三个问题： 结构类型定义， 结构变量定义， 结构变量引用 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 简单写法1： 结构类型定义和 结构变量定义写在一起， struct student ｛ int num； char name[20]； char sex； int age； float score； char addr[30]； ｝student1,student2； 简单写法2： 结构类型定义和 结构变量定义写在一起， 省略类型名字 struct ｛ int num； char name[20]； char sex； int age； float score； char addr[30]； ｝student1,student2； 保留字：不能用作变量名,数组名，函数名 ========================= 指向结构体类型数据的指针 struct student *p; 或者 STUDENT *p; p自己占4个字节，管65字节 p里只存一个地址，; p=&student1; 把student1的第一个字节的地址存到p中。 能不能通过p来访问student1的成员？ 可以。 方式1: p->num 就是student1.num p->name 就是student1.name p->name[0] 就是student1.name[0] p->name[1] 就是student1.name[1] p->birthday.month 就是student1.birthday.month .... 方式2:不常用 (*p).num 就是student1.num (*p).name 就是student1.name p++ 加65 *(p+2).num 等价 (p+2)->num (p++)->num *(p++).num (++p)->num ==================== 类型定义：typedef例子： typedef struct x *YYY;//*表示指针变量类型，类型名是YYY,x表示YYY是指向x模板的类型 typedef struct x{ int a; int b; char c; }ListItem; void main(){ ListItem y; y.a=6;//y家a房间住6 YYY p; p=&y;//y家地址保存在p中 p->a=7; } 五、指针 6、 typedef struct x *YYY;//*表示指针变量类型，类型名是YYY,x表示YYY是指向x模板的类型 typedef struct x{ int a; int b; char c; }ListItem; void main(){ ListItem y; //y是结构变量， //y是a,b,c变量的总名字， y.a=6;//一旦有了y，则a,b,c不能 //单独被访问， y.b=7;//必须在y.之后被访问 y.c='a'; //一旦分了房子，不能单独说 //厨房漏水，要说张三家厨房漏水 YYY p; //p是另外一个变量，而且 //是另外一个类型 p=&y; //p与y不是一个变量，也不 //是一个类型，p中存放y首字节地址。 //p管理y的所有字节 p->a=7; //可以通过p来访问y的a,b,c p->b=6; //因为p是指向y类型的指 //针，p->b会自动跳过a所 //占的字节（不止一个字节）， //取得b所占的字节（不止一个）， //这就是指针类型的必要性。 p->c='b'; } p++相当于p加上sizeof(y)， 即y变量占用的字节数 第二章 线性表 线性表概念：p18 同一类型元素的有限序列，a1,a2,...an 前驱，后继，长度，空表 一、顺序表(线性表存在数组中) 假定数组是int a[n]; 1、 顺序表查询：给定一个关键字，在数组中顺序比较 for(i=0;i 查询最好复杂度：O(1)，第一个a[0]就是 查询最坏复杂度: O(n)，最后一个a[n-1]才是 查询每个元素需要比较次数之和 查询平均复杂度=------------------------------ 元素个数 1 + 2 + 3 +... +n = --------------------------- n n*(n+1) --------- 2 n+1 =------------- =----- =0.5n+0.5=O(n) n 2 查询平均复杂度 = （每个元素查询次数*该元素查询概率） 之和 = 第1个元素的查询次数*该元素查询概率 +第2个元素的查询次数*该元素查询概率 +...+ +第n个元素的查询次数*该元素查询概率 1 1 1 =1*--- + 2*---- + ...+ n* ---- =O(n) n n n