用C语言创建单链表并实现插入、删除等简单操作

单链表比起顺序表来说存储更灵活，在需要进行频繁的插入或删除操作的情况下，使用单链表来操作更加简单。但是在需要查找元素，计算链表长度时又会显得比较麻烦。选择顺序表还是单链表是要依情况而定。

创建单链表（头插法）：

头插法：始终让每个新结点放在链表中第一个位置，这样导致的结果是：当我们对链表进行遍历时，先遍历的是最后加入链表的结点。（下面给出的代码先不给新结点的数据域赋值，尾插法也是）

void CreateListHead( LinkList *L , int length )
{
    int i ;
    LinkList p ;
    *L = ( LinkList )malloc( sizeof( Node ) ) ; //建立一个头节点，并让头指针指向这个头节点
    ( *L )->next = NULL ;
    for( i = 0 ; i < length ; i++ )
    {
        p = ( LinkList )malloc( sizeof( Node ) ) ; //为新结点动态分配一块Node结点大小的一块内存
        p->next = ( *L )->next ;
        ( *L )->next = p ;
    }
}

创建单链表（尾插法）：

尾插法：每次都把新结点放在链表的最后一个位置。

void CreateListTail( LinkList *L , int length )
{
    int i ;
    LinkList p , r ;
    *L = ( LinkList )malloc( sizeof( Node ) ) ;
    r = *L ;
    for( i = 0 ; i < length ; i++ )
    {
        p = ( LinkList )malloc( sizeof( Node ) ) ;
        r->next = p ;
        r = p ;
    }
    r->next = NULL ;

}

遍历单链表：

void TraverseList( LinkList L )
{
    LinkList p = L->next ;
    while( p )
    {
        printf( "%d " , p->data ) ;//可以对结点的值进行修改
        p = p->next ;
    }
    printf( "\n" ) ;
}

取链表特定位置的值：（把要找的值赋给val）

Status GetElem( LinkList L , int pos , int *val )
{
    int j = 1 ;
    LinkList p = L->next ;

    while( p && (  j < pos ) ) //while和下面的if语句是常常用来查找元素位置的方法
    {
        p = p->next ;
        j++ ;
    }
    if( !p || (  j > pos ) )
        return ERROR ;

    *val = p->data ;
    return OK ;
}

查看链表长度：（在这里链表的长度不包括头节点）

Status GetLength( LinkList L )
{
    int length = 0  ;
    LinkList p ;
    p = L->next ;
    while( p )
    {
        p = p->next ;
        length++ ;
    }
    return length ;
}

查找给定值在链表中的位置：

Status LocateElem( LinkList L , int e )
{
    LinkList p ;
    int flag , index = 1 ;
    flag = 0 ;
    p = L->next ;
    while( p )
    {
        if( p->data == e )
        {
            flag = 1 ;
            break ;
        }
        else
        {
            p = p->next ;
            index++ ;
        }
    }
    return ( flag == 1 ? index : ERROR ) ;//查找到的话则返回元素在链表中的位置，否则返回0
}

插入操作：（pos代表要插入的位置）

Status ListInsert( LinkList *L , int pos , int e )
{
    int j = 1 ;
    LinkList p , s ;
    p = *L ;
    while( p && ( j < pos ) )
    {
        p = p->next ;
        j++ ;
    }

    if( !p || (  j > pos ) )
        return ERROR ;
    s = ( LinkList )malloc( sizeof( Node ) ) ;
    s->data = e ;
    s->next = p->next ;
    p->next = s ;

    return OK ;
}

删除操作：

Status ListDelete( LinkList *L , int pos , int *val )
{
    int j = 1 ;
    LinkList p , q ;
    p = *L ;
    while( ( p->next ) && j < pos )
    {
        p = p->next ;
        j++ ;
    }
    if( !( p->next ) ||  ( j > pos ) )
        return ERROR ;

     q = p->next ; //注意这行不能和下面互换位置
     p->next = q->next ;
     
     *val = q->data ;
     free( q ) ;//一定要free掉要删除的结点，防止内存溢出
     return OK ;
}

销毁单链表：

Status DestoryList( LinkList *L )
{
    LinkList p , q ; //如果只是free(*L)是不够的，因为这样的话只是删除了链表的头节点，而且直接这样删除的话就找不到头节点以后的节点了
    p = ( *L )->next;
    while( p )
    {
        q = p->next ;
        free( p ) ;
        p = q ;
    }
    ( *L )->next = NULL ;
    return OK ;
}

下面再附上源代码：

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0

