c ++链表_c遍历链表_判断链表是否有环(2)

例:int?*p1,*p2;p1malloc10*sizeofint;p2p1;……freep2?/*或者freep2*/malloc返回值赋给p1,又把p1的值赋给p2,所以此时p1,p2都可作为free函数的参数。malloc函数是对存储区域进行分配的。free函数是释放已经不用的内存区域的。所以由这两个函数就可以实现对内存区域进行动态分配并进行简单的管理了。三、单链表的建立有了动态内存分配的基础,要实现链表就不难了。所谓链表,就是用一组任意的存储单元存储线性表元素的一种数据结构。链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。所谓单链表,是指数据接点是单向排列的。一个单链表结点,其结构类型分为两部分:1、数据域:用来存储本身数据2、链域或称为指针域:用来存储下一个结点地址或者说指向其直接后继的指针。例:typedef struct nodechar name[20];struct node *link;stud;这样就定义了一个单链表的结构,其中char name[20]是一个用来存储姓名的字符型数组,指针*link是一个用来存储其直接后继的指针。定义好了链表的结构之后,只要在程序运行的时候爱数据域中存储适当的数据,如有后继结点,则把链域指向其直接后继,若没有,则置为NULL。

下面就来看一个建立带表头(若未说明,以下所指链表均带表头)的单链表的完整程序。#include#include /*包含动态内存分配函数的头文件*/#define N 10 /*N为人数*/typedef struct nodechar name[20];struct node *link;stud;stud * creatint n /*建立单链表的函数,形参n为人数*/stud *p,*h,*s; /* *h保存表头结点的指针,*p指向当前结点的前一个结点,*s指向当前结点*/int i; /*计数器*/ifhstud *mallocsizeofstudNULL /*分配空间并检测*/printf"不能分配内存空间!";exit0;h-name[0]'\0'; /*把表头结点的数据域置空*/h-linkNULL; /*把表头结点的链域置空*/ph; /*p指向表头结点*/fori0;iN;I++ifs stud * mallocsizeofstudNULL /*分配新存储空间并检测*/printf"不能分配内存空间!";exit0;p-links; /*把s的地址赋给p所指向的结点的链域,这样就把p和s所指向的结点连接起来了*/printf"请输入第%d个人的姓名",i+1;scanf"%s",s-name; /*在当前结点s的数据域中存储姓名*/s-linkNULL;ps;returnh;mainint number; /*保存人数的变量*/stud *head; /*head是保存单链表的表头结点地址的指针*/numberN;headcreatnumber; /*把所新建的单链表表头地址赋给head*/这样就写好了一个可以建立包含N个人姓名的单链表了。

写动态内存分配的程序应注意,请尽量对分配是否成功进行检测。四、单链表的基本运算建立了一个单链表之后,如果要进行一些如插入、删除等操作该怎么办?所以还须掌握一些单链表的基本算法,来实现这些操作。单链表的基本运算包括:查找、插入和删除。下面我们就一一介绍这三种基本运算的算法,并结合我们建立单链表的例子写出相应的程序。1、查找对单链表进行查找的思路为:对单链表的结点依次扫描,检测其数据域是否是我们所要查好的值,若是返回该结点的指针,否则返回NULL。c ++链表因为在单链表的链域中包含了后继结点的存储地址,所以当我们实现的时候,只要知道该单链表的头指针,即可依次对每个结点的数据域进行检测。以下是应用查找算法的一个例子:#include#include#include /*包含一些字符串处理函数的头文件*/#define N 10typedef struct nodechar name[20];struct node *link;stud;stud * creatint n /*建立链表的函数*/stud *p,*h,*s;int i;ifhstud *mallocsizeofstudNULLprintf"不能分配内存空间!";exit0;h-name[0]'\0';h-linkNULL;ph;fori0;iN;I++ifs stud * mallocsizeofstudNULLprintf"不能分配内存空间!";exit0;p-links;printf"请输入第%d个人的姓名",i+1;scanf"%s",s-name;s-linkNULL;ps;returnh;stud * searchstud *h,char *x /*查找链表的函数,其中h指针是链表的表头指针,x指针是要查找的人的姓名*/stud *p; /*当前指针,指向要与所查找的姓名比较的结点*/char *y; /*保存结点数据域内姓名的指针*/ph-link;whilep!NULLyp-name;ifstrcmpy,x0 /*把数据域里的姓名与所要查找的姓名比较,若相同则返回0,即条件成立*/returnp; /*返回与所要查找结点的地址*/else pp-link;ifpNULLprintf"没有查找到该数据!";mainint number;char fullname[20];stud *head,*searchpoint; /*head是表头指针,searchpoint是保存符合条件的结点地址的指针*/numberN;headcreatnumber;printf"请输入你要查找的人的姓名:";scanf"%s",fullname;searchpointsearchhead,fullname; /*调用查找函数,并把结果赋给searchpoint指针*/2、插入(后插)假设在一个单链表中存在2个连续结点p、q(其中p为q的直接前驱),若我们需要在p、q之间插入一个新结点s,那么我们必须先为s分配空间并赋值,然后使p的链域存储s的地址,s的链域存储q的地址即可。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-33457-2.html