《C语言程序设计：链表部分》由会员分享，可在线阅读，更多相关《C语言程序设计：链表部分（39页珍藏版）》请在金锄头文库上搜索。
1、 链表是一种常见的重要的数据结构链表是一种常见的重要的数据结构链表是一种常见的重要的数据结构链表是一种常见的重要的数据结构, ,是是是是动态动态动态动态地进行地进行地进行地进行存储分配的一种结构存储分配的一种结构存储分配的一种结构存储分配的一种结构, ,根据需要开辟内存单元。根据需要开辟内存单元。（与数组对比）（与数组对比） 链表的组成链表的组成：n头指针：存放一个地址，该地址指向一个元素头指针：存放一个地址，该地址指向一个元素 n结点：用户需要的实际数据和链接节点的指针结点：用户需要的实际数据和链接节点的指针n链表链表* *P285链表特点： 所有结点为相同结构体类型 至少一个成员为指针至少
2、一个成员为指针，该指针基类 型与链表结点的类型相同需解决问题：需解决问题： （1）建立链表）建立链表 （2）输出链表中各结点的值）输出链表中各结点的值 （3）在链表中插入一个结点）在链表中插入一个结点 （4）删除链表中的一个结点）删除链表中的一个结点 数组与链表的比较数组与链表的比较数组数组static int a10=1,2,3;3a01a1a2 a32a4a5a6a8a7a9 定义数组必须事先定义数组的长度，定义数组必须事先定义数组的长度，若使用时不需要这么多的存储空间，若使用时不需要这么多的存储空间，必将浪费内存必将浪费内存链表链表struct student int num; floa
3、t score; struct student *next; a,b,c,d;struct student *next;a.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextheadstruct student *head;a.next=&b;b.next=&c;c.next=&d;d.next=Null;Null1、数组对数据在内存的分配是静态的、数组对数据在内存的分配是静态的 链表对数据在内存中的分配是动态的链表对数据在内存中的分配是动态的2、malloc(size) 函数可在内存的动态存储区中分配到
4、一个长度函数可在内存的动态存储区中分配到一个长度为为size的连续空间。若成功返回值为该空间的起始地址。的连续空间。若成功返回值为该空间的起始地址。3、calloc(n,size) 函数可在内存的动态存储区中分配到函数可在内存的动态存储区中分配到n个长度个长度为为size的连续空间。若成功返回值为分配域空间的起始地址。的连续空间。若成功返回值为分配域空间的起始地址。4、free(prt) 函数释放由指针函数释放由指针prt指向的内存区为动态存储区指向的内存区为动态存储区#include 用结构体建立链表：用结构体建立链表：structstruct student student intint
5、num num； floatfloat score score； structstruct student *next student *next ； ; ; 其中成员其中成员numnum和和scorescore用来存放结点中的有用数据用来存放结点中的有用数据（用户需要用到的数据），（用户需要用到的数据），nextnext是是指针类型指针类型的成的成员，它指向员，它指向struct studentstruct student类型数据（这就是类型数据（这就是nextnext所在的结构体类型）所在的结构体类型）运行结果：1010189.51010390.01010785.0例例:建立一个如图建立一
6、个如图所示的静所示的静态链表，它由态链表，它由3个学生数个学生数据的结点组成。输出各结据的结点组成。输出各结点中的数据。点中的数据。#include #define NULL 0 struct student long num; float score; struct student *next; ;main() struct student a,b,c,*head,*p; a. num=10101; a.score=89.5; b. num=10103; b.score=90; c. num=10107; c.score=85; head=&a; a.next=&b; b.next=&c;
7、c.next=NULL; p=head; do printf(%ld %5.1fn,p-num,p-score); p=p-next; while(p!=NULL); n n内嵌结构体类型为本结构体类型的示例内嵌结构体类型为本结构体类型的示例#include struct lst intnum; struct lst * next ； ; 能指向能指向 struct lst 类型变量类型变量 abcnum nextnum nextnum nexta.num = 1;a.next = &b;b.num = 2;b.next = &c;c.num = 3;c.next = NULL;p = &a;
8、printf (%4d, p - num );main( ) struct lst a, b, c, *p;1230p1abcnum nextnum nextnum nexta.num = 1;a.next = &b;b.num = 2;b.next = &c;c.num = 3;c.next = NULL;p = &a;printf (%4d, p - num );main( )p = p - next;printf (%4d, p - num );1230p12 struct lst a, b, c, *p;需创建的单向链表结构需创建的单向链表结构 head头结点头结点 结点结点1结点结点
9、2尾结点尾结点101103105 0n动态链表动态链表 所谓建立动态链表是指所谓建立动态链表是指在程序执行过程中在程序执行过程中从无到有从无到有地建立起一个链表，即一个一个地开辟结点和输入各结地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系点数据，并建立起前后相链的关系例：构建一个3节点的单向动态链表，并输出链表中相关结点的数据之和。#include#includestruct node int num; struct node *next; ;main()struct node *p1,*p2,*p3;p1=(struct node *) malloc(size
10、of(struct node);p2=(struct node *) malloc(sizeof(struct node);p3=(struct node *) malloc(sizeof(struct node);p1-num=1;p2-num=2;p3-num=3;p1-next=p2;p2-next=p3;printf(%dn,p1-num+p1-next-num);n n动态开辟和释放存储单元的示例 #include #include main（ ） int *p=NULL;p = (int *) malloc (2);if ( p != NULL )printf (%4d, *p )
11、;free ( p );p = (int *) malloc ( sizeof(int) );if ( p != NULL )printf (%4dn, *p );free ( p );p38*p = 6;6*p = 38;38*p(int *)sizeofp2=p1;n链表的操作链表的操作链表建立链表建立heada.numa.scorea.nextp1p2p1指向新建立的结点指向新建立的结点p2指向当前结点指向当前结点b.numb.scoreb.nextp1p2c.numc.scorec.nextp1p2d.numd.scored.nextp1p2p2- next=Null;Nullp1=(
12、struct student *)malloc(sizeof(struct student);head=p1;p1=(struct student *)malloc(sizeof(struct student);p2-next=p1;p2=p1;p1=(struct student *)malloc(sizeof(struct student);p2-next=p1;p2=p1;p1=(struct student *)malloc(sizeof(struct student);p2-next=p1;p2=p1;对链表的删除对链表的删除删除的结点为头结点删除的结点为头结点a.numa.scor
13、ea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullheadp2p2=head;head=p2-next;heada.numa.scorea.nextb.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullhead删除链表中非头尾结点删除链表中非头尾结点p1=head;寻找要删除的结点：寻找要删除的结点：p2=p1;p1=p1-next;p1p2p1p2p1删除该结点删除该结点p2-next=p1-next;a.numa.scorea.nextb.numb.
14、scoreb.nextc.numc.scorec.nextd.numd.scored.nextNullhead删除尾结点：删除尾结点：for ( p1=head;p1-next!=Null;p1=p1-next) p2=p1;p1p2p2-next=Null;Nulln对链表进行插入操作对链表进行插入操作b.numb.scoreb.nextc.numc.scorec.nextd.numd.scored.nextNulla.numa.scorea.nextp0head插入头结点插入头结点p1headp0-next=p1;head=p0;p1插入尾结点插入尾结点d.numd.scored.next
15、p0b.numb.scoreb.nextc.numc.scorec.nextheada.numa.scorea.nextNullfor (p1=head;p1-next!=Null;p1=p1-next);p1p1-next=p0;Nullc.nextp0-next=Null;p2p1p2插入中间结点插入中间结点c.numc.scorec.nextp0寻找插入点：寻找插入点：p2=p1-next;p1=p2;p1p2插入新结点：插入新结点：a.numa.scorea.nextb.numb.scoreb.nextd.numd.scored.nextNullheadp0-next=p2;p1-ne
16、xt=p0;例例： 写一写一函数函数建立一个有建立一个有3名学生数据的名学生数据的单向动态单向动态链表。链表。n解题思路：解题思路：u定义定义3个指针变量：个指针变量：head,p1和和p2，它们都是用来，它们都是用来指向指向struct Student类型数据类型数据u用用malloc函数开辟第一个结点，并使函数开辟第一个结点，并使p1和和p2指向指向它它p1=p2=(struct Student*)malloc(LEN);p1p2n解题思路：解题思路：u读入一个学生的数据给读入一个学生的数据给p1所指的第一个结点所指的第一个结点p1scanf(%ld,%f,&p1-num,&p1-scor
17、e);p21010189.5n解题思路：解题思路：u读入一个学生的数据给读入一个学生的数据给p1所指的第一个结点所指的第一个结点u使使head也指向新开辟的结点也指向新开辟的结点headp1p2scanf(%ld,%f,&p1-num,&p1-score);1010189.5n解题思路：解题思路：u再开辟另一个结点并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.5n解题思路：解题思路：u再开辟另一个结点并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.5p1=(
18、struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010390n解题思路：解题思路：u使第一个结点的使第一个结点的next成员指向第二个结点成员指向第二个结点，即，即连接第一个结点与第二个结点连接第一个结点与第二个结点u使使p2指向刚才建立的结点指向刚才建立的结点headp1p21010189.5p2-next=p1;1010390n解题思路：解题思路：u使第一个结点的使第一个结点的next成员指向第二个结点成员指向第二个结点，即，即连接第一个结点与第二个结点连接第一个结点与第二个结点u使使p2指向刚才建立的结点指向刚才建
19、立的结点headp1p21010189.5p2-next=p1;1010390p2=p1;n解题思路：解题思路：u再开辟另一个结点并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.51010390n解题思路：解题思路：u再开辟另一个结点并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.51010390p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010785n解题思路：解题思路：u
20、使第使第二二个结点的个结点的next成员指向第成员指向第三三个结点个结点，即，即连接第二个结点与第三个结点连接第二个结点与第三个结点u使使p2指向刚才建立的结点指向刚才建立的结点headp1p21010189.510103901010785p2-next=p1;n解题思路：解题思路：u使第使第二二个结点的个结点的next成员指向第成员指向第三三个结点个结点，即，即连接第二个结点与第三个结点连接第二个结点与第三个结点u使使p2指向刚才建立的结点指向刚才建立的结点headp1p21010189.510103901010785p2-next=p1;p2=p1;n解题思路：解题思路：u再开辟另一个结点
21、并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.5101039010107850n解题思路：解题思路：u再开辟另一个结点并使再开辟另一个结点并使p1指向它，接着输入该指向它，接着输入该结点的数据结点的数据headp1p21010189.5101039010107850p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);n解题思路：解题思路：u输入的学号为输入的学号为0，表示建立链表的过程完成，该，表示建立链表的过程完成，该结点不应连接到链表中结点不应连
22、接到链表中headp1p21010189.5101039010107850NULLp2-next=NULL;#include #include #define LEN sizeof(struct Student)struct Student long num; float score; struct Student *next;int n;struct Student类型数据的长度类型数据的长度main() struct Student *pt; pt=creat(); printf(“nnum:%ld nscore:%5.1fn”, pt-num,pt-score); struct Stud
23、ent *creat(void) struct Student *head,*p1,*p2; n=0; p1=p2=( struct Student*) malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); head=NULL; while(p1-num!=0) n=n+1; if(n=1) head=p1; else p2-next=p1; p2=p1; p1=(struct Student*)malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); p2-next=NULL; return head;p1总是总
24、是开辟开辟新新结点结点p2总是总是指向最后结点指向最后结点用用p2和和p1连接连接两个两个结点结点例例： 编写一个输出链表的函数编写一个输出链表的函数print。100167.5100387100599NULLpn解题思路：解题思路：u输出输出p所指的结点所指的结点u使使p后移一个结点后移一个结点p100167.5100387100599NULLprintf(%ld %5.1fn,p-num,p-score);100167.5100387100599NULLp=p-next;解题思路：解题思路：u输出输出p所指的结点所指的结点u使使p后移一个结点后移一个结点printf(%ld %5.1fn,
25、p-num,p-score);p100167.5100387100599NULL解题思路：解题思路：u输出输出p所指的所指的新结点结点u使使p后移一个结点后移一个结点printf(%ld %5.1fn,p-num,p-score);p100167.5100387100599NULLp=p-next;解题思路：解题思路：u输出输出p所指的所指的新结点结点u使使p后移一个结点后移一个结点printf(%ld %5.1fn,p-num,p-score);p100167.5100387100599NULLp=p-next;解题思路：解题思路：u输出输出p所指的所指的新新结点结点u使使p后移一个结点后移一个结点printf(%ld %5.1fn,p-num,p-score);p相当于相当于p=NULL;void print(struct Student *p) printf(nThese %d records are:n,n); if(p!=NULL) do printf(%ld %5.1fn, p-num,p-score); p=p-next; while(p!=NULL);
