c++课件-结构与链表.ppt

26.1 6.1 结构类型结构类型 6.1.1 结构类型说明结构类型说明说明结说明结构类型构类型的关键字的关键字 struct 结构类型标识符结构类型标识符 结构成员结构成员1;1; 结构成员结构成员2;2;结构成员结构成员n;n;类型可任意类型可任意（不能为该结构自身）（不能为该结构自身） C语言提供了这样一种数据结构：它将不同类型的数据组合成一个有机的整体结构体。3struct date int month; int day; int year; struct man char name15; char sex; int age; date birthday;如，说明一个结构类型如，说明一个结构类型datedate，含三个整型数据成员，含三个整型数据成员在此基础上，又在此基础上，又可说明另一个结可说明另一个结构类型构类型manmanbirthdayNamesexagemonthdayyear struct man结构类型46.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; struct date birthday; man1, man2;无类型名变量无类型名变量5 struct goods /定义一个商品结构类型定义一个商品结构类型 char bh6; /商品编号商品编号 char mc20; /商品名称商品名称 float dj; /商品单价商品单价 int sl; /商品数量商品数量 char jhrq8; /进货日期进货日期g1=10012, shoes, 124,100, 080912；结构变量也允许在定义的同时给出初值，即初始化。如： struct person char name15; char sex; int age; s10 =Fang Min,F,24, Fang Hua,M,35;定义一个结构数组并对其部分元素初始化。66.1.3 6.1.3 结构变量的访问结构变量的访问访问形式：访问形式： 结构变量名结构变量名. .成员名成员名( (* *指向结构的指针指向结构的指针).).成员名成员名 指向结构的指针指向结构的指针-成员名成员名或或或或通过指向结构的指针引用结构变量成员通过指向结构的指针引用结构变量成员成员访问运算符成员访问运算符优先级最高的优先级最高的四个运算符之一四个运算符之一 括号不能少括号不能少如，假设有定义如，假设有定义man m,*p=&m; strcpy (m.name, Fang Min);p-birthday.month = 8; 则可如下引用结构成员则可如下引用结构成员7【例6.1】某商场周年店庆期间对其会员进行积分换购活动，活动内容为允许每天前五名光临的会员用其积分换购相应的商品，假设每100个积分可以换购5元的商品，编程序求该商场店庆期间每天换购出去的商品金额以及会员换购后的剩余积分值。假设会员将全部可能积分全部进行换购。 分析：可以将会员卡号和积分组合在一起定义一个结构类型，用结构数组来描述若干会员的信息。如， struct card char num10; int score; c10;8#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.score=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;206.2.2 6.2.2 链表的建立链表的建立【例6.3】创建一个含有n个结点的、包含一个数据域，且其类型为整型的单链表。链表的建立过程如下：首先设置head为NULL，即建立一个空的链表。申请一个新结点存储区域，让newnode指向该结点，然后向其数据域输入数据。把newnode所指向的结点插入到链表中。如果当前链表是空表，newnode所指向的结点应该成为该链表中唯一的一个结点，故head和tail都应该指向该结点。21如果当前链表非空，则newnode所指向的结点应该做为链表中的最后一个结点加入到链表中，故应该将其插在tail指向的结点后面。 重复执行第2、3步共n次。 将最后一个结点的next域置空(NULL)。22#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);23 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 = newnode246.2.3 6.2.3 单链表的基本操作单链表的基本操作1、链表的遍历 由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。【例6.4】输出上例中建立的单链表的各结点的值。 假设定义p是指向链表中结点的工作指针，该指针从表头head开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到p的值为NULL。25遍历的函数实现如下：void print(struct node *head)struct node *p=head;while(p!=NULL)coutdatanext262 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);273、查找结点【例6.6】在链表中按序号查找第i个结点。 设置一个序号计数器j和一个工作指针p，从表头结点开始，顺着链表的链进行查找。仅当j=i并且p!= NULL时查找成功，否则查找不成功。28void search(struct node *head, int i)int j=1;struct node *p=head;if(i0)coutillegal indexn;elsewhile(j !=i &p!= NULL)j+; ;if( )coutindexi:data;else coutnextj=i&p!=NULL294 4、在链表中插入结点、在链表中插入结点 假定有一个指针behind 指向链表中的某个结点，newnode指向待插入结点。newnode12 10 15 19behindfront 如果有一个指针front指向behind的前驱，则仅需编写下面的两个语句，即可实现插入。 ; ; 如果没有behind指针，插入操作仍然可以完成。newnode-next=front-next;front-next=newnode;思考题：上述两个语句的次序能否交换？为什么？newnode-next=behindfront-next=newnode30behind7两种特殊情况：1. 在表头结点之前插入： ; ;2. 在尾结点之后插入： ; ;newnodeheadbehind6 7newnode 8 【例6.7】编写函数，实现在头结点为head的链表中插入值为x的结点。newnode-next=behindhead=newnodebehind-next=newnodeNULLnewnode-next=NULL31struct 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(behind=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;325 5、删除链表中的某个结点、删除链表中的某个结点 删除链表中的某个结点，是把被删除结点的后继结点的地址,赋给其前趋结点的指针域或表头指针head，无后继结点时，则赋NULL。 假定p为指向要删除结点的指针，q为指向删除结点前趋的指针。 如果p=head，则删除的是第一个结点，则应修改表头指针head，使其指向第二个结点，并释放第一个结点占据的存储空间。 head=p-next;delete p; 33如果删除的是链表的中间结点，则应把被删除结点p的后继结点的地址，赋给其前趋结点q的指针域。如果没有后继结点时，则赋空指针NULL。q-next=p-next ; delete p;34【例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 ; delete p; else /未找到要删除的元素coutx-next = p-link; p-next = newnode;headnewnodeheadnewnode插入插入headnewnodeheadnewnode插入插入pppp非空表非空表空表空表可见，空表和非空表的操作是一致的，无需再分别讨论，简化了操作。37q = p-next;p-next = q-next;delete q; headheadheadheadpqpq可见，即使删除后为空表，也无需修改head，与非空表操作一致386.3 6.3 应用举例应用举例【例6.9】建立一个带表头结点的单链表，要求每次都将最后加入的结点加到最前面，结点中的数据均是不为0的整数（要求输入0时建立过程结束），然后统计结点个数并输出结点中的所有数据。分析分析 根据题意，建立该链表的过程是不断向表头插入新结点的过程。考虑到题目要求建立的是一个含表头结点的单链表，因此新结点应加入到伪结点的后面，成为第一个有效结点。 39#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;结束结束