搜索
1第十一章链表2例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。结构的概念与应用0123456784321结点12345673依上图有7个结点(x1,y1)(x2,y2)(x6,y6)(x7,y7)为了表示这种既有数据又有指针的情况，引入结构这种数据类型。411.7用指针处理链表链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。动态性体现为：链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；51249A1356B1475C1021DNull1、链表中的元素称为“结点”，每个结点包括两个域：数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL)。Head1249135614751021结点里的指针是存放下一个结点的地址6链表中结点的定义链表是由结点构成的，关键是定义结点;链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；递归函数的定义也违反了先定义再使用；这是C语言程序设计上的两大特例7链表的基本操作对链表的基本操作有：（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k’，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k’成为ki-1的后继、ki的前驱.8（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继.(5)打印输出9一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据9910189.599103909910785numScorenextnext是structstudent类型中的一个成员，它又指向structstudent类型的数据。换名话说：next存放下一个结点的地址1011.7.2简单链表#defineNULL0structstudent{longnum;floatscore;structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do{printf(%ld%5.1f\n,p-num,p-score);p=p-next;}while(p!=NULL);}例11.7建立和输出一个简单链表各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”1111.7.3处理动态链表所需的函数C语言使用系统函数动态开辟和释放存储单元1.malloc函数函数原形：void*malloc(unsignedintsize);作用：在内存的动态存储区中分配一个长度为size的连续空间。返回值：是一个指向分配域起始地址的指针（基本类型void）。执行失败：返回NULL12函数原形:void*calloc(unsignedn,unsignedsize);作用：在内存动态区中分配n个长度为size的连续空间。函数返回值：指向分配域起始地址的指针执行失败：返回null主要用途：为一维数组开辟动态存储空间。n为数组元素个数，每个元素长度为size2.calloc函数133.free函数函数原形：voidfree(void*p);作用：释放由p指向的内存区。P:是最近一次调用calloc或malloc函数时返回的值。free函数无返回值动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足而出现故障。14结点的动态分配ANSIC的三个函数(头文件malloc.h)void*malloc(unsignedintsize)void*calloc(unsignedn,unsignedsize)voidfree(void*p)C++的两个函数new类型（初值）delete[]指针变量/*[]表示释放数组，可有可无）*/使用new的优点：可以通过对象的大小直接分配，而不管对象的具体长度是多少（p340例14.10）1511.7.4建立动态链表基本方法:三个结点（头结点head、尾结点NULL和待插入结点P）第一步：定义头结点head、尾结点p2和待插入结点p1，待插入的结点数据部分初始化；第二步：该结点被头结点、尾结点同时指向。P1=p2=(structstudent*)malloc(LEN);头指针部分为空，head=NULL;第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）.P2-next=P1;P2=P1;最后:P2-next=NULL;*head,*p1,*p2使用malloc(LEN)P2-next=NULL;1611.7.4建立动态链表9910189.5headP1p21.任务是开辟结点和输入数据2.并建立前后相链的关系待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向.17图11.149910189.5headp29910390p19910189.5headp29910390p1(a)(b)p1重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）P2-next指向p1新开辟的结点。18图11.14head9910189.5p1p29910390(c)P2指向新结点p2=p119图11.159910189.59910189.5p29910785p1head9910189.59910189.5p29910785p1head(a)(b)20图11.1699103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.521例11.8建立一个有3名学生数据的单向动态链表#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;structstudent*creat(void){structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);head=NULL;结构体类型数据的长度，sizeof是“字节数运算符”定义指针类型的函数。带回链表的起始地址开辟长度为LEN的内存区P1,p2是指向结构体类型数据的指针变量，强行转换成结构体类型假设头指向空结点22续while(p1-num!=0){n=n+1;/*n是结点的个数*/if(n==1)head=p1;elsep2-next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);}p2-next=NULL;return(head);}//返回链表的头指针算法：p1指向新开的结点:p1=(stuctstudent*)malloc(LEN);p1的所指向的结点连接在p2所指向结点后面，用p2-next=p1来实现。p2指向链表中最后建立的结点，:p2=p1;头指针指向p1结点P1开辟的新结点链到了p2的后面P1继续开辟新结点给新结点赋值此2311.7.5输出链表链表遍历1.单向链表总是从头结点开始的；2.每访问一个结点，就将当前指针向该结点的下一个结点移动：p=p-next;3.直至下一结点为空P=NULL24图11.18headpP’P’NULL25例题9voidprint(structstudent*head){structstudent*p;printf(\nNow,These%drecordsare:\n,n);p=head;if(head!=NULL)do{printf(%ld%5.lf\n,p-num,p-score);p=p-next;}while(p!=NULL);}2611.7.6对链表的删除操作删除结点原则：不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。两种情况：1、要删的结点是头指针所指的结点则直接操作；2、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点27链表中结点删除需要由两个临时指针：P1:判断指向的结点是不是要删除的结点（用于寻找）；P2:始终指向P1的前面一个结点；28图11.19ABDECABDEC(a)(B)29图11.2099101headp19910399107NULL（a）(b)99101head9910399107NULLp2p1原链表P1指向头结点P2指向p1指向的结点。P1指向下移一个结点。30图11.2099101head9910399107NULLp199101head9910399107NULLp2p1(c)(d)经判断后，第1个结点是要删除的结点，head指向第2个结点，第1个结点脱离。经P1找到要删除的结点后使之脱离。31例题10structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;if(head==NULL){printf(\nlistnull!\n);gotoend;}p1=head;while(num!=p1-num&&p1-next!==NULL){p2=p1;p1=p1-next;}if(num==p1-num){if(p1==head)head=p1-next;elsep2-next=p1-next;printf(delete:%ld\n,num);n=n-1;}elseprintf(%ldnotbeenfound!\n,num);end:return(head);}找到了没找到3211.7.7对链表的插入操作插入结点：将一个结点插入到已有的链表中插入原则：1、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置实现方法：应该有一个插入位置的查找子过程共有三种情况：1、插入的结最小2、插入的结点最大3、插入的结在中间33操作分析同删除一样，需要几个临时指针：P0:指向待插的结点;初始化：p0=数组stu;P1:指向要在P1之前插入结点；初始化:p1=head;P2:指向要在P2之后插入结点；插入操作：当符合以下条件时：p0-num与p1-num比较找位置if(p0-nump1-num)&&(p1-next!=NULL)则插入的结点不在p1所指结点之前；指针后移，交给p2；p1=p1-next;p2=p1;则继续与p0指向的数组去比，直到（p1-next!=NULL)为止。否则有两种情况发生：if(head==p1)head=p0;p0-next=p1插到原来第一个结点之前；elsep2-next=p0;p0-next=p1;插到p2指向的结点之后；还有另外一种情况：插到最后的结点之后；p1-next=p0;p0-next=NUL