《六章节结构和链表》由会员分享，可在线阅读，更多相关《六章节结构和链表（39页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 结构和链表结构和链表6 6.1 .1 结构类型结构类型6 6.2 .2 结构的应用结构的应用-链表链表6 6.3 .3 应用举例应用举例暑苍凭涵讼尸矢婴笆蜀擅鲜挪妓滦坚配砍渣鞋先矣吝歧柿泣票良佰澳绊时六章节结构和链表六章节结构和链表16.1 6.1 结构类型结构类型 6.1.1 结构类型说明结构类型说明说明结说明结构类型构类型的关键字的关键字 struct 结构类型标识符结构类型标识符 结构成员结构成员1;1; 结构成员结构成员2;2;结构成员结构成员n;n;类型可任意类型可任意（不能为该结构自身）（不能为该结构自身） C语言提供了这样一种数据结构：它将不同类型的数据组合成一个有
2、机的整体结构体。判踏似浩创惹杜瘩里秸鞭撮吮宵沫霉锚荡增滑橱蜘仑叠冀球臣俭盔叫冉狱六章节结构和链表六章节结构和链表2struct date int month; int day; int year; struct man char name15; char sex; int age; date birthday;如，说明一个结构类型如，说明一个结构类型datedate，含三个整型数据成员，含三个整型数据成员在此基础上，又在此基础上，又可说明另一个结可说明另一个结构类型构类型manmanbirthdayNamesexagemonthdayyear struct man结构类型搪咋刽障糯陋刷吉彪蚀炮
3、冻瞎旋脐年饼精失吻京津汛纺煞骂舍联峰狐雏砧六章节结构和链表六章节结构和链表36.1.2 6.1.2 结构变量定义及初始化结构变量定义及初始化先说明结构类型再定义结构变量先说明结构类型再定义结构变量在说明结构数据类型的同时定义结构变量在说明结构数据类型的同时定义结构变量省略结构标识符直接定义结构类型变量省略结构标识符直接定义结构类型变量struct man man1, man2;struct man char name15;char sex;int age; struct date birthday; man1, man2;struct char name15;char sex;int age;
4、 struct date birthday; man1, man2;无类型名变量无类型名变量锑层刹聋备阉唤咀成纠坚盗坪狰嘘脚墩懂滴褪闲吓妖畜踞虞荣垄佩赌盒斗六章节结构和链表六章节结构和链表4 struct goods /定义一个商品结构类型定义一个商品结构类型 char bh6; /商品编号商品编号 char mc20; /商品名称商品名称 float dj; /商品单价商品单价 int sl; /商品数量商品数量 char jhrq8; /进货日期进货日期g1=10012, shoes, 124,100, 080912；结构变量也允许在定义的同时给出初值，即初始化。如： struct per
5、son char name15; char sex; int age; s10 =Fang Min,F,24, Fang Hua,M,35;定义一个结构数组并对其部分元素初始化。谭铝猾幽忌迂惟锰帮疯窿炯饭铁洛懦弊诸逢默嗽倚惰伦汞祖倚斟颖盯盔载六章节结构和链表六章节结构和链表56.1.3 6.1.3 结构变量的访问结构变量的访问访问形式：访问形式： 结构变量名结构变量名. .成员名成员名(*(*指向结构的指针指向结构的指针).).成员名成员名 指向结构的指针指向结构的指针-成员名成员名或或或或通过指向结构的指针引用结构变量成员通过指向结构的指针引用结构变量成员成员访问运算符成员访问运算符优先级最
6、高的优先级最高的四个运算符之一四个运算符之一 括号不能少括号不能少如，假设有定义如，假设有定义man m,*p=&m; strcpy (m.name, Fang Min);p-birthday.month = 8; 则可如下引用结构成员则可如下引用结构成员运诲档临迢澎隅米娄偏逾险串惹搅芳皆门栓彤辜这草店怪猿榨镜叔叁趣郝六章节结构和链表六章节结构和链表6【例6.1】某商场周年店庆期间对其会员进行积分换购活动，活动内容为允许每天前五名光临的会员用其积分换购相应的商品，假设每100个积分可以换购5元的商品，编程序求该商场店庆期间每天换购出去的商品金额以及会员换购后的剩余积分值。假设会员将全部可能积分
7、全部进行换购。 分析：可以将会员卡号和积分组合在一起定义一个结构类型，用结构数组来描述若干会员的信息。如， struct card char num10; int score; c10;盾皑恕瘟恐割划弱疥霞剔弥浑或漆煞毕回菲婴礼耽赌我占填笔判邓硝挑镶六章节结构和链表六章节结构和链表7#include iostream.h#define N 5void main( ) struct card char num10; int score; cN; int i,s=0; for(i=0;ici.numci.score; s=s+5*(ci.score/100); /每100分换购5元商品 ci.sc
8、ore=ci.score-100*(ci.score/100); /该会员的剩余积分 cout扣除积分后:n; for(i=0;iN;i+)coutci.numtci.scoreendl; cout积分换购金额=sdata=10;q=new node;q-data=20;NULLq-next=NULLp-next=q;珍码留创舜问血驴烟撰鸭核忻溯父诬笆猪粹祷磨痈志狈锦庚浴塑垄拽杆笆六章节结构和链表六章节结构和链表196.2.2 6.2.2 链表的建立链表的建立【例6.3】创建一个含有n个结点的、包含一个数据域，且其类型为整型的单链表。链表的建立过程如下：首先设置head为NULL，即建立一个空
9、的链表。申请一个新结点存储区域，让newnode指向该结点，然后向其数据域输入数据。把newnode所指向的结点插入到链表中。如果当前链表是空表，newnode所指向的结点应该成为该链表中唯一的一个结点，故head和tail都应该指向该结点。较屿墓悸袍镍裔普熟用肆汉添蜒葡趁袒援枝恒憨蒲嗽晕署贪赤妖观斥领啸六章节结构和链表六章节结构和链表20如果当前链表非空，则newnode所指向的结点应该做为链表中的最后一个结点加入到链表中，故应该将其插在tail指向的结点后面。 重复执行第2、3步共n次。 将最后一个结点的next域置空(NULL)。札想遥贴渔玉奈丽拌展诸纲株洛叁佳彩幢驱述崎占柒宗斌愈盅桐媳
10、穴掐紧六章节结构和链表六章节结构和链表21#include iostream.hstruct node int data; struct node *next;struct node *create(int n ) struct node *head = NULL; struct node *tail,*newnode; int x; for (int i=0; ix; newnode= ; /为newnode申请存放空间newnode-data=x;new node也可用如下语句newnode=( struct node *) malloc(sizeof( struct node);撩熄慷迹
11、尝顺遇补许隋绰圃獭咳地阶力也怎喉岂淫延阁醋虹稼惜卸久氧有六章节结构和链表六章节结构和链表22 if(head=NULL) ; /newnode成为空表的第一个结点 else ;/将newnode连接到原来的表尾 ; / newnode成为新的表尾 tail-next=NULL; return(head);void main( ) struct node *head; int n; coutn; head = create(n);head=newnodetail-next=newnodetail = newnode诗晤豺觉朋陡泌捅弦恢假侯浑距捧综致恒吓泄姑干烈浅某凭瓤法痒殴绵据六章节结构和链表六
12、章节结构和链表236.2.3 6.2.3 单链表的基本操作单链表的基本操作1、链表的遍历 由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。【例6.4】输出上例中建立的单链表的各结点的值。 假设定义p是指向链表中结点的工作指针，该指针从表头head开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到p的值为NULL。女棺紊勤虐簇乡漂粤唁削护柳粤肿煌谎滓祭谭邯撒品赶铲烯蜘黑巡叼欧墅六章节结构和链表六章节结构和链表24遍历的函数实现如下：void print(struct node *head)struct node *p
13、=head;while(p!=NULL)coutdatanext烧矽粪沁拒塞迪润臭浅季岳帛客备恐擅骑唇吼冤肯成镍乡稳欧捉缮窑滑色六章节结构和链表六章节结构和链表252 2、 统计结点个数统计结点个数【例6.5】统计例6.3中创建的链表中结点的个数。 设置一个工作指针从表头结点开始，每经过一个结点，计数器的值增加1。实现统计的函数形式如下：int count(struct node *head) struct node *p = head; int n = 0; while (p != NULL) n+; p = p-next; return(n);铀篙揭宏斯哉童禽卜阑钨差昧叙樟颓毅卤具党世玲疼
14、拯拿姬花凹壳二糖依六章节结构和链表六章节结构和链表263、查找结点【例6.6】在链表中按序号查找第i个结点。 设置一个序号计数器j和一个工作指针p，从表头结点开始，顺着链表的链进行查找。仅当j=i并且p!= NULL时查找成功，否则查找不成功。榆还微阎少锣荒麓糖虎铣拇鼓汰蛤獭罗冰争亭吹侣少纪跳传哲丰旦芭笺捐六章节结构和链表六章节结构和链表27void search(struct node *head, int i)int j=1;struct node *p=head;if(i0)coutillegal indexn;elsewhile(j !=i &p!= NULL)j+; ;if( )co
15、utindexi:data;else coutnextj=i&p!=NULL思闷锤进褐哨引然族纲怂击耙雪圆灶瓶澜梆冲照膝包呐隶朴鲍隙子孔婪宝六章节结构和链表六章节结构和链表284 4、在链表中插入结点、在链表中插入结点 假定有一个指针behind 指向链表中的某个结点，newnode指向待插入结点。newnode12 10 15 19behindfront 如果有一个指针front指向behind的前驱，则仅需编写下面的两个语句，即可实现插入。 ; ; 如果没有behind指针，插入操作仍然可以完成。newnode-next=front-next;front-next=newnode;思考题：
16、上述两个语句的次序能否交换？为什么？newnode-next=behindfront-next=newnode有画舰壳摔晋筐胯副独歼鞭烦荫艺握滓霹故蚁习茸状塔抨本茫嫉萝织涤骗六章节结构和链表六章节结构和链表29behind7两种特殊情况：1. 在表头结点之前插入： ; ;2. 在尾结点之后插入： ; ;newnodeheadbehind6 7newnode 8 【例6.7】编写函数，实现在头结点为head的链表中插入值为x的结点。newnode-next=behindhead=newnodebehind-next=newnodeNULLnewnode-next=NULL交抛锻宿返蟹路莽断上博爆
17、倚禄恒盗桌么茸盐箭场逝轿靡烟宏聘谷娃捌客六章节结构和链表六章节结构和链表30struct node * insert(node *head,int x) struct node *behind,*front,*newnode; newnode=new node; newnode-data=x; behind=head; if(head=NULL) /空表 head=newnode;newnode-next=NULL; else /非空表 while(behind!=NULL&xbehind-data)/找插入位置 front=behind; behind=behind-next; if(beh
18、ind=head) /插到第一个结点前 newnode-next=head ; head=newnode; else if(behind=NULL) /插到最后一个结点后 front-next=newnode; newnode-next=NULL; else /插到front之后,behind之前 front-next=newnode;newnode-next=behind; return head;黄予塞签再驴沮灿迅藤蔫舅巡脚勿唐止螺姑兑舵往谈逞扑军渗纫鄙允却溅六章节结构和链表六章节结构和链表315 5、删除链表中的某个结点、删除链表中的某个结点 删除链表中的某个结点，是把被删除结点的后继结
19、点的地址,赋给其前趋结点的指针域或表头指针head，无后继结点时，则赋NULL。 假定p为指向要删除结点的指针，q为指向删除结点前趋的指针。 如果p=head，则删除的是第一个结点，则应修改表头指针head，使其指向第二个结点，并释放第一个结点占据的存储空间。 head=p-next;delete p; 宏诛际拈结暖餐墅捏姬乃颤咕泌免焦韧汲厚霜汉组冒二筑晒肝软妄驱嘱卉六章节结构和链表六章节结构和链表32如果删除的是链表的中间结点，则应把被删除结点p的后继结点的地址，赋给其前趋结点q的指针域。如果没有后继结点时，则赋空指针NULL。q-next=p-next ; delete p;亥奸噪侮孺淮匀
20、很商嘶名逼扛丰炼齐禄梗存啊坐响珠慷陡李亮杉镑苦权九六章节结构和链表六章节结构和链表33【例6.8】编写函数实现在头结点为head的链表中删除值为x的结点。struct node *delnode(node *head,int x) struct node *p,*q; /p为工作指针,q为p的前驱 p = head; if(head=NULL) /空表 coutdata!= x) / 找删除的结点 q=p; p = p-next; if(p=head) /删除第一个结点 head=p-next; delete p; else if(p!=NULL) /删除非表头结点 q-next=p-next
21、 ; delete p; else /未找到要删除的元素coutx-next = p-link; p-next = newnode;headnewnodeheadnewnode插入插入headnewnodeheadnewnode插入插入pppp非空表非空表空表空表可见，空表和非空表的操作是一致的，无需再分别讨论，简化了操作。驭惊等纪潮灵扒唾达呀洛韦声入龄喳泪边狱井吊铀娘能炭介荆潜痪鲁幸蹦六章节结构和链表六章节结构和链表36q = p-next;p-next = q-next;delete q; 从带表头结点的单链表中删除最前端的结点从带表头结点的单链表中删除最前端的结点从带表头结点的单链表中删
22、除最前端的结点从带表头结点的单链表中删除最前端的结点headheadheadheadpqpq可见，即使删除后为空表，也无需修改head，与非空表操作一致禾纠晶态骡吨丫彭咙超凯悄瞅孔陌价蚁筏掳很却监尧见陷物瘤艾隐剐爽冉六章节结构和链表六章节结构和链表376.3 6.3 应用举例应用举例【例6.9】建立一个带表头结点的单链表，要求每次都将最后加入的结点加到最前面，结点中的数据均是不为0的整数（要求输入0时建立过程结束），然后统计结点个数并输出结点中的所有数据。分析分析 根据题意，建立该链表的过程是不断向表头插入新结点的过程。考虑到题目要求建立的是一个含表头结点的单链表，因此新结点应加入到伪结点的后
23、面，成为第一个有效结点。 驹搪迪交趟谋仰魔湃象牢符莽锻澡障取季键呀纪待李机冒趾藉郁炬姚简钧六章节结构和链表六章节结构和链表38#include iostream.hstruct node int data; struct node *next;void main() struct node *head,*newnode,*p; int x,count=0; head=new node ; head-next=NULL; while(1) cinx; if(x=0) break; newnode=new node; newnode-data=x; newnode-next=NULL; newnode-next=head-next; /让新结点指向第一个有效结点 head-next=newnode; /让新结点成为第一个有效结点 接while语句后p=head-next;while(p!=NULL) count+; coutdatanext; coutcount=countendl;摹穷瘸巫窍迄境七未足朽厄慈肿撮兹疮门雇净滥孙耳虐凡猾亿额雁滩贡蚂六章节结构和链表六章节结构和链表39
