第6章 数据的组织结构课件

第6章数据的组织结构第6章数据的组织结构（二）6.3文件

6.2指针类型

6.1结构体类型

6.4联合体与枚举类型

第6章数据的组织结构6.1结构体类型

结构体类型的概念

结构体是一种可以将若干个不同数据类型的变量组合在一起的复合型数据类型。人们常常借助于它将表达同一对象的不同属性封装在一起，使之达到逻辑概念与程序变量一一对应的目的，从而提高程序的清晰度，降低程序的复杂度，改善程序的可维护性。第6章数据的组织结构结构体类型的声明

类型声明的语法格式为：struct<结构体类型名>{<数据类型><成员1>；<数据类型><成员2>；

......<数据类型n><成员n>；};第6章数据的组织结构例如：structpoint_type{intx;/*x坐标*/inty;/*y坐标*/};这个结构体类型表示：point_type类型的变量将包含两个成员x、y，它们分别用于存储坐标点的两个坐标值。可以利用point_type类型声明下面这个结构体类型：structrectangle_type{structpoint_typelefttop;/*左上角的坐标*/structpoint_typerightbottom;/*右下角的坐标*/};第6章数据的组织结构

在C语言中，允许用户为已经存在的数据类型起一个别名，其说明格式为：

typedef原数据类型新数据类型名；

typedefstructpoint_type{intx;inty;}POINT;

在这里，POINT与structpoint_type完全等价第6章数据的组织结构结构体变量的定义：利用结构体类型名定义变量的格式为：<结构体类型名><变量名>[，<变量名>[，<变量名>...]]；例如：POINTp1,p2;等价于structpoint_typep1,p2;与其他数据类型的变量一样，一旦定义了变量之后，系统就会为这个变量分配相应的存储空间。对于结构体型变量而言，系统为之分配的存储单元数量取决于结构体所包含的成员数量以及每个成员所属的数据类型。例如，上面定义的结构体型变量p1包含两个int类型的成员。第6章数据的组织结构结构体变量的初始化struct<结构体类型名><变量名>={<成员值列表>}；例：structpoint_typep={10,20};structdate_typed={2005,5,20};structrectangle_typerect={{10,10},{100,100}};结构体变量的引用

<结构体变量名>.<成员名>第6章数据的组织结构结构体型变量的基本操作结构体型变量的输入

scanf(“%d%d%”,&d.year,&d.month,&d.day);结构体型变量的输出

printf(“%d%d%d”,d.year,d.month,d.day);结构体型变量的赋值d.year=2005;d.month=5;d.day=20;如果一个结构体型变量已经被赋值，并且希望将它的值赋给另外一个类型完全相同的结构体型变量，则可以采用整体赋值的方式。第6章数据的组织结构学生基本信息的组织方式学生基本信息的组织和管理是一个十分有代表性的结构体应用实例。为了简化程序的复杂度，减少程序的书写量，在这里，假设学生的基本信息只包括：学号、姓名、出生日期、所属院系、所学专业。

第6章数据的组织结构例1：通过键盘输入30名学生的基本信息，并显示输出。然后，再通过键盘输入一个月份和日期，查找并输出本年度在这个给定日期之后过生日的学生信息。第6章数据的组织结构问题分析为了表示一名学生的基本信息，应该声明一个包括学号、姓名、出生日期、所属院系、所学专业的结构体类型。“出生日期”需要用三个数据项才能够表示完整，而“日期”是一个独立的概念，也应该为之声明一个结构体类型。组织30名学生的信息。30名学生的基本信息属于同一个性质的数据，因此，应该利用一维数组将它们组织在一起。第6章数据的组织结构算法描述

第6章数据的组织结构#include<stdio.h>#defineNUM30typedefstruct{ /*日期结构*/intyear;intmonth;intday;}DATE;typedefstruct{ /*学生信息结构*/intnum;charname[24];DATEbirthday;chardepartment[48];charmajor[32];}STUDENTIFNO;voidinputInfo(STUDENTIFNO[]);voidoutputInfo(STUDENTIFNO[]);voidsearchInfo(STUDENTIFNO[],DATE);程序代码第6章数据的组织结构main(){STUDENTIFNOs[NUM];DATEdate;inputInfo(s);outputInfo(s);printf("\nEnteradate(month,day)");scanf("%d%d",&date.month,&date.day);searchInfo(s,date);}voidinputInfo(STUDENTIFNOs[]){inti;

