计算机程序设计基础课程教学PPTFOP08.ppt

乔 林,计算机程序设计基础,Email: Tel: 62780973,清华大学计算机科学与技术系,第八章 数组与字符串,学习目标 理解数据类型及数据在内存中是如何存储的 了解数组的意义及数组的使用方法 了解字符串的意义及字符串的使用方法,8.1 数据类型与数据结构,数据与数据结构的关系 数据结构指数据的组织形式，即数据的抽象机制 数据的逻辑结构：元素间的逻辑关系 线性数据结构与非线性数据结构 数据的物理结构：物理实现方法，与机器有关 顺序方式、链接方式、索引方式、散列方式 数据结构上的操作：检索、插入、删除、排序等 同质复合数据类型：数据元素具有同样相同的性质,8.2 数 组,数组的下标 下标从 0 开始，一般使用半开半闭区间 例：for( i = 0; i n; +i ) ai = i; 数组的内部表示 按维顺序存放 数组的基地址，元素的地址 数组下标越界问题 程序不检查下标越界，为什么？,数组应用示例一,通过键盘输入10个整数，然后逆序打印,#include #define E 10 void Get( int a, int n ); void Reverse( int a, int n ); void Swap( int a, int x, int y ); void Print( int a, int n ); void main() int arrayE; Get( array, E ); Reverse( array, E ); Print( array, E ); ,数组应用示例一,void Get( int a, int n ) int i; for( i = 0; i n; i+ ) scanf( “%dn“, ,数组作为函数参数,传递数组时需要传递元素个数信息。为什么？ 传递的其实是数组基地址，不提供元素个数信息就无法确知元素有多少个,数组作为函数参数,不恰当的数组传递方法 数组参数声明错误 例：void Reverse( int an ); 不能在参数列表中使用变量声明数组 数组参数声明不恰当 例：void Reverse( int a10 ); 魔数10：在分析函数声明时，编译器忽略之，只对函数内部代码有意义 函数只能操作10个元素的整数数组,数组作为函数参数,多维数组的传递方法：指定数组元素个数 正确：void DisplayBoard( char board1919 ); 正确：void DisplayBoard( char board19, int n ); 错误：void DisplayBoard( char board, int m, int n );,数组应用示例二,素数查找的埃拉托色尼筛法 在公元前三世纪，希腊天文学家Eratosthenes 发明了一种算法，用来找出某一范围内的全部素数 算法过程：首先列写从 2 到 n 的整数，假设 n = 20,将第一个数圈起，表明已发现了一个素数，并将数列中所有该素数的倍数打上，因为它们一定不是素数,重复上述步骤，直到所有整数或者被圈起或者打上叉,数组应用示例二,#include #define Max 1000 typedef enum FALSE, TRUE bool; bool IsPrimeMax; void Init(); void GetPrime(); void Output(); void main() Init(); GetPrime(); Output(); ,数组应用示例二,void Init() int i; for( i = 0; i Max; i+ ) IsPrimei = TRUE; void GetPrime() int tmp; int i; for( i = 2; i Max; i+ ) if( IsPrimei ) tmp = i + i; while( tmp Max ) IsPrimetmp = FALSE; tmp += i; ,数组应用示例二,void Output() int i; int count = 0; for( i = 2; i Max; i+ ) if( IsPrimei ) count+; printf( “Prime %d:%4dt“, count, i ); if( count % 5 = 0 ) printf( “n“ ); printf( “nTotal :%4dn“, count ); ,学生成绩查询系统，假设有五名学生七门考试，要求程序完成如下功能 根据输入的学号，给出每次考试成绩及平均成绩 根据输入的考试号，打印出该次考试中每个学生的成绩，并给出平均成绩 根据学号查出学生某次考试成绩 录入考试成绩,数组应用示例三,#include void main() int select; int i, j; int score68; int average = 0; int sum = 0; do printf( “本程序有4项功能n“ ); printf( “1.根据学号查询学生成绩n“ ); printf( “2.根据考试号统计学生成绩n“ ); printf( “3.根据考试号和学号查询学生成绩n“ ); printf( “4.成绩录入n“ ); printf( “0.退出n“ ); printf( “请输入04进行选择：n“ ); scanf( “%dn“, ,数组应用示例三,switch( select ) case 0: printf( “Okn“ ); exit( 0 ); break; case 1: printf( “输入学号：” ); scanf( “%dn“, ,数组应用示例三,case 2: printf( “输入考试号：”); scanf( “%dn“, ,数组应用示例三,case 4: printf( “输入成绩：n“ ); for( i = 1; i 6; i+ ) for( j = 1; j 8; j+ ) scanf( “%dn“, ,本程序的设计有什么问题？,字符串,数组型字符串 for( i = 0; i n; +i ) stri = ( char )( a + i ); 指针型字符串 for( p = str; *p != 0; +p ) *q = *p; 作为抽象数据的字符串 typedef char* string;,字符串应用示例一,编写函数 FindFirstVowel()，找出字符串中第一个元音字母,int FindFirstVowel( char str, int n ) int i; for( i = 0; i n; i+ ) if( IsVowel( stri ) ) return i; return 1; int IsVowel( char ch ) if( !isalpha( ch ) ) return 0; ch = toupper( ch ); if(ch=A|ch=E|ch=I|ch=O|ch=U) return 1; return 0; ,使用字符数组,字符串应用示例一,编写函数 FindFirstVowel()，找出字符串中第一个元音字母,int FindFirstVowel( char str ) int i; for( i = 0; stri != 0; i+ ) if( IsVowel( stri ) ) return i; return 1; ,使用字符数组,字符串应用示例一,编写函数 FindFirstVowel()，找出字符串中第一个元音字母,int FindFirstVowel( char* str ) char* p; for( p = str; *p != 0; p+ ) if( IsVowel( *p ) ) return (p str); return 1; ,使用字符指针,字符串应用示例一,编写函数 FindFirstVowel()，找出字符串中第一个元音字母,int FindFirstVowel( string str ) int i; for( i = 0; i strlen(str); i+ ) if( IsVowel( IthChar(str, i) ) return i; return 1; char IthChar( string str, int i ) return stri; ,使用抽象字符串,字符串变量,数组型字符串：使用前已经分配空间 例：char str9 = “Tsinghua”;,指针型字符串：使用前未分配空间 例：char* p; p = str;,字符串应用示例二,编写程序，将英语人名从姓在后的形式转换为姓在前的形式，如“First Middle Last”转换为“Last, First Middle”,#include #include #define MaxName 40 static void InvertName( char result, char name );,字符串应用示例二,void main() char standardNameMaxName+1; char invertedNameMaxName+1; printf(“This program converts a name in standard ordern“); printf(“into inverted order with the last name first.n“); printf(“Indicate the end of input with a blank line.n“); while(1) printf(“Name: “); gets( standardName ); if( strlen(standardName) = 0 ) break; InvertName( invertedName, standardName ); printf(“%sn“, invertedName ); ,字符串应用示例二,static void InvertName( char result, char name ) int len; char *p; len = strlen( name ); p = strrchr( name, ); if( p != 0 ) len+; if(len MaxName) printf(“Name too longn“); exit(1); if( p = 0 ) strcpy( result, name ); else strcpy( result, p + 1 ); strcat( result, “, “ ); strncat( result, name, p name ); resultlen = 0; ,字符串应用示例三,使用字符串处理函数编写游戏 hangman 在游戏中，电脑随机从某个范围内选择一个单词，然后输出一列短横，每个短横代表一个字母 使用者猜测该单词，如果猜到了单词中的字母，就会显示出该字母所在的位置，而其他字母仍用短横表示 如果所猜的字母不在单词中，就是一次不成功的猜测 重复上述步骤，直到猜出整个单词，或者累计 8 次不成功猜测,字符串应用示例三,#include #include #include #include #include void begin() / tell user how to play the game printf( “Lets play hangman! I will pick a secret word.n“ ); printf( “On each turn, you guess a letter.n“ ); printf( “If the letter is in the secret word, I will show you where it appears.n“ ); printf( “If you make an incorrect guess, part of n“ ); printf( “your body gets strung up on the scaffold.n“ ); printf( “The object is to guess it before hanged.nn“ ); return; ,字符串应用示例三,void run( char* letters, int m ) / the main part of the game /* guess marks if a guess is correct, k marks if the word is guessed correctly */ int i, j, k, l, p, q, z, guess, times = 8; int abc26; /* 26 marks to memorize if the letter guessed */ int condition20; /* 20 marks to memorize if the letter in the secret word guessed */ char cc, tmp; /* mark that none of the letters has been guessed */ for( j = 0; j m; j+ ) conditionj = 1; for( j = 0; j 26; j+ ) abcj = 0; k = 0; /* The word has not been guessed */,字符串应用示例三,/ check that the game has not ended while( ( k = 0 ) ,字符串应用示例三,printf( “Your guess:“ ); guess = 0; tmp = getchar(); if( tmp != n ) cc = tmp; /* read other letters so that they dont affect the guess */ for( q = 0; getchar() != n; q+); for( p = 0; p m; p+ ) if( lettersp = cc ) guess = 1; conditionp = 1; if( abccc97 = 1 ) / chech if the letter has been guessed guess = 2; printf(“The letter has been guessed, choose anothern“ ); abccc97 = 1; / mark that the letter has been guessed,字符串应用示例三,if( guess = 0 ) printf( “nThere is no %c in the word.n“, cc ); times; else if( guess = 1 ) printf( “nThat guess is correct.n“ ); / chech if the conditions to end the game has been reached l = 0; while( l m ) if( conditionl = 1) k = 0; break; k = 1; l+; / while( ( k = 0 ) & ( times != 0 ) ),字符串应用示例三,if( times