結(jié)構(gòu)(struct)
現(xiàn)實(shí)需求
在現(xiàn)實(shí)問題中剔氏，常常需要用一組不同類型的數(shù)據(jù)來描述一個(gè)事物塑猖。比如一個(gè)
學(xué)生的學(xué)號(hào)、姓名和績點(diǎn)谈跛。一個(gè)工人的姓名羊苟、性別、年齡感憾、工資蜡励、電話......如果編程時(shí)要用多個(gè)不同類型的變量來描述一個(gè)事物，就很麻煩阻桅。當(dāng)然希望
只用一個(gè)變量就能代表一個(gè)“學(xué)生”這樣的事物凉倚。C++允許程序員自己定義新的數(shù)據(jù)類型。因此針對(duì)“學(xué)生”這種事物鳍刷，可以
定義一種新名為Student的數(shù)據(jù)類型占遥，一個(gè)Student類型的變量就能描述一個(gè)學(xué)
生的全部信息。同理输瓜，還可以定義數(shù)據(jù)類型 Worker以表示工人瓦胎。用“struct”關(guān)鍵字來定義一個(gè)“結(jié)構(gòu)”，也就定義了一個(gè)新的數(shù)據(jù)類型：
struct 結(jié)構(gòu)名
{
類型名 成員變量名尤揣；
類型名 成員變量名搔啊；
類型名 成員變量名；
……
};
struct Student {
unsigned ID;
char szName[20];
float fGPA;
};
Student 即成為自定義類型的名字北戏，可以用來定義變量
Stuent s1,s2;
例兩個(gè)同類型的結(jié)構(gòu)變量负芋，可以互相賦值。但是結(jié)構(gòu)變量之間不能用
“==”嗜愈、“!=”旧蛾、“<”、“>”蠕嫁、“<=”锨天、“>=”進(jìn)行比較運(yùn)算。一般來說剃毒，一個(gè)結(jié)構(gòu)變量所占的內(nèi)存空間的大小病袄，就是結(jié)構(gòu)中所有成員變
量大小之和搂赋。結(jié)構(gòu)變量中的各個(gè)成員變量在內(nèi)存中一般是連續(xù)存放的，一個(gè)結(jié)構(gòu)的成員變量可以是任何類型的益缠，包括可以是另一個(gè)結(jié)構(gòu)類型:
struct Date {
int year;
int month;
int day;
};
struct StudentEx {
unsigned ID;
char szName[20];
float fGPA;
Date birthday;
};
- 結(jié)構(gòu)的成員變量可以是指向本結(jié)構(gòu)類型的變量的指針
struct Employee {
string name;
int age;
int salary;
Employee * next;
};
訪問結(jié)構(gòu)變量的成員變量
- 一個(gè)結(jié)構(gòu)變量的成員變量脑奠，可以完全和一個(gè)普通變量一樣來使用，也可以
取得其地址幅慌。使用形式：
結(jié)構(gòu)變量名.成員變量名
struct Date {
int year;
int month;
int day;
};
struct StudentEx {
unsigned ID;
char szName[20];
float fGPA;
Date birthday;
};
StudentEx stu;
cin >> stu.fGPA;
stu.ID = 12345;
strcpy(stu.szName, "Tom");
cout << stu.fGPA;
stu.birthday.year = 1984;
unsigned int * p = & stu.ID; //p指向stu中的ID成員變量
結(jié)構(gòu)變量的初始化
- 結(jié)構(gòu)變量可以在定義時(shí)進(jìn)行初始化:
StudentEx stu = { 1234,"Tom",3.78,{ 1984,12,28 }};
結(jié)構(gòu)數(shù)組
StudentEx MyClass [50];
StudentEx MyClass2[50] = {
{ 1234,"Tom",3.78,{ 1984,12,28 }},
{ 1235,"Jack",3.25,{ 1985,12,23 }},
{ 1236,"Mary",4.00,{ 1984,12,21 }},
{ 1237,"Jone",2.78,{ 1985,2,28 }}
};
MyClass[1].ID = 1267;
MyClass[2].birthday.year = 1986;
int n = MyClass[2].birthday.month;
cin >> MyClass[0].szName;
指向結(jié)構(gòu)變量的指針
- 定義指向結(jié)構(gòu)變量的指針
結(jié)構(gòu)名 * 指針變量名;
StudentEx * pStudent;
StudentEx Stu1;
pStudent = & Stu1;
StudentEx Stu2 = * pStudent;
指向結(jié)構(gòu)變量的指針
- 通過指針宋欺，訪問其指向的結(jié)構(gòu)變量的成員變量：
指針->成員變量名
或：
(* 指針).成員變量名
StudentEx Stu;
StudentEx * pStu;
pStu = & Stu;
pStu->ID = 12345;
(*pStu).fGPA = 3.48;
cout << Stu.ID << endl; //輸出 12345
cout << Stu.fGPA << endl; //輸出 3.48
C++程序結(jié)構(gòu)
全局變量和局部變量
- 定義在函數(shù)內(nèi)部的變量叫局部變量（函數(shù)的形參也是局部變量）
- 定義在所有函數(shù)的外面的變量叫全局變量
- 全局變量在所有函數(shù)中均可以使用，局部變量只能在定義它的函數(shù)內(nèi)部使用
#include <iostream>
using namespace std;
int n1 = 5, n2 = 10; //全局變量
void Function1() {
int n3 =4;
n2 = 3;
}
void Function2() {
int n4;
n1 = 4;
n3 = 5; //編譯出錯(cuò)欠痴，n3無定義
}
靜態(tài)變量
- 全局變量都是靜態(tài)變量迄靠。局部變量定義時(shí)如果前面加了“static”關(guān)鍵字，
則該變量也成為靜態(tài)變量 - 靜態(tài)變量的存放地址喇辽，在整個(gè)程序運(yùn)行期間掌挚，都是固定不變的
- 非靜態(tài)變量(一定是局部變量)地址每次函數(shù)調(diào)用時(shí)都可能不同,在函數(shù)的一次
執(zhí)行期間不變 - 如果未明確初始化，則靜態(tài)變量會(huì)被自動(dòng)初始化成全0(每個(gè)bit都是0）菩咨，局
部非靜態(tài)變量的值則隨機(jī)
靜態(tài)變量示例
#include <iostream>
using namespace std;
void Func()
{
static int n = 4; //靜態(tài)變量只初始化一次
cout << n << endl;
++ n;
}
int main()
{
Func(); Func(); Func();
}
輸出結(jié)果：
4
5
6
靜態(tài)變量應(yīng)用:strtok的實(shí)現(xiàn)
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char str[] ="- This, a sample string, OK.";
//下面要從str逐個(gè)抽取出被" ,.-"這幾個(gè)字符分隔的字串
char * p = strtok (str," ,.-");
while ( p != NULL) //只要p不為NULL吠式，就說明找到了一個(gè)子串
{
cout << p << endl;
p = strtok(NULL, " ,.-");
//后續(xù)調(diào)用，第一個(gè)參數(shù)必須是NULL
}
return 0;
}
char * p = strtok (str," ,.-");
while ( p != NULL) //只要p不為NULL抽米，就說明找到了一個(gè)子串
{
cout << p << endl;
p = strtok(NULL, " ,.-");
//后續(xù)調(diào)用特占，第一個(gè)參數(shù)必須是NULL
}
輸出結(jié)果：
This
a
sample
string
OK
-?This,?a?sample?string,?OK\0
char * Strtok(char * p,char * sep)
{
static char * start ; //本次查找子串的起點(diǎn)
if(p)
start = p;
for(; *start && strchr(sep,*start); ++ start); //跳過分隔符號(hào)
if( * start == 0)
return NULL;
char * q = start;
for(; *start && !strchr(sep,*start); ++ start); //跳過非分隔符號(hào)
if( * start) {
* start = 0;
++ start;
}
return q;
}
標(biāo)識(shí)符的作用域
- 變量名、函數(shù)名云茸、類型名統(tǒng)稱為“標(biāo)識(shí)符”是目。一個(gè)標(biāo)識(shí)符能夠起作用的范圍
，叫做該標(biāo)識(shí)符的作用域 - 在一個(gè)標(biāo)識(shí)符的作用域之外使用該標(biāo)識(shí)符标捺，會(huì)導(dǎo)致“標(biāo)識(shí)符沒有定義”的編
譯錯(cuò)誤懊纳。使用標(biāo)識(shí)符的語句，必須出現(xiàn)在它們的聲明或定義之后 - 在單文件的程序中亡容，結(jié)構(gòu)嗤疯、函數(shù)和全局變量的作用域是其定義所在的整個(gè)文
件 - 函數(shù)形參的作用域是整個(gè)函數(shù)
- 局部變量的作用域，是從定義它的語句開始闺兢，到包含它的最內(nèi)層的那一對(duì)大
括號(hào)“{}”的右大括號(hào) “}”為止 - for循環(huán)里定義的循環(huán)控制變量茂缚，其作用域就是整個(gè)for循環(huán)
- 同名標(biāo)示符的作用域，可能一個(gè)被另一個(gè)包含屋谭。則在小的作用域里脚囊，作用域
大的那個(gè)標(biāo)識(shí)符被屏蔽，不起作用桐磁。
void Func(int m)
{
for( int i = 0; i < 4;++i ) {
if( m <= 0 ) {
int k = 3;
m = m *( k ++ );
}
else {
k = 0; //編譯出錯(cuò)悔耘，k無定義
int m = 4;
cout << m;
}
}
i= 2; //編譯出錯(cuò)，i無定義
}
變量的生存期
- 所謂變量的“生存期”所意，指的是在此期間淮逊，變量占有內(nèi)存空間，其占有的內(nèi)
存空間只能歸它使用扶踊，不會(huì)被用來存放別的東西泄鹏。 - 而變量的生存期終止，就意味著該變量不再占有內(nèi)存空間秧耗，它原來占有的內(nèi)
存空間备籽，隨時(shí)可能被派做他用。 - 全局變量的生存期分井，從程序被裝入內(nèi)存開始车猬，到整個(gè)程序結(jié)束。
- 靜態(tài)局部變量的生存期尺锚，從定義它語句第一次被執(zhí)行開始珠闰，到整個(gè)程序結(jié)束
為止。 - 函數(shù)形參的生存期從函數(shù)執(zhí)行開始瘫辩，到函數(shù)返回時(shí)結(jié)束伏嗜。非靜態(tài)局部變量的
生存期，從執(zhí)行到定義它的語句開始伐厌，一旦程序執(zhí)行到了它的作用域之外承绸，其
生存期即告終止。
void Func(int m)
{
for( int i = 0; i < 4;++i ) {
if( m <= 0 ) {
int k = 3;
m = m *( k ++ );
}
else {
k = 0; //編譯出錯(cuò)挣轨，k無定義
int m = 4;
cout << m;
}
}
i= 2; //編譯出錯(cuò)军熏，i無定義
}
簡單排序
排序問題
- 例題: 編程接收鍵盤輸入的若干個(gè)整數(shù)，排序后從小到大輸出卷扮。先輸入一個(gè)
整數(shù)n荡澎，表明有n個(gè)整數(shù)需要排序，接下來再輸入待排序的n個(gè)整數(shù)画饥。
解題思路：先將n個(gè)整數(shù)輸入到一個(gè)數(shù)組中衔瓮，然后對(duì)該數(shù)組進(jìn)行排序，最后遍
歷整個(gè)數(shù)組抖甘，逐個(gè)輸出其元素热鞍。
對(duì)數(shù)組排序有很多種簡單方法，如“冒泡排序”衔彻、 “選擇排序”薇宠、 “插入排
序”等
選擇排序
如果有N個(gè)元素需要排序，那么首先從N個(gè)元素中找到最小的那個(gè)(稱為第0
小的)放在第0個(gè)位子上(和原來的第0個(gè)位子上的元素交換位置)艰额，然后再從剩
下的N-1個(gè)元素中找到最小的放在第1個(gè)位子上澄港，然后再從剩下的N-2個(gè)元素中
找到最小的放在第2個(gè)位子上……直到所有的元素都就位。
void SelectionSort(int a[] ,int size)
{
for( int i = 0; i < size - 1; ++i ){//每次循環(huán)后將第i小的元素放好
int tmpMin = i;
//用來記錄從第i個(gè)到第size-1個(gè)元素中柄沮，最小的那個(gè)元素的下標(biāo)
for( int j = i+1; j < size ; ++j) {
if( a[j] < a[tmpMin] )
tmpMin = j;
}
//下面將第i小的元素放在第i個(gè)位子上回梧，并將原來占著第i個(gè)位子的元素挪到后面
int tmp = a[i];
a[i] = a[tmpMin];
a[tmpMin] = tmp;
}
}
插入排序
- 將整個(gè)數(shù)組a分為有序的部分和無序的兩個(gè)部分废岂。前者在左邊，后者在右邊狱意。
- 開始有序的部分只有a[0]湖苞，其余都屬于無序的部分
- 每次取出無序部分的第一個(gè)（最左邊）元素，把它加入到有序部分详囤。假設(shè)插
入到合適位置p, 則原p位置及其后面的有序部分元素财骨，都向右移動(dòng)一個(gè)位子。
有序的部分即增加了一個(gè)元素藏姐。 - 直到無序的部分沒有元素
void InsertionSort(int a[] ,int size)
{
for(int i = 1;i < size; ++i ) {
//a[i]是最左的無序元素隆箩，每次循環(huán)將a[i]放到合適位置
for(int j = 0; j < i; ++j)
if( a[j]>a[i]) {
//要把a(bǔ)[i]放到位置j，原下標(biāo)j到 i-1的元素都往后移一個(gè)位子
int tmp = a[i];
for(int k = i; k > j; --k)
a[k] = a[k-1];
a[j] = tmp;
break;
}
}
}
冒泡排序
- 將整個(gè)數(shù)組a分為有序的部分和無序的兩個(gè)部分羔杨。前者在右捌臊，后者在左邊。
- 開始兜材，整個(gè)數(shù)組都是無序的娃属。有序的部分沒有元素。
- 每次要使得無序部分最大的元素移動(dòng)到有序部分第一個(gè)元素的左邊护姆。移動(dòng)的
方法是：依次比較相鄰的兩個(gè)元素矾端，如果前面的比后面的大，就交換他們的位
置卵皂。這樣秩铆，大的元素就像水里氣泡一樣不斷往上浮。移動(dòng)結(jié)束有序部分增加了
一個(gè)元素灯变。 - 直到無序的部分沒有元素
void BubbleSort(int a[] ,int size)
{
for(int i = size-1;i > 0; --i ) {
//每次要將未排序部分的最大值移動(dòng)到下標(biāo)i的位置
for(int j = 0; j < i; ++j) //依次比較相鄰的兩個(gè)元素
if( a[j] > a[j+1]) {
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
簡單排序的效率
- 上面3種簡單排序算法殴玛，都要做 n^2量級(jí)次數(shù)的比較(n是元素個(gè)數(shù)）！
- 好的排序算法添祸，如快速排序滚粟，歸并排序等,只需要做n*log2(n)量級(jí)次數(shù)的比
較!