printf("\nEnter%dstudent'sinfmation(name,birthday,department,major)\n",NUM);for(i=0;i<NUM;i++){ s[i].num=i+1; scanf("%s",s[i].name);

scanf("%d%d%d",&s[i].birthday.year,&s[i].birthday.month,&s[i].birthday.day); scanf("%s",s[i].department); scanf("%s",s[i].major);}}第6章数据的组织结构/*输出全部学生的信息*/voidoutputInfo(STUDENTIFNOs[]){inti;printf("\nNumNameDirthdayDepartmentMajor\n");for(i=0;i<NUM;i++){ printf("\n%4d%14s%4d/%2d/%2d%16s%16s",s[i].num,s[i].name, s[i].birthday.year,s[i].birthday.month,s[i].birthday.day, s[i].department,s[i].major);}}第6章数据的组织结构voidsearchInfo(STUDENTIFNOs[],DATEdate){inti;for(i=0;i<NUM;i++){if(s[i].birthday.month>date.month){printf("\n%4d%16s%2d//%2d",s[i].num, s[i].name,s[i].birthday.month,s[i].birthday.day);continue;}if(s[i].birthday.month==date.month&&s[i].birthday.day>date.day){printf("\n%4d%16s%2d//%2d",s[i].num, s[i].name,s[i].birthday.month,s[i].birthday.day);}}}第6章数据的组织结构例2：假设通过键盘输入一个含有10个整数的数列。请编写一个程序，将10个整数按照从小到大的顺序重新排列，要求输出排序后的结果以及每个整数在排序前的位置。结构体类型应用实例

第6章数据的组织结构问题分析排序是一种基本且应用广泛的操作。在前面的实例中，我们已经看到过排序操作的实现方法。然而，这个题目不仅要求输出排序之后的结果，还要求输出每个数据在排序前的位置。解决这个问题的一种方法是：将原始位置作为每个数据的属性保留起来，并借助于结构类型DATATYPE将每个数值data及位置pos绑定在一起，形成描述每个数据的整体信息。如果在排序过程中，需要交换两个数据的位置，可以将两个数据对应的结构型变量整体相互交换，以便实现每个数据的原始位置信息永远跟随数值一同移动的目的。在这个程序中，定义了三个函数inputValue()、outputValue()和selectSort()，分别用于完成输入、输出和查找的操作。第6章数据的组织结构#include<stdio.h>#defineNUM10 /*数列中包含的数值个数*/typedefstruct{intdata; /*整型数值*/intpos; /*原始位置*/}DATATYPE;voidinputValue(DATATYPE[]);voidoutputValue(DATATYPE[]);voidselectSort(DATATYPE[],int);main(){DATATYPEvalue[NUM];inputValue(value);selectSort(value,NUM);outputValue(value);}程序代码

第6章数据的组织结构/*通过键盘输入10个整型数值*/voidinputValue(DATATYPEvalue[]){inti;printf("\nEnter%dvalues:",NUM);for(i=0;i<NUM;i++){scanf("%d",&value[i].data);value[i].pos=i+1; /*每个数值的原始位置*/}}/*输出结果*/voidoutputValue(DATATYPEvalue[]){inti;for(i=0;i<NUM;i++) /*输出数据及其原始位置*/printf("\n%3d:(%4d:%2d)",i+1,value[i].data,value[i].pos);}第6章数据的组织结构/*选择排序（n项）*/voidselectSort(DATATYPEvalue[],intn){inti,max=0;DATATYPEtemp;if(n<2)return;for(i=1;i<n;i++) /*求最大项的下标*/if(value[max].data<value[i].data) /*按照数据大小计算*/max=i;if(max!=n-1){/*整体交换两个结构型变量*/ temp=value[n-1]; value[n-1]=value[max]; value[max]=temp; /*将最大项移到最后*/}selectSort(value,n-1); /*将前n-1项按照同样方法排序*/}第6章数据的组织结构例3：编写一个程序，模拟发扑克牌的过程。问题分析1、每张扑克牌有两个属性：一个是花色；一个是面值，因此，可以定义一个用于描述一张扑克牌的结构类型。

typedefstruct{intrank; /*面值*/intsuit; /*花色*/}CARD;其中，rank表示扑克牌的面值，它应该是1~13之间的整数；suit表示扑克牌的花色，它应该是1~5之间的整数，用1~4表示花色，用5表示大小王。第6章数据的组织结构为了增加程序的可读性，可以声明下面这样一组宏定义：#defineKing5 /*王*/#defineSpade4 /*黑桃*/#defineHearts3 /*红桃*/#defineDiamonds2 /*方块*/#defineClub1 /*梅花*/2、一副扑克牌有54张扑克，它们属于相同的性质，因此可以采用一维数组类型将54张牌的信息组织起来。第6章数据的组织结构算法描述

