[数据结构与算法]自定义结构类型与电话通讯录的实现

??CSDN的小伙伴们中秋节快乐呀！

??整理了一下今天所学与大家分享，就当是中秋节礼物啦。

一、结构体

struct Node{
    int data;
    Struct Node n;
}//这样定义的缺陷在于每个node里头都有个node，不断地递归至无限的大，无法确定需要的内存空间大小。
struct Node{
    int data;
    struct Node* next;
}//指针的大小就是四个字节或者八个字节，避免了上面无法确定内存空间大小的问题。
//结构体自引用：这个结构体可以找到同类型的结构体

1.0 结构体的创建与初始化

struct Point{
    int x;
    int y;
}p3={1,2},p4={5,6};
struct Point p2={7,8};
int main()
{
    struct Point p1={10,12};
    
    return 0;
}

1.1 结构体内存对齐

#include <stdio.h>
struct S1{
    char c1;//1
    int data;//4
    char c2;//1
}s={'c',100,'f'};
struct S2{
    char c1;
    char c2;
    int a;
}
int main()
{
    printf("%d\n",sizeof(s));
    printf("%d\n",sizeof(struct S2));
}
结果居然是
12
8

不一样的原因是因为内存对齐（在结构体体现的非常明显）。

结构体内存对齐的规则：

1.结构体的第一个成员永远放在结构体起始位置偏移量为0的位置。

2.从第二个结构体成员开始，总是放在偏移量为一个对齐数的整数倍处。

对齐数=编译器默认的对齐数和变量自身大小的较小值。

Linux没有默认对齐数。

VS下默认对齐数是8。

3.结构体的总大小必须是各个成员的对齐数中最大那个对齐数的整数倍。

4.如果嵌套了结构体，嵌套结构体对齐到自己的成员的最大对齐数的整数倍处，结构体的整体大小就是所有最大对齐数（含嵌套结构体的对齐数）的整数倍。

存在内存对齐的原因：

1.平台原因（移植原因）：

不是所有的硬件平台都能访问任意地址上的任意数据，某些硬件平台只能在某些地址处取某特定类型的数据，否则抛出硬件异常。

2.性能原因

数据结构（尤其是栈）应该尽可能的在自然边界上，原因在于为了访问未对齐的内存，处理器需要做两次内存访问，而对齐的内存仅需要访问一次。

总的来说：结构体的内存对齐是拿空间来换取时间的做法。

12
struct S1{
    char c1;//1
    int data;//4
    char c2;//1
}s={'c',100,'f'};
8
struct S2{
    char c1;
    char c2;
    int a;
}

我们通过对比发现设计结构体时稍微动动脑筋是不是可以节约一些空间呢。

对比s1、s2，我们在创建结构体时建议：让占用空间小的对象尽量放在一起，减少空间浪费。

VS下能否修改默认对齐数呢，当然是可以的。

修改默认对齐数：用编译预处理指令#pragma

#pragma pack(1)//设置默认对齐数是1 这样就全部堆在一起了
struct S1{
    char a;
    int i;
    char c;
};
#pragma pack()//取消设置的默认对齐数
#pragma pack(8)
struct S2 {
	char a;
	int b;
	char c;
};
int main()
{
	printf("%d", sizeof(struct S1));
	printf("%d", sizeof(struct S2));
	return 0;
}
输出的值为6 12	

比较S1和S2我们得出结论：结构在对齐方式不合适的时候，我们也可以自己更改默认对齐数。

但是要注意：为了效率的保证，由于32位机器寄存器每次读取4位，64位机器寄存器每次读取8位，如果默认对齐数设置为奇数影响读取效率，修改默认对齐数最好修改成偶数。

1.2 offsetof函数

我们能不能用一个函数直接返回一个结构体成员相对结构体首地址的偏移量呢？答案是可以的——offsetof函数。

offsetof(struct,struct.member)
返回该成员相对结构体首地址的偏移量。
这是一个宏，需要一个头文件<stddef.h>

1.3 结构体传参数：

#include <stdio.h>
struct S {
	int data[100];
	int number;
};
void print1(struct S a)
{
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a.data[i]);
	}
	printf("\n%d\n", a.number);
}
void print2(struct S* p)
{
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n%d\n", p->number);
}
int main()
{
	struct S s1 = { {1,2,3,4,5,6,9,8,10},10 };
	print1(s1);
	print2(&s1);
	return 0;
}

上面的print1和print2函数选哪个？

首选print2函数

原因：函数在传参的饿时候，参数是需要压栈的，会有时间和空间上的开销、

