《《结构体及链表》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《结构体及链表》PPT课件.ppt(21页珍藏版)》请在三一办公上搜索。
1、1,结构体及链表,2,结构体类型,先定义结构体类型,再定义结构体类型的变量,再使用变量结构体类型定义struct studentint num;char name20;char sex;float score5;,struct dateint year,month,day;struct fapiaochar khmc40;/客户名称struct date kprq;/开票日期int pzs;/品种数float zje;/总金额char kpr20;/开票人;,3,结构体类型,结构体类型变量的定义方式一:struct studentint num;char name20;float score5
2、;char sex;struct student stu1,stu2;/变量定义/每个变量占用字节数:4+20+20+1=45,4,结构体类型,方式二:struct dateint year,month,day;struct fapiaochar khmc40;/客户名称struct date kprq;/开票日期int pzs;/品种数float zje;/总金额char kpr20;/开票人fp1,fp2;/定义2个变量,方式三:structint shuh;/书号char shum40;/书名char zuozh40;/作者char chubs20;/出版社int zish;/字数boo
3、k1,book2;/定义2个变量/只用一次的方式,5,结构体类型,初始化嵌套的结构体变量#includestruct dateint year,month,day;struct fpchar khmc40;date kprq;int pzs;float zje;char kpr20;void main()fp fp1=“小小公司”,2014,01,02,3,300,“小王”;coutfp1.kprq.yearendl;,6,链表,结点:一种数据结构,包含若干数据域、若干指针域链表:通过结点的指针域将若干结点连接成链结点只有一个指针域的链表称单向链表结点有2(3)个指针域的链表称为双(三)向链表
4、单向链表,7,结点算法,设结点有1个数据域和1个指针域struct stint data;st*link;在结点C和结点D之间添加结点Bp=new node;p-data=B;/产生一个新结点/从head开始找到结点C的地址p1(代码略)p2=p1-link;/从结点C的指针域找到结点D的地址p2p1-link=p;/使结点C的指针域指向结点Bp-link=p2;/使结点B指向结点D/如果在第一个结点前插入,则要修改指针head,此插入函数应返回结点类型的指针,8,结点算法,删除一个结点C/从head找到结点C前结点B的地址p1/找到结点C后结点D的地址p2p1-link=p2;/使结点B指向
5、结点Ddelete p;/回收结点C/如果删除的是第一个结点,也要修改head,应返回结点类型的指针修改结点数据/找到指定结点,修改数据域,返回类型void查找给定结点/查找数据域为给定值的结点,返回结点类型的指针,9,链表算法,创建链表的函数创建链表,就是逐个产生结点并加入链表;首结点和尾结点需单独处理;使用3个指针,head、p2指向尾结点、p1指向当前结点。/在链尾加入1个结点p1=new node;cinp1-data;p2-link=p1;/可输入一个特殊数据标记创建结束,但要记住释放最后一个结点/此函数返回head指针,10,链表算法,删除链表的函数可从head开始逐个删除结点;删
6、除当前结点前,要保存指针域的指针,以便删除下一个结点;返回类型void。输出链表的函数可从head开始,逐个输出结点的数据域中的数据;每次输出后,取出当前结点的指针域的指针,以便输出下一个数据;返回类型void。,11,程序代码1,学生成绩管理程序实例用结构体链表实现#includestruct student/学生结构体int num;/学号char name9;/姓名int english;/英语成绩int math;/数学成绩int cpp;/C+成绩student*next;/指针域,指向下一个结点;,12,程序代码2,创建链表函数student*creat()int n=1;stud
7、ent*head,*p1,*p2;/以下处理第1个结点head=new(student);p1=p2=head;coutp1-nump1-namep1-englishp1-mathp1-cpp;,13,程序代码3,/以下处理后续结点while(p1-num!=0)n+;p2-next=p1;p2=p1;/当前结点为新链尾p1=new(student);coutp1-nump1-namep1-englishp1-mathp1-cpp;p2-next=NULL;/链尾结点处理delete p1;return head;,14,程序代码4,输出链表的函数void print(student*head
8、)student*p1;coutnumnameenglishmathcppnext;while(p1!=NULL);,15,程序代码5,删除链表的函数void delech(student*head)student*p1;while(head)p1=head;head=head-next;delete p1;,查找结点的函数student*search(student*head,int x)student*p1=head;if(!head)coutnum=x)return p1;p1=p1-next;p1=NULL;return p1;,16,程序代码6,删除结点的函数student*dele
9、no(student*head,int x)student*p1=head,*p2;if(!head)coutnum=x)head=head-next;delete p1;return head;p2=p1-next;while(p2)if(p2-num=x)p1-next=p2-next;delete p2;return head;p1=p2;p2=p1-next;cout链表中无要删的结点xendl;return head;,17,程序代码7,求最高、最低平均成绩的函数void aver(student*head)int sum,maxsum,minsum;student*p1,*p2,*
10、p3;p1=head;if(head!=NULL)maxsum=p1-english+p1-math+p1-cpp;minsum=maxsum;p2=p3=p1;p1=p1-next;while(p1!=NULL)sum=p1-english+p1-math+p1-cpp;if(summaxsum)p2=p1,maxsum=sum;if(sumnext;coutnumnumtminsum/3.0endl;else cout链表空endl;,18,程序代码8,主函数void main()int x;student*head;head=creat();print(head);aver(head);
11、cinx;if(search(head,x)deleno(head,x);,19,约瑟夫环,n=6,m=3,20,约瑟夫环,#includestruct nodeint num;struct node*next;node*creat(int n)/创建环形链表函数node*head,*p2,*p1;head=new(node);p1=p2=head;p1-num=1;for(int i=2;inum=i;p2-next=p1;p2=p1;p2-next=head;return head;,21,约瑟夫环,void main()int n,m,i;node*p,*p1;coutnm;p=creat(n);cout1)for(i=1;inext;p1-next=p-next;coutnum;,delete p;n-;p=p1-next;coutnumendl;delete p;当n=10,m=4,输出:初始链:1 2 3 4 5 6 7 8 9 10出局者:4 8 2 7 3 10 9 1 6优胜者:5,