第6章数据的组织结构#include<stdio.h>#include<stdlib.h>#defineKing5 /*王*/#defineSpade4 /*黑桃*/#defineHearts3 /*红桃*/#defineDiamonds2 /*方块*/#defineClub1 /*梅花*/#defineNUM54typedefstruct{intrank; /*面值*/intsuit; /*花色*/}CARD;voidcreate(CARDcard[]); /*构造扑克牌*/voidriffle(CARDcard[]); /*洗牌*/voiddeal(CARDcard[]); /*发牌*/main(){CARDcard[NUM];create(card);riffle(card);deal(card);}程序代码

第6章数据的组织结构voidcreate(CARDcard[])/*构造扑克牌*/{inti;for(i=0;i<NUM;i++){card[i].rank=i%13+1; /*产生扑克牌的面值*/card[i].suit=i/13+1; /*产生扑克牌的花色*/}}voidriffle(CARDcard[])/*洗牌*/{inti,rand1,rand2;CARDtemp;for(i=0;i<1000;i++){ /*重复1000次*/rand1=random(NUM); /*产生两个随机数*/rand2=random(NUM);if(rand1!=rand2){ /*交换两个位置的扑克牌信息*/ temp=card[rand1]; card[rand1]=card[rand2]; card[rand2]=temp;}}}第6章数据的组织结构/*发牌*/voiddeal(CARDcard[]){inti,count;for(i=0;i<4;i++){ /*循环4次*/printf("\n\n%drdman:\n",i+1);for(count=0;count<NUM;count+=4){ /*显示花色*/ switch(card[count+i].suit){ caseKing: printf("(King,"); break; caseSpade: printf("(Spade,"); break; caseHearts: printf("(Herats,"); break; caseDiamonds:printf("(Diamonds,"); break; caseClub: printf("(Club,"); break; }/*显示面值见下页*/}}}

第6章数据的组织结构

switch(card[count+i].rank){ /*显示面值*/ case1:if(card[count+i].suit==King) printf("Big_King)"); else printf("A)"); break; case2:if(card[count+i].suit==King) printf("Small_King)"); else printf("2)"); break; case3:case4: case5:case6: case7:case8: case9: case10:printf("%d)",card[count+i].rank); break; case11:printf("J)"); break; case12:printf("Q)"); break; case13:printf("K)"); break; }

第6章数据的组织结构6.2指针类型指针类型

指针类型是C语言提供的一种特殊的基本数据类型。指针类型变量中存放的不是待操作的数据，而是那些待操作数据的存储地址。

地址是用来表示数据在内存中存放位置的一种标识C语言提供了一种获取变量地址的途径。“&”被称为取地址运算符，它是一个一元运算符，其使用格式为：&变量名。

第6章数据的组织结构指针型变量的定义与引用

指针型变量的定义<数据类型>*<指针型变量名>；例如：int*intptr;intptr=&a;指针型变量的引用指针部分的引用格式：<指针型变量>指针所指变量部分的引用格式：*<指针型变量>例如：*intptr=30;例如：scanf(“%d”,intptr);printf(“%d”,*intptr);第6章数据的组织结构指针与指针所指变量的关系

第6章数据的组织结构指针的基本操作

指针的初始化int*ptr1=&value;int*ptr2=NULL;

NULL是一个特殊的值，它表示目前指针没有指向任何变量，通常将这种状态称为“空”指针。指针的赋值ptr2=ptr1

可以将一个指针赋给另一个基类型相同的指针，其含义是两个指针在同一时刻指向同一个变量。第6章数据的组织结构指针的比较用来判断两个指针在同一时刻是否指向同一个变量，或者判断某个指针是否为“空”。例如if(ptr1==NULL)return;指针的加减在利用指针访问数组元素的时候，应用这种操作移动指针十分便捷。

第6章数据的组织结构指针与一维数组的关系数组名是一个含有数组第1个元素地址的常量指针。a[i]等价于*(a+i)。

数组名本身并不占有内存空间，它是一个指针常量，一旦定义，不允许被更改；而指针却是一个独立的变量，在TurboC环境下占用2个字节的存储单元，它的内容可以被随时地更改。例如：int*ptr,iarray[10]；

ptr=iarray；这样一来，*(ptr+1)就等价于iarray[1]第6章数据的组织结构利用指针对数组元素进行操作假设有定义：intiarray[20],*ptr;ptr=iarray将数组iarray的内容显示输出方法1、for(ptr=iarray,i=0;i<20;i++)

printf(“%d“,*(ptr+i));方法2、for(ptr=iarray;ptr<iarray+20;ptr++)

