郝斌老师数据结构笔记.docx
- 文档编号:2226798
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:42
- 大小:23.67KB
郝斌老师数据结构笔记.docx
《郝斌老师数据结构笔记.docx》由会员分享,可在线阅读,更多相关《郝斌老师数据结构笔记.docx(42页珍藏版)》请在冰点文库上搜索。
郝斌老师数据结构笔记
数据结构概述
定义:
我们如何把现实中大量而复杂的问题已特定的
数据类型和特定的存储结构保存到主存储器(内存)中,以及
在此基础上位实现某个功能二执行的相应操作,
这个相应的操作也叫算法。
数据结构解决存储问题,算法解决数据间的关系。
数据结构=个体+个体的关系
算法=对存储数据的操作。
狭义的算法
算法:
解题的方法和步骤
衡量算法的标准:
1时间复杂度
大概程序要执行的次数,而非执行
的时间:
运行步骤最多的最关最核心的要运行的次数
可以大概代表
2空间复杂度:
算法执行过程中大概
所占有的最大内存。
3难易程度
4健壮性
前两个最重要
(一般算法有循环)
第三个内容:
数据结构的地位
(数据结构是软件中最核心的课程)
数据库和数据结构的区别:
数据库是数据结构的简化版
程序:
数据的存储+数据段操作+可以被计算机之行的语言
预备知识:
伪算法不是真正的算法
通过语言来实现伪算法,希望编程语言实现要通过指针。
链表的知识很重要,以后都会用到。
C++的指针不够,学
C语言的用途是为了以后能看懂更高级的语言
*p就代表一个变量,例如i。
int*p表示定义一个存放整
形变量的地址的指针变量。
程序运行完,内存就终止了。
复习:
1:
指针:
int*p//p是个变量名字,用来存放地址,只能存储int型变量的地址
指针的重要性:
是C语言的灵魂,
定义
地址
内存单元的编号(cpu只能访问内存,不能访问硬盘)
从0开始的非负整数,范围为0——4g-1
指针就是地址,地址就是指针
指针变量是存放内存单元地址的变量
指针和指针变量不一样
指正的本质是一个操作受限的非负整数
分类:
1基本类型的指针(p=&i表示指针变量存储i的地址,但是p为p,i为i两者无任何关系,
但是*p和i却是等效的两者可以互换)
2
2:
指针结构体
3:
动态内存的分配和释放。
4:
内存的基本单位是字节
5:
&为取地址符号
6:
#include
voidf(int*p)
{
*p=100
}
intmain()
{
inti=9;
f(&i)
printf("i=%d\n",i);
return0
}
@@如何实现被掉函数修改主调函数中普通变量的值
1:
实参为相关变量的地址(&i)
2:
形参为以该变量的类型(int型)为类型的指针变量(指针变量p)
3:
在被调函数中通过*形参变量名的方式就可以修改主函数中普通变量的值
(*p和i可以等效替换两者无任何区别)
指针和数组(Array)
数组名
一位数组名a是个指针常量
它存放的是一维数组第一个元素的地址,
它的值不能被改变
一维数组名指向的是数组的第一个元素。
下表和指针的关系
a[i]<<==>>*(a+i)下标和指针的关系
假设指针变量的名字为p
则p+i的值是p+i*(p所指向的变量所占的字节数)
指针变量的运算
指针变量不能相加,乘除。
如果两指针变量属于同一数组,则可以相减
指针变量可以相减一整数,前提是最终结果不能草果指针的范围
p+i的值是p+i*(p所指向的变量所占的字节数)
p-i的值是p-i*(p所指向的变量所占的字节数)
p++《==》p+1
如何通过被调函数修改主函数中一位数组的内容
两个参数
存放数组首元素的指针变量
存放数组元素长度的整形变量
#include《stdio.h》
voidshow-array(int*p,intlen)
{
p[2]=-1;//p[0]==*pp[2]==*(p+2)==*(a+2)==a[2]//p【i】此时就是主函数的a【i】
}
intmain(void)
{
inta[5]={11,2,3,4,5};
show_arraya(a,5)//a等价于&a[0],&a[0]本身就是int*类型
return0
}
一个double占八个字节,一个字节是8位,美一个字节都占一个地址。
指针变量都只占四个字节
p=&x表示p只代表x的第一个字节的地址
如何通过函数修改时惨的值
#include
voidf(int*q)//函数声明
intmain(void)
{
inti=9;
int*p=&i;//等效为int*p;p=&i;
printf("%p\n",p);//%P表示输出指针变量所指向的元素的地址例如此例中就输出的事i的地址。
return0;
}
voidf(int**q)
{
*q=(int*)0xFFFFFFFF;//(int*)表示强制转换0xFFFFFFFF为地址,如果不强制转换0xFFFFFFFF只表示一个十六进制的数
}
如果想改写一个变量的值,只需要发送它的地址给被掉函数,否则无法实现对主函数中变量的值的改变。
结构体:
为什么会出现结构体:
为了表示一些复杂的数据,而普通的基本类型变量无法满足要求
什么叫结构体:
(是c++中类的过度)是用户根据实际需要自己定义的复合数据类型
如何使用结构体:
structStudent={1000,”zhangshan”,20};
结构体Structsudent*pst=&st;
1;
st.sid
2.
pst->sid
Pst所指向的结构体中的sid这个成员
注意事项;结构体变量不能加减乘除,但是可以相互赋值
普通结构体变量和结构体指针变量作为函数传参的问题
#include
#include
struct结构体Student
{
intsid;
charname[200];
intage;
};//分号不能省
intmain(void)
{
structStudentst={1000,"zhangshan",20};
printf("%d%s%d\n",st.sid,st.name,st.age);
st.sid=99;
strcpy(st.name,"lisi");//st.name="lisi";error
st.age=22;
printf("%d%s%d\n",st.sid,st.name,st.age);
//printf("%d%s%d\n",st);
return0;
}
结构体2
#include
#include
struct结构体Student
{
intsid;
charname[200];
intage;
};//分号不能省
intmain(void)
{
结构体
StructStudentst={1000,“张三”,20};
//st.sid=99;第一种方式
StructStudent*pst;//定义一个指针变量,此指针变量只能存放我们自己定义的StructStudent类型的变量的地址
Pst=&st;
Pst->sid=99;//pst->sid等价于(*pst).sid而(*pst).sid等价于st.sid,所以pst->sid=st.sid
return0;
}
第八次课:
结构体:
1:
为什么会出现结构体
为了表示一些复杂的数据,而普通的基本类型变量无法满足要求
2:
什么叫做结构体
用户根据实际需要自己定义的复合数据类型
3:
如何使用结构体
算法1:
#include
structStudent
{
intsid;
charname[100];
intage;
};
intmain()
{
structStudentst={
2013213990,"wangchuankun",20
};
printf("%d%s%d\n",st.sid,st.name,st.age);
return0;
}
输出结果:
————————————--
2013213990wangchuankun2
请按任意键继续...
有两种方式:
1:
4:
注意事项
结构提变量不能加减乘除,但是可以相互赋值。
结构提变量和结构体指针变量作为函数传参
算法2:
算法目的:
通过结构体调用指针给主函数中结构体变量赋值
#include
#include
structStudent
{
intsid;
charname[200];
intage;
};
voidf(structStudent*pst)
{
(*pst).sid=2013213990;
strcpy(pst->name,"wangchuankun");
pst->age=22;
}
intmain()
{
structStudentst;
f(&st);
printf("%d%s%d\n",st.sid,st.name,st.age);
return0;
}
运行结果:
——————————————————
2013213990wangchuankun22
请按任意键继续...
——————————————————
算法3:
算法目的:
通过结构体调用指针给主函数中结构体变量赋值
并且通过函数调用将主函数中的结构体变量依次输出。
#include
#include
structStudent
{
intsid;
charname[100];
intage;
};
voidf(structStudent*pst)
{
(*pst).sid=2013213990;
strcpy(pst->name,"汪传坤");
pst->age=20;
}
voidg(structStudent*pst)
{
printf("学号:
%d\n姓名:
%s\n年龄:
%d\n\n",pst->sid,pst->name,pst->age);
}
intmain()
{
structStudentst;
f(&st);
g(&st);
return0;
}
运行结果:
学号:
2013213990
姓名:
汪传坤
年龄:
20
请按任意键继续...
跨函数使用内存必须要通过动态分配来完成!
算法4:
跨函数使用内存必须通过动态分配内存来实现
#include
#include
intf(int**q)
{
inti;
*q=(int*)malloc(16);
/*for(i=0;i<4;i++)
{
printf("%d\n",q[i]);
}
*/
return0;
}
intmain()
{
inti;
int*p;
f(&p);
for(i=0;i<4;i++)
{
scanf("%d",&p[i]);
}
for(i=0;i<4;i++)
{
printf("%d\n",p[i]);
}
return0;
}
运行结果:
78
45
89
12
78
45
89
12
请按任意键继续...
算法总结:
通过把指针变量的地址发给形参变量q(int**q表示q是存放int*类型变量的地址q本身是一个变量,)
算法5:
#include
#include
structStudent
{
intsid;
intage;
};
structStudent*CreateStudent(void);
voidShowStudent(structStudent*);
intmain()
{
structStudent*ps;
ps=CreateStudent();
ShowStudent(ps);
return0;
}
voidShowStudent(structStudent*pst)
{
printf("%d%d\n",pst->sid,pst->age);
}
structStudent*CreateStudent(void)
{
structStudent*p=(structStudent*)malloc(sizeof(structStudent));
p->sid=99;
p->age=88;
returnp;
}
运算结果:
9988
请按任意键继续...
注:
只能通过动态分配内存通过调用函数分配内存才有效。
数据结构正式课程
模块一:
算法1;静态调用函数:
#include
intf()
{
intj=20;
returnj;
}
intmain()
{
inti;
i=f();
printf("%d\n",i);
return0;
}
#include
#include
#include
structArr//定义数据类型,数据类型名为structArr,该数据类型含有三个成员。
没有定义变量
{
int*pBase;//存储第一个元素的地址
intlen;
intcnt;//当前有效元素的个数
//intincrement;//自动增长因子
};
voidinit_arr(structArr*pArr,intlen);
boolappend_arr(structArr*pArr,intval);//追加
boolinsert_arr(structArr*pArr,intpos,intelem);
booldelete_arr();
intget();
boolis_empty(structArr*pArr);
boolis_full(structArr*pArr);
voidsort_arr();
voidshow_arr(structArr*pArr);
voidinversion_arr();
intmain()
{
structArrarr;//已经分配好内存,数组没有形成
init_arr(&arr,10);
//append_arr(&arr,1);
if(append_arr(&arr,1))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,2);
if(append_arr(&arr,2))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,3);
if(append_arr(&arr,3))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,8);
if(append_arr(&arr,78))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,1000))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,188))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,89))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,8))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
show_arr(&arr);
insert_arr(&arr,2,99);
show_arr(&arr);
insert_arr(&arr,7,9999);
show_arr(&arr);
return0;
}
voidinit_arr(structArr*pArr,intlength)
{
pArr->pBase=(int*)malloc(sizeof(int)*length);
(*pArr).len=99;
if(NULL==pArr->pBase)
{
printf("动态内存分配失败!
\n");
exit(-1);//终止整个程序
}
else
{
pArr->len=length;
pArr->cnt=0;
}
}
voidshow_arr(structArr*pArr)
{
if(is_empty(pArr))
{
printf("数组为空!
\n");
}
else
{
for(inti=0;i
{
printf("%d",pArr->pBase[i]);
printf("\n");
}
}
}
boolis_empty(structArr*pArr)
{
if(0==pArr->cnt)
{
returntrue;
}
else
{
returnfalse;
}
}
boolis_full(structArr*pArr)
{
if(pArr->cnt==pArr->len)
{
returntrue;
}
else
{
returnfalse;
}
}
boolappend_arr(structArr*pArr,intval)
{
if(is_full(pArr))
{
returnfalse;
}
else
{
pArr->pBase[pArr->cnt]=val;
pArr->cnt++;
returntrue;
}
}
boolinsert_arr(structArr*pArr,intpos,intelem)
{
if(pos<0||pos>(pArr->cnt+2)||pArr->len==pArr->cnt)
{
printf("无法插入元素\n");
}
else
{
for(inti=pArr->cnt-1;i>=pos-1;--i)
pArr->pBase[i+1]=pArr->pBase[i];
pArr->pBase[pos-1]=elem;
printf("在第%d个元素之前插入%d成功\n",pos,elem);
}
}
#include
#include
#include
structArr//定义数据类型,数据类型名为structArr,该数据类型含有三个成员。
没有定义变量
{
int*pBase;//存储第一个元素的地址
intlen;
intcnt;//当前有效元素的个数
//intincrement;//自动增长因子
};
voidinit_arr(structArr*pArr,intlen);
boolappend_arr(structArr*pArr,intval);//追加
boolinsert_arr(structArr*pArr,intpos,intelem);
booldelete_arr();
intget();
boolis_empty(structArr*pArr);
boolis_full(structArr*pArr);
voidsort_arr();
voidshow_arr(structArr*pArr);
voidinversion_arr();
intmain()
{
structArrarr;//已经分配好内存,数组没有形成
init_arr(&arr,100);
//append_arr(&arr,1);
if(append_arr(&arr,1))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,2);
if(append_arr(&arr,2))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,3);
if(append_arr(&arr,3))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
//append_arr(&arr,8);
if(append_arr(&arr,78))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,1000))
{
printf("追加成功\n");
}
else
{
printf("追加失败\n");
}
if(append_arr(&arr,188))
{
printf("追加成功\n");
}
else
{
printf(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 老师 数据结构 笔记