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

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

说明:

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

注释已更新完毕

代码如下:

/*
    带头结点单链表 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;
}
目录
相关文章
|
13天前
|
存储
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
13 0
|
13天前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
14 0
|
13天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
9 0
|
13天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
10 0
|
23天前
<数据结构>栈和队列. 顺序表实现栈,单链表实现队列.
<数据结构>栈和队列. 顺序表实现栈,单链表实现队列
26 3
|
23天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
23 1
|
23天前
(数据结构)单链表 —— 尾插,尾删,头插,头删,查找,插入,删除。
数据结构单链表 —— 尾插,尾删,头插,头删,查找,插入,删除
25 0
|
23天前
|
索引
【数据结构】单链表代码实现
【数据结构】单链表代码实现
11 1
|
23天前
|
Java
DAY-1 | Java数据结构之链表:删除无头单链表中等于给定值 val 的所有节点
力扣203题解:使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre,记录cur的前一个节点,遍历链表时,若cur.val!=key,pre和cur同时前进;若cur.val==key,则pre.next=cur.next,cur继续前进,确保pre不急于跟随以处理连续相同值的情况。遍历结束后,处理头节点可能需要删除的特殊情况。
27 0
|
5天前
数据结构——栈和队列
数据结构——栈和队列
8 1