当前位置:首页 > 开发 > 互联网 > 正文

数据结构学习笔记

发表于: 2014-08-06   作者:501311837   来源:转载   浏览:
摘要: 1.衡量算法的标准:时间复杂度:大概程序执行的次数,而非执行的时间空间复杂度:算法执行过程中大概所占用的最大内存难易程度健壮性   2.int *p  //p是个指针变量,int *表示该P变量只能存储int类型变量的地址   3.地址:内存单元的编号,内存是可以被cpu直接访问的,内存的编号是不能重复的,内存的基本划分单位是字节   CPU--

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

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

数据结构学习笔记

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
数据结构学习笔记(一) 假期以来我都坚持每天看一点郝斌的数据结构视频。讲的很透彻,也很风趣。
数据结构学习笔记(一) 假期以来我都坚持每天看一点郝斌的数据结构视频。讲的很透彻,也很风趣。
我们常说的数据结构分为两个部分,逻辑结构和物理结构,逻辑结构即我们平时在程序中或者理论上进行
在Lua中的table不是一种简单的数据结构,它可以作为其他数据结构的基础。其他语言提供的数据结构,
在Lua中的table不是一种简单的数据结构,它可以作为其他数据结构的基础。其他语言提供的数据结构,
第一章 绪论 数据结构基本概念 1 数据:数据是用来描述现实世界的数字、字符、图像、声音,以及能够
1.IplImage数据结构 (1)IplImage的结构 typedef struct _IplImage { int nSize; //IplImage大小 i
如果你学习过java,会发现里面有很多像array,list,String等等,这些不外乎是存储一类相同数数据的
计算机解决问题的步骤: 从具体问题抽象出数学模型 设计一个求解此数学模型的算法 编写程序,进行测
《Redis源码学习笔记》文章列表 由于图片较大,缩放较为模糊,请双击打开查看原图 ^_^ 要看懂redis代
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号