如果传递一个结构体对象的时候，结构体过大，参数压栈的系统开销比较大，所以会导致性能下降。

K&R曾在最初的C语言使用手册中提到，如果你想要把结构体作为参数传入一个函数，最好的做法是传入指向该结构体的指针。

二、位段

2.0 什么是位段？

位段的声明和结构体类似，不过有两个不同点。

• 位段的成员必须是int、unsigned int或signed int（其实char也可以，整型家族的好像都行）
• 位段的成员名至少后面有一个冒号和一个数字，我们并不是要求每个位段的成员名后面都要有冒号和数字。

位段是可以节省空间的，但也并不意味着一点浪费都没有。

这里的位值得是二进制位。

#include <stdio.h>
struct A {
	int a : 2;
	int b : 5;
	int c : 10;
	int d : 30;
};
int main()
{
	printf("%d", sizeof(struct A));
	return 0;
}

输出：16
为什么呢？这就涉及到了位段这种结构的内存分配。

2.1 位段的内存分配

位段的空间上是按照需要先以4个字节（int）或者一个字节（char）的方式来开辟的，如果不够再新开辟4个字节或者1个字节，至于怎么使用所给的空间（从左边开始用还是从右边开始用）还有怎么放那个导致不够的位段成员（是直接放到新开辟的空间里还是既用原本的空间也用新开辟的空间），C的标准并没有给出，故不确定。

位段涉及以上不确定因素，故位段是不跨平台的，注重可移植的程序应避免使用位段。

可以用一个实验来验证

struct S {
	char a : 3;
	char b : 4;
	char c : 5;
	char d : 4;
};
int main()
{
	struct S s = { 0 };
	s.a = 10;
	s.b = 12;
	s.c = 3;
	s.d = 4;

	return 0;
}

如果是从右边开始用这片空间且申请新的空间后导致申请的东西直接放到新的空间里去，我们下面将各个数以2进制展开。

一开始给你一个字节 8bit,0000 0000。

a=10=0000 1010过来后，取3个位变成010，放进去变成 0000 0010

b=12=0000 1100，取4个位变成1100，过来以后放进去变成 0110 0010

c过来不够用了 再申请一块 0000 0000

c=3=0000 0110 取5个位变成00110.

放进去 变成0000 0110

d过来了 不够了 再开辟一块 0000 0000

d=4=0000 0100 取4个位 0100

放进去0000 0100

这样在机器是小端的情况下，以16进制读这块内存就是

0110 0010 0000 0110 0000 0100

? 6 2 0 3 0 4

经过实验后结论与我们的假设吻合，不过或许也仅仅是vs这个编译器是这样做的，并不是所有编译器都这样做，因为C没有规定标准。

经过实验发现：offsetof是不能对位段操作的。

2.2 位段的跨平台问题

• int位段（int开辟的空间）被当成有符号数还是无符号数是不确定的。

• 位段中最大数目不确定，比如在16位机器上 int是2byte 写超过16的位段就没法运行了。

• 位段中的成员从左向右定义还是从右向左定义标准并为明确定义

• 当一个结构包含两个位段是，第二个位段成员比较大，无法容纳于第一个位段剩余的位时，是舍弃剩余的位还是利用，这是不确定的。

三、枚举

枚举的含义就是一一列举。

性别有男 女 保密 可以一一列举

月份有12个月 也可以一一列举

这些地方就可以使用枚举了

#include <stdio.h>
enum COLOR {
	RED=6,
	GREEN=10,
	BLUE
};//枚举常量初始化
int main()
{
	enum COLOR  c= GREEN;//定义一种枚举变量c
	printf("%d %d %d", RED, GREEN, BLUE);
	return 0;
}

枚举让名字有了一些意义，这样我们设计程序的时候尤其是使用switch语句时可以case RED:这样写，看起来也更加易读。

枚举的优点

• 增加代码的可读性和可维护性
• 和#define定义的标识符相比，枚举有类型检查，更加严谨、
• 防止了命名污染（封装）
• 便于调试（调试可以看值，#define就会直接替换）
• 使用方便，一次可以定义多个枚举常量。

四、联合（共用体）

联合也是一种特殊的自定义类型。

这种类型定义的变量也包含一系列的成员，特征是这些成员公用一块空间。（所以联合体也叫共用体）

#include <stdio.h>
union U {
	char c;
	int a;
};
int main()
{
	union U u = { 0 };
	printf("%d\n", sizeof(union U));
	printf("%p\n", &u);
	printf("%p\n", &(u.a));
	printf("%p\n", &(u.c));
	return 0;
}

