数据结构学习笔记
1.衡量算法的标准：
时间复杂度：大概程序执行的次数，而非执行的时间
空间复杂度：算法执行过程中大概所占用的最大内存
难易程度
健壮性
2.int *p //p是个指针变量，int *表示该P变量只能存储int类型变量的地址
3.地址:内存单元的编号，内存是可以被cpu直接访问的，内存的编号是不能重复的，内存的基本划分单位是字节
CPU--地址线（可以确定对哪个地址进行操作）
控制线（控制读和写）
数据线（数据传输）
4.指针就是地址，地址就是指针。
5.指针变量就是存放内存单元地址的变量
6.指针的本质就是一个受限的非负整数
分类：
1.基本类型的指针
int * p//p是个指针变量，int *表示该p变量只能存储int类型的指针变量地址
int *p;
int i =10;
p=&i;
如果*p就是i,可以互换。任何一个改变都会变化
p保存i的地址，修改p的值不改变i的值
*p指向一个不确定的单元的值
2.指针与数组的关系
int a[5]={0,1,2,3,4,5};
printf("%p\n",a+1); 0012FF70 //指向第二个元素
printf("%p\n",a+2); 0012FF74 //指向第三个元素
printf("%d\n",*a+3); 4 //等价于a[0]+3
一维数组名是个指针变量
它存放的是以维数组第一个元素的地址，他的值不能被改变，一唯数组名指向的是数组的第一个元素
a-->a[0]
所以下标和指针的关系：a[i]==*(a+i)
只要是数组物理空间一定是连续的
指针变量的运算：
指针变量不能相加，不能相乘相除
如果两个指针属于同一个数组，就可以相减
p+i的值是p+i*(p所指向的变量所占的字节数)
p-i的值是p-i*(p所指向的变量所占的字节数)
p++==p+1
p--=p-1
int 4个字节 一个字节是8位，一个字节是一个地址
double 8个字节
%p实际就是以十六进制输出
所有的指针变量只占4个子节 用第一个字节的地址表示整个变量的地址
例1：
int main(void){
int i =10;
f(&i);
printf("i=%d\n",i); //i=99
return 0;
}
void f(int * p){
*p=99;
}
例2：
int main(void){
int i =9;
int * p=&i;
printf("%p\n",p);//p的地址已经改变
f(&p);//要改变他在内存的值就把地址放进去
printf("%p\n",p);
return 0;
}
void f(int ** q){
*q=（int *）0xFFFFFFFF
}
结构体：
1.为什么会出现结构体
#include<stdio.h>
#include<string.h>
struct Student{
int sid;
String name;
int age;//只有属性没有方法，功能相对较弱，类更能完整的表现失误，结构体就是类的一个过渡
}
为了表现一些复杂的数据，而普通的基本数据类型无法满足要求。所以会出现
2.什么叫结构体
结构体是用户根据用户实际需要和自己定义的复合数据类型
3.如何使用结构体
int main(void){
struct Student st={1000,"zhangsan",20};
printf("%d %s %d \n",st.sid,st.name,st.age);//字符串输出是%s
st.sid=99;
strcpy(st.name,"lisi");//字符串要这样赋值
st.age=22;
printf("%d %s %d \n",st.sid,st.name,st.age);
return 0;
}
int main(void){
struct Student st={1000,"zhangsan",20};
struct Student * pst;
pst=&st;
pst->sid=99;//pst->sid等价于（*pst）.sid 第一种方式：st.sid 2.ppst->sid
return 0;
}
4.注意事项
结构体变量不能加减乘除，但是可以相互复制
普通结构体变量和结构体指针变量作为函数传参的问题
//把第一个字节转化成整形,就可以把pArr当成数组使用
int * pArr=(int *)malloc(sizeof(int)* len)
*pArr=4; //类似于a[0]=4
pArr[1]=10;//类似于a[1]=10
free(pArr)//释放内存
下程序中能够调用函数fun()，使main函数中的指针变量p指向一个合法的整形单元：
跨函数使用内存的例子
main(){
int *p;
fun(&p);
...
}
int fun(int **q){
*q=(int *)malloc(4);
}
数据的存储不一样，数据的操作就不一样了
数据结构=个体的存储+个体的关系存储
算法=对存储数据的操作
数据结构：
1.数据的存储：
线性结构：把所有的节点用一根直线穿起来
连续存储【数组】：类型大小相同。
数组的优缺点：
离散存储【链表】
链表的优缺点：
线性结构最常见的应用：1.栈，队列
非线性结构存储
2.用c实现java中ArrayList功能
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//定义了一个数据类型，struct Arr的类型
struct Arr{
int *pBase;//存储的是数组第一个元素的地址
int len;//数组所能容纳的最大元素的个数
int cnt;//当前数组有效元素的个数
}
void init_arr(struct Arr * pArr,int length);
bool append_arr(struct Arr * pArr,int val);//追加
bool insert_arr();
bool delete_arr();
int get();
bool is_empty(struct Arr * pArr);
bool is_full(struct Arr * pArr);
void sort_arr();
void show_arr(struct Arr * pArr);
void inversion_arr();
int main(void){
struct Arr arr;
int_arr(&arr,6);
show_arr(&arr);
append_arr(&arr,1);
return 0;
}
void int_arr(struct Arr * pArr,int length){
pArr->pBase=(int *)maclloc(sizeof(int)* length);
if(NULL==pArr->pBase){
printf("动态内存分配失败")
exit(-1);//终止整个程序
}else{
pArr->len=length;
pArr->=0;
}
return;
}
bool is_empty(struct Arr * pArr){
if(0==aArr->cnt){
return true;
}else
return false;
}
void show_arr(struct Arr * pArr){
if(is_empty(pArr)){//如果数组为空，提示
printf("数组为空");
}else{
for(int i=0;i<pArr->len;==i){
printf("%d",pArr->pBase[i]);//int *类型
}
}
bool is_full(struct Arr * pArr){
if(pArr->cnt==pArr->len)
return true
else
return false
}
bool append_arr(struct Arr * pArr,int val){
//满了就返回false
if(is_full(pArr))
return false;
//不满就追加
pArr->pBase[pArr->cnt]=val;
(pArr->cnt)++;
return true;
}
}
typedef int zhangsan; //zhangsan等价于int
typedef struct Student{
int sid;
char name[100];
char sex;
}ST;
//链表节点的数据类型
struct Node{
int data;//数据域
struts Node * pNext;//指针域
}NODE,* pNODE;
链表分类：
单链表
双链表：每一个节点有两个指针域，双向指
循环链表：能通过任何一个节点找到所有的节点
非循环链表
泛型：利用某种技术达到的效果是：不同的存数方式，执行的操作是一样的
算法：狭义的算法是与数据的存数方式密切相关
广义的算法是与数据的存储方式无关
离散存储[链表]
优点：空间没有限制 插入删除元素很快
缺点：存取速度慢
连续存储【数组】：
优点：
存取速度快
缺点：事先必须知道数组的长度、 插入删除元素很慢、空间通常有限制、需要大块的连续内存
栈
定义：一种可以实现“先进后出”的存储结构
栈类似于箱子
应用：函数调用，中断，表达式求值，内存分配，缓冲处理，迷宫
1.栈程序的演示：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node * pNext;
}NODE,* PNODE;
typedef struct Stack{
PNODE pTop;
PNODE pBottom;
}STACK,* pSTACK;
void init(pSTACK);
void push(pSTACK,1);
void push(pSTACK);
int main(void){
STACK S;//STACK等价于struct Stack
init(&S);//目的是造出一个空栈
push(&S,1);
push(&S,2);
traverse(&S);//遍历输出
return 0;
}
void init(pSTACK pS){
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(NULL==pS->pTop){
printf("动态内存分配失败")；
exit(-1);
}
else{
pS->pBottom=ps->pTop;
pS->pTop->pNext=NULL;
}
}
void push(pSTACK pS,int val){
PNODE pNew==(PNODE)malloc(sizeof(NODE));
pNew->data=val;
pNew->pNext=pS->pTop;
pS->pTop=pNew;
}
void traverse(pSTACK pS){
PNODE p=pS->pTop;
while(p!=pS->pBottom){
printf("%d",p->data);
p=p->pNext;
}printf("\n");
return;
}
链表队列--用链表实现
静态队列--用数组实现
静态队列通常都必须是循环队列
队头出，队为入，所以不论新增还是删除front和rear都会增加，所以静态队列必须是循环队列
队列空：font和rear相等就是空的
入队：r=(r+1)%队列的长度
出队：font=(font+1)%队列的长度
判断队列是否满(f和r值紧挨着)：（rear+1）%数组长度==f
递归：
一个函数自己直接或间接调用自己
举例：
1.求阶乘(1)n!=n*(n-1)!
#include<stdio.h>
int main(void){
int val;
int i,mult=1;s
printf("请输入一个数字";)
printf("val=");
for(i=1;i<=val;++i){
mult=mult*1;
printf(mult);
}
}
2.递归求阶乘(2)
long f(long n){
if(1==n)
return 1;
else
return f(n-1)*n
}
int main(void){
printf("%d\n",f(3));
return 0;
}
3.递归求和
long sum(long n){
if(1==n)
return 1;
else
return n+sum(n-1);
}
int main(void){
printf("%ld\n",sum(100));
return 0;
}
函数的调用：
1.当一个函数在运行期间调用另一个函数时候，在运行被调函数之前，系统需要完成3件事情：
将所有的实际参数，返回地址等信息传递给被调函数保存
为被调函数的局部变量分配存储空间
将控制转移到被调函数的入口
2.从被调函数返回主调函数之前，系统也要完成3件事情
保存被调函数的返回结果
释放被调函数所占用的存储空间
依照被调用函数保存的返回地址将控制转移到调用函数
递归必须满足的3个条件：
1.递归必须要有一个明确的终止条件
2.该函数所处理的数据规模必须在递减
3.这个转化必须是可解的
递归和循环式可以转换的
递归：1.易于理解2.速度慢占用存储空间大
循环：不易理解，速度快，存储空间小
线性结构：
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点 尾节点没有后续节点