<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
说明
1. 建议用notepad++、或UE打开,文件以.c的形式提供,就是是为了高亮显示,才会有论坛图片上的效果,如果用记事本观看会有
点乱,如果记事本采用自动换行会更乱。
2. 本人没什么技术,所以就放点学习笔记,希望能帮到想要或者正在学习数据结构的人。郝斌老师的教程没有图的讲解,需要自己
看,但郝斌老师是个非常认真负责的好老师,教程以《数据结构(严蔚敏)》为教材,所以我就买了一本,等看完视频发现,白
买了,老师上课基本没提它。印象中就提到2次还是3次说要翻书,但都将书上的东西以附件的形式提供在网上了。在此十分感激
本来没几节课,老师将视频教程划分得十分仔细,所以网上流传版本有78课(不包括附加的自学指针等视频(只能说老师太尽责
了))
3. 文件中的代码均经过本人测试(VC6.0 英文版)并通过
4. 欢迎大家到以下两个论坛交流
初学编程者乐园:
www.fishc.com(小甲鱼的网站) 鱼C论坛
www.cctry.com(Syc老大的论坛) VC驿站
当然,国内最牛的非 看雪 莫属,一蓑烟雨也相当不错,我还是菜鸟,就在上面混。看完自行删去
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
课程大纲
1.从12课开始正式讲解数据结构,前面课程是学该门课程的必备基础
2.★14课正式讲解——链表
3.第27课——如何学习算法自己的一些感想 很不错!!
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
模块一:线性结构
连续存储[数组]
1. 数组:元素类型相同,大小相等
2. 数组优缺点:(相对于链表)
离散存储[链表]
1.定义:
头结点数据类型和首节点数据类型一样。
n个节点离散分配
彼此通过指针相连
每个节点只有一个前驱节点和后续节点
首节点没有前驱节点,尾节点没有后续节点
首节点:第一个有效节点(注意区别于头结点)。
尾节点:最后一个有效节点。
头结点:为了方便对链表的操作而指向链表首节点的指针。只是为了方便操作,无其它意义,并不包含链表有效节点个数等信息。
头指针:指向头结点的指针变量(注意区别首指针)
尾指针: 指向尾节点的指针变量
2.分类:
单链表
双链表:每个节点有两个指针域;
循环链表:能通过任何一个节点找到其他所有节点。
非循环链表
3.算法:
遍历
清空
查找
销毁
求长度
排序
删除节点
插入节点
算法:
狭义的算法是与数据的存储方式密切相关
广义的算法与数据的存储无关
泛型:
利用某种技术达到的效果:不同的存储方式,达到的效果是一样的。
线性结构的两种常见应用:栈和队列
专题:递归
定义:函数自己调用自己(直接或间接)
1.1+2+3+4+...+100
2.求阶乘
3.汉诺塔
4.走迷宫
模块二:非线性结构
树
图
模块三:
查找和排序
折半查找
排序:
冒泡
插入
选择
快速排序
归并排序
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
***************************************************************************************************************************
1.ST概述/衡量算法的标准
***************************************************************************************************************************
数据结构定义
把现实中大量复杂的问题以特定的数据类型和特定的存储结构保存的主存储器(内存)中,以及在此基础上为实现某个
功能(如查找、删除元素,对元素排序)而执行的相应操作。这个相应的操作也叫算法
数据结构=个体存储+个体关系
算法=对存储数据的操作
衡量算法的标准:
1.时间复杂度 即程序大概执行次数,而非执行时间长短
2.空间复杂度 算法执行过程中,大概所占用的内存
3.难易程度
4.健壮性
数据结构中没有“堆”的概念,“堆栈”就是指“栈”;
***************************************************************************************************************************
3.数据结构的特点 2012.3.20
***************************************************************************************************************************
堆内存:以堆排列的方式分配内存
栈内存:以压栈出栈的方式分配的内存
两者分配内存的算法不一样。
字段:反应的是事物的——属性
记录:一个整体的事物
表 :同一事物的集合
***************************************************************************************************************************
4.预备知识 2012.3.20
***************************************************************************************************************************
1.指针
2.结构体
3.动态内存的分配和释放
1.指针:
指针就是地址,地址就是指针 注意:指针和指针变量是两回事
指针变量是存放内存地址的变量 int *p:系统分配内存表将p变量标记为——已分配
p+i的值是p+i*(p所指向的变量所占字节数)
指针本质是操作受限的非负整数
指针分类:
1.基本类型的指针
2.指针和数组的关系
int a[5]={1,2,3,4,5} 数组名a 是一个 指针常量,存放数组首元素地址即a[0]地址 它是指针,不可更改的指针
下标与指针关系: a[i]<=>*(a+1)<=>i[a]
%p表示输出地址
***************************************************************************************************************************
6.指针补充 2012.3.20
***************************************************************************************************************************
指针变量统一只占4个字节。
***************************************************************************************************************************
7.通过函数修改实参的值 2012.3.20
***************************************************************************************************************************
#include "stdio.h"
void f(int *p);
void main()
{
int i=10;
f(&i);
}
void f(int *p)
{
*p=99;
}
若不考函数的返回值,只能靠指针来改变实参的值
***************************************************************************************************************************
8.结构体的使用 2012.3.20
***************************************************************************************************************************
相对于C++的类而言,结构体里只能有属性,没有方法,就是说里面没函数。而类里可以有类函数。
和类不同结构体适用于算法。
#include "stdio.h"
#include "string.h"
struct Student
{
int sid;
char name[20];
int age;
}; //末尾分号不能省略。。。。。。。。。
void main()
{
struct Student st={303930,"lose",12}; //第一种方式
printf("%d %s %d\n",st.sid,st.name,st.age);
st.sid=123456;
//st.name="lose all"; error!!
strcpy(st.name,"loseall");
st.age=34;
printf("%d %s %d\n",st.sid,st.name,st.age);
struct Student *pst;
pst=&st
(*pst).sid=999999;
pst->name="nisi";
}
两种方式,假如有结构体:
struct Student
{
int sid;
char name[20];
int age;
}
struct Student st={1111111,"2222222",3333333}
struct Student *pst=&st;
则有:
st.sid=100
pst->sid=100 两种方式效果相同
************************************************************
// 比较两种方式的不同
#include "stdio.h"
#include "string.h"
struct Student
{
int sid;
char name[20];
int age;
};
void f(struct Student *pst);
void g1(struct Student st);
void g2(struct Student *st);
void main()
{
struct Student st;
f(&st);
//方法一输出,特点是耗内存,耗时间
g1(st);
//方法二输出:
g2(&st);
}
void f(struct Student *pst)
{
pst->sid=1111111;
strcpy(pst->name,"pst_name");
pst->age=200;
}
void g1(struct Student st)
{
printf("%d %s %d 方法1 特点是耗内存,耗时间\n",st.sid,st.name,st.age);
}
void g2(struct Student *st)
{
printf("%d %s %d 方法2\n",st->sid,st->name,st->age);
}
*******************
- 1
- 2
- 3
前往页