发现三个地址一模一样，为什么呢？

这说明c和i共用了一块空间。

由于他们共用了一块空间，修改c就会导致i变化，修改i就会导致c变化。

出于能够储存成员的考虑，一个联合的大小，至少是最大成员的大小。

16.0 判断一个机器是大端还是小端

判断一个机器是大端还是小端
int main()
{
    int a=1;//0x 00 00 00 01
    //这里 低地址向高地址
    //01 00 00 00 小端存储
    //00 00 00 01 大端存储
    //大端会把高位放在低地址，低位放在高地址
    //小端会把高位放在高地址，低位放在低地址
    //做法1 我们只看第一个字节
    char* pc=(char*)&a;
    if(*pc==1)
    {
        printf("小端");
    }
    else
    {
        printf("大端");
    }
}
//这里不能用用强制类型转化char来判断，因为它只会转化第一位，第一位大端放后头小端放前头根本看不出来。

//做法2 利用union共用体
    union U {
        char c;
        int i;
    } u;
    u.i = 1;
//如果是大端 那么他在高地址存放了这个低位 我们的u.c只读低地址的一位读不到
//如果是小端 那么他在低地址存放了这个低位，我们的u.c就可以读到。
    if (u.c == 1)
    {
        printf("\n小端");
    }
    else
    {
        printf("\n大端");
    }

出于联合体的性质考虑使用场景：同一时间使用一个成员时不要使用别的成员。

16.1 联合体的大小计算：

• 联合体的大小至少是最大成员的大小，所以我们一般先假设联合体的大小就是最大成员的大小
• 如果检查到最大成员大小不是最大对齐数的整数倍的时候，将联合体的大小对齐到最大对齐数的整数倍。

共用体的对齐

#include <stdio.h>

union Un1
{
	char c[5];//数组在找对齐数的时候，就相当于在这放了5个本身类型的元素 对齐数自然是1
	int i;//对齐数是4
};//max(5,4)=5 不是最大对齐数4的倍数 所以浪费一些空间对齐到8
union Un2
{
	short c[7];//对齐数是2
	int i;//对齐数是4
};//max(4,14)=14 不是4的倍数 对齐到16.
int main()
{
	printf("%d\n", sizeof(union Un1));
	printf("%d\n", sizeof(union Un2));
	return 0;
}

五、电话通讯录的实现

这是对于自定义类型的一次很好的练习，也用了我不少时间。

contact.h

#define _CRT_SECURE_NO_WARNINGS 1

#ifndef define _CONTACT_H_

#define _CONTACT_H_



#include <stdio.h>

#include <string.h>

//一些方便改的数

#define MAXNAME 20

#define MAXSEX 5

#define MAXTEL 20

#define MAXDOOR 30

#define MAX 1000



//人的信息

typedef struct {

	char name[MAXNAME];

	char sex[MAXSEX];

	int age;

	char tel[MAXTEL];

	char address[MAXDOOR];

}person;



//通讯录

typedef struct {

	person perinfo[MAX];

	int sz;//当前通讯录中有效的人的个数

}Contact;



enum Option {

	EXIT,

	ADD,

	DELETE,

	FIND,

	CHANGE,

	SHOW,

	CLEAR,

	SORT,

};//利用枚举让switch看起来更加直观

void Initcontact(Contact* p);



void add(Contact* p);



void show(Contact* p);



void find(Contact* p);



void contactdelete(Contact* p);



void contactchange(Contact* p);



void contactclear(Contact* p);



void contactsort(Contact* p);



#endif



contact.c



#define _CRT_SECURE_NO_WARNINGS 1

#include "contact.h"



void Initcontact(Contact* p)

{

	p->sz = 0;

	memset(&p->perinfo, 0, MAX * sizeof(person));

}



void add(Contact* p)

{

	if (p->sz == MAX)

	{

		printf("通讯录满了\n");

	}

	else

	{

		printf("请输入姓名\n");

		scanf("%s", p->perinfo[p->sz].name);

		printf("请输入性别\n");

		scanf("%s", p->perinfo[p->sz].sex);

		printf("请输入年龄\n");

		scanf("%d", &(p->perinfo[p->sz].age));

		printf("请输入电话\n");

		scanf("%s", p->perinfo[p->sz].tel);

		printf("请输入住址\n");

		scanf("%s", p->perinfo[p->sz].address);

		p->sz++;

	}

}



void show(Contact* p)

