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

会计学1C语言设计实例教程动态组织数据2023/1/172主要内容1.建立链表的过程

2.链表结点的查找

3.链表结点的插入

4.链表结点的删除

5.循环链表

第1页/共57页2023/1/1737.1建立链表的过程看杂志时碰到有篇文章3页不够放，4页又空着太多。怎么办？编辑往往先给这篇文章（称做a）排3页(且称这3页为a.part1)，接着排其他文章，等什么时候有空的页面还够安排a剩下的部分(称它为a.part2)时，就把a.part2排进去。第2页/共57页2023/1/1747.1建立链表的过程这样文章a在排版时被分成了不连续的两块，读者怎样找到第二部分呢？编辑在a.part1的末尾加进了一个线索“下接XX页”，读者顺着线索很容易就找到了a.part2。所以a.part1放的不仅有文章本身，还有指示下一部分在哪的线索。通过这个线索，a.part1和a.part2就联系在一起了。第3页/共57页2023/1/175那a.part2的后面还有没有另外一部分呢？杂志的每篇文章的最后都有一个特殊的符号，看到这个符号就知道这已经是最后了。厚厚的一本书中，又怎样找到文章a呢？翻翻目录就知道了，那里有文章a所在页码的信息。第4页/共57页2023/1/176文章a......a.part1......a.part2文章axx页目录下接xx页完a.part1和a.part2组成了由两个结点构成的链表：目录的页码指向链表a的第一个结点，此页码信息称为头指针，通过它能找到整个链表；a.part1后面的线索就是指针域，指示下一个逻辑块在哪；a.part2的指针域指示后面不再有结点，称为尾结点。第5页/共57页2023/1/177链表的基本概念☞什么是链表

链表的存储结构

第6页/共57页2023/1/178什么是链表？链表——一种重要且常用的数据结构，可动态地组织数据。链表不要求两个元素在物理上相邻，只要在元素结构中加一个指针项，用来指向下一个元素的地址便可。链表的基本概念第7页/共57页2023/1/179链表的基本概念

什么是链表☞

链表的存储结构

第8页/共57页2023/1/17102.3.1链表的基本概念链表的存储结构链表中的每个数据元素称为结点

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

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

指针域——存放直接后继的地址,即指向后继结点链表正是通过每个结点的指针域将n个数据元素按其逻辑顺序链接在一起的链表中数据元素的逻辑顺序与其物理存储顺序不一定相同；第9页/共57页2023/1/1711

head:

头指针，类型为指向结构体的指针，存放链表第一个元素的地址；

结点：链表中的每一个元素称为一个结点；

NULL：表示空指针，经常用来表示；

表尾：链表的最后一个结点，不指向任何元素；链表中各个元素的地址并不连续DA0012B4152C14302160head2160001241521430链表第10页/共57页2023/1/1712利用结构体类型来实现链表structstudent{intnum;floatscore;

structstudent

*next;};78.51001numscorenext901002第11页/共57页2023/1/1713准备工作

malloc(intsize)

——

在内存中分配长度为size的连续空间

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

free(void*p)

——

释放p指向的内存区动态链表——

在执行的过程中从无到有建立一个链表，即一个个开辟结点和输入各结点数据，并建立前后链的关系静态链表——

所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放建立、输出——动态链表第13页/共57页2023/1/1715例.建立有1个学生数据单链表typedef

structstudent{intnum;floatscore;student*next;}student;

student*head,*p;head=NULL;p=(student*)malloc(sizeof(student));scanf(“%d,%f”,&p->num,&p->score);p->next=NULL;head=p;headpp110195.510287第14页/共57页2023/1/1716链表创建就像穿一条珠链：一根线头能将整串珠链提起，称头指针head。开始时没有任何珠子，只有一根空线头head；第一颗珠子（头结点）接到head上，且其后有一根线头（指针域next）可接下一颗珠子；每次把新加入的珠子pNew（结点）接到最后一颗珠子q后的线头上。指针q指向每次最新接入的珠子,新珠子接到q的线头上：q->next=pNew。当不需接入珠子时，把最后一颗珠子后的线头q->next打上结：q->next=NULL。第15页/共57页2023/1/1717链表置空：head=NULL循环：插入结点设置尾结点：q->next=NULL图7.5“链表创建”的PAD图第16页/共57页2023/1/1718循环体中每插入一个结点需要做以下操作：准备新结点pNew：分配空间，为新结点赋值pNew插入链表pNew成为新的尾结点：q=pNew图7.6“对链表插入一个结点”的PAD图新结点pNew插入链表时有两种情况：若链表为空，则放到head后；否则，插入到尾结点q之后。第17页/共57页2023/1/1719与数组不同，链表中每个元素的存储空间都需在使用前在程序中显式地分配，并用指针指向所分配空间的首地址，用完以后再显式地释放每个元素占用的空间.需要动态地分配和释放内存空间。

