搜索
链表●要点●链表的创建●链表的输出●链表的插入●链表的删除2一、动态内存分配函数1.malloc()函数原型在stdlib.h中1)调用方式void*malloc(unsignedsize)2)功能在内存中分配size个字节的存储空间，并返回指向分配存储区起始地址的指针；如果不能获得需要的存储空间，将返回空指针。注：在把返回值赋给具有一定数据类型的指针变量时，应对返回值作强制类型转换。3例：为1000个字符动态分配内存char*base_ptr;base_ptr=(char*)malloc(1000);4structdata{charname[10];intno;};structdata*ptr;ptr=(structdata*)malloc(sizeof(structdata));if(ptr==NULL){puts(“outofmemory\n”);exit(1);}5①(structdata*)返回结构指针②sizeof(structdata)通知malloc分配足够的内存给structdata的每一个结构成员③ptr接受返回的指针④如果内存heap区已满，则返回NULL⑤exit()函数被定义在process.h或者stdlib.h中0:程序正常终止非0：程序非正常终止例：(1117)62.calloc()函数原型在stdlib.h中1)调用方式void*calloc(unsignedn,unsignedsize)2)功能分配n个具有size个字节的存储空间，并返回一个指向被分配内存起始地址的指针；如果没有足够的内存满足要求，则返回一个空指针例：(1118)例：(1119)73.free()函数原型在stdlib.h中1)调用方式voidfree(void*ptr)2)功能释放由ptr指向的内存空间，并将它返回给堆注：free()只能由前面动态内存分配函数中所分配地址的那个指针来调用例：(1120)8二、链表1.概念是由指针链接的一种动态数据结构结点(node)：构成链表的数据项，由数据域和指针组成头指针：head指向链表的起始结点结构之内必须说明一个指向自己的结构指针例：structNode{intdata;structNode*next;};2.单向链表的结构6185237054∧head头结点是在链表的起始结点之前附加的一个结点.●2.3.1线性链表带头结点的单链表123∧head123∧head头结点单链表带头结点的单链表∧head空表∧head空表head-next==Null头结点有两个优点：⑴由于起始结点的位置被存放在头结点的指针域中，故在链表的第一个位置上的操作与表中其他位置上操作一致，无须进行特殊处理。⑵无论链表是否为空，其头指针都是指向头结点的非空指针，故此空表和非空表的处理也统一了。起始结点structNode{intdata;structNode*next;};structNode*head;head63head-next(head-next)-data起始结点的地址6链表的访问120structNode*p;p=head-next;head63120p=p-next;p=head-next;pstructNode*p;head63120p=p-next;p=p-next;pstructNode*p;p=head-next;head63120p=p-next;p=p-next;pp=p-next;structNode*p;p=head-next;head63120p-next==NULL表明p到达表尾结点p=p-next;p=p-next;p=0空指针p=p-next;structNode*p;p=head-next;head63120对于线性链表，可以从头指针(head)开始，沿各结点的指针扫描到链表中的所有结点。*将当前结点的元素值赋给xpx=p-data;ListNode*p;intx;x6head63120*将x赋给当前结点，修改当前结点的元素值px=10;p-data=x;structNode*p;intx;head31206101创建单链表由数组中的数据创建一个带头结点的单链表,返回头指针或者NULL.算法设计p总是指向表尾结点从数组中获取数据，申请、填装结点，将新结点插入到p所指结点后面，p指向新结点。●3链表的基本运算linklist.hstructNode*create_LinkList(inta[],intn)2输出表中数据结构：带头结点的单链表算法设计p从起始结点开始，沿指针扫描各结点，并输出数据域的值。linklist.hvoidprint_LinkList(structNode*head)3释放链表空间释放带头结点的单链表中所有结点的空间，即操作后链表不存在了。算法设计从前往后逐个释放结点空间。p指向第一个结点，修改头指针删除p所指结点，释放p所指空间。重复此步骤。linklist.hvoidfree_LinkList(structNode*head)linklist-1.c4插入操作⑴后插结点设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p后面。a1a2an∧head…aiai+1……xps①s-next=p-next;②p-next=s;①②注意两个指针的操作顺序不能交换，否则p结点后面的结点将被断开，不能实现正确插入。⑵前插结点设s指向待插入的值为x的新结点，将*s插入到结点ai前面。由于单链表结点结构是单向后指，所以必须先找到ai的前驱结点ai-1，然后再完成在ai-1后面插入*s。a1a2an∧headai-1ai……xp②③s①前插入结点算法①找到第i-1个结点，若存在，继续进行，否则结束。②申请、填装新结点。③将新结点插入，结束。5删除结点设s指向单链表中某个结点，删除s，首先要找到s的前驱结点p，指针操作如下：a1ai+1an∧headai-1ai……psp-next=s-next;free(s);？删除链表中第i个结点的基本步骤如下：①找到第i-1个结点；若存在，继续进行，否则结束。②若存在第i个结点，则继续③，否则结束。③删除第i个结点，结束。通过前面的基本操作：⑴在单链表上插入、删除结点，必须知道其前驱结点。⑵单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。