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

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

如果看不懂不带头结点的，强烈建议看带头结点的代码，看懂了再去看不带头结点的代码

/*
    带头结点单链表 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 Empty( 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 ); //实现 偷天换日法删除非尾结点P。（若P为尾节点则会出错）
void PrintLinkList( LinkList L );//定义 打印单链表各元素的值 函数
int ReturnListLength( LinkList L );//定义 返回链表长度 函数

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

int main() {

    srand( ( unsigned )time( NULL ) );

    LNode *L;
    L = InitList( L );
    printf( "%d\n", Empty( 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 = ( LNode * ) malloc( sizeof( LNode ) );
    L->next = NULL;
    return L;
}

//实现判断单链表是否为空 函数
bool Empty( LinkList L ) {
    return ( L->next == 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 ) {
        s = ( LNode * )malloc( sizeof( LNode ) );
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf( "%d", &x );

//        if( ++cnt == MaxSize ) break;   //随机生成链表值。如果生成了MaxSize个则退出循环
//        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 ) {
        s = ( LNode * )malloc( sizeof( LNode ) );
        s->next = NULL;
        s->data = x;
        t->next = s;
        t = s;
        scanf( "%d", &x );                //输入节点元素值

//        if( ++cnt == MaxSize ) break;   //随机生成链表值。如果生成了MaxSize个则退出循环
//        x = rand() % 100;

    }
    return L;
}

//实现 获取第i个位置上的节点 函数        注意该函数返回值为Lnode* 所以为返回结点，并非结点值。
LNode *GetElem( LinkList L, int i ) {

    int count = 1;            //因为带头结点 直接将p=L->next 所以当此处将count初始化为1，因为当不是空表且i合法时P已经指向了第一个有效结点，所以count初始化为1
    LNode *p = L->next;        //也可以将count初始化为0，然后将下面while循环的条件修改为count < i-1即可  手动模拟一下就明白啦

    if( Empty( L ) || i < 1 || i > ReturnListLength( L ) )    //判断是否为空表 及 i的合法性
        return NULL;

    while( p != NULL && count < i ) {
        count++;
        p = p->next;
    }

    return p;
}

//实现 按值查找结点 函数    注意该函数返回值为Lnode* 所以为返回结点，并非结点值。
LNode *LocateElem( LinkList L, ElemType e ) {
    LNode *p = L->next;
    while( p != NULL && !isEquality( p->data, e ) ) {    //改循环判断条件 判断了两个东西：
        p = p->next;                                    //1. p != NULL来限定不是空表！，并且判断了有没有走到尾结点
    }                                                    //2. !isEquality( p->data, e )来限定该节点值不是e
    return p;
}

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

    LNode *p = ( *L )->next;
    LNode *s = ( LNode * )malloc( sizeof( LNode ) );
    int count = 1;

    while( p != NULL && count < i - 1 ) {            //找到第i-1个节点
        count++;                                //该while循环可由 p = GetElem( *L, i - 1 ); 一句代替！
        p = p->next;
    }

    if( p == NULL || s == NULL )        //若没有找到第i个节点或空间不足s结点申请失败则，返回false
        return false;

    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//实现 在节点p 前 插入新节点(偷天换日法)    以前插之名，行后插之实
/*
    在已知结点的情况下，交换该结点的元素值， 及其next指针 即可完成；
    ...->(已知)[p.data|p.next]->[q.data|q.next]->...
    新申请一个s指向[s.data|s.next]
    ①交换p.data与s.data
    ②s.next指向p->next  p->next指向s这样。 s就后插到p的后面了，并且p的值为s的值即e，s的值为之前p的值。
    然后链表就变成 ...->(已知)[e|p]->[p.data|p.next]->[q.data|q.next]->... 这样就完成了前插操作。
    以下为代码实现：
*/
bool InsertPriorNodePro( LNode *p, ElemType e ) {
    LNode *s = ( LNode * )malloc( sizeof( LNode ) );
    if( p == NULL || s == NULL )
        return false;
    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 ) {
    LNode *p = GetElem( *L, i - 1 );        //先找到第i-1个节点 给p 
    if( p == NULL || p->next == NULL )        //若p没找到，或者p的下一个即第i个节点为空 则返回false 
        return false;
    LNode *q = p->next;                        //当程序运行到这时，代表第i-1个顺利找到，并且第i个不空  
    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为 尾结点在 此处会出错，因为p->next==NULL故无法找到s->data即无法找到p->next->data
    p->next = s->next;
    free( s );
    return true;
}


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

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

LinkList Test( LinkList L, int a, int x ) {
    LNode *p = L->next;
    while( p != NULL && p->data != a ) {
        p = p->next;
    }
    LNode *q = ( LNode * )malloc( sizeof( LNode ) );
    if( p == NULL ) {        //若p==NULL,则证明为空表或，未找到值为a的节点，故应该在表尾插入
        q->next = NULL;        //则新节点q的next应为NULL
    } else {                //若p!=NULL,则证明找到值为a的节点p，故应该在后插入
        q->next = p->next;    //则新节点q的next应为p->next
    }
    q->data = x;
    p->next = q;
    return L;
}