数据结构-第二章-单链表-不带头节点实现各种基本功能

说明：

这是不带头结点的功能实现程序
不带头结点的程序，在进行插入、删除、查值等函数功能时需要对表首进行特殊处理
故，不带头结点函数较为麻烦，考虑情况过多。
如果看不懂不带头结点的代码的话，强烈建议先学会带头结点的代码

注释已更新完毕

代码如下：

/*
    带头结点单链表 C语言指针实现
*/

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

#define ElemType int
#define MaxSize 10

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

LNode * InitList( LinkList L );//定义初始化单链表 函数
bool LinkListEmpty( LinkList L );//定义判断单链表是否为空 函数
bool isEquality( ElemType e1, ElemType e2 );//定义 判断两元素值是否相等 函数
LinkList HeadInsert( LinkList L );//定义 头插法新建单链表 函数
LinkList TailInsert( LinkList L );//定义 尾插法新建单链表 函数
LNode *GetElem( LinkList L, int i );//定义 按序号查找节点 函数
LNode *LocateElem( LinkList L, ElemType e );//定义 按值查找节点 函数
bool InsertPriorNode( LinkList *L, int i, ElemType e );//定义 在第i个位置上插入值为e的新节点(二级指针带回表头，并且能返回bool)
bool InsertPriorNodePro( LNode *p, ElemType e );//实现 在节点p 前 插入新节点(偷天换日)
bool DeleteNode( LinkList *L, int i , ElemType *e );//定义 删除第i个结点 并且返回该结点值 函数
bool DeleteLNodePro( LNode *p );//定义 偷天换日法删除第i个结点 函数
void PrintLinkList( LinkList L );//定义 打印单链表各元素的值 函数
int ReturnListLength( LinkList L );//定义 返回链表长度 函数

LinkList Test( LinkList L, int a, int x );//定义 老师出的那个题的函数
/*    题目：
    在第一个值为a的节点后面插入一个 值为x的节点
    若没有找到值为a的节点或者L为空表则在表尾插入一个 值为x的节点。
*/

bool DeleteNode( LinkList *L, int i , ElemType *e );
int main() {

    srand( ( unsigned )time( NULL ) );

    LNode *L;
    L = InitList( L );
    printf( "%d\n", LinkListEmpty( L ) );

    //测试头插法
//    L = HeadInsert( L );
//    PrintLinkList( L );


    //测试尾插法
    L = TailInsert( L );
    PrintLinkList( L );

//    测试GetElem函数
//    printf( "GetElem( L, 7 )->data = %d\n", GetElem( L, 7 )->data );

    //测试LocateElem函数
//    printf( "LocateElem( L, 710 )->data = %d", LocateElem( L, 710 )->data );

    //测试InsertPriorNode函数
//    printf( "InsertPriorNode( &L, 3, 710 ) = %d\n", InsertPriorNode( &L, 3, 710 ) );
//    PrintLinkList( L );

    //测试InsertPriorNodePro函数
//    printf( "InsertPriorNodePro( GetElem( L, 10 ), 710 ) ) = %d\n", InsertPriorNodePro( GetElem( L, 10 ), 710 ) );
//    PrintLinkList( L );

    //测试DeleteNode函数
//    ElemType e = 0;
//    printf( "DeleteNode( &L, 7, &e ) = %d\n", DeleteNode( &L, 7, &e ) );
//    printf( "e = %d\n", e );
//    PrintLinkList( L );

    //测试Test函数
//    PrintLinkList( Test( L, 710, 717 ) );


    return 0;
}

//-----------------函数实现-----------------
//实现初始化单链表 函数
LinkList InitList( LinkList L ) {
    L = NULL;
    return L;
}

//实现判断单链表是否为空 函数
bool LinkListEmpty( LinkList L ) {
    return ( L == NULL );
}

//定义判断两元素值是否相等 函数
bool isEquality( ElemType e1, ElemType e2 ) {
    /*
    元素类型为int char double等基本类型则不需要此函数，
    但若元素类型不是Int数据组 而是struct类型数组则判断相等需要比较struct中各成员的值，进行特殊处理。
    故引进判断元素值是否相等函数。
    */
    if( e1 == e2 )
        return true;
    return false;
}

//实现 头插法新建单链表 函数
LinkList HeadInsert( LinkList L ) {

//    int cnt = 0;

    LNode *s;
    ElemType x;
    scanf( "%d", &x );
//    x = rand() % 100;

    while( x != 777 ) {
        if( L == NULL ) {
            L = ( LNode * )malloc( sizeof( LNode ) );
            L->data = x;
            L->next = NULL;
            scanf( "%d", &x );

//            if( ++cnt == MaxSize ) break;
//            x = rand() % 100;

            continue;
        }
        s = ( LNode * )malloc( sizeof( LNode ) );
        s->data = x;
        s->next = L;
        L = s;
        scanf( "%d", &x );

//        if( ++cnt == MaxSize ) break;
//        x = rand() % 100;

    }

    return L;
}

