c++结构体方法实现
2013-07-29 11:52:00 weixin_34368949 阅读数 4

C语言允许用户自己指定这样一种数据结构,它由不同类型的数据组合成一个整体,以便引用,这些组合在一个整体中的数据是互相联系的,这样的数据结构称为结构体。
C++结构体中可以使用函数,有下面的测试代码:

int main(int argc,char *argv[])
{
	struct MyStruct
	{
		char *name;
		int income;
		int expenses;
		int profit(){
			return income-expenses;
		}
	};
	MyStruct person;
	person.name="Mike";
	person.income=3600;
	person.expenses=1200;

	int x=person.profit();

	return 0;
}
有一个名为MyStruct的结构体,有三个数据成员,有一个函数成员,下面声明一个这样的结构体变量,对其进行赋值,然后调用函数取得返回值。

对应汇编代码如下:

struct MyStruct
	{
		char *name;
		int income;
		int expenses;
		int profit(){
			return income-expenses;
		}
	};
//可以看到上面的声明中并没有编译出任何汇编码,包括函数,只是告诉编译器有这么一个数据结构
	MyStruct person;
	person.name="Mike";
00E43A58  mov         dword ptr [ebp-14h],0E458A8h  
//将字符串"Mike"的首地址放进第一个成员char*name指针,这个地址在内存中的表现见下图
//通过查看&person和&name可以发现是同一个位置,
	person.income=3600;
00E43A5F  mov         dword ptr [ebp-10h],0E10h  
//这里是第二个成员的赋值
	person.expenses=1200;
00E43A66  mov         dword ptr [ebp-0Ch],4B0h  
//第三个赋值
	int x=person.profit();
//第四个调用函数
00E43A6D  lea         ecx,[ebp-14h]  
00E43A70  call        00E433B0  
00E43A75  mov         dword ptr [ebp-20h],eax  
//可以看到先是把这个结构的首地址放进ecx,由于无参数所以没有压栈操作
//函数计算结果同样是放在了eax中
字符串"Mike"(0E458A8h):

注意这个Mike周围还有许多英文单词,而且每个字母之间都是00隔开的,这就是所谓的宽字符WCHAR,在Windows编程中常常看到。

再来看看结构体里面的函数编译到哪里去了?