{

	printf("%-20s\t%-5s\t%-s\t%-14s\t%-30s\n", "name", "sex", "age", "tel", "address");

	for (int i = 0; i < p->sz; i++)

	{

		printf("%-20s\t%-5s\t%-d\t%-14s\t%-30s\n", p->perinfo[i].name, p->perinfo[i].sex, p->perinfo[i].age, p->perinfo[i].tel, p->perinfo[i].address);

	}

}



void find(Contact* p)

{

	int a = 0;

	printf("如果你是要根据电话号查找，请输入1，如果要根据姓名查找，请输入0\n");

	scanf("%d", &a);

	if (a == 0)

	{

		char c[MAXNAME];

		printf("请输入查找姓名\n");

		scanf("%s", c);

		int ret = 0;

		for (int i = 0; i < p->sz; i++)

		{

			if (strcmp(c, p->perinfo[i].name) == 0)

			{

				printf("查找成功\n对应信息为\n");

				ret = 1;

				printf("%-20s\t%-5s\t%-d\t%-14s\t%-30s\n", p->perinfo[i].name, p->perinfo[i].sex, p->perinfo[i].age, p->perinfo[i].tel, p->perinfo[i].address);

				break;

			}

		}

		if (ret == 0)

		{

			printf("电话簿中查无此人，请核对此人的姓名是否输入正确\n");

		}

	}

	else if (a == 1)

	{

		int ret = 0;

		printf("请输入待查找的电话号码\n");

		char c[MAXTEL];

		scanf("%s", c);

		for (int i = 0; i < p->sz; i++)

		{

			if (strcmp(c, p->perinfo[i].tel) == 0)

			{

				printf("查找成功\n对应信息为\n");

				ret = 1;

				printf("%-20s\t%-5s\t%-d\t%-14s\t%-30s\n", p->perinfo[i].name, p->perinfo[i].sex, p->perinfo[i].age, p->perinfo[i].tel, p->perinfo[i].address);

				break;

			}

		}

		if (ret == 0)

		{

			printf("电话簿中查无此人，请核对此人的姓名是否输入正确\n");

		}

	}

	else

	{

		printf("输入错误，即将回到初始界面\n");

	}

}



void contactdelete(Contact* p)

{

	int a = 0;

	printf("如果你是要根据电话号删除，请输入1，如果要根据姓名删除，请输入0\n");

	scanf("%d", &a);

	if (a == 0)

	{

		char c[MAXNAME];

		printf("请输入要删除的姓名\n");

		scanf("%s", c);

		int ret = 0;

		int i = 0;

		for ( i = 0; i < p->sz; i++)

		{

			if (strcmp(c, p->perinfo[i].name) == 0)

			{

				ret = 1;

				break;

			}

		}

		if (ret == 0)

		{

			printf("电话簿中查无此人，请核对此人的姓名是否输入正确\n");

		}

		else

		{

			for (int j= i; j < p->sz; j++)

			{

				p->perinfo[j] = p->perinfo[j + 1];

			}

			p->sz--;

			printf("删除成功\n");

		}

	}

	else if (a == 1)

	{

		int ret = 0;

		printf("请输入你要删除的电话号码\n");

		char c[MAXTEL];

		scanf("%s", c);

		for (int i = 0; i < p->sz; i++)

		{

			if (strcmp(c, p->perinfo[i].tel) == 0)

			{

				int j = i;

				for (j = i; i < p->sz; j++)

				{

					p->perinfo[j] = p->perinfo[j + 1];

				}

				p->sz--;

				printf("删除成功\n");

				ret = 1;

				break;

			}

		}

		if (ret == 0)

		{

			printf("电话簿中查无此人，请核对此人的电话号码是否输入正确\n");

		}

	}

	else

	{

		printf("输入错误，即将回到初始界面\n");

	}

}



void contactchange(Contact* p)

