Skip to content

0.md

Latest commit

 

History

History
277 lines (252 loc) · 8.68 KB

0.md

File metadata and controls

277 lines (252 loc) · 8.68 KB

==课程基本情况==

课程名称：数据结构

教材：严蔚敏老师人气销量第一的紫/白书

授课教师：刘鹏远

办公室：主南310

微信没变：13911510796 不定时回复

固定答疑：每周1,2,5的6:00-6:50，操场

助教：韩越，卢梦依（硕士） 可加微信

课代表：汇总想法建议意见、沟通、协助考勤。爱学。

考核（动态调整）：

  • 考勤+期中+作业： 30%-

  • 期末： 70%+（笔试）

作业要求：

  • 不能晚交作业，否则零分

  • 提交后，每一个人在电脑前当助教面，讲提交的代码，由助教判定分数

  • 检查评分标准区间如下：

    • 零分：没交/没按时交/抄作业/没当助教面讲代码思路

    • 60分：不能执行，代码很多问题，能讲清楚一些代码

    • 80分：不能执行，代码问题较少，基本能讲清楚

    • 100分：能执行，代码基本没有问题，能够讲清楚

注意：

  • 1、难以考试前靠几天突击通过

  • 2、中途别轻易掉队/溜号，不容易追

==课程重要性==

为什么安排最优秀的老师(之一)给大家上课呢？(害羞笑)

重要哈

专业基础必修核心课程（训练思维能力+动手能力）

课程设置时间为大二：

  • 大一清闲得无聊了，大二学生精力最充沛

  • 求知欲、学习力最强

功利上：名企笔试面试核心、考研专业必考，有用

此外：课时较多，不及格率高，平均成绩低

最后，也是最重要的是，安排了中国，外国双助教，请多多请教

彩蛋：帮老师减肥计划(老师承诺，减肥斤数=平均分-60)

==本讲内容==

数据结构是什么？

回忆(复习)C语言

==回忆指针==

C语言中变量名、值、地址、存储单元及类型间的关系(声明某个类型的变量并赋值后发生了什么？)

  • int a = 10;

  • 编译器将分配一个可用起始地址，类型确定，则存储单元大小(末尾)确定。存储单元大小为4字节，假设起始于00000010，则结束于00000013

  • 存储单元中放入数据10，存储单元中的数据就是该单元的值

  • 存储单元的起始地址，称为该单元的地址，该单元的地址为：00000010

  • 为方便写代码的人指称，用变量名来标示存储单元，以后用变量a来指称该单元

  • 对变量名a操作就是操作a的内容（值），a的值就是单元的值，a的址就是单元的址

  • 存储单元四个属性：

    • 名-对应变量名

    • 值-对应存储值

    • 址-对应存储地址

    • 类型-与名的类型一致，对应单元所占字节数

示例

  • int a=10; //值为10，存储在名为a的存储单元

  • 可用&a即&加变量名得到变量a的地址也就是存储单元a的地址

  • printf("addr:%p\n", &a);，%p表示指针类型

  • 指针就是用来存放地址的一种数据类型

声明

  • 声明指针的类型名要与其指向的数据类型匹配

  • int * ptr;，通过 类型名 * 指针名 来声明指针

  • 则ptr为一个将指向整型存储单元的指针

  • ptr = &a;，此时ptr的值为变量a的地址，也就是存储单元a的地址，因为可通过ptr的值，找到存储单元a，所以一般称指针ptr指向a（单元）

&及*运算

  • &，取址符，对变量名(即存储单元)操作，得到变量名(即存储单元)对应地址

  • *，取值符，对地址操作，得到对应地址存储单元内存储的数值

  • int b, a = 10; int * ptr = &a; b = *ptr;

  • 以上语句最后实现了将数值10赋值给b，结果是b单元内也存储了10

演示程序

  • 1、基本使用，各程序块内同名变量地址

  • 2、试图交换变量

  • 3、指针交换变量

下午上机及作业

  • 0、实现课上代码

  • 1、分别定义int/float/char/double变量，赋值，并打印值及变量地址

  • 2、定义相应指针，指向上述变量，打印各个指针的值，指针的地址，指针指向的值

  • 3、写函数，三个参数(a,b,c)，执行后，可使main中的a,b,c对应a+b,b+c,c+a

==回忆指针与数组==

