单向链表操作资料.doc

/* =============================================== 目的:学****单向链表的创建、删除、插入(无序、有序)、输出、排序(选择、插入、冒泡)、反序================================================ */ /* 单向链表的图示: ---->[NULL] head 图1 :空链表---->[p1]---->[p2]...---->[pn]---->[NULL] head p1->next p2->next pn->next 图2 :有 N 个节点的链表*/ #include <> #include <> #define NULL 0 #define LEN sizeof(struct student) struct student { long num; /* 学号*/ float score; /* 分数,其他信息可以继续在下面增加字段*/ struct student *next; /* 指向下一节点的指针*/ }; int n; /* 节点总数*/ /* ========================== 功能:创建节点返回:指向链表表头的指针========================== */ struct student *Create() { struct student *head; /* 头节点*/ struct student *p1=NULL; /*p1 保存创建的新节点的地址*/ struct student *p2=NULL; /*p2 保存原链表最后一个节点的地址*/ n= 0; /* 创建前链表的节点总数为 0 :空链表*/ p1= (struct student *)malloc(LEN); /* 开辟一个新节点*/ p2= p1; /* 如果节点开辟成功,则 p2 先把它的指针保存下来以备后用*/ if (p1 == NULL) /* 节点开辟不成功*/ { printf("\nCann't create it, try it again ina moment!\n"); return NULL; } else /* 节点开辟成功*/ { head = NULL; /* 开始 head 指向 NULL*/ printf("Please input %d node -- num,score: ",n+1); scanf("%ld,%f",&(p1->num),&(p1->score)); /* 录入数据*/ } while(p1->num != 0) /* 只要学号不为 0 ,就继续录入下一个节点*/ {n += 1; /* 节点总数增加 1个*/ if (n==1) /* 如果节点总数是 1 ,则 head 指向刚创建的节点 p1*/ { head = p1; /* 注意: 此时的 p2 就是 p1, 也就是 p1->next 指向 NULL 。这样写目的是与下面 else 保持一致。*/ p2->next = NULL; } else { p2->next = p1; /* 指向上次下面刚开辟的节点*/ } p2= p1; /*把 p1 的地址给 p2 保留,然后 p1 去产生新节点*/ p1= (struct student *)malloc(LEN); printf("Please input %d node -- num,score: ",n+1); scanf("%ld,%f",&(p1->num),&(p1->score)); } p2->next = NULL; /* 此句就是根据单向链表的最后一个节点要指向 NULL*/ free(p1); /* 释放 p1 。用 malloc() 、 calloc() 的变量都要 free()*/ p1= NULL; /* 特别不要忘记把释放的变量清空置为 NULL, 否则就变成" 野指针" ,即地址不确定的指针。*/ return head; /* 返回创建链表的头指针*/ } /* =========================== 功能:输出节点返回: void =========================== */ void Print(struct student *head) { struct student *p; printf("\nNow , These %d records are:\n",n); p= head; if(head != NULL) /* 只要不是空链表,就输出链表中所有节点*/ { printf("head is %o\n", head); /* 输出头指针指向的地址*/ d