printf(“%d“,*ptr);第6章数据的组织结构例4：从键盘输入一个文本行，统计其中包含的空格和非空格字符的数量。问题分析在一个文本行中，所包含的字符由空格和非空格两部分组成。统计空格和非空格字符的数量需要对整个文本行从前向后扫描一遍。从前面的例子我们早已得知，文本行可以采用字符型数组表示。在这里，我们采用指针法引用字符型数组中的每个元素，然后对其进行判断和统计处理。第6章数据的组织结构算法描述第6章数据的组织结构#include<stdio.h>#defineNUM80/*文本行包含的最多字符数目*/main(){chartextline[NUM]; /*存放文本行内容的字符型数组*/char*s; /*作为索引的指针变量*/intcharnum,spacenum; /*字符个数和空格个数*/printf("\nEnterastring:"); /*输入文本行内容*/gets(textline);charnum=0; /*统计空格和非空格字符的数量*/spacenum=0;for(s=textline;*s!='\0';s++){ /*检查字符串结尾*/if(*s=='') spacenum++;else charnum++;}

printf("\n%dcharactersand%dspacesinthestring.",charnum,spacenum);}程序代码第6章数据的组织结构指针与二维数组的关系

假设有下列定义：#defineROWNUM5#defineCOLNUM4inta[ROWNUM][COLNUM];int*ptr1;int(*ptr2)[ROWNUM];输出二维数组的每个元素内容第6章数据的组织结构方法一：ptr1=a[0];for(i=0;i<ROWNUM;i++){for(j=0;j<COLNUM;j++)printf("%3d",*(ptr1+i*COLNUM+j));printf("\n");}方法二：ptr2=a;for(i=0;i<ROWNUM;i++){for(j=0;j<COLNUM;j++)printf("%3d",*(*(ptr2+i)+j));printf("\n");}第6章数据的组织结构例5：构造一个如下所示的下三角方阵。

1000000

1200000

1230000

1234000

1234500

1234560

1234567

第6章数据的组织结构问题分析位于下三角部分的元素内容等于列下标加1，上三角部分的元素内容全部为0。位于下三角元素的坐标特点是i>=j；位于上三角元素的坐标特点是i<j。第6章数据的组织结构#include<stdio.h>#defineNUM7main(){inta[NUM][NUM];int*ptr,i,j;/*构造下三角方阵*/for(i=0;i<NUM;i++){ptr=*(a+i);/*ptr指向第i行的第1个元素*/for(j=0;j<NUM;j++)if(i>=j) *(ptr+j)=j+1;/*ptr+j指向ptr所指行的下标为j的元素*/ else *(ptr+j)=0;}/*输出下三角方阵*/for(i=0;i<NUM;i++){ptr=*(a+i);for(j=0;j<NUM;j++)printf("%3d",*(ptr+j));printf("\n");}}程序代码第6章数据的组织结构动态申请存储空间

所谓动态是指在程序运行之后，再根据实际需求申请相应的存储空间，这样既可以满足用户在确定所需的元素数量之后再申请空间，也可以提高存储空间的利用率。

void*malloc(intsize)这个标准函数的功能是：请求系统分配size个字节的连续存储空间。如果分配成功，将返回所分配的存储空间的首地址；否则返回NULL。

例如：ptr=(int*)malloc(sizeof(int)*20);voidfree(void*p)这个标准函数的功能是：释放由指针p指向且由malloc()函数分配的存储空间。例如：free(ptr);第6章数据的组织结构例6：构造10行杨辉三角形。杨辉三角形的数据如下所示：1

11

121

1331

14641

15101051

第6章数据的组织结构问题分析第i行就有i个数值每行的第1个数值和第i个数值都是1，第j（<1<j<i）个数值是上1行第

j-1个和第j个数值之和。考虑到各行数据的个数不同，应为每行数据提供不同数量的存储空间，来保存每行的整数。同时，为了将各行数据组织在一起，需要使用一个数组，保存每行数据的首地址。第6章数据的组织结构算法描述

第6章数据的组织结构#include<stdio.h>#include<stdlib.h>#defineMAXLINE10main(){int*a[MAXLINE];/*存放杨辉三角形的指针型数组*/inti,j;a[0]=(int*)malloc(sizeof(int)); /*构造第1行数值*/*a[0]=1;for(i=1;i<MAXLINE;i++){ /*构造2~10行内容*/a[i]=(int*)malloc(sizeof(int)*(i+1));/*申请i+1个整数的存储空间*/*a[i]=1;for(j=1;j<i;j++) *(a[i]+j)=*(a[i-1]+j-1)+*(a[i-1]+j); /*计算第i+1行的第j+1个数据*/*(a[i]+i)=1;}for(i=0;i<MAXLINE;i++){/*显示杨辉三角形*/for(j=0;j<=i;j++) printf("%4d",*(a[i]+j));printf("\n");}for(i=0;i<MAXLINE;i++)free(a[i]);/*释放所有存储空间*/}程序代码第6章数据的组织结构指针与字符串字符串是一种以字符’\0’作为结束标志的字符数组。表示字符串可以有下面几种方法：charstr1[]=“ThisisaCprogram.”;char*str2=“ThisisaCprogram.”;char*str3=(char*)malloc(sizeof(char)*25);strcpy(str3,str2);str1是一个含有21个元素的字符型数组，前20个元素用来存放字符序列“ThisisaCprogram.”，最后一个元素存放字符串结束符‘\0’；str2是一个指向字符串常量的指针；str3指向一块动态申请且可以放置25个字符的存储空间，调用strcpy()函数的目的是将str2所指向的字符串常量复制到str3指向的存储空间中。第6章数据的组织结构计算字符串的长度