指针和数组

  • int a[10]={0,1,2};

  • 编译器分配一个可用起始地址，分配存储单元大小为数组元素类型大小*数组元素个数

  • 将该单元起始地址命名为a。a的值是确定的地址(a就是一个确定地址的别名，可想象为#define a 00xxxxx0)，因此数组名a是指针常量，是带类型与元素个数信息的指针常量。

  • 由于该单元的起始地址也是数组的第一个元素的地址，因此可知：a==&a[0]

  • 指针的+-运算，可以跳到前/后一个元素的地址

  • a+n == &a[n]，因此，a[n] == *(a+n)

  • 指针变量可以做++/--运算，但数组名不能做自加自减运算(因为它是一个确定的存储单元地址的常量)

演示程序

  • 4、指针的+-运算

  • 5、数组/指针作为函数参数

内存分配

  • 一般内存分配

  • 动态内存分配，malloc---memory allocate，原型在stdlib.h

  • 内存释放，free

  • 内存再分配，realloc

示例程序

  • 6、内存分配释放与再分配

下午上机及作业（均需要完整实现）

  • 0、实现课上代码，并实验指针的赋值，+-，自增自减，指针相减

  • 1、函数参数为数组及大小，使其奇数索引位置的值为0(指针运算实现)

  • 2、将5.c改为函数参数为数组首尾元素地址，实现求和

  • 3、写程序，用户可输入n，动态分配大小为n的数组A并求和；然后用户可以再输入m个数，重新分配内存，使输入的m个数能够连在A的后面，形成大小为m+n的数组B，最后释放动态分配的内存。

==回忆结构体struct==

声明(图示)：

struct student{
	char name[20];
	int age;
	char sex;
};

  • 结构声明了一个“模板”，其实就是声明了一个“用户自定义类型”

  • 也就是说，struct student目前就是一个类型名,因此：

  • 可用类型名声明该类型的变量：

  • struct student computer;

  • 这个类型包含多个“项”，操作每一个项：

computer.age = 20; 
computer.sex = 'm'; 
strcpy(computer.name, “AlphaGo”);

也可以在定义结构体时候直接声明一个结构体变量，效果等价

struct student{
	char name[20];
	int age;
	char sex;
}computer;

可用typedef定义别名

  • 如教材中P10中的：typedef int Status;则Status a;等价于int a;

  • typedef int * Ttype;则Ttype p;等价于int * p;

  • 对结构体可以：typedef struct student Student;

  • 则就可以直接 Student computer;

  • 也可以在定义结构体的时候，同时定义别名，效果等价：

typedef struct student
{
    char name[20]; 	
    int age; 
    char sex;
}Student;

结构体指针

  • 即指向结构体的指针

  • 整体上将结构体想成普通变量使用

  • 结构体指针访问结构体各项的值一般用->更方便

computer->age = 20; 
computer->sex = 'm'; 
strcpy(computer->name, “AlphaGo”);
//等价于
(*computer).age = 20; 
(*computer).sex = 'm'; 
strcpy((*computer).name, “AlphaGo”);

结构体指针别名定义

typedef struct student{
	char name[20];
    int age; 
    char sex;
}*Student;

  • 定义一个指向该结构体的指针别名

  • 相当于typedef struct student * Student;

  • Student computer;，computer为指向student结构体的指针

  • 访问结构体指针指向的值：

computer->sex='f';
computer->age=10;

程序示例

  • 7 结构体及指针

明天上机及作业

  • 1、将程序示例7中的test_error_1改正确

  • 2、在程序示例7中，使用typedef

==回忆程序结构==

单文件程序的代码组织

//标准库
#include <xxx.h>
//常量
#define YYY 100

//函数原型
int zzz(float, int *);

//主函数
int main(void)
{
    xxxxxxx;
    return 0;
}

//函数实现
int zzz(float a, int * p)
{
    xxxxxxx;
    return cccc;
}

简单项目的代码组织

  • 设项目名称为exp
  • 三个文件：exp.h, exp.c, use_exp.c
//exp.h 

//常量
#define YYY 100
#define ZZZ 100

//结构声明

struct xxx
{
    int a;
    char b;
};


//函数原型
int ex1(float, int *);
int ex2(float, int *);
//exp.c 

//标准库区
#include <xxx.h>
#include <yyy.h>
//头文件
#include "exp.h"
//函数实现
int ex1(float f, int * a)
{
    //代码
}
int ex2(float g, int * b)
{
    //代码
}
//use_exp.c 

//标准库区
#include <xxx.h>
#include <yyy.h>
//头文件
#include "exp.h"
//函数实现
int main(void)
{
    //代码
    return 0;
}