结构体
结构体是一种特殊形态的类，与类的唯一区别是：类的缺省访问权限是private，结构体的缺省访问权限是public。
那么什么时候用结构体而不用类：定义主要用来保存数据，没没有什么操作的类型。人们习惯将结构体的数据成员设为公有，这时使用结构体更方便。
结构体相当于构造了一个新的数据类型，用一组变量描述同一个“事物”。
1
2
3
4
5
6
7
8
9
| struct stduent
{
int id;
char name[20];
char sex;
int age;
float score;
char addr[30];
};
|
定义结构体变量的方式：
- 直接用已声明的结构体类型定义变量名
1
| student student1, student2;
|
- 在声明类型的同时定义变量
1
2
3
4
5
6
7
8
9
| struct stduent
{
int id;
char name[20];
char sex;
int age;
float score;
char addr[30];
}student1,student2;
|
结构体数据类型的特性与普通数据类型的特性是一致的，可以赋值，做函数参数，有指向结构体的指针，结构体数组等等。
定义结构体类型的变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
using namespace std;
struct student
{
int id_num;
char name[10];
};
int main()
{
student mike = { 123,"mike" };
mike.id_num = 2123000 + mike.id_num;
for (int i = 0; mike.name[i] != '\0'; i++)
mike.name[i] = toupper(mike.name[i]);
cout << mike.id_num << " " << mike.name << endl;
return 0;
}
|
结构体变量赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<iostream>
using namespace std;
struct student
{
int id_num;
char name[10];
};
int main()
{
student mike1 = { 123,"mike" };
student mike2;
mike2 = mike1;
mike2.id_num = 2123000 + mike2.id_num;
for (int i = 0; mike2.name[i] != '\0'; i++)
mike2.name[i] = toupper(mike2.name[i]);
cout << mike1.id_num << " " << mike1.name << endl;
cout << mike2.id_num << " " << mike2.name << endl;
return 0;
}
|
结构体做函数参数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<iostream>
using namespace std;
struct student
{
int id_num;
char name[10];
};
void renew(student one)
{
one.id_num = 2123000 + one.id_num;
for (int i = 0; one.name[i] != '\0'; i++)
one.name[i] = toupper(one.name[i]);
cout << one.id_num << " " << one.name << endl;
}
int main()
{
student mike = { 123,"mike" };
renew(mike);
return 0;
}
|
指向结构体的指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<iostream>
using namespace std;
struct student
{
int id_num;
char name[10];
};
int main()
{
student mike = { 123,"mike" };
student *one = &mike;
cout << one->id_num << " " << one->name << endl;
return 0;
}
|
结构体数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<iostream>
using namespace std;
struct student
{
int id_num;
char name[10];
};
int main()
{
student myclass[3] = { 123,"mike",133,"tom", 143,"jack"};
student *one = myclass;
cout << one->id_num << " " << one->name << endl;
one++;
cout << one->id_num << " " << one->name << endl;
one++;
cout << one->id_num << " " << one->name << endl;
return 0;
}
|
枚举类型
枚举：如果一个变量只有几种可能的取值，则可以将该变量定义为枚举类型。
枚举类型的定义
1
2
3
4
5
6
7
|
enum weekday{sun,mon,tue,wed,thu,fri,sat};
enum weekday workday,weekend;
weekday workday,weekend
workday = sun; weekend = moon;
|
需要注意的是：
- 枚举类型按常量处理，不能对它们赋值。
sun = mon; （错误）
- 枚举类型不能直接输出元素的名字。
enum color{red,green,white,black}; color cloth = red; cout<<cloth; //结果为0。
- 枚举类型可以比较。
if(cloth > white) count++
- 一个整型不能直接赋给一个枚举变量。
workday = 2; （错误）
- 枚举元素有值：
- 定义时枚举元素如未指定值，编译系统按定义顺序取默认值依次为0,1,2,3,….
- 也可以给枚举元素指定对应的值，
enum day {sun=7,mon=1, tue, wed, thu, fri, sat}; 这时有sun=7, mon=1, tue=2, wed=3,......
- 若要把整数赋给枚举变量应先进行强制类型转换，
workday = (enum weekday) 2;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<iostream>
using namespace std;
enum color{red,yellow, green=3,blue};
enum color cl;
int main()
{
cl = blue;
cout << "red=" << red << " yellow=" << yellow << " green=" << green << endl;
cout << "blue=" << blue << " cl=" << cl << endl;
switch (cl)
{
case red: cout << "red\n"; break;
case yellow: cout << "yellow\n"; break;
case green: cout << "green\n"; break;
case blue: cout << "blue\n"; break;
}
return 0;
}
|
例子：计算工资
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<iostream>
using namespace std;
int main()
{
enum day{Mon,Tue,Wed,Thu,Fri,Sat,Sun};
day workDay;
double times, wages = 0, hourlyPay, hours;
cout << "Enter the hourly wages rate." << endl;
cin >> hourlyPay;
cout << "Enter hours worked daily" << endl;
for (int i = 0; i < 7; i++)
{
cin >> hours;
switch ((day)i)
{
case Sat:times = 1.5*hours; break;
case Sun:times = 2 * hours; break;
default:times = hours;
}
wages = wages + times * hourlyPay;
}
cout << "The wages for the week are " << wages << endl;
return 0;
}
|
共用体
共用体：为了节省内存空间，可以将几种不同类型的变量存放到同一段内存单元中，这段内存单元所对应的数据结构称为共用体。
共用体的定义：uniom 共用体名{ 成员列表; }变量列表;
1
2
3
4
5
6
7
8
| union data
{
int i;
char ch;
float f;
}a,b,c;
data a,b,c;
|
共用体的引用：不能引用共用体变量，只能引用共用体变量中的成员。
共用体类型数据的特点：
- 同一内存段可以存放几种不同类型的成员，但在同一时刻时只能存放其中一种。
- 共用体变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后原有的成员就失去作用。
- 共用体变量的地址和它的各成员的地址都是同一地址，如
&a, &a.i, &a.ch, &a.f都是同一地址值。
- 共用体不能初始化，不能对整个共用体赋值。
- 在函数中，可以使用共用体的指针，但不能使用名字做函数参数。
- 共用体的空间是所有成员中最大的一个。
例子：
1
2
3
4
5
6
7
8
9
10
11
12
| struct
{
int num;
char name[10];
char sex;
char job;
union
{
int Class;
char position[10];
}category;
}preson[2];
|
链表
链表是一种非常常用的动态数据结构，可以用来表示顺序访问的线性群体：
- 链表头：指向第一个链表结点的指针；
- 链表结点：链表中的每一个元素，包括：当前结点的数据，下一个结点的地址；
- 链表尾：不再指向其他结点的结点，其地址部分放一个
NULL，表示链表到此结束。
关于new & delete
new：C++运算符，动态地分配内存空间，并将所分配的内存的地址赋给指针变量。
delete：C++运算符，将动态分配的内存空间归还给系统。
用法一：
分配某种类型大小的一片连续内存空间，并将内存空间的首地址赋给指针变量。
1
2
3
4
5
6
7
8
9
10
11
12
| #include<iostream>
using namespace std;
int main()
{
int *p = new int;
cout << *p << endl;
*p = 10;
cout << *p << endl;
delete p;
return 0;
}
|
用法二：
分配空间，并将初始值存入所分配的空间中。
1
2
3
4
5
6
7
8
9
| int main()
{
int *p = new int(10);
cout << *p << endl;
delete p;
cout << *p << endl;
return 0;
}
|
用法三：
- <指针变量> = new<类型>[<常量表达式>];
分配指定类型的数组空间，并将数组的首地址赋给指针变量。
将指针变量所指向一维数组内存空间归还给系统。
1
2
3
4
5
6
7
8
9
10
11
12
| #include<iostream>
using namespace std;
int main()
{
int *p = new int[5];
memset(p, 0, 20);
for(int i=0;i<5;i++)
cout << *(p+i) << endl;
delete p;
return 0;
}
|
当new & delete 用于结构体
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<iostream>
using namespace std;
struct Node
{
int n;
Node *next;
};
int main()
{
Node *p = new Node;
cout << p->n << endl;
cout << p->next << endl;
return 0;
}
|
逐步建立链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
using namespace std;
struct student
{
int id;
student *next;
};
student *create()
{
student *head, *temp;
int num, n = 0;
head = new student;
temp = head;
cin >> num;
while (num != -1)
{
n++;
temp->id = num;
temp->next = new student;
temp = temp->next;
cin >> num;
}
if (n == 0)
head = NULL;
else
temp->next = NULL;
return head;
}
int main()
{
student *pointer = create();
while (pointer->next != NULL)
{
cout << pointer->id << endl;
pointer = pointer->next;
}
return 0;
}
|
删除结点
例子：在链表中将值为n的结点删掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| student *dele(student *head, int n)
{
student *temp, *follow;
temp = head;
if (head == NULL)
return(head);
if (head->id == n)
{
head = head->next;
delete temp;
return(head);
}
while (temp != NULL && temp->id != n)
{
follow = temp;
temp = temp->next;
}
if (temp == NULL)
cout << "not found";
else
{
follow->next = temp->next;
delete temp;
}
return(head);
}
|
插入结点
1.将结点unit插入链表的最前面
2.将结点unit插入链表的中间
3.将结点unit插入链表的最后
例子：插入结点值为n的结点（按大小顺序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| student *insert(student *head, int n)
{
student *temp, *unit, *follow;
temp = head;
unit = new student;
unit->id = n;
unit->next = NULL;
if (head == NULL)
{
head = unit;
return(head);
}
while ((temp->next != NULL) && (temp->id < n))
{
follow = temp;
temp = temp->next;
}
if (temp == head)
{
unit->next = head;
head = unit;
}
else
{
if (temp->next == NULL)
temp->next = unit;
else
{
follow->next = unit;
unit->next = temp;
}
}
return(head);
}
|
单向链表
双向链表
删除结点temp
将结点unit插入到temp之后
例子：约瑟夫环问题
问题描述：n个孩子围坐成一圈，并按顺时针编号为1,2,3, ……,n，从编号为p的小孩顺时针依次报数，由1报到m，当报到m时，该小孩从圈中出去，然后下一个小孩再从1报数，当报到m时再出去。如此反复，直至所有的小孩都从圈中出去。请按出去的先后顺序输出小孩的编号（假设小孩的个数不多于300个）。
关于输入：n,p,m的值在1行内输入，以空格间隔
关于输出：按出圈的顺序输出编号，编号之间以逗号间隔。
思路：
首先定义结点的结构体，列出需要的函数的，然后再考虑每个函数需要完成的功能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<iostream>
using namespace std;
struct Node
{
int num;
Node *next;
Node *ahead;
};
Node *Create(int N);
Node *Search(Node *head, int P);
Node *Release(Node *head, int M);
int main()
{
int N, P, M = 0;
cout << "请输入人数N，从几号开始P，报到哪个数M：" << endl;
cin >> N >> P >> M;
Node *head = Create(N);
head = Search(head, P);
while (head->next != head)
{
head = Release(head, M);
}
cout << head->num;
return 0;
}
Node *Create(int N)
{
int n = 1;
Node *node = new Node;
node->num = n;
Node *head = node;
Node *tail = head;
while (n++ < N)
{
node = new Node;
node->num = n;
tail->next = node;
node->ahead = tail;
tail = tail->next;
}
tail->next = head;
head->ahead = tail;
return head;
}
Node *Search(Node *head, int P)
{
while (head->num != P)
{
head = head->next;
}
return head;
}
Node *Release(Node *head, int M)
{
int count = 1;
Node *temp = head;
while (count < M)
{
temp = temp->next;
count++;
}
temp->ahead->next = temp->next;
temp->next->ahead = temp->ahead;
cout << temp->num << ", ";
head = temp->next;
delete temp;
return head;
}
|