比较两个字符串大小

intstrlen(char*s)

{intlen=0;for(;*s!='\0';s++,len++);returnlen;}

intstrcmp(char*s,char*t){for(;*s==*t;s++,t++)/*对应字符比较，且两个指针同步加1*/if(*s==’\0’)return0;

/*如果比较到’\0’，两个对应字符仍相等，则返回0*/return*s-*t;/*此时*s!=*t，根据对应字符的大小决定比较结果*/}

第6章数据的组织结构

voidstrcpy(char*s,char*t){ while((*s=*t)!=’\0’){s++;t++;}}拷贝字符串。第6章数据的组织结构例7：输入若干个单词（<50个），每个单词占据一行。假设以空行作为结束标志。请将输入的所有单词按照字典序列重新排序，并输出排序后的结果。第6章数据的组织结构问题分析由于输入若干个单词，且需要对它们进行排序，所以必须保存每个单词，并且将它们组织成单词序列。从前面的实例中可以想到：为了提高存储空间的利用率，可以定义一个字符指针型数组char*word[50]；每个数组元素保存一个字符指针，也就是单词首字符的地址，而为每个单词申请的存储单元数量可以通过调用函数strlen()得到。申请到相应的存储空间后，再调用strcpy()函数将刚刚输入的单词拷贝到分配的存储空间中，从而实现将输入的所有单词保留起来的目的。判断单词之间大小的操作需要调用strcmp()函数实现。第6章数据的组织结构#include<stdio.h>#include<stdlib.h>#include<string.h>main(){charbuf[32],*p;char*word[64];intindex,i,j,min;index=0;while(1){/*输入若干个单词*/gets(buf); if(strlen(buf)==0)break;word[index]=(char*)malloc(strlen(buf)+1);strcpy(word[index++],buf);}程序代码第6章数据的组织结构for(i=0;i<index;i++){/*按照字典序列排序*/min=i;for(j=i+1;j<index;j++) if(strcmp(word[j],word[min])<0) min=j;if(min!=i){ p=word[i]; word[i]=word[min]; word[min]=p;}}for(i=0;i<index;i++)/*输出结果*/puts(word[i]);}程序代码第6章数据的组织结构指针型函数参数及函数返回值

指针型参数的特殊用途—函数实现两个数互换

voids*x,int*y){ inttemp;

temp=*x; *x=*y; *y=temp;}

第6章数据的组织结构指针与数组型参数

数组名代表了数组首元素的地址。因此，它可以保存在指针型变量中，也可以传递给指针型的形式参数；而数组型的形式参数和指针型的形式参数是完全等价的。

voidinputValue(intvalue[],intnum){ inti;

printf(“\nEnter%dintegers:”,num); for(i=0;i<num;i++) scanf(“%d”,value+i);}

第6章数据的组织结构命令行参数main函数带参数的形式：

main(intargc,char*argv[])使用这种形式的main函数可以让用户在发出运行程序命令的同时，通过命令行向程序传递若干个参数。参数表中的第一个参数argc负责带入命令行包含的参数个数，第二个参数argv是一个指向字符的指针型数组，它负责带入命令行中的每个参数。利用命令行参数向程序传递信息，可以加大程序的灵活性，扩展程序的使用范围。

第6章数据的组织结构例8：通过键盘输入若干个文本行，输出所有包含给定字符串的文本行。这个给定字符串是通过命令行参数给出的。第6章数据的组织结构问题分析由于需要由命令行参数传入一个字符串，所以命令行应该包含两个参数，一个是将要运行的程序名称，另一个是需要带入的字符串。在main()函数中，首先应该判断命令行中是否包含两个参数，如果不是，输出相应的提示信息，并结束程序的执行。第6章数据的组织结构算法描述