typedef int Status ;
typedef struct Node
{
    int data ;
    struct Node * next ;
} Node , * LinkList ;

//void CreateListHead( LinkList * L , int length ) ;
void TraverseList( LinkList L ) ;
void CreateListTail( LinkList *L , int length ) ;
Status GetElem( LinkList L , int pos , int *val ) ;
Status ListInsert( LinkList *L , int pos , int e ) ;
Status ListDelete( LinkList *L , int pos , int *val ) ;
Status LocateElem( LinkList L , int e ) ;
Status DestoryList( LinkList *L ) ;
Status GetLength( LinkList L ) ;

int main( void )
{
    int val ;
    LinkList L ;

    CreateListTail( &L , 5 ) ;
    TraverseList( L ) ;

    ListInsert( &L , 2 , 7 ) ;
    TraverseList( L ) ;

    ListDelete( &L , 3 , &val ) ;
    printf( "删除的是：%d\n" , val ) ;
    TraverseList( L ) ;

    printf( "链表的长度是%d\n" , GetLength( L ) ) ;

    printf( "在第%d个结点中\n" , LocateElem( L , 5 ) ) ;

    DestoryList( &L ) ;
    return 0 ;
}

/*void CreateListHead( LinkList *L , int length )
{
    int i ;
    LinkList p ;
    *L = ( LinkList )malloc( sizeof( Node ) ) ;
    ( *L )->next = NULL ;
    for( i = 0 ; i < length ; i++ )
    {
        p = ( LinkList )malloc( sizeof( Node ) ) ;
        printf( "请输入第%d个结点的值：" , i+1 ) ;
        scanf( "%d" , &p->data ) ;
        p->next = ( *L )->next ;
        ( *L )->next = p ;
    }
}*/

void CreateListTail( LinkList *L , int length )
{
    int i ;
    LinkList p , r ;
    *L = ( LinkList )malloc( sizeof( Node ) ) ;
    r = *L ;
    for( i = 0 ; i < length ; i++ )
    {
        p = ( LinkList )malloc( sizeof( Node ) ) ;
        printf( "请输入第%d个节点的值：" , i+1 ) ;
        scanf( "%d" , &p->data ) ;

        r->next = p ;
        r = p ;
    }
    r->next = NULL ;

}

void TraverseList( LinkList L )
{
    LinkList p = L->next ;
    while( p )
    {
        printf( "%d " , p->data ) ;
        p = p->next ;
    }
    printf( "\n" ) ;
}

Status GetElem( LinkList L , int pos , int *val )
{
    int j = 1 ;
    LinkList p = L->next ;

    while( p && (  j < pos ) )
    {
        p = p->next ;
        j++ ;
    }
    if( !p || (  j > pos ) )
        return ERROR ;

    *val = p->data ;
    return OK ;
}

Status ListInsert( LinkList *L , int pos , int e )
{
    int j = 1 ;
    LinkList p , s ;
    p = *L ;
    while( p && ( j < pos ) )
    {
        p = p->next ;
        j++ ;
    }

    if( !p || (  j > pos ) )
        return ERROR ;
    s = ( LinkList )malloc( sizeof( Node ) ) ;
    s->data = e ;
    s->next = p->next ;
    p->next = s ;

    return OK ;
}

Status ListDelete( LinkList *L , int pos , int *val )
{
    int j = 1 ;
    LinkList p , q ;
    p = *L ;
    while( ( p->next ) && j < pos )
    {
        p = p->next ;
        j++ ;
    }
    if( !( p->next ) ||  ( j > pos ) )
        return ERROR ;

     q = p->next ;
     p->next = q->next ;
     *val = q->data ;
     free( q ) ;
     return OK ;
}

Status DestoryList( LinkList *L )
{
    LinkList p , q ;
    p = ( *L )->next;
    while( p )
    {
        q = p->next ;
        free( p ) ;
        p = q ;
    }

    ( *L )->next = NULL ;
    return OK ;
}

Status GetLength( LinkList L )
{
    int length = 0  ;
    LinkList p ;
    p = L->next ;
    while( p )
    {
        p = p->next ;
        length++ ;
    }
    return length ;
}

Status LocateElem( LinkList L , int e )
{
    LinkList p ;
    int flag , index = 1 ;
    flag = 0 ;
    p = L->next ;
    while( p )
    {
        if( p->data == e )
        {
            flag = 1 ;
            break ;
        }
        else
        {
            p = p->next ;
            index++ ;
        }

    }
    return ( flag == 1 ? index : ERROR ) ;
}