结构与链表ppt课件

华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012 构造由数目固定的成员构成构造由数目固定的成员构成 各成员可以具有不同的数据类型各成员可以具有不同的数据类型 一个构造变量在内存占有一片延续的存储空间一个构造变量在内存占有一片延续的存储空间5.3 5.3 构造构造华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012构造类型定义方式为：构造类型定义方式为：struct 标识符标识符 类型类型 成员成员1 ; 类型类型 成员成员2 ; 类型类型 成员成员n ; ; w 5.3.1 5.3.1 定义构造定义构造例：例：struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 20 ; ;类型名类型名华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造例：例：struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 20 ; ; 可以用不同方法定义一个构造变量可以用不同方法定义一个构造变量(1) 声明类型之后声明变量声明类型之后声明变量employee worker1, worker2, *Emp ;华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造例：例：struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 20 ; ; 可以用不同方法定义一个构造变量可以用不同方法定义一个构造变量(1) 声明类型之后声明变量声明类型之后声明变量worker1, worker2, *Emp ;(2) 声明类型的同时声明变量声明类型的同时声明变量华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造例：例：struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 20 ; ; 可以用不同方法定义一个构造变量可以用不同方法定义一个构造变量(1) 声明类型之后声明变量声明类型之后声明变量worker1, worker2, *Emp ;(2) 声明类型的同时声明变量声明类型的同时声明变量(3) 直接声明构造类型变量直接声明构造类型变量留意留意此时没有了构造类型标识符此时没有了构造类型标识符华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造例：例：struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 20 ; ;employee worker1, worker2, *Emp = &worker1 ; 阐明阐明(1) 构造变量占有一片延续内存构造变量占有一片延续内存 空间，具有构造类型的特征空间，具有构造类型的特征Wang Li9910834561200.5guang zhou87111111worker1Emp华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造 阐明阐明(2) 一个构造类型的成员一个构造类型的成员 可以是另一个已定义的构造类型可以是另一个已定义的构造类型struct date int month ; int day ; int year ; ;struct employee char name 10 ; date birthday ; long code ; double salary ; char address 50 ; char phone 11 ; worker1, worker2 ;例如例如: 为职工构造添加出生日期信息为职工构造添加出生日期信息 类型和变量声明为类型和变量声明为:华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造 阐明阐明(2) 一个构造类型的成员一个构造类型的成员 可以是另一个已定义的构造类型可以是另一个已定义的构造类型struct person char name 10 ; long code ; double salary ; char address 50 ; char phone 11 ; worker1, worker2 ;错误错误不能实现的无穷递归构造不能实现的无穷递归构造华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012w 5.3.1 5.3.1 定义构造定义构造 阐明阐明(3) 声明构造类型变量可以同时初始化声明构造类型变量可以同时初始化struct employee char name 10 ; long code ; double salary ; char address 50 ; char phone 11 ; worker = Wang Li , 991083456, 1200.5, guang zhou , 87111111 ;华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220121访问构造变量的成员访问构造变量的成员构造变量构造变量 . 成员成员点运算符点运算符/例例5-7# include using namespace std ;struct weather/ 声明构造类型声明构造类型 double temp; double wind; ;int main ( ) weather today ;/ 声明构造类型变量声明构造类型变量 today . temp = 10.5 ;/ 对构造变量成员赋值对构造变量成员赋值 today . wind = 3.1 ; cout “Temp = today . temp endl ; / 按按成员输出成员输出 cout “Wind = today . wind 成员成员 (*构造指针构造指针 ) . 成员成员/例例5-8# include using namespace std ;# include struct person char name20 ; unsigned long id; double salary; ;int main ( ) person pr1 ; person * pp ;/ 定义构造指针定义构造指针 pp = & pr1 ;/ 取构造变量地址取构造变量地址 strcpy ( pp - name , “David Marat ) ;/ 对构呵斥对构呵斥员赋值员赋值 pp - id = 987654321 ; pp - salary = 335.0 ; cout name t id t salary 成员成员 (*构造指针构造指针 ) . 成员成员/例例5-8# include using namespace std ;# include struct person char name20 ; unsigned long id; double salary; ;int main ( ) person pr1 ; person * pp ;/ 定义构造指针定义构造指针 pp = & pr1 ;/ 取构造变量地址取构造变量地址 strcpy ( pp - name , “David Marat ) ;/ 对构呵斥对构呵斥员赋值员赋值 pp - id = 987654321 ; pp - salary = 335.0 ; cout name t id t salary endl ;5.1.2 访问构造5.3.2 5.3.2 访问构造访问构造华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012/例例5-9# include using namespace std ;struct weather double temp; double wind; yesterday ;int main ( ) weather today ; yesterday . temp = 10.5 ; yesterday . wind = 3.1 ; today = yesterday ; / 构造变量整体赋构造变量整体赋值值 cout “Temp = today . temp endl ; cout “Wind = today . wind endl ;3类型一样的构造变量可以整体赋值类型一样的构造变量可以整体赋值5.1.2 访问构造5.3.2 5.3.2 访问构造访问构造华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220123类型一样的构造变量可以整体赋值类型一样的构造变量可以整体赋值例如：例如：struct weather1 double temp; double wind; yesterday ;struct weather2 double temp; double wind; today ;“类型一样的变量类型一样的变量 是指用同一类型标识符阐明的变量是指用同一类型标识符阐明的变量yesterday 和和 today虽然成员一样，但不是同类型变量虽然成员一样，但不是同类型变量不可以整体赋值不可以整体赋值5.1.2 访问构造5.3.2 5.3.2 访问构造访问构造华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220125.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012例如例如struct S_type int a; double x; ;S_type S_ary10;S_ary是一个有是一个有10个元素的数组，元素类型是个元素的数组，元素类型是S_type。数组的每一个元素包含两个数据成员。数组的每一个元素包含两个数据成员。S_ary0.a S_ary0.xS_ary1.a S_ary1.xS_ary9.a S_ary9.x5.2 构造数组5.4 5.4 构造数组构造数组 数组的元素类型为构造类型时，称为构造数组。数组的元素类型为构造类型时，称为构造数组。华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ;/ 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ;/ 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序struct person/ 构造定义构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明构造数组声明5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ; / 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序int main ( ) int i ; person temp ;/ 构造变量声明构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;接受空格输入接受空格输入5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ; / 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序cout “Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员以成员salary作关键字排序作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; 冒泡排序冒泡排序5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ; / 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序for ( i = 0 ; i 6 ; i + )/ 输出排序后数据输出排序后数据 coutallonei.nametallonei.idtallonei.salaryendl ;5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012# include using namespace std ;struct person/ 构造定义 char name10 ; unsigned int id; double salary ; ;person allone6 ;/ 构造数组声明int main ( ) int i ; person temp ; / 构造变量声明 for ( i = 0 ; i 6 ; i + )/ 输入数据 cout i : name: ; cgets ( allonei.name ) ; cout allonei.id ; cout allonei.salary ; cout endl ; ;cout Sort:n ; for ( i=1 ; i 6 ; i + )/ 以成员salary作关键字排序 for ( int j = 0 ; j allonej+1.salary ) / 构造变量的整体交换 temp = allonej ; allonej = allonej+1 ; allonej+1 = temp ; for ( i = 0 ; i 6 ; i + )/ 输出排序后数据 cout allonei.name t allonei.id t allonei.salary endl ;例例5-10 对构造数组以某一成员作关键字排序对构造数组以某一成员作关键字排序5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012问题：问题： 构造变量的整体交换降低了排序效率构造变量的整体交换降低了排序效率处理：处理： 运用索引机制运用索引机制, 建立构造指针数组建立构造指针数组方法方法 :1. 建立索引数组建立索引数组2. 以关键字作根据进展数据比较，挪动索引以关键字作根据进展数据比较，挪动索引3. 经过索引访问数据经过索引访问数据5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0pa 0 &allone0 1 &allone1 2 &allone2 3 &allone3 4 &allone4 5 &allone51. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 &allone1 2 &allone2 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 &allone1 2 &allone2 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 &allone1 2 &allone2 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 &allone1 2 &allone2 3 &allone3 4 &allone4 5 &allone5pa 1 pa 2 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 2 3 &allone3 4 &allone4 5 &allone5pa 1 pa 2 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0&allone2&allone15.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 0 &allone0 1 &allone2 2 &allone1 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone3 4 &allone4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone3 4 &allone4 5 &allone5pa 3 pa 4 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 4 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0&allone4&allone35.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法pa 3 pa 4 华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone4 4 &allone3 5 &allone5allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone4 4 &allone3 5 &allone5pa 4 pa 5 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone4 4 5 pa 4 pa 5 &allone5&allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone4 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone0 1 &allone2 2 &allone1 3 &allone4 4 &allone5 5 &allone3pa 0 pa 2 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 1 2 &allone1 3 &allone4 4 &allone5 5 &allone3pa 0 pa 2 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0&allone2&allone05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone1 3 &allone4 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone1 3 &allone4 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone1 3 &allone4 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone1 3 &allone4 4 &allone5 5 &allone3pa 2 pa 3 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 3 4 &allone5 5 &allone3pa 2 pa 3 allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0&allone4&allone15.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone4 3 &allone1 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序pa 0 &allone2 1 &allone0 2 &allone4 3 &allone1 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序排序结果：排序结果：pa 0 &allone2 1 &allone0 2 &allone4 3 &allone1 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.05.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序排序结果：排序结果：pa 0 &allone2 1 &allone0 2 &allone4 3 &allone1 4 &allone5 5 &allone3allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.03. 输出输出for ( k = 0; k6; k+) coutnameidsalary; 5.2 构造数组1. 建立索引数组建立索引数组2. 排序冒泡法排序冒泡法华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012： person * pa6 = &allone0 , &allone1 , &allone2 , &allone3 , &allone4 , &allone5 ; person * temp; ：for ( i = 1 ; i 6 ; i + + ) for ( int j = 0 ; j salary pa j+1 - salary ) temp = pa j ; pa j = pa j+1 ; pa j+1 = temp ; 5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012运用索引排序运用索引排序allone name id salary 0 Jone 12345 339.0 1 David 16 449.0 2 Marit 27519 311.0 3 Jasen 42876 623.0 4 Peter 23987 400.0 5 Yoke 12335 511.0pa 0 0 1 1 2 2 3 3 4 4 5 5假设索引数组阐明为：假设索引数组阐明为：int pa 6 = 0, 1, 2, 3, 4 , 5 ;想一想想一想程序该如何修正？程序该如何修正？ 请他试一试请他试一试5.2 构造数组华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012 程序对数据的表示，不但要求存放根本信息，程序对数据的表示，不但要求存放根本信息，还要表示与其它数据元素的关系还要表示与其它数据元素的关系 线性表是最简单的数据组织方式线性表是最简单的数据组织方式5.3 链表5.5 5.5 链表链表华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220125.3 链表5.5 5.5 链表链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head结点结点华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220125.3 链表5.5 5.5 链表链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head数据元素信息数据元素信息华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220125.3 链表5.5 5.5 链表链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head元素关系元素关系华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 201220125.3 链表5.5 5.5 链表链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head结点数据类型结点数据类型struct node char name20 ; double salary ; node * next ; ; 单向链表结点数据类型单向链表结点数据类型struct node dataType data ; node * next ; ; 华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012建立链表的过程：建立链表的过程：生成头结点；生成头结点；while未终了未终了 生成新结点；生成新结点； 把新结点插入链表；把新结点插入链表；struct node int data ; node * next ; ; node * head ; node * CreateList() node * s, * p ; s = new node ; cin s-data ; head = NULL ; while ( s-data != 0 ) if ( head = NULL ) head = s ; else p-next = s ; p = s ; s = new node ; cin s-data ; p - next = NULL ; delete s ; return ( head ) ;5.3 链表华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012建立链表的过程：建立链表的过程：生成头结点；生成头结点；while未终了未终了 生成新结点；生成新结点； 把新结点插入链表；把新结点插入链表；struct node int data ; node * next ; ; node * head ; node * CreateList() node * s, * p ; s = new node ; cin s-data ; head = NULL ; while ( s-data != 0 ) if ( head = NULL ) head = s ; else p-next = s ; p = s ; s = new node ; cin s-data ; p - next = NULL ; delete s ; return ( head ) ;构造类型构造类型5.3 链表华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012建立链表的过程：建立链表的过程：生成头结点；生成头结点；while未终了未终了 生成新结点；生成新结点； 把新结点插入链表；把新结点插入链表；struct node int data ; node * next ; ; node * head ; node * CreateList() node * s, * p ; s = new node ; cin s-data ; head = NULL ; while ( s-data != 0 ) if ( head = NULL ) head = s ; else p-next = s ; p = s ; s = new node ; cin s-data ; p - next = NULL ; delete s ; return ( head ) ;头指针头指针5.3 链表华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012建立链表的过程：建立链表的过程：生成头结点；生成头结点；while未终了未终了 生成新结点；生成新结点； 把新结点插入链表；把新结点插入链表；struct node int data ; node * next ; ; node * head ; node * CreateList() node * s, * p ; s = new node ; cin s-data ; head = NULL ; while ( s-data != 0 ) if ( head = NULL ) head = s ; else p-next = s ; p = s ; s = new node ; cin s-data ; p - next = NULL ; delete s ; return ( head ) ;建立链表函数建立链表函数前往头指针前往头指针5.3 链表华南理工大学计算机学院华南理工大学计算机学院 周霭如周霭如 20122012建立链表的过程：建立链表的过程：生成头结点；生成头结点；while未终了未终了 生成新结点；生成新结点； 把新结点插入链表；把新结点插入链表；struct node int data ; node * next ; ; node * head ; node * CreateList() node * s, * p ; s = new no