数据的组织结构二高级语言程序设计北京工业大学.pptx

一、结构体如何表示多个不同类型的数据项，这些数据项逻辑上构成一个数据元素？如：每个学生都有学号、姓名每本书都有书号、书名、作者、出版社用结构体类型来表示。第1页/共111页struct ;struct point int x;int y;struct student int sNum;char name10;结构体类型声明声明的是数据类型，不是变量！第2页/共111页point p1,p2;/对比：int i,j;student zhang,wang;定义时初始化point p1=1,1;student zhang=1,张一;结构体类型变量定义p1p1p111zhang1张一整型大小10个字符大小第3页/共111页结构体类型变量的成员变量的引用.p1.x p1.y zhang.sNum zhang.name即看成普通变量使用scanf(%d%d,&p1.x,&p1.y);scanf(%s,zhang.name);printf(%s,zhang.name);p1.x=1;zhang.name=张一;第4页/共111页同一结构体类型变量可以赋值point p1=1,2,p2;p2=p1;等同于：p2.x=p1.x;p2.y=p1.y;第5页/共111页例：学生基本信息的组织学生信息：学号、姓名、出生日期、所属院系、专业完成任务键盘输入30个学生的信息、并屏幕输出；键盘输入月份和日期，查找并输出本年度在给定日期之后过生日的学生信息第6页/共111页例：学生基本信息的组织设计数据结构：每个学生基本信息用结构体描述学号学号int num;姓名姓名char name24;出生日期出生日期自定义一个结构：年、月、日自定义一个结构：年、月、日所属院系所属院系char department48;专业专业char major32;第7页/共111页struct Date/*日期结构*/int year;int month;int day;struct StudentInfo/*学生信息结构*/int num;char name24;Date birthday;char department48;char major32;第8页/共111页数据类型的别名用户可以为已有的数据类型起别名语法：typedef 原数据类型 新的数据类型名例如：typedef int xuehao;思考这样做的好处？程序更加清晰易懂日期Date和学生信息StudentInfo结构的另一种定义方式：第9页/共111页typedef struct /*日期结构*/int year;int month;int day;Date;typedef struct /*学生信息结构*/int num;char name24;Date birthday;char department48;char major32;StudentInfo;第10页/共111页30名学生用数组表示#define NUM 30StudentInfo sNUM;第11页/共111页程序结构设计给出每个函数的定义，包括：功能说明，入口参数，出口参数等。主模块main()输入模块inputIofo()查询处理模块searchInfo()输出模块outputInfo第12页/共111页输入模块void inputInfo(StudentInfo);功能：将全部学生信息通过键盘输入到StudentInfo 数组。参数：学生信息数组。返回值：没有。输出模块void outputInfo(StudentInfo );功能：格式化输出StudentInfo 数组中的全部学生信息。参数：学生信息数组。返回值：没有。查询处理模块void searchInfo(StudentInfo,DATE);功能：查找并输出StudentInfo 数组中，DATE之后过生日的学生信息。参数：学生信息数组。查找关键字：Date返回值：没有。第13页/共111页依据定义设计函数的流程，编写代码。编写主模块函数的代码。看书P170，程序代码。分析书中设计的优缺点？第14页/共111页结构体应用例题P172，键盘输入10个整数，将它们从小到大重新排序，要求输出排序后的结果和排序前的位置数据结构用结构体类型将整数和原始位置绑在一起typedef struct int data;/*整型数值*/int pos;/*原始位置*/DATATYPE;算法输入：针对本次任务修改输出：针对本次任务修改排序：用以前的函数第15页/共111页例：模拟发扑克牌数据结构一张扑克牌的表示一副扑克牌的表示算法初始化一副扑克牌洗牌发牌P175第16页/共111页二、指针指针类型变量的定义*int*intptr;char*chptr;intptr0 x0012ff78一个地址大小chptr0 x0012ff70一个地址大小指针是变量是地址变量第17页/共111页指针类型变量的引用int*intptr;char*chptr;int i=0；char c=a；intptr=&i;/i的地址赋给intptrchptr=&c;/c的地址赋给chptr第18页/共111页intptr0 x0012ff780 x0012ff78chptr0 x0012ff700 x0012ff700aint*intptr;char*chptr;int i=0；char c=a；intptr=&i;chptr=&c;ci第19页/共111页指针变量所指的值*intptr=30;在格式化输入输出中的应用printf(“%d,%c”,*intptr,*chptr);scanf(“%d%c”,intptr,chptr);intptr30第20页/共111页intptr1intptr2NULL指针变量可初始化为空指针int*intptr1=&i;int*intptr2=NULL;指针赋值intptr2=intptr1;i第21页/共111页指针比较if(intptr2=intptr1)if(intptr2=NULL)if(!intptr2)第22页/共111页指针加减int*p=data;/p指向data0;即：&data0p+;/p指向data1;p=p+2;/p指向data3;p=p-2;/p指向data1;p=p+12;/成为bug;0 1 2 3 4 5 6 7 8 9dataint data10；第23页/共111页例char*strchr(char*s,char c)函数确定某个字符在字符串中出现的位置s 是字符串，c 要找的字符strchr函数返回指向找到的字符的指针用此函数获取指定字符在字符串中的位置数目char s=1236.87;int p;p=strchr(s,.)-s+1;printf(位置在：%dn,p);strchr函数返回指针，指针相减定位位置第24页/共111页例#include stdio.h#include string.hint main(int argc,char*argv)char b=Goodbye;char*pb=&b7;while(-pb=&b0)putchar(*pb);putchar(n);return 0;逆序第25页/共111页为什么指针变量也要有类型？指针变量所存地址没有区别但对指针变量所存地址指向的数据的操作不同 （不同数据集合上定义的操作不同，如：指针加1的操作）指针可指向各种数据类型，如基本类型、数组、函数、对象、指针等第26页/共111页指针与数组数组名是指向数组第1个元素的指针，但这个指针是常量；char str=program;printf(“%cn”,*str);/打印p printf(“%cn”,*+str);/错 printf(“%cn”,*(1+str);/对char*p;p=str;printf(“%cn”,*+p);/打印r第27页/共111页指针与数组数组名定位数组元素P184 图6-14指针定位数组元素P184 图6-15第28页/共111页利用指针对数组元素进行操作int iarray20;int*ptr;/方法一for(ptr=iarray,i=0;i20;i+)printf(“%d”,*(ptr+i);/方法二for(ptr=iarray;ptriarray+20;ptr+)printf(“%d”,*ptr);例6-4 P185第29页/共111页指针数组例子/打印整型数组指定的行。j：行号（0开始），rowD:行长度，p:指向数组第一个元素的指针void pr_row(int j,int rowD,int*p)int i;p=p+(j*rowD);for(i=0;irowD;i+)printf(“%d ”,*(p+i);第30页/共111页二维数组与一维指针数组int a32;a00a01a10a11a20a21a0a0a1a2第31页/共111页二维数组与一维指针数组int a32;a00a01a10 a11a20 a21a0a1a2a0,a1,a2，一维数组的首地址，是指针。用指针定位二维数组元素：i 代表行，j 代表列int*ptr=a0；元素：*(ptr+i*列数+j)第32页/共111页例：P187#define ROWNUM 5#define COLNUM 4int aROWNUMCOLNUM;int*ptr1;ptr1=a0;for(i=0;iROWNUM;i+)for(j=0;jCOLNUM;j+)printf(%3d,*(ptr1+i*COLNUM+j);printf(n);可替换：ptr1=&a00;ptr1=(int*)a;第33页/共111页例：P187int(*ptr2)COLNUM;ptr2=&a0;/a0是指针，可以：ptr2=a;for(i=0;iROWNUM;i+)for(j=0;jCOLNUM;j+)printf(%3d,*(*(ptr2+i)+j);printf(n);书错int(*ptr2)COLNUM;与 int*ptr2COLNUM;区别int*ptr2COLNUM;/是整型指针的数组int(*ptr2)COLNUM;/指向整型指针的指针数组第34页/共111页指针数组int a10;int *b3;b0=&a0;for(i=0;inumber);/等价：printf(%d,zhang.number);第41页/共111页例：选举问题选举问题：某部门，需要由全体员工推选一名办公室主任。假设有10名候选人。编程序依据每个候选人的得票数量，得票最多当选，给出选举结果包括候选人编号和得票数。定义结构体：struct Candidateint number;/候选人号码int vote;/候选人得票数;第42页/共111页int main()Candidate data NUM;Candidate MySelected;input(data,NUM);MySelected=max(data,NUM);output(MySelected);return 0;第43页/共111页/*查找得票最多的候选人。参数，返回值。*/Candidate max(Candidate value,int n)int i;Candidate selected;selected.vote=value0.vote;selected.number=value0.number;for(i=1;i selected.vote)selected.vote=valuei.vote;selected.number=valuei.number;return selected;第44页/共111页void output(Candidate selected)printf(当选者是%d候选人。得票数%d。n,selected.number,selected.vote);return;void input(Candidate value,int n)int i;printf(请输入%d个候选人的号码：,n);for(i=0;in;i+)scanf(%d,&valuei.number);printf(请输入%d个候选人的得票数：,n);for(i=0;idata);/等价：printf(%d,a.data);第46页/共111页三、动态申请存储空间库函数中动态申请和释放存储空间的函数，包含：stdlib.hvoid*malloc(int size)/申请void free(void*p)/释放例：int*ptr=(int*)malloc(sizeof(int)*20);free(ptr);为什么叫动态内存分配？第47页/共111页数组：int a10;/静态内存分配动态申请内存空间存储数组int*ptr=(int*)malloc(sizeof(int)*10);比较：程序运行到此语句才分配内存空间必须释放注意内存泄漏第48页/共111页例6-6，P190，构造杨辉三角形a分析题目，设计数据结构一维整型指针数组动态生成整型数组空间第49页/共111页四、引用引用类型变量定义：int&a;/变量的别名用法：int&a;a=0;第50页/共111页与地址相关的运算符：*&int*p;/声明 p 是一个int型指针int i=0;int&rf=i;/声明一个int 型的引用，rf存int型数据的地址,/所以 int&rf=0 错,但可以 int rf(0);p=&i;printf(%dn,*p);/指针 p 所指的内容，*是指针运算符printf(%dn,(*p)+);/指针 p 所指的内容加1printf(%dn,*p);printf(%dn,rf);/rf此时用 i 的值rf+;/引用数据加1p=&rf;printf(%dn,*p);第51页/共111页五、再谈函数和函数参数值传递：变量值做函数参数void exchang1(int x,int y)int s;s=x;x=y;y=s;main()int t1=1,t2=2;exchange1(t1,t2);Exchange1中对x，y的改变不影响t1，t2的值。实际没有完成交换功能。结论：值传递时，被调用函数中对参数值的改变，不影响调用它的函数实参的值。第52页/共111页地址传递：指针变量做函数参数void exchang3(int*x,int*y)int s;s=*x;*x=*y;*y=s;main()int t1=1,t2=2;exchange3(&t1,&t2);Exchange3中对x，y所指值的改变使t1，t2的值发生改变。完成了交换功能。结论：地址传递时，被调用函数中对参数值的改变，将影响调用它的函数实参的值。第53页/共111页引用变量做函数参数void exchang2(int&x,int&y)int s;s=x;x=y;y=s;main()int t1=1,t2=2;exchange2(t1,t2);Exchange2中对x，y的改变使t1，t2的值发生改变。完成了交换功能。结论：地址传递时，被调用函数中对参数值的改变，将影响调用它的函数实参的值。第54页/共111页数组做函数参数void exchang4(char*a,char*b)char s5;strcpy(s,a);strcpy(a,b);strcpy(b,s);main()char t35=aaa;char t45=bbb;exchang4(t3,t4);Exchange4中对a，b的值改变使t3，t4的值发生改变。完成了交换功能。第55页/共111页利用函数返回值例题int main()char a;while(1)scanf(%c,&a);getchar();if(fun(a)=-1)printf(出现异常n);break;else printf(%cn,a);return 0;int fun(char&c)if(c=a-1&cz)c+;/处理c return 0;else return-1;第56页/共111页指针型函数函数的返回值为指针 (P199代码)char*strsub(char*str,int start,int len)int i,num;char*p;if(strlen(str)start)return NULL;if(strlen(str)start+len)num=strlen(str)start;elsenum=len;p=(char*)malloc(sizeof(char)*(num+1)for(i=0;inum;i+)*(p+i)=*(str+start+i);*(p+i)=0;return p;第57页/共111页选举的例子（教育在线课件资料中有完整的例子）int main()int n=NUM;int*data;int MySelected;input(&data);MySelected=max(data,n);output(MySelected);return 0;int input(int*value)int i;*value=(int*)malloc(sizeof(int)*NUM);if(!*value)return-1;/-1代表申请存储空间失败 printf(请输入%d个整型数：,NUM);for(i=0;iNUM;i+)scanf(%d,*value+i);return 0;/函数成功返回第58页/共111页错误例子，错在哪里？int main()int n=NUM;int*data;int MySelected;input(data);MySelected=max(data,n);output(MySelected);return 0;int input(int*value)int i;value=(int*)malloc(sizeof(int)*NUM);if(!value)return-1;/-1代表申请存储空间失败 printf(请输入%d个整型数：,NUM);for(i=0;idata);L-next=NULL;/先建立第一个结点 p=L;while(结束条件表达式)s=(node*)malloc(sizeof(node);scanf(%d,&(s-data);s-next=NULL;p-next=s;p=s;/CreateList_E第65页/共111页带头结点的单链表：为了使所有元素统一处理方式，专门加一个头结点带头结点的空链表a1a2ana3L.L第66页/共111页void CreateList_E(node*L)/正序输入元素的值，建立带头结点的单链表L node*p,*s;L=(node*)malloc(sizeof(node);L-next=NULL;/先建立一个带头结点的单链表 p=L;while(结束条件表达式)s=(node*)malloc(sizeof(node);scanf(%d,&(s-data);s-next=NULL;p-next=s;p=s;/CreateList_E第67页/共111页构建单链表方法二：头插法该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的头指针上，直到读入结束标志为止。a1a2ana3L.在此插入应逆序插入头结点第68页/共111页void CreateList_L(node*L)/逆序输入n个元素的值，建立带头结点的单链表L node*p;L=(node*)malloc(sizeof(node);L-next=NULL;/先建立一个带头结点的空的单链表 for(i=n;i 0;-i)p=(node*)malloc(sizeof(node);/生成新结点 scanf(%d,&(p-data);p-next=L-next;/插入到表头 L-next=p;/createList_L体会有头结点的好处第69页/共111页例：计算链表结点的个数int ListLength(node*L)/带头结点 node*p;p=L;int len=0;for(;p!=NULL;p=p-next)len+;return len;a1a2ana3L.第70页/共111页插入链表结点在第i个元素前插入一个新元素x 首先找到ai-1的存储位置p生成一个数据域为x的新结点*s插入过程先做：s-next=p-next再做：p-next=s5353xPPSai-1ai12第71页/共111页int ListInsert_L(node*L,int i,int x)node*s,*p=L;int j=0;while(p&jnext;+j;/寻找第i-1结点 if(!p|ji-1)return-1;/i小于1或大于（表长+1）s=(node*)malloc(sizeof(node);/生成新结点 s-data=x;s-next=p-next;p-next=s;return 0;anaia1a2ai-1xL第72页/共111页删除链表结点删除运算是将表的第i个结点删去。思路首先找到ai-1的存储位置pq=p-next，为处理被删除结点做准备 删除操作：p-next=q-next处理q所指结点ai-1a1aiai+1Lpq第73页/共111页int ListDelete_L(node*L,int i,int&e)node*q,*p=L;int j=0;while(p-next&jnext;+j;/寻找第i-1结点 if(!(p-next)|ji-1)return-1;/删除位置不合理 q=p-next;p-next=q-next;e=q-data;/参数带回被删数值 free(q);return 0;第74页/共111页例6-9，P203，约瑟夫环数据使用没有头结点的循环单链表每个结点数据：每个人的序号。当然有指向下一个结点的指针。功能建造循环链表游戏的过程打印输出序列（一边游戏一边打印？将结果保存之后一起打印？）第75页/共111页例6-10，P206，学生考试成绩处理数据学生信息采用数组，是结构体数组，每个数组元素有数据：学生姓名，指向成绩链的指针。学生选修每门课程和成绩，一个学生一个单链表，链表结点数据有：课程名，成绩，单链表指针。功能见P206图6-31定义每个模块中函数（函数功能，函数名，参数，返回值）。第76页/共111页例：有序数组插入元素/*在第i个元素之前插入元素x。a为整型数组首地址，length为当前数组元素个数，x为元素值。*/int insertSq(int*a,int&length,int i,int x)int q;if(ilength+1)return-1;/i值合理范围：1length+1for(q=length;q=i;q-)*(a+q)=*(a+q-1);*(a+q)=x;length+;return 0;第77页/共111页例：有序数组删除元素/*删除第i个元素，指放入参数x。a为整型数组首地址，length为当前数组元素个数。*/int delSq(int*a,int&length,int i,int&x)int q;if(ilength)return-1;/i值合理范围：1lengthx=*(a+i-1);for(q=i;qlength;q+)*(a+q-1)=*(a+q);length-;return 0;第78页/共111页数组与单链表的优缺点总结数组预知数据多少必须用连续存储空间支持随机存取插入删除操作需要移动大量元素单链表不需预知数据量不需连续存储空间不支持随机存取插入删除操作不需移动大量元素第79页/共111页不用指针实现单链表有些语言没有提供指针类型第80页/共111页七、文件持久化存储数据外存数据以文件形式组织依组织形式不同，分为两类：文本文件二进制文件第81页/共111页文本文件以字符为单位，每个字符一个字节，存放ASCII码例如：00111000001101110011011000110101存放8765 有若干文本行，每行以换行符n结束文本文件结束标志是EOF，它的值为-1第82页/共111页二进制文件以二进制形式存储数据例如：数值8765存放：0010001000111101 需要两个字节存储这个数值所以，二进制文件也可以看成字节序列，称为字节流，有了这一特征，也将文件称为流式文件第83页/共111页文件指针FILE结构：一个内存中的FILE结构对应一个磁盘文件，FILE结构声明在stdio.h中。见P211页定义。使用想文件，先定义文件指针FILE*;FILE*fp;第84页/共111页打开文件打开文件，系统自动创建一个FILE结构，并将提供指向此结构的指针。完成库函数：FILE*fopen(char*fname,char*mode)FILE*fp;if(fp=fopen(“c:file.dat,“r)=NULL)printf(“n不能打开文件);第85页/共111页文件操作模式mode参数的值，见P212表第86页/共111页关闭文件打开文件后必须关闭文件，否则可能造成文件指针泄漏或文件数据丢失。完成库函数：成功返回0，否则为非0值int fclose(FILE *fp)if(fclose(fp)printf(“n文件关闭有错误);第87页/共111页文件读写打开文件后可对文件进行读写操作。库函数中有若干文件读写函数：字符读写操作字符串读写操作数据块读写操作格式化读写操作第88页/共111页字符读写操作int fgetc(FILF *fp)在stdio.h中从fp所指文件的当前位置读取一个字符，并将文件位置指示器增大；返回值为字符转换的整数。到达文件尾时返回值为EOFint fputc(int c,FILF *fp)在stdio.h中将字符c写到fp所指的文件的当前位置，并将文件位置指示器增大；返回值为所写的字符的值；第89页/共111页字符读写操作例题：读取一个文本文件，并将内容显示。#include int main()FILE*fp;int ch;if(fp=fopen(e:a.txt,r)=NULL)printf(打不开文件);return-1;第90页/共111页ch=fgetc(fp);while(ch!=EOF)putchar(ch);ch=fgetc(fp);fclose(fp);return 0;第91页/共111页字符读写操作例题：文本文件拷贝#include int main()FILE*fp1,*fp2;int ch;if(fp1=fopen(e:a.txt,r)=NULL)printf(打不开旧文件);return-1;第92页/共111页if(fp2=fopen(e:b.txt,w)=NULL)printf(打不开新文件);return-1;while(ch=fgetc(fp1)!=EOF)fputc(ch,fp2);fclose(fp1);fclose(fp2);第93页/共111页字符串读写操作 char*fgets(char*str,int num,FILF *fp)在stdio.h中从fp中读取至多num-1个字符，放入str指向的字符数组，并在最后一个字符位置加上0，遇到换行符或EOF时读取也停止；操作成功，返回str，失败时返回空指针；int fputs(char*str,FILF *fp)在stdio.h中把str所指的字符串的内容写入fp文件流，但不写0；操作成功，返回0，失败时为非0值；第94页/共111页字符串读写操作例题：读取一个文本文件，并将内容显示。#include int main()int i;char lines102480;FILE*fp;int ch;if(fp=fopen(e:a.txt,r)=NULL)printf(打不开文件);return-1;第95页/共111页for(i=0;!feof(fp);i+)fgets(&linesi0,80,fp);puts(linesi);fclose(fp);return 0;第96页/共111页字符串读写操作例题：文本文件拷贝#include int main()int i;char lines102480;FILE*fp1,*fp2;int ch;if(fp1=fopen(e:a.txt,r)=NULL)printf(打不开旧文件);return-1;第97页/共111页if(fp2=fopen(e:b.txt,w)=NULL)printf(打不开新文件);return-1;for(i=0;!feof(fp1);i+)fgets(&linesi0,80,fp1);fputs(&linesi0,fp2);fclose(fp1);fclose(fp2);第98页/共111页数据块读写操作int fread(void*buffer,int size,int count,FILE*fp)int fwrite(void*buffer,int size,int count,FILE*fp)buffer-指向存放位置的指针size-每个读写块的字节数count-待读写的块数fp-文件指针第99页/共111页数据块读写操作例题：从键盘输入学生信息，写入二进制文件，再从该文件中读取学生信息，显示在屏幕上。#include#define NUM 3struct infoint No;char name16;第100页/共111页int main()int i;info s;FILE*fp;if(fp=fopen(e:c.txt,wb)=NULL)printf(打不开文件);return-1;for(i=0;iNUM;i+)scanf(%d%s,&s.No,s.name);fwrite(&s,sizeof(info),1,fp);fclose(fp);第101页/共111页if(fp=fopen(e:c.txt,rb)=NULL)printf(打不开文件);return-1;while(fread(&s,sizeof(info),1,fp)printf(n%4d%16s,s.No,s.name);fclose(fp);第102页/共111页格式化读写操作int fscanf(FILE*fp,char*format,arg_list)int fprintf(FILE*fp,char*format,arg_list)与scanf和printf类似第103页/共111页格式化读写操作例题：从键盘输入学生信息，写入二进制文件，再从该文件中读取学生信息，显示在屏幕上。#include#define NUM 3struct infoint No;char name16;第104页/共111页int main()int i;info s;FILE*fp;if(fp=fopen(e:c.txt,w)=NULL)printf(打不开文件);return-1;for(i=0;iNUM;i+)scanf(%d%s,&s.No,s.name);fprintf(fp,n%4d%16s,s.No,s.name);fclose(fp);第105页/共111页if(fp=fopen(e:c.txt,r)=NULL)printf(打不开文件);return-1;while(!feof(fp)fscanf(fp,%d%s,&s.No,s.name);printf(n%4d%16s,s.No,s.name);fclose(fp);第106页/共111页八、联合体与枚举类型联合体多个变量共用一个存储空间位置，这些变量可以是不同的数据类型，联合体存储空间大小为多个变量中最大一个变量占用的空间大小第107页/共111页union union uType int i;/2个字节 char ch;/1个字节 uType a；a占多大空间？2个字节a.i占多大空间？2个字节a.ch占多大空间？1个字节第108页/共111页枚举类型定义类型：enum enum weekdaySun,Mon,Tue,Wed,Thu,Fri,Sat;枚举是一个被命名的整型常量的集合。列表中每个枚举值对应一个序号：0、1、2、3、4、5、6。而不是字符串。占整型常量空间枚举变量值只能是枚举值列表中列出的值之一第109页/共111页枚举类型使用枚举变量的好处限制变量取值范围提高程序的可读性定义变量：enum weekday day;操作：day=Wed;第110页/共111页感谢您的观看。第111页/共111页