C语言设计实例教程动态组织数据课件

C

程序设计实例教程第七章动态组织数据

1数组：必须事先定义固定长度，静态分配存储空间。链表：无需事先知道数据的个数，可以动态分配存储空间，插入删除简便学习的意义要想改变数组长度可以吗？怎么解决2/7/20232主要内容1.建立链表的过程

2.链表结点的查找

3.链表结点的插入

4.链表结点的删除

5.循环链表

2/7/202337.1建立链表的过程这样文章a在排版时被分成了不连续的两块，读者怎样找到第二部分呢？编辑在a.part1的末尾加进了一个线索“下接XX页”，读者顺着线索很容易就找到了a.part2。所以a.part1放的不仅有文章本身，还有指示下一部分在哪的线索。通过这个线索，a.part1和a.part2就联系在一起了。2/7/20235那a.part2的后面还有没有另外一部分呢？杂志的每篇文章的最后都有一个特殊的符号，看到这个符号就知道这已经是最后了。厚厚的一本书中，又怎样找到文章a呢？翻翻目录就知道了，那里有文章a所在页码的信息。2/7/20236文章a......a.part1......a.part2文章axx页目录下接xx页完a.part1和a.part2组成了由两个结点构成的链表：目录的页码指向链表a的第一个结点，此页码信息称为头指针，通过它能找到整个链表；a.part1后面的线索就是指针域，指示下一个逻辑块在哪；a.part2的指针域指示后面不再有结点，称为尾结点。2/7/20237什么是链表？链表——一种重要且常用的数据结构，可动态地组织数据。链表不要求两个元素在物理上相邻，只要在元素结构中加一个指针项，用来指向下一个元素的地址便可。链表的基本概念2/7/20239链表的基本概念

什么是链表☞

链表的存储结构

2/7/2023102.3.1链表的基本概念链表的存储结构链表中的每个数据元素称为结点

每个结点至少包括2个域：

数据域——存放数据元素的值；

指针域——存放直接后继的地址,即指向后继结点链表正是通过每个结点的指针域将n个数据元素按其逻辑顺序链接在一起的链表中数据元素的逻辑顺序与其物理存储顺序不一定相同；2/7/202311利用结构体类型来实现链表structstudent{intnum;floatscore;

structstudent

*next;};78.51001numscorenext9010022/7/202313准备工作

malloc(intsize)——在内存中分配长度为size的连续空间

