《关于单链表的操作》由会员分享，可在线阅读，更多相关《关于单链表的操作（7页珍藏版）》请在金锄头文库上搜索。
1、关于单链表的操作单向链表结构描述示例： struct linklist int data；struct linklist *next； ； struct linklist *head；单链表的建立 在链表的操作中用到的几个函数： (1)malloc（size）在内存的动态存储区申请一个长度为 size 字节的连续 空间。并将此存储空间的起始地址作为函数值返回。malloc 函数的原型为：void *malloc(unsigned int size) 函数值为指针（地址），这个指针是指向 void 类型的，也就是不规定指向 任何具体的类型。如果内存缺乏足够大的空间进行分配，则 malloc 的函
2、数值为 “空指针”。 (2)calloc（n， size）在内存的动态存储区申请 n 个长度为 size 字节的 连续空间，函数返回值为分配空间的首地址。若此函数未被成功执行，函数返 回值为 0。函数返回值为该空间的首地址。其函数原型为：void *calloc(unsigned int n，unsigned int size) (3)free（p）释放由指针 p 所指向的存储单元，而所释放的存储单元的大 小是最近一次调用 malloc（）函数或 calloc（）函数时所申请的存储空间。fr ee 函数的原型为：void free(void *ptr) 系统可以回收所释放的空间，另行分配作为它
3、用。 (4)realloc 函数。其函数的原型为：void realloc(void *ptr，unsigned int size) 其作用是将 ptr 所指向的存储区（原先用 malloc 函数分配的）的大小改为 size 个字节。可以使原先分配区扩大和缩小。它的函数返回值是一个指针，即 新的存储区的首地址。 例 1 使用表首插入法表首插入法建立链表。 表首插入法建立链表，这种方法的特点是：新产生的结点作为新的表头插 入链表。 #include void main(） struct linklist int data；struct linklist *next； ； struct linkl
4、ist *head，*p； /*head 头指针，p 申请单元指针*/ head=NULL； /*空链表*/*申请空间，并将指针 p 强制转换成所指向的结构体类型*/ p=(struct linklist*)malloc(sizeof(struct linklist)； scanf(“%d“， scanf（“%d“， if(head=NULL) printf(“n list null!n“); return(head); p1=head; while(num!=p1-num p1=p1-next; if(p1!=NULL)printf(“find:%d,%6.2fn“,p1-num, p1-s
5、core); else printf(“%d not found!n“,num); 说明：一般查找操作总是与其它相关操作相联系的。如：插入、删除操作 等，故在查找的过程中，设置了两个工作指针 p2 与 p1，p1 指向要查找的结点 ，p2 指向要查找结点的左边的一个结点。以方便进行插入和删除操作。 例 3 假设链表结点信息包括学生学号、成绩，结点定义如下： typedef struct plist int no; float score; struct plist *next; plist; 设已经建立了两个具有上述结构的链表，且两个链表都是以学号升序排列 ，要求编写一个函数，将两个链表（按升
6、序）合并。 算法： 函数应有两个链表指针形参：p1, p2 指向它们各自的表头； 最初链表的头指针 head=NULL，新链表的当前结点指针 p=NULL； 产生新链表的头结点； 当两个链表的指针均没指向表尾，则依次选择两个链表中的结点并入到 新链表中； 当某一个链表已到表尾，则将另一个链表的剩余部分直接链接到新链表 的表尾。 完成此功能的程序为： plist *merge(plist *p1, plist *p2) /*p1 与 p2 分别为两个链表的头指针*/ plist *p, *head; if(p1-nono ) head=p=p1; p1=p1-next; /*产生新链表的头结点*
7、/ else head=p=p2; p2=p2-next; while(p1!=NULL /*p1 指示的结点并入到新链表*/ p=p1; /*p1 指向新链表的表尾*/ p1=p1-next; /*p1 指向后继*/ else p-next=p2; /*p2 指示的结点并入到新链表*/ p=p2; p2=p2-next; /*p2 指向后继*/ if(p1!=NULL) /*p1 没有到达表尾*/ p-next=p1; /*p1 指示的链表后部分链接新链表的表尾*/ else p-next=p2; /*p2 指示的链表后部分链接新链表的表尾*/ return head; 循环 while(p
8、1!=NULL &p2!=NULL)终止时，表示有 p1 指示的链表为空或 p 2 所指示的链表为空，再只将另一非空的链表（p2 指示的链表或 p1 所指示的链 表）链入到新链表中即可。 例 4 用链表实现若干学生的成绩处理，求出学生人数、每个学生的总成 绩及平均成绩。 算法： 每个学生包括姓名与 8 门课程成绩，用一链表存放，总成绩、平均成绩 亦存放于链表。 若输入学生姓名为“x”，则数据结束。建立成绩链表的同时求出学生人 数(链表结点数)、每个学生的总成绩及平均成绩。 建立成绩链表和输出成绩链表，分别用函数完成。 程序如下： #include #define NULL 0 struct l
9、inkllist char *name；float cj8；float tcj， avcj；struct linklist *next； ； int num； void main(） struct linklist *creathead（）；void print（）；struct linklist *h；h=creathead( )；/*调用 creathead()函数建立成绩链表，返回头指针*/printf（“%d 个学生成绩数据： n“， num）；print（h）； /*调用 print（ ）函数输出成绩链表*/ struct linklist *creathead（） /*头插法建立成
10、绩链表*/ struct linklist *head，*p；int i；num=1；p=（struct linklist *）malloc（sizeof（struct linklist）；scanf（“%s“，p-name）；p-tcj=0；for（i=0；icji）；p-tcj+=p-cji； p-avcj=p-tcj/8； head=NULL； while（strcmp（p-name，“x“）！=0） p-next=head；head=p；num+； p=（struct linklist *）malloc（sizeof（struct linklist） ；scanf（“%s“，p-nam
11、e）；if（p-name！=x）for（i=0；icji）；p-tcj+=p-cji； p-avcj=p-tcj/8；return（head）； void print（struct linklist *head） /*输出成绩链表*/ struct linklist *p；p=head；while（p！=NULL）printf（“%s“， p-name）；for（i=0； icji）；printf（“%8.2f， %8.2f“， p-tcj， p-avcj）；p=p-next； 注意两点： 将链表作为参数传递进函数，只需将链表表头指针传递进函数。函数的 形参对应实参的头指针。 对链表的访问用循环条件控制，循环的条件是结点的指针域非空。