//实现 不带头结点尾插法建立单链表 函数
LinkList TailInsert( LinkList L ) {

    int cnt = 0;

    ElemType x;
    LNode *s, *t = L;                    //t为表尾（tail）指针
    scanf( "%d", &x );                    //输入节点元素值
//    x = rand() % 100;

    while( x != 777 ) {
        if( L == NULL ) {
            L = ( LNode * )malloc( sizeof( LNode ) );
            L->next = NULL;
            L->data = x;
            t = L;
            scanf( "%d", &x );            //输入节点元素值

//            if( ++cnt == MaxSize ) break;
//            x = rand() % 100;

            continue;
        }
        s = ( LNode * )malloc( sizeof( LNode ) );
        s->next = NULL;
        s->data = x;
        t->next = s;
        t = s;
        scanf( "%d", &x );

//        if( ++cnt == MaxSize ) break;
//        x = rand() % 100;
    }
    return L;
}

//实现 获取第i个位置上的结点 函数        注意该函数返回值为Lnode* 所以为返回结点，并非结点值。
LNode * GetElem( LinkList L, int i ) {
    int count = 1;
    LNode *p = L;
    if( i < 1 ) return NULL;
    if( L == NULL )return NULL;
    while( p->next != NULL && count < i && i != 1 ) {
        count++;
        p = p->next;
    }
    return p;
}

//实现 按值查找结点 函数
LNode *LocateElem( LinkList L, ElemType e ) {
    LNode *p = L;
    while( p != NULL && !isEquality( p->data, e ) ) {
        p = p->next;
    }
    return p;
}

//实现 在第i个位置上插入值为e的新节点 (二级指针带回表头，并且能返回bool)
bool  InsertPriorNode( LinkList *L, int i, ElemType e ) {
    if( LinkListEmpty( *L ) || i < 0 || i > ReturnListLength( *L ) ) {    //若表空 或 i不合法 则返回false;
        return false;
    }

    if( i == 1 ) {    //对只有一个节点时进行特殊处理
        LNode *s = ( LNode * )malloc( sizeof( LNode ) );
        s->data = e;
        s->next = *L;
        *L = s;
        return true;
    }

    LNode *p = GetElem( *L, i - 1 );
    LNode *s = ( LNode * )malloc( sizeof( LNode ) );

    if( p == NULL || s == NULL )
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//实现 在节点p 前 插入新节点(偷天换日)
bool InsertPriorNodePro( LNode *p, ElemType e ) {
    if( p == NULL )
        return false;
    LNode *s = ( LNode * )malloc( sizeof( LNode ) );
    ElemType temp = p->data;
    p->data = e;
    s->data = temp;
    s->next = p->next;
    p->next = s;
    return true;
}

//实现 删除第i个节点 函数
bool DeleteNode( LinkList *L, int i , ElemType *e ) {
    if( i == 1 ) {

        if( ( *L ) == NULL )
            return false;

        if( ( *L )->next == NULL ) { //对只有一个节点时进行特殊处理
            *e = ( *L )->data;
            free( *L );
            *L  = NULL;
            return true;
        }

        LNode *p = ( *L );
        *e = ( *L )->data;
        *L = ( *L )->next;
        free( p );
        return true;
    }

    LNode *p = GetElem( *L, i - 1 );
    if( p == NULL || p->next == NULL )return false;
    LNode *q = p->next;
    p->next = q->next;
    *e = q->data;
    free( q );
    return true;
}

//实现 偷天换日法删除非尾结点P。（若P为尾节点则会出错） 详细解析查看带头结点讲解。过程一样
bool DeleteLNodePro( LNode *p ) {
    if( p == NULL && p->next != NULL )
        return false;
    LNode *s = p->next;
    p->data = s->data;
    p->next = s->next;
    free( s );
    return true;
}

//实现 返回链表长度 函数
int ReturnListLength( LinkList L ) {
    int len = 0;
    LNode *p = L;
    if( LinkListEmpty( L ) ) {
        return 0;
    }
    while( p != NULL ) {
        len++;
        p = p->next;
    }
    return len;
}

//实现打印链表函数
void PrintLinkList( LinkList L ) {
    printf( "当前链表遍历结果为：\n" );
    LNode *s = L;
    if( LinkListEmpty( L ) ) {
        printf( "空表\n" );
        return;
    }
    while( s != NULL ) {
        printf( "%d ", s->data );
        s = s->next;
    }
    printf( "\n表长为：%d\n", ReturnListLength( L ) );
}

LinkList Test( LinkList L, int a, int x ) {
    LNode *p = L;
    while( p != NULL && p->data != a ) {
        p = p->next;
    }

    //若p==null 则证明 L是空表 或 没有找到值为a的节点 所以应在表尾插
    if( p == NULL ) {

        //因为这个单链表没有头结点，所以需要对空表情况下进行特殊处理。
        if( LinkListEmpty( L ) ) {    //若为空表则改变L的data域及其指针域
            L = ( LNode * )malloc( sizeof( LNode ) );
            L->data = x;
            L->next = NULL;
            return L;
        } else {
            //若不是空表，则证明 没有找到值为a的节点
            //在表尾插入时，应将新节点q的next赋值为null
            LNode *q = ( LNode * )malloc( sizeof( LNode ) );
            q->next = NULL;
            p->next = q;
            q->data = x;
            return L;
        }

    }
    //当程序走到这时，证明p!=null即，找到了第一个值为a的节点P,则在p后进行插入新结点q即可
    LNode *q = ( LNode * )malloc( sizeof( LNode ) );
    q->next = p->next;
    q->data = x;
    p->next = q;
    return L;
}