第6章数据的组织结构#include<stdio.h>#include<string.h>#defineMAXLINE80intgetline(char*line);main(intargc,char*argv[]){charline[MAXLINE];if(argc!=2){printf("usage:exatext\n");return;}else{while(getline(line)>0)/*如果读入非空文本行，执行循环体*/if(strstr(line,argv[1])!=NULL)/*查找给定字符串*/ printf("%s\n",line);}}intgetline(char*line)/*读入文本行，并返回文本行包含的字符数量*/{gets(line);returnstrlen(line);}程序代码第6章数据的组织结构指针型函数返回值

返回字符串str中由start开始的len个字符组成的子串。

char*strsub(char*str,intstart,intlen){ inti,num; char*p;if(strlen(str)<start) returnNULL; /*start无效返回NULL*/ if(start+len>strlen(str))num=strlen(str)-start; /*确定子串包含的字符数量*/ elsenum=len; p=(char*)malloc(sizeof(char)*(num+1)); /*申请存储空间*/ for(i=0;i<num;i++)/*构造子串*/ *(p+i)=*(str+start+i); *(p+i)=’\0’; returnp;/*返回子串*/}第6章数据的组织结构指针类型的应用实例——链表链表的相关概念

将一系列结点通过指针连接起来，好像一个链，人们习惯地将这种存储形式称为链表。其中，每个结点有表示数据值部分的数据域（data）；表示后继数据存储地址的指针域（next）。链表结构:head是头指针，它指向链表中的第一个结点。这是链表操作的唯一入口点，所有链表元素的访问必须从这里出发。由于最后一个结点没有后继结点，所以，它的指针域存放一个特殊值NULL。NULL在图中常用（^）符号表示，代表了表尾，也可以代表一个空表。

第6章数据的组织结构链表的基本操作1、计算链表中包含的结点个数

intListLength(NODE*p){intlen=0；

for(;p!=NULL;p=p->next)len++; *扫描并累加结点数量*/returnlen;

}

第6章数据的组织结构2、在链表head中第i个结点之前插入一个新数据e，返回表头指针。将新结点s插入到p之后的方法s->next=p->next;p->next=s;第6章数据的组织结构Node*ListInsert(NODE*head,inti,inte){NODE*p,*s;if(i<1||i>ListLength(head)+1) /*检测i的合理性*/ returnhead;s=(NODE*)malloc(sizeof(NODE));/*构建新结点s*/if(s==NULL) returnhead; /*空间分配失败时*/s->item=e;if(i==1){ s->next=head; /*直接添加在第1结点前*/ returns;}p=head;for(p=head;i>2;p=p->next) /*寻找第i-1个结点，并由p指向*/ i--;s->next=p->next; /*将s结点插入到p之后*/p->next=s;returnhead;}

第6章数据的组织结构3、将链表head中第i个结点删除，返回表头指针从链表中将s结点删除s=p->next;p->next=s->next;free(s);第6章数据的组织结构Node*ListDelete(NODE*head,inti){NODE*p,*s;

if(i<1||i>ListLength(L)) /*检查i值的合理性*/returnhead;if(i==1){ p=head->next; free(head); returnp;}for(p=head;i>2;p=p->next) /*寻找第i-1个结点*/ i--;s=p->next; /*用s指向将要删除的结点*/p->next=s->next; /*删除s指针所指向的结点*/free(s);returnhead;}

第6章数据的组织结构例9：约瑟夫（Joseph）问题：编号为1，2，···，n的n个人按顺时针方向围坐在一张圆桌旁。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，然后从顺时针方向的下一个就坐在桌旁的人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。

假设有10个人，编号从1到10，最初的m=3，通过报数，这10个人离开桌旁的顺序应该是：3，6，9，2，7，1，8，5，10，4。

请设计一个C程序来模拟这个过程。要求输出所有人离开桌旁的顺序。

第6章数据的组织结构问题分析为了区分不同的人，需要为每个人分配一个编号，由这n个编号组成了一个线性序列。最初，这个线性序列应该为1，2，3，...，n由于n个人坐在一个圆桌旁，所以这个线性序列应该首尾相接，形成一个环状。由于每次报到m的人离开桌旁，所以线性序列中的数据越来越少。第6章数据的组织结构算法描述

第6章数据的组织结构#include<stdio.h>#include<stdlib.h>#defineNUM10typedefstructnode{intNo;/*编号*/structnode*next;}NODE;