{

	char c[MAXNAME];

	printf("请输入要待修改单位的姓名\n");

	scanf("%s", c);

	int ret = 0;

	for (int i = 0; i < p->sz; i++)

	{

		if (strcmp(c, p->perinfo[i].name) == 0)

		{

			int change[5] = {0};

			printf("是否需要修改姓名？需要修改姓名请输入1，否则输入0\n");

			scanf("%d", &change[0]);

			if (change[0] == 1)

			{

				printf("请输入新姓名\n");

				scanf("%s", p->perinfo[i].name);

			}

			printf("是否需要修改性别？需要修改性别请输入1，否则输入0\n");

			scanf("%d", &change[1]);

			if (change[1] == 1)

			{

				printf("请输入正确性别\n");

				scanf("%s", p->perinfo[i].sex);

			}

			printf("是否需要修改年龄？需要修改年龄请输入1，否则输入0\n");

			scanf("%d", &change[2]);

			if (change[2] == 1)

			{

				printf("请输入新年龄\n");

				scanf("%d",&( p->perinfo[i].age));

			}

			printf("是否需要修改电话号码？需要修改电话号码请输入1，否则输入0\n");

			scanf("%d", &change[3]);

			if (change[3] == 1)

			{

				printf("请输入新电话号码\n");

				scanf("%s", p->perinfo[i].tel);

			}

			printf("是否需要修改住址？需要修改住址请输入1，否则输入0\n");

			scanf("%d", &change[4]);

			if (change[4] == 1)

			{

				printf("请输入新住址\n");

				scanf("%s", p->perinfo[i].address);

			}

			ret = 1;

			printf("修改成功！\n");

			printf("此人的新联系信息为:\n");

			printf("%-20s\t%-5s\t%-d\t%-14s\t%-30s\n", p->perinfo[i].name, p->perinfo[i].sex, p->perinfo[i].age, p->perinfo[i].tel, p->perinfo[i].address);

			break;

		}

	}

	if (ret == 0)

	{

		printf("电话簿中查无此人，请核对此人的姓名是否输入正确\n");

	}

}



void contactclear(Contact* p)

{

	Initcontact(p);

}



void contactsort(Contact* p)

{

	int i, j;

	char temp1[MAXNAME];

	char temp2[MAXSEX];

	int temp3;

	char temp4[MAXTEL];

	char temp5[MAXDOOR];

	for (i = 0; i < p->sz; i++)

	{

		for (j = 0; j < p->sz - 1 - i; j++)

		{

			if (strcmp(p->perinfo[j].name, p->perinfo[j + 1].name) > 0)

			{

				strcpy(temp1, p->perinfo[j].name);

				strcpy(temp2, p->perinfo[j].sex);

				temp3 = p->perinfo[j].age;

				strcpy(temp4, p->perinfo[j].tel);

				strcpy(temp5, p->perinfo[j].address);



				strcpy(p->perinfo[j].name, p->perinfo[j + 1].name);

				strcpy(p->perinfo[j].sex, p->perinfo[j + 1].sex);

				p->perinfo[j].age = p->perinfo[j + 1].age;

				strcpy(p->perinfo[j].tel, p->perinfo[j + 1].tel);

				strcpy(p->perinfo[j].address, p->perinfo[j + 1].address);



				strcpy(p->perinfo[j + 1].name, temp1);

				strcpy(p->perinfo[j + 1].sex, temp2);

				p->perinfo[j + 1].age = temp3;

				strcpy(p->perinfo[j + 1].tel, temp4);

				strcpy(p->perinfo[j + 1].address, temp5);

			}

		}

	}

	printf("排序成功！新的通讯录信息如下！\n");

	show(p);

}



test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "contact.h"



void menu()

{

	printf("*******************************************\n");

	printf("************这是一个通讯录设备*************\n");

	printf("*******************************************\n");

	printf("********输入对应数字启动对应功能***********\n");

	printf("*******************************************\n");

	printf("******1.ADD******************2.DELETE******\n");

	printf("*******************************************\n");

	printf("******3.FIND*****************4.CHANGE******\n");

	printf("*******************************************\n");

	printf("******5.SHOW*****************6.CLEAR*******\n");

	printf("*******************************************\n");

	printf("******7.SORT*****************0.EXIT********\n");

	printf("*******************************************\n");

}

int main()

{

	int input = 0;

	Contact contact;

	Initcontact(&contact);



	do {

		menu();

		scanf("%d", &input);

		switch (input)

		{

		case ADD: add(&contact); break;

		case DELETE:contactdelete(&contact); break;

		case FIND:find(&contact); break;

		case CHANGE:contactchange(&contact); break;

		case SHOW:show(&contact); break;

		case CLEAR:contactclear(&contact); break;

		case SORT:contactsort(&contact); break;

		case EXIT:

			printf("退出\n");

			break;

		default: printf("输入错误 请重新输入\n");

		}

	} while (input!=0);



	return 0;

}
//主函数方面，我们可以不用switch语句
//因为这些函数都是类似的，我们可以用函数指针数组
//不过这需要再定义一下exittable函数
void exittable(Contact* p)
{
	printf("退出\n");
}
int main()
{
	int input = 0;
    void(*pf[])(Contact*)={exitable,add,contactdelete,
    find,contactchange,show,contactclear,contactsort};
	Contact contact;
	Initcontact(&contact);
	do {
		menu();
		scanf("%d", &input);
		(*pf[input])(&contact);
	} while (input!=0);

	return 0;
}