struct MyStruct
	{
		char *name;
		int income;
		int expenses;
		int profit(){
//作为函数同样是要分配栈空间
00E433B0  push        ebp  
00E433B1  mov         ebp,esp  
00E433B3  sub         esp,0CCh  
00E433B9  push        ebx  
00E433BA  push        esi  
00E433BB  push        edi  
00E433BC  push        ecx  //由于下面必须要用ecx,这里先压入栈内保存
00E433BD  lea         edi,[ebp+FFFFFF34h]  
00E433C3  mov         ecx,33h  
00E433C8  mov         eax,0CCCCCCCCh  
00E433CD  rep stos    dword ptr es:[edi]  
00E433CF  pop         ecx  //这里恢复出来
00E433D0  mov         dword ptr [ebp-8],ecx  
//把传进来的该结构体地址(相当于this指针)放进栈
			return income-expenses;
00E433D3  mov         eax,dword ptr [ebp-8]  
00E433D6  mov         ecx,dword ptr [ebp-8]  
//把this放进eax和ecx,因为下面要用它来寻址
00E433D9  mov         eax,dword ptr [eax+4]  
00E433DC  sub         eax,dword ptr [ecx+8]  
//[this+4]就是变量income,[this+8]就是变量expenses,这里用[eax+8]应该也可以
//作差后返回
		}
00E433DF  pop         edi  
00E433E0  pop         esi  
00E433E1  pop         ebx  
00E433E2  mov         esp,ebp  
00E433E4  pop         ebp  
00E433E5  ret
小结:结构体最关键的还是首地址,或者叫做结构体的this指针,用它可以访问结构体中的每个成员,是通过[this+偏移]来实现的,这个偏移不同所访问到的成员就不同,偏移具体是多少是在编译期分析成员类型决定的。


转载于:https://my.oschina.net/ybusad/blog/147994

2017-11-28 16:36:25 qq_19320865 阅读数 127
​面试过程中,经常会被问到结构体内存的问题。即结构体内部数据成员并不是按照所占空间大小顺序存储的。这样就会导致:一个结构体变量定义完之后,其在内存中的存储并不等于其所包含元素的宽度之和。引用别人的总结:“假设我们同时声明两个变量:
文章大部分内容转自

假设我们同时声明两个变量: 
char a; 
short b; 
用&(取地址符号)观察变量a, 
b的地址的话,我们会发现(以16位CPU为例): 
如果a的地址是0x0000,那么b的地址将会是0x0002或者是0x0004。 
那么就出现这样一个问题:0x0001这个地址没有被使用,那它干什么去了? 答案就是它确实没被使用。 因为CPU每次都是从以2字节(16位CPU)或是4字节(32位CPU)的整数倍的内存地址中读进数据的。如果变量b的地址是0x0001的话,那么CPU就需要先从0x0000中读取一个short,取它的高8位放入b的低8位,然后再从0x0002中读取下一个short,取它的低8位放入b的高8位中,这样的话,为了获得b的值,CPU需要进行了两次读操作。

但是如果b的地址为0x0002, 那么CPU只需一次读操作就可以获得b的值了。所以编译器为了优化代码,往往会根据变量的大小,将其指定到合适的位置,即称为内存对齐(对变量b做内存对齐,a、b之间的内存被浪费,a并未多占内存)


 一个结构体变量定义完之后,其在内存中的存储并不等于其所包含元素的宽度之和。
例一:
                                      #include <iostream>
                                      using namespace std;
                                         struct X
                                         {
                                              char a;
                                              int b;
                                              double c;
                                         }S1;
 
                                     void main()
                                    {
                                         cout << sizeof(S1) << endl;
                                         cout << sizeof(S1.a) << endl;
                                         cout << sizeof(S1.b) << endl;
                                         cout << sizeof(S1.c) << endl;
                                    }
     比如例一中的结构体变量S1定义之后,经测试,会发现sizeof(S1)= 16,其值不等于sizeof(S1.a) = 1、sizeof(S1.b) = 4和 sizeof(S1.c) = 8三者之和,这里面就存在存储对齐问题。
    原则一:结构体中元素是按照定义顺序一个一个放到内存中去的,但并不是紧密排列的。从结构体存储的首地址开始,每一个元素放置到内存中时,它都会认为内存是以它自己的大小来划分的,因此元素放置的位置一定会在自己宽度的整数倍上开始(以结构体变量首地址为0计算)。
    比如此例,首先系统会将字符型变量a存入第0个字节(相对地址,指内存开辟的首地址);然后在存放整形变量b时,会以4个字节为单位进行存储,由于第一个四字节模块已有数据,因此它会存入第二个四字节模块,也就是存入到4~8字节;同理,存放双精度实型变量c时,由于其宽度为8,其存放时会以8个字节为单位存储,也就是会找到第一个空的且是8的整数倍的位置开始存储,此例中,此例中,由于头一个8字节模块已被占用,所以将c存入第二个8字节模块。整体存储示意图如图1所示。
    考虑另外一个实例。
例二:
                                           struct X
                                           {
                                                char a;
                                                double b;
                                                int c;
                                            }S2;
    在例二中仅仅是将double型的变量和int型的变量互换了位置。测试程序不变,测试结果却截然不同,sizeof(S2)=24,不同于我们按照原则一计算出的8+8+4=20,这就引出了我们的第二原则。
    原则二:在经过第一原则分析后,检查计算出的存储单元是否为所有元素中最宽的元素的长度的整数倍,是,则结束;若不是,则补齐为它的整数倍。
    掌握了这两个原则,就能够分析所有数据存储对齐问题了。再来看几个例子,应用以上两个原则来判断。
例三:
                                              struct X
                                              { 
                                                   double a;
                                                   char b;
                                                   int c;     
                                              }S3;
    首先根据原则一来分析。按照定义的顺序,先存储double型的a,存储在第0~7个字节;其次是char型的b,存储在第8个字节;接下来是int型的c,顺序检查后发现前面三个四字节模块都被占用,因此存储在第4个四字节模块,也就是第12~15字节。按照第一原则分析得到16个字节,16正好是最宽元素a的宽度8的整数倍,因此结构体变量S3所占存储空间就是16个字节。
例四:
                                              struct X
                                              { 
                                                   double a;
                                                   char b;
                                                   int c;
                                                   char d;   
                                              }S4;
 
    仍然首先按照第一原则分析,得到的字节数为8+4+4+1=17;再按照第二原则补齐,则结构体变量S4所占存储空间为24。
例五:
                                              struct X
                                              { 
                                                   double a;
                                                   char b;
                                                   int c;
                                                   char d;
                                                   int e; 
                                               }S5;
    同样结合原则一和原则二分析,可知在S4的基础上在结构体内部变量定义最后加入一个int型变量后,结构体所占空间并未增加,仍为24。
例六:
    如果将例五中加入的变量e放到第一个定义的位置,则情况就不同了。结构体所占存储空间会变为32。
            
             struct X
                                              { 
                                                  int e;
                                                  double a;
                                                  char b;
                                                  int c;
                                                  char d;
                                              }S6;

                              
    补充:前面所介绍的都是元素为基本数据类型的结构体,那么含有指针、数组或是其它结构体变量或联合体变量时该如何呢?
    1.包含指针类型的情况。只要记住指针本身所占的存储空间是4个字节就行了,而不必看它是指向什么类型的指针。
例七:
                    struct X              struct Y               struct Z
                    {                     {                      {     
                       char *a;              int *b;                 double *c;
                    };                     };                     };
    经测试,可知sizeof(X)、sizeof(Y)和sizeof(Z)的值都为4。
    2.含有构造数据类型(数组、结构体和联合体)的情况。首先要明确的是计算存储空间时要把构造体看作一个整体来为其开辟存储空间;其次要明确的是在最后补齐时是按照所有元素中的基本数据类型元素的最长宽度来补齐的,也就是说虽然要把构造体看作整体,但在补齐的时候并不会按照所含结构体所占存储空间的长度来补齐的(即使它可能是最长的)。
例八:
                                      struct X
                                     {
                                          char a;
                                          int b;
                                          double c;
                                      };
                                      struct Y
                                      {
                                           char a;
                                           X b;
                                       };
    经测试,可知sizeof(X)为16,sizeof(Y)为24。即计算Y的存储长度时,在存放第二个元素b时的初始位置是在double型的长度8的整数倍处,而非16的整数倍处,即系统为b所分配的存储空间是第8~23个字节。
    至于结构体若包含了其他结构体,则只用把包含的结构体替换进来即可。
    如果将Y的两个元素char型的a和X型的b调换定义顺序,则系统为b分配的存储位置是第0~15个字节,为a分配的是第16个字节,加起来一共17个字节,不是最长基本类型double所占宽度8的整数倍,因此要补齐到8的整数倍,即24。测试后可得sizeof(Y)的值为24。
    由于结构体所占空间与其内部元素的类型有关,而且与不同类型元素的排列有关,因此在定义结构体时,在元素类型及数量确定之后,我们还应该注意一下其内部元素的定义顺序。

2018-04-27 21:41:03 breakpoints_ 阅读数 639

浅谈sort排序

在写这篇文章之前我对于结构体排序都是用STL的std::sort()
现假现有

typedef struct STreeNode* pSTreeNode;
struct STreeNode
{
	int nodeid;
	int namevalue;
	vector<pSTreeNode> pChildList;
}; 

对于pChildList的排序,加上头文件#include <algorithm>就可以用
std::sort(pChildList.begin(), pChildList.end, cmp);其中cmp是自己定义的内部排序规则。可能很多人跟我一样这样使用,STL提供的sort算法类似快速排序,算法时间复杂度是n*log2(n)
但是在实际的项目中,有经验的人都知道不可以轻易地使用STL里面的算法,虽然方便,但是在头文件里面你引进#include,对于项目编译来说是加了一层压力,特别是大的项目,如果你不注意使用标准库,可能对于某个模块来说没有什么,但是你加一个,他加一个。。。对整个项目的编译无疑是沉重的打击,所以能自己实现的算法何不自己写接口

快速排序的介绍##

时间复杂度:

快速排序的平均时间复杂度是nlogn,最坏情况是N方(基本有序,后面我会给大家证明),平均时间复杂度的证明较为繁琐,数学公式啦,感兴趣的可以百度学习一下

核心思想

随机找出一个数(通常就拿数组第一个数据就行),把它插入一个位置,使得它左边的数都比它小,它右边的数据都比它大,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解为止。它也是分治思想的一个经典实验(归并排序也是) 。快速排序将数组排序的方式是当两个子数组都有序时整个数组也就自然有序了

举例说明

假设现在有 6 1 2 7 9 3 4 5 10 8 这十个数,我们对这个十个数进行从小到大排序

方法:

找一个基准数不要被这个名次吓到了,它就是一个可以用来参照的数,我们就用第一个数6作为参照吧,接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边。

友情提示。回忆一下冒泡排序,是如何通过“交换”,一步步让每个数归位的。此时可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?在纸上画画看。以前第一次学习冒泡排序算法的时(N方)候,觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想能不能。。。,后来才知道原来这就是“快速排序”。

步骤

1>分别从 序列6 1 2 7 9 3 4 5 10 8的两端开始试探,假设left = 0, right = n-1 先从右往左找一个小于6的数,把这个数放到低位,再从左往右找一个大于6的数,然后把这个数放到刚刚那个小于6的数的位置。

我们来模拟一下 从右往左找一个小于6的数,8 不是, 10不是, 5哦对了,记住他的下标,然后把5放到最低位,从左往右找一个大于6的数1 不是, 2不是, 7哦对了,然后把7放到刚刚5的位置
序列变成了 5 1 2 7 9 3 4 5 10 8(想想为什么), 比如 3 2 1这个序列 3 跟 2换, 3再跟1换。1再跟2换 何不 3直接跟1换(以2为参照的话)?

2>沿着刚刚的思想会继续换,这样序列变成了 5 1 2 4 9 3 9 7 10 8(这里为什么总是有两个数是相同的呢,想想这样会不会有什么影响,其实没有,因为每一轮下去两个游走的下标会相遇,即两个相同的数字相临,那么前者会是分界线,也就是基准数的位置 即会变成 5 1 2 4 3 9 9 7 10 8 )

3>下一次从右到左发现了他的前面就是left,然后把基准数移到left位置,至此第一轮交换完毕

4>这样的话 整个序列变成了 三个序列 分别是 5 1 2 4 3 和 6 和 9 7 10 8

然后对5 1 2 4 3 和 9 7 10 8重复上诉1 > 2> 3> 4>步骤

最后会得到 1 2 3 4 5 6 7 8 9 10

细心的朋友可能会发现如果每次能把这个序列均分,n个数 最终分成N/2组,最后再对每组的两个数排序,这样是最优的情况10000个数 一次分成2个5000
1+2次分成 四个 2500,1+2+3次分成8个1250,,那么最终需要1+…x 想想x是不是logn复杂度 就是 nlogn/2,,,
那么最糟糕的情况呢,基本有序的时候,10000个数分成9999 1 然后 9998 1 1以此类推,,然后每次移动都需要n-1次 这种情况是最糟糕的,所以快排是不稳定的排序算法。(每种排序算法都有缺点,局限性)

下面给出结构体的快速排序算法的代码实现,

假设有结构体

typedef struct STreeNode* pSTreeNode;
struct STreeNode
{
	int nodeid;
	int namevalue;
	vector<pSTreeNode> pChildList;
}; 

上诉实现

int 
CTree::Partition(vector<pSTreeNode>&nodeids, int left, int right)
{     
	pSTreeNode Righttmp = nodeids[left];//基准数
	while (left < right) {
		while(left < right && nodeids[right]->namevalue >= Righttmp->namevalue) {
			right--;
		}  
		nodeids[left] = nodeids[right];

		while(left < right && nodeids[left]->namevalue <= Righttmp->namevalue) {
			left++;
		}  
		nodeids[right] = nodeids[left];
	}
	nodeids[left] = Righttmp;
	return left;
}

void 
CTree::quickSort(vector<pSTreeNode>&nodeids, int left, int right)
{
	if (left < right)
	{
		int q = Partition(nodeids, left, right);
		quickSort(nodeids, left, q - 1);
		quickSort(nodeids, q + 1, right);
	}
}
2012-09-24 14:05:06 kafeiwuzhuren 阅读数 791

#pragma pack(push,1)//设置字节对齐为1字节

#pragma pack(pop)//恢复上面的字节对齐方式为默认

对齐很重要,对结构体,一定要对齐,尤其是涉及到文件/内存双向转换的

#pragma pack(push,1)
struct RateInfoOld
  {
   time_t            ctm;                    // rate time
   int               open;                   // open price: 11987=119.87
   short             high,low,close;         // high,low,close shift from open
   double            vol;                    // volume
  };
#pragma pack(pop)

2018-12-11 16:42:35 momingqimiao71 阅读数 62

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "DataStore.h"

DataStore*  ds_create()
{
	// 动态创建对象
	DataStore* store = (DataStore*)malloc(sizeof(DataStore));
	// 初始化
	store->head.next = NULL;

	return store;
}

void ds_destroy(DataStore*  store)
{
	// 释放所有相关资源
	Student* p = store->head.next;
	while(p)
	{
		Student* next = p->next;
		free(p);
		p = next;
	}
	// 销毁对象
	free(store);
}

void ds_add( DataStore* store, const Student* data)
{
	// 创建对象、复制数据
	Student* copy = (Student*)malloc(sizeof(Student));
	*copy = *data;

	// 插入一个对象到链表中
	Student* cur = store->head.next; // 当前节点current
	Student* pre = &store->head;  // 上一个节点previous
	while(cur)
	{		
		if(copy->id < cur->id) // 找到这个位置
			break;

		pre = cur;
		cur = cur->next;  // 找到最后一个对象
	}

	// 插入到pre节点的后面
	copy->next = pre->next;
	pre->next = copy;

}


// (2) 可以按ID来查找一个记录
Student* ds_find(DataStore* store, int id)
{
	Student* p = store->head.next; 
	while(p)
	{
		if(p->id == id)
			return p;

		p = p->next; // 下一个对象
	}
	return NULL;
}

//(3) 可以按ID删除一个记录
void ds_remove(DataStore* store, int id)
{

}

// (4) 可以打印显示所有的记录
void ds_print(DataStore* store)
{
	Student* p = store->head.next; 
	while(p)
	{
		printf("ID: %d, name: %s\n", p->id, p->name);
		p = p->next; // 下一个对象
	}
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "DataStore.h"

int main()
{
	DataStore* store = ds_create();

	Student s;
	s.id = 1;
	strcpy(s.name, "111");
	ds_add(store, &s);

	s.id = 2;
	strcpy(s.name, "222");
	ds_add(store, &s);

	Student* f = ds_find(store, 2);

	ds_print(store);

	ds_destroy(store);

	return 0;
}


struct Student {
	int id;
	char name[16];
	Student* next;
};

struct DataStore {
	Student head;
};

DataStore* ds_create();

void ds_destroy(DataStore* store);

void ds_add(DataStore* store, const Student* data);

Student* ds_find(DataStore* store, int id);

void ds_remove(DataStore* store, int id);

void ds_print(DataStore* store);

 

 

 

c++结构体

阅读数 255

C++结构体

阅读数 167

C++结构体

阅读数 187

C++结构体

阅读数 2

没有更多推荐了,返回首页