程序代码第6章数据的组织结构main(){NODE*head=NULL;NODE*p,*rear,*pre;inti,count,m;for(i=1;i<=NUM;i++){/*构造循环链表*/p=(NODE*)malloc(sizeof(NODE));p->No=i;if(head==NULL){head=p; /*第1个结点*/rear=p;}else{rear->next=p; /*加入新的结点*/rear=p; /*尾结点*/}}rear->next=head;第6章数据的组织结构printf("\Enterm:"); /*输入报数上限*/scanf("%d",&m);p=head; /*从第1个结点开始*/while(p->next!=p){ /*存在多个结点时，重复报数*/count=1;do{ /*报数过程*/p=p->next; /*p始终指向当前报数的结点*/count++;}while(count!=m);for(pre=p;pre->next!=p;pre=pre->next);/*找到当前结点之前的结点pre*/printf("%4d",p->No); /*输出离开者信息*/pre->next=p->next; /*从链表中删除离开者*/free(p);p=pre->next;}printf("%4d\n",p->No); /*处理最后一个人的信息*/free(p);}第6章数据的组织结构例10：记录学生考试成绩情况。假设在一个班中有35名学生，为了能够在毕业的时候打印出学生的成绩单，应该将每个学生的每次考试成绩记录下来。鉴于简化问题的考虑，这里仅记录每个学生参加考试的课程名称和考试成绩。请编写一个C程序，记录这个班级中每个学生的考试成绩情况。

第6章数据的组织结构问题分析在这个程序中，主要应该描述两个部分的数据，一部分是学生信息，假设只包含学生姓名，由于这部分数据的数量已经相对固定，所以可以采用一维数组组织学生信息；另外一部分是每个学生的若干门课程的考试成绩，由于每个学生的考试科目及数量又可能不一样，甚至差异可能较大，所以采用链表组织这部分数据。其中，每个结点包含课程名称、考试成绩和指向下一个结点的指针。

第6章数据的组织结构#include<stdio.h>#include<string.h>#include<stdlib.h>#defineNUM30typedefstructcnode{ /*考试成绩结点结构*/charcname[16]; /*课程名称*/intscore; /*成绩*/structcnode*next;}CNODE;typedefstruct{ /*学生基本信息结构*/charname[20]; /*学生姓名*/CNODE*head; /*指向成绩链表的指针*/}SNODE;voidinitStuInfo(SNODE[]);voidinputCourseInfo(SNODE[],intNo);voidoutputInfo(SNODE[]);程序代码第6章数据的组织结构voidmain(){inti;SNODEs[NUM];initStuInfo(s); /*输入学生信息*/for(i=0;i<NUM;i++) inputCourseInfo(s,i); /*输入一个学生的所有成绩*/outputInfo(s); /*输出所有学生的信息和成绩*/}voidinitStuInfo(SNODEs[]) /*输入学生基本信息*/{inti;printf("\nEnterinformationof%dstudents:\n",NUM);for(i=0;i<NUM;i++){ /*完成学生信息数组的初始化*/ gets(s[i].name); /*读入一行文本（学生姓名），存入结点*/ s[i].head=NULL;}}第6章数据的组织结构voidinputCourseInfo(SNODEs[],intNo)/*输入一个学生的考试成绩*/{chartext[80],buf[40];intscore,num,i;CNODE*c;printf("\nEntercourse'snumber:");gets(text); /*读入一行文本*/sscanf(text,"%d",&num); /*从字符数组中读取成绩*/printf("\nEntercourse'sname&score:\n");for(i=1;i<=num;i++){gets(text); /*读入一行文本*/c=(CNODE*)malloc(sizeof(CNODE));sscanf(text,"%s%d",c->cname,&c->score);/*从文本中取出课程名称和成绩*/c->next=s[No].head; /*添加到成绩链表的表头*/s[No].head=c;}}第6章数据的组织结构voidoutputInfo(SNODEs[])/*输出所有信息*/{inti;CNODE*p;for(i=0;i<NUM;i++){printf("\n%12s:",s[i].name);for(p=s[i].head;p!=NULL;p=p->next) printf("(%10s,%d)",p->cname,p->score);printf("\n");}}第6章数据的组织结构6.3文件文件的概念文件是指存储在外部介质上的一组相关数据的集合。按照不同的组织方式，文件被划分为两个类别：文本文件和二进制码文件。对文件的操作需要经过打开文件、读写文件和关闭文件三个阶段。

文本文件以字符为基本单位，每个字符占用一个字节存放对应的ASCII码；这种文件形式又被称为ASCII文件。二进制文件是指直接按照二进制编码形式存储数值的方式。第6章数据的组织结构文件的基本操作

定义文件指针定义格式为：FILE*<指针变量名>；例如FILE*fp;文件的打开<文件指针>=fopen（<文件名>，<操作模式>）if((fp=fopen("c:\\","r"))==NUUL){printf(“\nCannotopenthefile”);return1; }<文件名>是以字符串形式描述的文件名；<操作模式>是指文件的类别和操作方式。“r”表示只读,“w”表示只写。如果文件打开成功，函数返回FILE型变量的地址，否则，返回NULL。