malloc(intsize)free(void*p)在TurboC中的头文件是stdlib.h，在VC中是malloc.h文件。第18页/共57页2023/1/17207.2链表结点的查找由于单链表中结点只能通过前一个结点的指针域找到，得到结点的前驱很重要。第19页/共57页2023/1/1721图7.9通过指针p遍历链表各结点pheadNULLpheadNULL(a)p=head，从头开始遍历链表(b)p=p->next，p指向下一个结点pheadNULL(c)p==NULL时遍历完链表第20页/共57页2023/1/1722单链表只能从链表头head开始访问链表的各个结点，且只有前一个结点的指针域才能找到后一个结点。查找第i个结点：每访问过一个结点就让p指向下一个结点p=p->next，在访问完最后一个结点之前，沿着指针域的指向顺序遍历，直到找到第i个结点为止。第21页/共57页2023/1/1723问题：输入数据的同时，将数据插入到链表中，并且保持链表中数据有序分析：第一个：接到head后面第二个：查找合适的插入位置插入，并保持链表的前后链第三个……第N个……7.3链表结点的插入第22页/共57页2023/1/1724

A

C

Ehead

Bqpq->next=s;s->next=p;ss->next=q->next;q->next=s;或者链表的插入第23页/共57页2023/1/1725printf(“请输入待插入字符\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之间链表的插入第24页/共57页2023/1/1726考虑插入结点时的几种特殊情况插入后为第一个结点插入后为最后一个结点

A

C

Eheadsp

A

C

Eheadsq链表的插入第25页/共57页2023/1/17277.4链表结点的删除在数组操作中，无论是插入元素还是删除元素都有大量的数据需要移动链表中删除链表结点只要对个别结点的指针做一些调整即可。删除结点时要保证不破坏链表原来的连接关系，并且先要找到结点的前驱。第26页/共57页2023/1/1728链表的删除ABCDEABCDE从动态链表中删去一个结点，只要撤销原来的链接关系，把它从链表中分离开来即可第27页/共57页2023/1/1729sppreNULLhead图

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

输入104表示要求删除学号为104的结点……q->next=p->next;第29页/共57页2023/1/1731printf("请输入想删除的字符\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

找到要删除的结点第30页/共57页2023/1/17327.5循环链表【例7-9】

猴子选大王。给一群猴子都做了编号，编号是1，2，3...n,这群猴子（n个）按照1~n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，依次下来，直到圈中只剩一只猴子，即为大王。【分析】以n=8,m=3为例，猴子选大王的过程：第31页/共57页2023/1/1733图7.15猴子选大王猴子出圈的顺序：►起始位置12345678第32页/共57页2023/1/1734图7.15猴子选大王猴子出圈的顺序：12345678第33页/共57页2023/1/1735图7.15猴子选大王猴子出圈的顺序：12345678第34页/共57页2023/1/1736图7.15猴子选大王猴子出圈的顺序：31245678第35页/共57页2023/1/1737图7.15猴子选大王猴子出圈的顺序：31245678第36页/共57页2023/1/1738图7.15猴子选大王猴子出圈的顺序：31245678第37页/共57页2023/1/1739图7.15猴子选大王猴子出圈的顺序：36124578第38页/共57页2023/1/1740图7.15猴子选大王猴子出圈的顺序：36124578第39页/共57页2023/1/1741图7.15猴子选大王猴子出圈的顺序：36124578第40页/共57页2023/1/1742图7.15猴子选大王猴子出圈的顺序：36124578第41页/共57页2023/1/1743图7.15猴子选大王猴子出圈的顺序：36124578第42页/共57页2023/1/1744图7.15猴子选大王猴子出圈的顺序：36124578第43页/共57页2023/1/1745图7.15猴子选大王猴子出圈的顺序：36152478第44页/共57页2023/1/1746图7.15猴子选大王猴子出圈的顺序：36152478第45页/共57页2023/1/1747图7.15猴子选大王猴子出圈的顺序：36152478第46页/共57页2023/1/1748图7.15猴子选大王猴子出圈的顺序：36152478第47页/共57页2023/1/1749图7.15猴子选大王猴子出圈的顺序：36152478第48页/共57页2023/1/1750图7.15猴子选大王猴子出圈的顺序：36152478第49页/共57页2023/1/1751图7.15猴子选大王猴子出圈的顺序：36152847第50页/共57页2023/1/1752图7.15猴子选大王猴子出圈的顺序：36152874第51页/共57页2023/1/175