理解数据的存储和指针，关键在于了解其地址如何偏移及指针如何移动，下面我们就来聊聊关于链式存储占用的存储空间?接下来我们就一起去了解一下吧!
链式存储占用的存储空间
理解数据的存储和指针，关键在于了解其地址如何偏移及指针如何移动。
1 按字节移动string.h中有一串内存操作函数，函数参数和返回值的类型为void*，其实现按字节移动来操作（char的大小刚好是1个字节，char操作就是字节操作）。
void * memmove ( void * dst, const void * src, size_t count)
{
void * ret = dst;
if (dst <= src || (char *)dst >= ((char *)src count)) {
/*
* Non-Overlapping Buffers
* copy from lower addresses to higher addresses
*/
while (count--) {
*(char *)dst = *(char *)src;
dst = (char *)dst 1; // 按字节移动
src = (char *)src 1;
}
}
else {
/*
* Overlapping Buffers
* copy from higher addresses to lower addresses
*/
dst = (char *)dst count - 1;
src = (char *)src count - 1;
while (count--) {
*(char *)dst = *(char *)src;
dst = (char *)dst - 1;
src = (char *)src - 1;
}
}
return(ret);
}
2.1 数组
数组集中存储于一个内存块，数组名是这个内存块的首地址。准备的表达是数组首元素的指针常量。如果有一个指针变量指向其首元素，则其成员的地址偏移是：
指针变量 ＝ 指针变量 索引
其中的加操作不是简单的算术加操作，编译器会计算数组元素的长度，然后乘以索引值。这样就可以得到偏移的元素地址。
void arr2D(int arr[][5],int r)
{
int (*p5)[5] = arr; // arr指向首元素，arr元素的类型是一个数组，类型是int[5]
for(int i=0; i<r; i )
{
for(int j=0; j<5; j )
{
printf("%d ",*(*(p5 i) j)); // 加i的操作是移动5个int长度，加j的操作是移动一个int的操作
}
printf("\n");
}
}
字符数组：
int my_strlen(const char * str) // str指向一个字符数组
{
int count = 0;
while(*str) // 注意其循环结束条件，当字符中出现'\0'时
{
count ;
str ; // 指针移动，按一个字节长度偏移
}
return count;
}
数组集中存储，按数组成员类型长度移动，二维数组是数组的数组，其实质也是线性的顺序存储：
void arr2D(int arr[][5],int r)
{
int *p = (int*)arr;
for(int i=0; i<r; i )
{
for(int j=0; j<5; j )
{
printf("%d ",*(p 5*i j));
}
printf("\n");
}
}
数组的越界：
#include <stdio.h>
int main()
{
int flag = 999;
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
int i = 0;
for(i=0; i<=10; i )
{
printf("%d ", arr[i]);//当i等于10的时候，越界访问了
}
int* bound = (int*)(&arr 1);
printf("\n%d\n",*bound);
while(1);
return 0;
}
/*
1 2 3 4 5 6 7 8 9 10 999
999
*/
2.2 结构体自身
结构体各成员也是集中存储的，各成员按其类型的大小及内存对齐的填充来偏移地址。如何内存对齐及如何偏移的计算由编译器来完成。
#include <stdio.h>
struct compData{
double a;
int b;
char c;
}compData={11,22,'c'};
int main()
{
printf("%.2f %d %c\n",compData.a,compData.b,compData.c);
printf("%x %x %x\n",&compData.a,&compData.b,&compData.c);
// 不使用成员访问符访问结构体变量成员，注意内存对齐
double *d = (double*)&compData;
double *pa = (double*)((unsigned int)(&compData 0));
printf("%.2f\n",*pa);
int *pb = (int*)((unsigned int)(&compData) sizeof(double));
printf("%d\n",*pb);
char *pc = (char*)((unsigned int)(pb) sizeof(int));
printf("%c\n",*pc);
restart:
goto restart;
return 0;
}
/*
11.00 22 c
428a30 428a38 428a3c
11.00
22
c
*/
使用结构体变量的成员函数符来计算各成员占用的内存空间及地址偏移值：
#include <stdio.h>
#define PACKVALUE 4
#pragma pack(push)
#pragma pack(PACKVALUE)
typedef struct
{
char sa;
double sb;
int sc;
} innerS;
typedef struct
{
int a;
char b;
short c;
innerS d[2];
} testS;
#pragma pack(pop)
typedef unsigned long dword;
// 编译器如获取成员的内存址：基准 成员名(包含类型的偏移量)。
#define FSIZE(type, member) sizeof(((type*)0)->member)
#define FPOS(type, member) ((dword) & ((type*)0)->member)
int main(void)
{
printf("#pragma pack(%d):\nsizeof(char)=%d; \
sizeof(short)=%d;\n sizeof(int)=%d; sizeof(double)=%d\n\n",
PACKVALUE, sizeof(char), sizeof(short), sizeof(int), sizeof(double));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, a), FPOS(testS, a));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, b), FPOS(testS, b));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, c), FPOS(testS, c));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d), FPOS(testS, d));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[0]), FPOS(testS, d[0]));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[0].sa), FPOS(testS, d[0].sa));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[0].sb), FPOS(testS, d[0].sb));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[0].sc), FPOS(testS, d[0].sc));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[1]), FPOS(testS, d[1]));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[1].sa), FPOS(testS, d[1].sa));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[1].sb), FPOS(testS, d[1].sb));
printf("FSIZE = %d, FPOS = %d\n", FSIZE(testS, d[1].sc), FPOS(testS, d[1].sc));
while(1);
return 0;
}
/*
#pragma pack(4):
sizeof(char)=1; sizeof(short)=2;
sizeof(int)=4; sizeof(double)=8
FSIZE = 4, FPOS = 0
FSIZE = 1, FPOS = 4
FSIZE = 2, FPOS = 6
FSIZE = 32, FPOS = 8
FSIZE = 16, FPOS = 8
FSIZE = 1, FPOS = 8
FSIZE = 8, FPOS = 12
FSIZE = 4, FPOS = 20
FSIZE = 16, FPOS = 24
FSIZE = 1, FPOS = 24
FSIZE = 8, FPOS = 28
FSIZE = 4, FPOS = 36
*/
2.3 结构体可以含有位段
位段中直接指定成员的bit数。
位段的成员可以是 int unsigned int signed int或者是 char（属于整形家族）类型
位段的空间上是按照需要以4个字节（ int）或者1个字节（ char）的方式来开辟的。
#include <stdio.h>
struct A
{
int _a:2;
int _b:5;
int _c:10;
int _d:30;
double f;
int e;
};
int main()
{
A a;
printf("%d\n",sizeof(a));//24
return 0;
}
位段涉及很多不确定因素，位段是不跨平台的，注重可移植的程序应该避免使用位段。
1. int 位段被当成有符号数还是无符号数是不确定的。
2. 位段中最大位的数目不能确定。（16位机器最大16，32位机器最大32，写成27，在16位机器会出问题。
3. 位段中的成员在内存中从左向右分配，还是从右向左分配标准尚未定义。
4. 当一个结构包含两个位段，第二个位段成员比较大，无法容纳于第一个位段剩余的位时，是舍弃剩余的位还是利用，这是不确定的。
其它两个自定义类型：enum, union
enum定义的类型是一个值域限定的int，其值域限定为enum的成员（用作右值）。
union可以理解为一个泛类型容器，能够装下需要最大空间的那个成员。当最大成员大小不是最大对齐数的整数倍的时候，就要对齐到最大对齐数的整数倍。
各成员公用这一块空间，当使用其变量的成员时，注意其内存覆盖与按各自类型的编码规则来解释这个二进制序列的情形：
#include <stdio.h>
union Un
{
int i[7];
double d;
};
int main()
{
printf("%d\n", sizeof(union Un));// 32
Un un; // 分配32个字节，用0xC填充
printf("%x\n",&un);
un.i[0] = 24; // 18 00 00 00
printf("%d\n",un.i[0]);// 24
un.d = 0.24; // B8 1E 85 EB 51 B8 CE 3F
printf("%d\n",un.i[0]);// -343597384，此时前面的4个字节按int格式解读
while(1);
return 0;
}
/*
32
12ff28
24
-343597384
*/
3.1 链式存储的线性结构
对于链表，尾部结构会特殊处理，将next指针置为NULL，这样在循环时便可以将此作为结束标志。
typedef struct lnk
{
int data;
struct lnk* next;
}*lnkPtr;
lnkPtr p;
……
while (p)
{
p = p->next;
}
链表的指针域指向相邻结点，因此指针的移动用p = p->next;表示。
对于指针的赋值，可以理解为指针指向。如p = p->next;可以理解为p指向p->next。
p = p->next……→p(NULL)
3.2 链式存储的二叉树结构
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
typedef struct BiTNode{
char data; /*结点的数据域*/
struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){ /*按先序遍历的思想创建一棵二叉树*/
char c;
scanf("%c",&c);
if(c == ' ') *T = NULL;
else{
*T = (BiTNode * )malloc(sizeof(BiTNode)); /*创建根结点*/
(*T)->data = c; /*向根结点中输入数据*/
CreatBiTree(&((*T)->lchild)); /*递归地创建左子树*/
CreatBiTree(&((*T)->rchild)); /*递归地创建右子树*/
}
}
void PreOrderTraverse(BiTree T ){ /*先序遍历二叉树*/
if(T){ /*递归结束条件，T为空*/
printf("<",T->data); /*访问根结点,将根结点内容输出*/
PreOrderTraverse(T->lchild); /*先序遍历T的左子树*/
PreOrderTraverse(T->rchild); /*先序遍历T的右子数*/
}
}
void visit(BiTree p) {
printf("<",p->data);
}
void layerOrderTraverseSelfqueue(BiTree T) //按层遍历
{
BiTree queue[20],p;
int front,rear;
if(T!=NULL)
{
queue[0] = T; /*将根结点的指针（地址）入队列*/
front = -1;
rear = 0;
while(front<rear) /*当队列不为空时进入循环*/
{
p = queue[ front]; /*取出队头元素*/
visit(p); /*访问p指向的结点元素*/
if(p->lchild!=NULL) /*将p结点的左孩子结点指针入队列*/
queue[ rear] = p->lchild;
if(p->rchild!=NULL) /*将p结点的右孩子结点指针入队列*/
queue[ rear] = p->rchild;
}
}
}
void layerOrderTraverseQueue(BiTree T) //按层遍历，使用queue
{
BiTree p;
queue <BiTree> q;
if(T!=NULL)
{
q.push(T); /*将根结点的指针（地址）入队列*/
while(! q.empty()) /*当队列不为空时进入循环*/
{
p = q.front();
q.pop(); /*取出队头元素*/
visit(p); /*访问p指向的结点元素*/
if(p->lchild!=NULL) /*将p结点的左孩子结点指针入队列*/
q.push(p->lchild);
if(p->rchild!=NULL) /*将p结点的右孩子结点指针入队列*/
q.push(p->rchild);
}
}
}
main()
{
BiTree T = NULL; /*最开始T指向空*/
printf("需要创建和遍历的二叉树：\n");
printf(" A\n");
printf(" / \\\n");
printf(" B E\n");
printf(" / \\ \\\n");
printf(" C D F\n");
printf("Input some characters to create a binary tree\n");
printf("（按先序序列建立）\n");
printf("例如，ABC##D##E#F##↙，#表示空格输入（表示空节点）,↙表示回车\n");
CreatBiTree(&T); /*创建二叉树*/
printf("\n用自定义队列层遍历：\n");
layerOrderTraverseSelfqueue(T);
printf("\n先序遍历（递归）：\n");
PreOrderTraverse(T);
printf("\n用库队列层遍历：\n");
layerOrderTraverseQueue(T);
while(1);
}
/*
需要创建和遍历的二叉树：
A
/ \
B E
/ \ \
C D F
Input some characters to create a binary tree
（按先序序列建立）
例如，ABC##D##E#F##↙，#表示空格输入（表示空节点）,↙表示回车
abc d e f
用自定义队列层遍历：
a b e c d f
先序遍历（递归）：
a b c d e f
用库队列层遍历：
a b e c d f
*/
－End－
