C｜数据存储地址与字节偏移、数据索引( 三 ) _数据存储

4.2 平方取中法
先计算数据的平方，然后取中间的某段数字做为索引。
4.3 折叠法
将数据转换成一串数字后，先将这串数字拆成几个部分，然后把它们加起来。

STL中的set的底层为什么用红黑树，而不是哈希表？
集合的常见运算有并、交、差等，这些运算在数据有序时对应算法的时间复杂度会大大降低，红黑树恰好是有序结构，而哈希表不是。

5 共用体只是一种字节共享（或特殊的类型泛化或类型强制转换）联合能够规避C语言的类型系统，允许以多种类型来引用对象，用不同的字段来引用相同的内存块。与结构体不同的是，其成员不存在位移，两个字段的使用是互斥的，一个共用体总的大小等于它最大字段的大小。

void cngb(){union{struct {unsigned int i:4;unsigned int j:4;unsigned int k:4;unsigned int L:4;unsigned int m:4;unsigned int n:4;};char hanzi[3];}hz;fflush(stdin);puts("查询gb2312码，请输入一个汉字：");gets(hz.hanzi);//strcpy(hz.hanzi,"中");printf("%X%X%X%Xn",hz.j,hz.i,hz.L,hz.k);//for(int i=0;i<2;i++)//printf("%2Xn",hz.hanzi[i]);}

6 位域可以实现比字节长度颗粒度更小的偏移要将一个浮点数的二进制存储用16进制的符号表示出来，使用字节的颗粒还是太大，因为一个16进制是4个二进制位，半个字节长度，可以使用位域：

#include <stdio.h>#include <string>using namespace std;string double2hex(double db){union {//用于将浮点数的二进制位解析为int位输出float input;int output;} data;union {struct {unsigned j:4;unsigned i:4;}by;char ch;}un;char *hexa = "0123456789ABCDEF";int i=0;int j=0;char *ch = (char*)&db;string hexd = "";for(i=7;i>=0;i--){un.ch = ch[i];hexd += hexa[un.by.i];hexd += hexa[un.by.j];hexd += " ";}return hexd;}int main(){string str = double2hex(-15.525);printf("%sn",str.c_str()); // C0 2F 0C CC CC CC CC CDgetchar();return 0;}

7 索引表以空间换时间缩小搜索范围提高搜索效率将大范围的数据建立索引，通过查找索引来确定数据的位置是一个提高查找效率的策略。
给数据建立索引也是利用数据在文件中的偏移量。

#include <iostream>// 建立索引表并排序#include <fstream>#include <cstdlib>using namespace std;typedef struct{int NO;char name[8];int chinese;int math;int english;int Comprehensive;int total;} Student;//高考学生信息 typedef struct{int NO;long offset;//数据在文件中的偏移量} StudentIndex;//高考学生索引 void createIndex();void writeIndex(StudentIndex *si, int n); int main(){createIndex();return 0;}/*功能：创建索引*/ void createIndex(){int stuNum;StudentIndex *studentsIndex;//索引表的起始地址Student student;ifstream binaryFile("binarydata.dat", ios::in|ios::binary);if(!binaryFile){cerr<<"cannot open binary file!"<<endl;exit(1);}//建立索引binaryFile.read((char*)&stuNum, sizeof(stuNum));//读入实际人数//读入数据，建立未排序的索引表studentsIndex = new StudentIndex[stuNum];int i, j;long mOffset;for(i=0; i<stuNum; ++i){mOffset = binaryFile.tellg();binaryFile.read((char*)&student, sizeof(Student));studentsIndex[i].NO = student.NO;studentsIndex[i].offset = mOffset;//记录对应学号学生数据的偏移量}//关闭数据文件binaryFile.close();//为索引表排序StudentIndex temp;//用于交换的中间变量for (i=0; i<stuNum-1; i++)for(j=0; j<stuNum-i-1; j++)if (studentsIndex[j].NO>studentsIndex[j+1].NO){temp=studentsIndex[j];studentsIndex[j]=studentsIndex[j+1];studentsIndex[j+1]=temp;}//将建好的索引表通过文件存储writeIndex(studentsIndex, stuNum);return;} /*功能：将索引写入文件参数：si - 索引表起始地址；n - 考生人数，索引记录条数*/void writeIndex(StudentIndex *si, int n){//打开文件ofstream indexFile("binarydata.idx", ios::out|ios::binary);if(!indexFile){cerr<<"cannot open index file!"<<endl;exit(1);}int i;for(i=0; i<n; ++i){//indexFile<<si[i].NO<<"t"<<si[i].offset<<endl;//索引用作文本文件时indexFile.write((char*)&si[i], sizeof(StudentIndex)); //索引用二进制文件时}//关闭文件indexFile.close();return;}

－End－

【C｜数据存储地址与字节偏移、数据索引】