数据结构考研笔记——数据类型
数据类型 (1)结构型 结构体是系统提供给程序员制作新的数据类型的一种机制。
eg:制作一个由不同类型的变量组成的数组
typedef struct { int a; char b; float c; } TypeA;
TypeA a; //定义了一个数组,a.a a.b a.c分别对应于结构体变量a的第一第二第三个元素的值 TypeA a[3]; //定义了一个二维数组,a[0].a a[0].b ...
(2)指针型 每种数据类型的指针都有特定写法
int *a; char *b; float *c; TypeA *d;
若指针型变量a已指向变量b *a就是取变量b的内容(x=*a;等价于x=b) &b就是取变量b的地址(a=&b;就是将变量b的地址存于a中,即指针a指向b)
指针型用的最多的就是和结构型结合起来构造结点(如链表的结点、二叉树的结点等) (3)结点的构造
要构造一种结点,必须先定义结点的结构类型。
1)链表结点的定义 链表的结构有两个域: 数据域:用来存放数据; 指针域:用来存放下一个结点的位置
链表结点的结构型定义:
typedef struct Node { int data; //可修改int类型 struct Node *next; //指向Node型变量的指针 } Node;
2)二叉树结点的定义
在链表结点结构型的基础上,再加上一个指向自己同一类型变量的指针域
typedef struct BTNode { int data; //可修改Int类型 struct BTNode *lchild; //指向左孩子结点指针 struct BTNode *rchild; //指向左孩子结点指针 } BTNode;
二叉树结点制作的写法:
① BTNode BT; ② BTNode *BT; BT = (BTNode*) malloc (sizeof(BTNode)); //熟练掌握
解析②制作过程:
先定义一个结点指针BT,然后用函数malloc()申请一个结点的内存空间,最后让指针BT指向这片内存空间。
//考研数据结构中所有类型结点的内存分配都可以用函数malloc()完成
Tip:动态申请数组空间的方法,可认为是一次申请一组结点,语法如下(假设申请的数组内的元素为int型,长度为n)
int *p; p = (int *) malloc (n * sizeof(int));
获取元素时和一般数组一样,如第二个元素,可写为p[1]。
回到二叉树结点,若想取数据域的值赋给x,①写为x=BT.data; 而②则写为x=BT->data;
对于②中的BT指针,用“.”取data值:(*BT).data;(与BT->data等价)
(4)关于typedef:可理解为给现有的数据类型起一个新名字
如给int起一个新名字A,可写为 typedef int A;
下一篇:
设计模式结构型代理模式