这学期刚刚学了数据结构课程，利用假期时间，把所学的数据结构用c写一遍，分享给大家，由于水平有限，错误的地方请大家见谅，欢迎指正。
对于单链表来说，它由节点的结构体组成，为了更清楚，我增加了一个链表结构体。请看代码！
typedef struct node { int data; struct node * next; } Node; typedef struct slist { Node * head; } Slist;
Node节点中有两部分，数据域data，也可以是其他结构体，这里为了操作简便，使用int类型。struct node * next则是指向下一个链表的指针。请看图示！
箭头代表指向，next里其实是下一个节点的地址，最后一个next的值是NULL。我们在插入，删除操作时，第一个节点和后续节点会有不同，这里涉及head指针。为了简化这些不同，我们使用一个不存数据的头结点。在链表的初始化时完成。
void s_init(Slist * list) { list->head = make_node(INT_MIN); }
INT_MIN代表整形最小值，在<limits.h>里。make_node是一个创建节点的函数，稍后会给出完整的程序。
插入操作，我们要写一个有序递增单链表，所以，我们要找到新节点对应的位置。单链表只能知道后继节点，不能通过后继节点找到前驱节点，所以，我们要找到一个节点，这个节点小于新节点，后继节点大于新节点。请看图示！
4是新节点，4要插入到3之后，先讲4的next指向3的next，也就是5。然后再将3的next指向4，链表插入完成。关键问题，在找到的位置是3而不是5。就是说current指向3，最后一个小于新节点的值。
while ( ptem->next != NULL && ptem->data < data ) if ( ptem->next->data <= data) ptem = ptem->next; else break;
这段代码实现了这个功能，其中ptem->next->data是后继节点的data值。如果后继节点的值大于data，说明找到了最后一个小于新节点的值，跳出循环。
删除操作，删除由两步构成，1、把删除节点从链表中去除。2、释放删除节点内存。
我们需要找到删除节点的前驱，然后将前驱节点的next指向删除节点的后继节点。请看图示！
先将previous的next指向5，也就是current的next，然后释放4的内存。
//找到删除节点,每次将pervious,current向后移动一个结点，previous一直是current前一个节点. while ( (current = previous->next) != NULL && current->data != key) if ( current->data > key ) return false; else previous = previous->next;
因为是顺序链表，我们不必找完整个链表，只找到第一个大于删除节点的值就可以结束查找了。
遍历节点，这里使用了函数指针，因为销毁链表和输出链表，都用到了遍历这个函数，它提高了函数的扩展性。也许会有更多的地方用到这个函数。
while ( (current = current->next) != NULL ) func(current);
这段代码跳过头结点，所以在如果想对头节点进行操作，还需要对head进行操作，例如销毁链表。
完整代码由slist.h 和 slist.c组成。
slist.h
#ifndef _SLIST_H #define _SLIST_H typedef struct node { int data; struct node * next; } Node; typedef struct slist { Node * head; } Slist; void s_init(Slist * list);//初始化 bool s_insert(Slist * list, const int data);//插入 bool s_remove(Slist * list, const int key);//移除 bool s_modify(Slist * list, const int key, const int data);//修改 Node* s_find(Slist * list, const int key);//查找 void s_treaverse(Slist * list, void (*func)(void * p));//遍历 void s_destroy(Slist * list);//销毁 #endif //_SLIST_H
slist.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> #include "slist.h" static Node* make_node(const int data); static void destroy_node(void * node); //带头节点的单链表 void s_init(Slist * list) { list->head = make_node(INT_MIN); } //按顺序插入 bool s_insert(Slist * list, const int data) { Node * ptem = list->head; Node * node; //查找插入位置 while ( ptem->next != NULL && ptem->data < data ) if ( ptem->next->data <= data) ptem = ptem->next; else break; //如果数据重复，插入失败 if ( ptem->data == data) return false; node = make_node(data); node->next = ptem->next; ptem->next = node; return true; } bool s_remove(Slist * list, const int key) { // previous是被删除节点的前一个结点 // current 是被删除节点 Node * previous = list->head; Node * current; //找到删除节点,每次将pervious,current向后移动一个结点，previous一直是current前一个节点. while ( (current = previous->next) != NULL && current->data != key) if ( current->data > key ) return false; else previous = previous->next; //如果没有找到节点，删除失败 if ( current == NULL ) return false; previous->next = current->next; free( current ); return true; } //修改函数是通过删除函数和插入函数实现的。 //不能直接修改的原因是这是个有序链表 bool s_modify(Slist * list, const int key, const int data) { if ( s_remove(list, key) ) s_insert(list, data); else return false; return true; } //找到返回关键字的节点，否则返回NULL指针 Node* s_find(Slist * list, const int key) { Node * current = list->head; while ( (current = current->next) != NULL && current->data != key) if ( current->data > key ) return NULL; return current; } void s_treaverse( Slist * list, void (*func)(void * p) ) { Node * current = list->head; while ( (current = current->next) != NULL ) func(current); } void s_destroy(Slist * list) { s_treaverse(list, destroy_node); free(list->head); } //创建结点,为了更好的封装性,使用static修饰 static Node* make_node(const int data) { Node * p = (Node *)malloc(sizeof(Node)); assert( p != NULL ); p->data = data; p->next = NULL; return p; } static void destroy_node(void * node) {free( (Node *)node ); }
2016-01-10