p=(structstudent*)malloc(sizeof(structstudent))建立、输出——动态链表malloc函数的返回值是一个指向分配空间的起始地址的指针。如果分配不成功，malloc函数返回NULLif(!(p=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);2/7/202314准备工作

free(void*p)——释放p指向的内存区动态链表——在执行的过程中从无到有建立一个链表，即一个个开辟结点和输入各结点数据，并建立前后链的关系静态链表——所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放建立、输出——动态链表2/7/202315链表创建就像穿一条珠链：一根线头能将整串珠链提起，称头指针head。开始时没有任何珠子，只有一根空线头head；第一颗珠子（头结点）接到head上，且其后有一根线头（指针域next）可接下一颗珠子；每次把新加入的珠子pNew（结点）接到最后一颗珠子q后的线头上。指针q指向每次最新接入的珠子,新珠子接到q的线头上：q->next=pNew。当不需接入珠子时，把最后一颗珠子后的线头q->next打上结：q->next=NULL。2/7/202317链表置空：head=NULL循环：插入结点设置尾结点：q->next=NULL图7.5“链表创建”的PAD图2/7/202318循环体中每插入一个结点需要做以下操作：准备新结点pNew：分配空间，为新结点赋值pNew插入链表pNew成为新的尾结点：q=pNew图7.6“对链表插入一个结点”的PAD图新结点pNew插入链表时有两种情况：若链表为空，则放到head后；否则，插入到尾结点q之后。2/7/2023197.2链表结点的查找由于单链表中结点只能通过前一个结点的指针域找到，得到结点的前驱很重要。2/7/202321图7.9通过指针p遍历链表各结点pheadNULLpheadNULL(a)p=head，从头开始遍历链表(b)p=p->next，p指向下一个结点pheadNULL(c)p==NULL时遍历完链表2/7/202322单链表只能从链表头head开始访问链表的各个结点，且只有前一个结点的指针域才能找到后一个结点。查找第i个结点：每访问过一个结点就让p指向下一个结点p=p->next，在访问完最后一个结点之前，沿着指针域的指向顺序遍历，直到找到第i个结点为止。2/7/202323

A

C

Ehead

Bqpq->next=s;s->next=p;ss->next=q->next;q->next=s;或者链表的插入2/7/202325printf(“请输入待插入字符\n");scanf("%c",&ch);s=(student*)malloc(LEN);s->data=ch;s->next=NULL;

p=head;while(p&&ch>p->data){q=p;p=p->next;}q->next=s;s->next=p;接受输入的数据，新生成一个新的结点SBs寻找合适的插入位置AheadCqps插入到p

和q之间链表的插入2/7/202326链表的删除ABCDEABCDE从动态链表中删去一个结点，只要撤销原来的链接关系，把它从链表中分离开来即可2/7/202329sppreNULLhead图

链表结点的删除×删除结点的语句为：{pre->next=s;free(p);}；链表结点删除后，用free()释放该结点占用的内存空间。或pre->next=p->next2/7/202330……101102110headqp103……101103110headqp104例

输入104表示要求删除学号为104的结点……q->next=p->next;2/7/202331printf("请输入想删除的字符\n");scanf("%c",&ch);p=head;while(p&&p->data!=ch){q=p;p=p->next;}if(p==NULL)printf("链表中无此字符\n");elseif(p==head)head=p->next;elseq->next=p->next;例.

输入104表示要求删除学号为104的结点未找到结点删除的是第一个结点删除的是中间结点、P=NULL

p走到表尾P->data=ch

找到要删除的结点2/7/2023327.5循环链表【例7-9】

猴子选大王。给一群猴子都做了编号，编号是1，2，3...n,这群猴子（n个）按照1~n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，依次下来，直到圈中只剩一只猴子，即为大王。【分析】以n=8,m=3为例，猴子选大王的过程：2/7/202333图7.15猴子选大王猴子出圈的顺序：►起始位置123456782/7/202334图7.15猴子选大王猴子出圈的顺序：123456782/7/202335图7.15猴子选大王猴子出圈的顺序：123456782/7/202336图7.15猴子选大王猴子出圈的顺序：312456782/7/202337图7.15猴子选大王猴子出圈的顺序：312456782/7/202338图7.15猴子选大王猴子出圈的顺序：312456782/7/202339图7.15猴子选大王猴子出圈的顺序：361245782/7/202340图7.15猴子选大王猴子出圈的顺序：361245782/7/202341图7.15猴子选大王猴子出圈的顺序：361245782/7/202342图7.15猴子选大王猴子出圈的顺序：361245782/7/202343图7.15猴子选大王猴子出圈的顺序：361245782/7/202344图7.15猴子选大王猴子出圈的顺序：361245782/7/202345图7.15猴子选大王猴子出圈的顺序：361524782/7/202346图7.15猴子选大王猴子出圈的顺序：361524782/7/202347图7.15猴子选大王猴子出圈的顺序：361524782/7/202348图7.15猴子选大王猴子出圈的顺序：361524782/7/202349图7.15猴子选大王猴子出圈的顺序：361524782/7/202350图7.15猴子选大王猴子出圈的顺序：361524782/7/202351图7.15猴子选大王猴子出圈的顺序：361528472/7/202352图7.15猴子选大王猴子出圈的顺序：361528742/7/202353图7.15猴子选大王猴子出圈的顺序：361528742/7/202354图7.15猴子选大王猴子出圈的顺序：361528472/7/202355猴子选大王的过程中，需要将其他的n-1个猴子从圈中删除。采用单链表存储每个猴子数据。为了便于循环报数，让最后一只猴子挨着第一只坐，即最后一个结点的指针域指向头结点：q->next=head，形成了循环链表。猴子选大王的过程就是循环链表的结点不断被删除的过程。结点删除后还是循环链表，只是缩小了。当圈中只剩下一个结点：pre->next==pre时，pre就是要找的猴王。2/7/202356单循环链表最后一个结点的指针域的指针又指回第一个结点的链表怎么样判断链表为空？if(head->next==head)

循环链表的操作和