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

说明：

这是不带头结点的功能实现程序
不带头结点的程序，在进行插入、删除、查值等函数功能时需要对表首进行特殊处理
故，不带头结点函数较为麻烦，考虑情况过多。

注释未完全更新完毕，有空再更新

代码如下：

/*
	带头结点单链表 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 前 插入新节点(偷天换日)
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 = TailInsert( L );
    PrintLinkList( L );

    //测试采用头插法初始化链表
    L = HeadInsert( L );
    PrintLinkList( L );

    //测试按位序查找元素节点
    LNode *temp = GetElem( L, 1 );
    if( temp != NULL ) {
        printf( "GetElem( L, 1 )->data=%d\n", temp->data);
    }


//    测试按元素值查找元素节点
    if( LocateElem( L, 2 ) ) {
        printf( "LocateElem( L, 2 )->data=%d\n", LocateElem( L, 2 )->data );
    } else {
        printf( "404!\n" );
    }

    //测试在第i个节点前插入一个节点。  此时为在第一个节点前插入值为710的节点
//    InsertPriorNode( &L, 1, 710 );
//    PrintLinkList( L );

    //测试在值为7的节点前插入一个节点。  此时为在第一个值为7的节点前插入值为717的节点
//    InsertPriorNodePro( LocateElem( L, 7 ), 717 );
//    PrintLinkList( L );

    //测试删除函数  此时为删除第一个节点并返回其元素值e;
    printf( "\n进入删除函数：DeleteNode( &L, 1, &e )\n" );
    ElemType e = 0;
    int flag = DeleteNode( &L, 1, &e );
    if( flag ) {
        printf( "删除成功！ e=%d\n", e );
    } else {
        printf( "删除失败！\n" );
    }

    //打印链表函数 （内嵌求表长函数） ；
    PrintLinkList( L );

    //测试求表长函数
    printf( "当前链表表长为：%d\n", ReturnListLength( L ) );

    //测试上课那个题的函数
    L = Test( L, 3, 999 );
    PrintLinkList( L );

    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 ) {
    LNode *s;
    ElemType x;
    scanf( "%d", &x );

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

    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;
}

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( 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 ) );
    s->data = e;
    ElemType temp;
    s->next = p->next;
    p->next = s;
    temp = p->data;
    p->data = s->data;
    s->data = temp;
}

//实现 删除第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 );
    printf( "p->data=%d\n", p->data );
    if( p == NULL || p->next == NULL )return false;
    LNode *q = p->next;
    printf( "q->data=%d\n", q->data );
    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 ) ) {	//因为这个单链表没有头结点，所以需要对空表情况下进行特殊处理。 若有头结点则需此IF语句
            L = ( LNode * )malloc( sizeof( LNode ) );
            L->data = x;
            L->next = NULL;
            return L;
        }
        /*
        	在有头结点的单链表中 实现该函数功能时，直接删掉if( LinkListEmpty( L ) )语句即可
        */


        LNode *q = ( LNode * )malloc( sizeof( LNode ) );
        q->next = NULL;
        p->next = q;
        q->data = x;
        return L;
    }
    LNode *q = ( LNode * )malloc( sizeof( LNode ) );
    q->next = p->next;
    q->data = x;
    p->next = q;
    return L;
}