单链表的初始化，建立，插入，查找，删除。

////////////////////////////////////////////
//单链表的初始化，建立，插入，查找，删除。//
//Author:Wang Yong                                                //    
//Date: 2010.8.19                                                 //
//////////////////////////////////////////// 


#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
//////////////////////////////////////////// 

//定义结点类型 
typedef struct Node
{
        ElemType data;                          //单链表中的数据域 
        struct Node *next;                      //单链表的指针域 
}Node,*LinkedList;

//////////////////////////////////////////// 

//单链表的初始化

LinkedList LinkedListInit()
{
        Node *L;
        L = (Node *)malloc(sizeof(Node));       //申请结点空间 
        if(L == NULL)                                           //判断是否有足够的内存空间 
                printf("申请内存空间失败\n");
        L->next = NULL;                                      //将next设置为NULL,初始长度为0的单链表 
}

//////////////////////////////////////////// 

//单链表的建立1，头插法建立单链表

LinkedList LinkedListCreatH()
{
        Node *L;
        L = (Node *)malloc(sizeof(Node));       //申请头结点空间
        L->next = NULL;                                              //初始化一个空链表
        
        ElemType x;                                                     //x为链表数据域中的数据
        while(scanf("%d",&x) != EOF)
        {
                Node *p;
                p = (Node *)malloc(sizeof(Node));       //申请新的结点 
                p->data = x;                                         //结点数据域赋值 
                p->next = L->next;                                        //将结点插入到表头L-->|2|-->|1|-->NULL 
                L->next = p; 
        }
        return L; 
} 

//////////////////////////////////////////// 

//单链表的建立2，尾插法建立单链表

LinkedList LinkedListCreatT()
{
        Node *L;
        L = (Node *)malloc(sizeof(Node));       //申请头结点空间
        L->next = NULL;                                      //初始化一个空链表
        Node *r;
        r = L;                                                  //r始终指向终端结点，开始时指向头结点 
        ElemType x;                                                     //x为链表数据域中的数据
        while(scanf("%d",&x) != EOF)
        {
                Node *p;
                p = (Node *)malloc(sizeof(Node));       //申请新的结点 
                p->data = x;                                         //结点数据域赋值 
                r->next = p;                                 //将结点插入到表头L-->|1|-->|2|-->NULL 
                r = p; 
        }
        r->next = NULL; 
        
        return L;       
}

//////////////////////////////////////////// 

//单链表的插入，在链表的第i个位置插入x的元素

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)
{
        Node *pre;                                              //pre为前驱结点 
        pre = L;
        int tempi = 0;
        for (tempi = 1; tempi < i; tempi++)
                pre = pre->next;                                     //查找第i个位置的前驱结点 
        Node *p;                                                                //插入的结点为p
        p = (Node *)malloc(sizeof(Node));
        p->data = x; 
        p->next = pre->next;
        pre->next = p;
        
        return L;                                                       
} 

//////////////////////////////////////////// 

//单链表的删除，在链表中删除值为x的元素

LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
        Node *p,*pre;                                   //pre为前驱结点，p为查找的结点。 
        p = L->next;
        while(p->data != x)                          //查找值为x的元素 
        {       
                pre = p; 
                p = p->next;
        }
        pre->next = p->next;                      //删除操作，将其前驱next指向其后继。 
        free(p);
        return L;
} 

/////////////////////////////////////////////

int main()
{
        LinkedList list,start;
/*      printf("请输入单链表的数据："); 
        list = LinkedListCreatH();
        for(start = list->next; start != NULL; start = start->next)
                printf("%d ",start->data);
        printf("\n");
*/      printf("请输入单链表的数据："); 
        list = LinkedListCreatT();
        for(start = list->next; start != NULL; start = start->next)
                printf("%d ",start->data);
        printf("\n");

        int i;
        ElemType x;
        printf("请输入插入数据的位置：");
        scanf("%d",&i);
        printf("请输入插入数据的值：");
        scanf("%d",&x);
        LinkedListInsert(list,i,x);
        for(start = list->next; start != NULL; start = start->next)
                printf("%d ",start->data);
        printf("\n");
        printf("请输入要删除的元素的值：");
        scanf("%d",&x);
        LinkedListDelete(list,x); 
        for(start = list->next; start != NULL; start = start->next)
                printf("%d ",start->data);
        printf("\n");
        
        return 0;
}