Lecture 0 --基本说明
Abstract:本章所记录的知识是后面章节需要的前导知识,请务必仔细读本章,理解涉及的知识点,方便后面章节的学习。本次数据结构笔记主要参考殷人昆的《数据结构(C语言描述)》这本书,需要的语言基于C,但是在C++的环境中进行编译,就是建立C++的项目在里面跑C语言的程序。
1.C语言指针
http://www.cnblogs.com/HurryXin/p/6547831.html
2.typedef
自己感觉主要功能时重命名形式,看一下几个例子:
(1)
typedef int DataType;
这里是将int重命名为DataType类型。可以这么理解,DataType a这里的a是int型的,与int a是等价的。
那为什么会使用typedef呢?
设想在一个程序中定义了a这个int型变量,写了一大堆代码,结果最后发现我要用float或者其他的数据类型,那就慢慢一个一个换吧,凡是相关的全部换掉。但是使用typedef就容易多了,只需要将typedef int DataType;的int转换成float即可。
(2)
typedef struct { DataType a; int n; }SeqList;
定义的结构体名字叫SeqList,以后可以使用SeqList定义新的变量。
3.typedef与指针的特殊情况
这里主要解释两种用法,具体的代码先不体现以后会有的:
(1)
typedef struct node{ }LinkNode,*LinkList;
看到这种定义不知道是否很困惑,这里的typedef为什么后面跟着两个参数,这里简单理解为将struct node重命名为两个,但是两者又不一样。
LinkNode可以理解为一个数组其中的一个节点,而*LinkList则是该数组节点的地址,看着很难理解,画个图吧!
LinkNode与LinkList其实内容相同,但是又不完全相同。
(2)
LinkNode * Search(…);
这里被调函数为什么返回值是LinkNode*呢?主要是本函数是返回一个指针,所以使用LinkNode*。那用LinkList的时候该怎么办?这里仅需要把LinkNode*改成LinkList即可,注意不是LinkList*。但是建议使用LinkNode*,以后涉及的操作主要是删除等,所以最好返回节点而不是节点的地址。
4.C++部分知识介绍
(1)首先对比C语言与C++动态存储分配与释放命令
C语言 |
C++ |
|
动态分配 |
(DataType*)malloc(sizeof(DataType)); //简单变量 (DataType*)malloc(sizeof(DataType)*Size); //数组 |
new DataType; //简单变量 new DataType[Size]; //数组 |
动态释放 |
free(p); |
delete p; //简单变量 delete [] p; //数组 |
(2)报错函数
#include <stdlib.h> #include <iostream.h> void Error(char *message){ 5 cerr<<”Error:”<<message<<endl; ); }
(3)C++引用
这里的引用仅需要理解为重命名,但是只要发生在被调函数中,举个栗子:
void initList(SeqList &L){ };
这里的&L可以理解为重命名,其中把传入的参数不管是什么如何用L统一表示。注意C中是没有这种用法的,所以说基于C语言但是用C++的环境跑代码。
5.时间复杂度度量
void example(float x[][m],int m){ float sum[m]; int i; int j; ;i<m;i++){ sum[i]=0.0; ;j<m;j++) sum[i]=sum[i]+x[i][j]; } ;i<m;i++) count<<"Line"<<i<<":"<<sum[i]<<endl; }
这里可以看出,float sum[m]; int i; int j;与其他操作不同,该表自己详细研究一下,可以得出结论。
一般情况用大O表示时间复杂度。
基本做法就是T(n)<=O(f(n))也可以根据循环大体推算出最后结果。
void example(float a[],int& n){ int i; int j; ; ;i<n;i++) ;j<n;j++) if(a[i]==a[j]) a[j]=delTag; ;i<n;i++) if(a[i]!=delTag){ if(i!=k) a[k]=a[i]; k++; } }
这里的O(n2)当出现两个的O(n)时取最大值T(n)=O(max{f(n),g(n)})=O(n2)
算法时间复杂度排序:
c<log2n<n<nlog2n<n2<n3<2n<3n<n!
其中c,log2n,n,nlog2n都不错,n2,n3还可接受,2n,3n,n!就不能算是好的算法了。
转载请注明出处,O(∩_∩)O谢谢!
最新文章
- 写Action的三种方法
- WGZX:javaScript 学习心得--1
- jQuery动态加载css文件实现方法
- 【Scala学习笔记】第01弹——Scala安装与配置
- XTU OJ 1210 Happy Number (暴力+打表)
- Objective-C中release和nil的关系
- Qt见解:Post 与 Get 的区别(Get将参数直接与网址整合为一个整体,而Post则将其拆为两个部分)
- editPuls 常用知识
- 【java】文件复制的简单实现
- 《java入门第一季》之面向对象
- 配置Zookeeper、Dubbox
- AOP实践--利用MVC5 Filter实现登录状态判断
- java.io.UnsupportedEncodingException
- B-树、B+树
- elasticsearch5.0.1集群一次误删除kibana索引引发的血案
- InvocationHandler中invoke方法中的第一个参数proxy的用途
- android studio运行时报错AVD Nexus_5X_API_P is already running解决办法
- python类和模块区别,python命名空间
- redis安装以及php扩展
- 【整理】石子合并问题(四边形不等式DP优化)