链表及字符串处理函数集合

#include"linkedList.h" /* 功能：节点插入算法，在节点p之前插入值为e的节点 返回值：返回指向链表首节点的指针 */ Lnode *list_insert(Lnode *first,Lnode *p,int e) { Lnode *q,*s; //q为节点p的前驱结点，s为将要插入的新节点 s = (Lnode *)malloc(sizeof(Lnode)); //给新节点分配空间，构造新节点 s ->data = e; s ->next = NULL; if(first == NULL) //空链表 { first = s; return first; } if(p == first) //p是首节点，将s节点插入在链表首节点之前 { //s->next = p; s->next = first; first = s; } else //节点p是非首节点 { q = first; while(q -> next != p) //查找p的前驱结点 q = q ->next; s -> next = p; q -> next = s; } return first; } /* 功能：在链表first中，查找值为e的节点 返回值：返回指向节点值为e的节点的指针 */ Lnode *list_find(Lnode *first,int e) { Lnode *p; //要查找的节点值为e的节点 p = first; if(first == NULL) //空链表 { return NULL; } else { p = first; while(p) { if(p -> data == e) return p; //查找成功，返回指针p p = p -> next; //继续向后查找 } return NULL; //查找失败 } } /* 功能：在链表first中，删除值为e的节点，如果找到节点，物理删除 返回值：返回链表首指针first */ Lnode *list_delete(Lnode *first,int e) { Lnode *q,*p; //q为将要删除节点的前驱结点，p为将要删除的节点 q = p = first; if(first == NULL) // 空链表 { return NULL; } if(first -> data == e) //被删除节点是首节点 { first = first -> next; free(p); return first; } p = q -> next; //被删除的是中间节点才会执行以下步骤 while(p) { if(p ->data == e) //找到值为e的节点 { q -> next = p -> next; //这两条语句删除节点p free(p); return first; } q = q ->next; //值为e的节点没找到，继续向后查找 p = q -> next; } } /* 功能：链表遍历，在链表first中，依次打印链表的值 返回值：无 */ void list_print(Lnode *first) { Lnode *p; p = first; while(p != NULL) { printf("%d\t",p -> data); p = p -> next; } printf("\n"); } /* 功能：用数组a[0:n-1]中的数据，构成链表 返回值：返回链表首指针 */ Lnode *list_creat(Lnode *first,int a[],int n) { int i; for( i = n - 1;i >= 0;i--) //利用前插法建立链表 { first = list_insert(first,first,a[i]); } return first; } /* 功能：销毁链表first每个节点的内存空间 返回值：无 */ void list_destroy(Lnode * first) { Lnode *p = first; first = first -> next; free(p); while(first) { p = first; first = first -> next; free(p); } } /* 功能：将节点s按有序的方式插入到首指针为first的链表中 输入：first为链表首指针，s为指向被插入的节点的指针 返回值：返回插入新结点后的链表首指针 */ Lnode *list_insert_order(Lnode *first,Lnode *s) { Lnode *p = NULL, *q = NULL; if(first == NULL) //空链表 { first = s; first ->next = NULL; return first; } if( s -> data < first -> data ) //新节点s的值小于首节点 { s -> next = first; first = s; return first; } p = first; while(p->next != NULL) //寻找插入位置 { if(s->data >= p->data && s->data < p->next->data) { //找到p所指向的位置，将s插入到指针p所指向的结点之后 s->next = p->next; p->next =s; return first; } else p= p->next; //当前p指向的节点不是适合插入的位置，继续向后寻找 } //到链表结束都未找到合适的插入位置，说明s的值大于尾节点的值，将s插入到尾节点之后。 //注意p当前指向链表的尾部 p->next = s; s->next = NULL; return first; } /* 功能：取出first指向的链表的首节点，链表新的首节点是原来首节点的后继结点。 输入、输出参数：first是一个二级指针，作为输入参数时，first是还未取出首节点的链表的首指针。 作为输出参数时，first表示取出首节点后剩下的链表的首指针 */ Lnode *list_get_front(Lnode **first) //结合list_sort函数，思考为什么要将first声明为二级指针？声明为一级指针会出现什么问题？ { Lnode *p = 0; if(*first == NULL) return NULL; //空链表 else { p = *first; //p指向要取出的首节点 *first = (*first)->next; //新的首指针指向原来首指针的后继结点 return p; } } /* 功能：将first指向的链表排序。 输入参数：first,未排序链表的首指针，排序后，first的值无意义 返回值：返回排序后链表的首指针 */ Lnode *list_sort(Lnode *first) { Lnode *p = 0,*q = 0; //下面的代码中，first始终指向未排序部分（链表）的首节点 while(first != NULL)//待排序链表中的first值一直会变化直到NULL为止，只有只用二级指针才能反映出这地址的变化，因为函数值必须返回p而无法将first返回 { q = list_get_front(&first); //取出first为首指针的链表中的首节点//first取出后first在未排序链表 //中的指向后移（first的值会变化），这是list_get_front函数中的first必须用二级指针的原因 p = list_insert_order(p,q); //将取出的首节点q插入到有序链表p中 } return p; //返回排序后的链表首指针 } /* 功能：将链表first的节点逆置 返回值：返回逆置后的链表首指针 */ Lnode *list_reverse(Lnode *first) { Lnode *q,*p; if(first == NULL || first->next == NULL) //空链表或只有一个节点 { return first; } q = first->next; //q指向first的下一个节点 first->next = NULL; //将first与q节点的连接断开，并指向NULL while(q != NULL) { p = q->next; //将q节点的下一个节点设置为p，方便下一次循环将q后移 q->next = first; //将q的next节点设置为first, first = q; //将当前q节点设置为first节点，第一次循环到这儿已经完成第一二号节点的逆置，并将二号节点设置为first节点 q = p; //q节点后移一位，以便于剩下的节点继续逆置 } return first; } /* 功能：链表功能测试函数 输入参数：无 输出参数：无 返回值：无 */ void list_function_test(void) { int n = 7,a[] = {12,34,21,11,56,54,65}; Lnode *first = 0,*p = 0; first = list_creat(first,a,n); //用数组a创建链表 list_print(first); //输出链表的原始数据 //first = list_insert(first,first,100); //list_print(first); //输出表首前插入100后的链表 //p = list_find(first,11); //查找值为11的节点 //list_insert(first,p,200); //在值为11的节点前插入值为200的节点 //list_print(first); //在值为11的节点前插入200后的输出结果 //first = list_delete(first,54); //删除值为54的节点 //list_print(first); //删除54后的输出结果 first = list_sort(first); //对链表进行排序 list_print(first); //输出排序后的链表 first = list_reverse(first); list_print(first); list_destroy(first); //销毁整个链表 printf("\n销毁链表后first依然指向一个地址：%d\n这是因为list_destroy函数没有将first的值返回，如果返回了，将会有first=NULL\n",first); //list_print(first); //正确销毁整个链表后，这句代码会引起异常中断，因为销毁链表 //只是把链表的内存空间释放掉了，first指向的地址依然为原来的地址而不是NULL， //list_print(first)仍然会尝试去输出first的data值，但这个data的内存已经被释放了 //无法找到，故出错，要想此代码运行后输出0x00000000,需将first指针返回 getchar(); }