第6章数据的组织结构文件的关闭fclose（<文件指针>）；例如：fclose(fp);文件的读写操作字符读写函数

：fgetc()和fputc()字符串读写函数：fgets()和fputs()数据块读写函数：fread()和fwrite()格式化读写函数：fscanf()和fprinf()

第6章数据的组织结构字符读写操作

1、fgetc()的调用格式：

<字符型变量>=fgetc(<文件指针>)；例如：ch=fgetc(fp)；这条语句的功能是：从fp指向的文件中读取一个字符并将这个字符赋给char型变量ch。2、fputc()的调用格式：

fputc(<字符>，<文件指针>)；例如：fputc(ch,fp)；这条语句的功能是：将字符型变量ch的内容写入文件指针fp所指的文本文件中。第6章数据的组织结构例11：读取一个给定的文本文件，并将文件的内容显示在屏幕上。

问题分析需要读取文本文件，所以以“r”操作模式将文件打开。

文本文件的结束标志为EOF。当文件读写指针指向EOF时，表示文件已经读到了尾部。因此，在读文件时，需要设计一个while循环语句，它的结束条件是读取的字符等于EOF。需要读取的文件名称通过命令行参数带入，这样可以扩展程序的使用范围，增加程序运行的灵活性。第6章数据的组织结构算法描述

开始结束ch!=EOF非空行NNargs!=2输出提示信息输出chYYYN打开不成功输出提示信息fgetc()

chfclose()fgetc()

ch第6章数据的组织结构#include<stdio.h>main(intargc,char*argv[]){FILE*fp;intch;if(argc!=2){printf("\nNo.");return1;}if((fp=fopen(argv[1],"r"))==NULL){ /*打开文件*/printf("Cannotopenfile!");return1;}ch=fgetc(fp); /*以字符方式读取文件*/while(ch!=EOF){putchar(ch);ch=fgetc(fp);}fclose(fp); /*关闭文件*/}程序代码第6章数据的组织结构例12：文本文件的拷贝。

问题分析旧文件名和新文件名均通过命令行参数带入。旧文件以读方式打开，新文件以写方式打开。一边从旧文件中读取字符，一边往新文件中写入，直到原文件结束。第6章数据的组织结构#include<stdio.h>main(intargc,char*argv[]){FILE*fp1,*fp2;intch;if(argc!=3){ /*判断参数的数量*/printf("No.");return1;}if((fp1=fopen(argv[1],"r"))==NULL){ /*打开旧文件*/printf("Cannotopen%s\n",argv[1]);return1;}if((fp2=fopen(argv[2],"w"))==NULL){ /*打开新文件*/printf("Cannotopen%s\n",argv[2]);return1;}while((ch=fgetc(fp1))!=EOF) /*拷贝文件*/fputc(ch,fp2);fclose(fp1); /*关闭两个文件*/fclose(fp2);}程序代码第6章数据的组织结构字符串读写操作

1、fgets()的调用格式：

fgets(<字符数组>，n，<文件指针>)；例如：fgets(str,n,fp)；这条语句的功能是：从fp所指的文件中读出n-1个字符并存入字符数组str中。2、fputs()的调用格式：

fputs(<字符串>，<文件指针>)；例如：fputs(“Cprogram”,fp);这条语句的功能是：将字符串“Cprogram”写入fp所指的文件中。第6章数据的组织结构例13：请编写一个程序，为指定文件的读取、显示和写入提供支持，并以菜单方式提供操作手段。

问题分析设计一个菜单。菜单中包含读文件并显示（readFile）、写文件（writeFile）和退出（exit）三个选项。当程序运行后，根据用户的选择进行相应的操作。假设文件中每行的内容不超过80个字符，则读取一行内容的操作可以用下面这条语句实现：

fgets(str,80,fp);除主函数外，设计两个函数，一个是用于读取文件的函数readFile()；另一个是用于写文件的函数writeFile()。

第6章数据的组织结构算法描述

开始结束显示菜单choice==1YNchoice!=3NYreadFile()choice==2YNwriteFile()第6章数据的组织结构#include<stdio.h>#include<string.h>voidreadFile();voidwriteFile();main(){intchoice,num;charlines[100][80];do{/*显示菜单*/printf("\n=====MENU=====\n");printf("\nread");printf("\nwrite");printf("\nexit.........................3");printf("\nselect:");scanf("%d",&choice);getchar();/*用户选择*/if(choice==1)num=read);if(choice==2)write,num);}while(choice!=3);}程序代码第6章数据的组织结构intreadlines[][80]) /*读文件*/{inti;FILE*fp;char[30];printf("\Enter:"); /*输入要进行写操作的文件名*/gets();if((fp=fopen(,"r"))==NULL){ /*打开