数据结构学习笔记

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.速度慢占用存储空间大
循环：不易理解，速度快，存储空间小

线性结构：
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点  尾节点没有后续节点