数据结构-第二章-线性表-动态/静态分配数据元素各功能实现

简介: 数据结构-第二章-线性表-动态/静态分配数据元素各功能实现

目录

说明:

演示:

1.顺序表-静态分配数据元素各功能实现(C语言 指针)

2.顺序表-静态分配数据元素各功能实现(C语言 引用)

3.顺序表-动态分配数据元素各功能实现(C语言 指针)

4.顺序表-动态分配数据元素各功能实现(C语言 引用)




说明:

1.由于数据分配有动态分配和静态分配两种方式,所以采用每种分配方式都写了实现代码,基本大同小异。(以后就只写一种了)

2.由于C语言本身不支持引用类型,而且书上是采用引用类型的,所以需要把文件的后缀.c改成.cpp这样就可以使用引用类型了。

3.由于老师上课讲用的是C语音讲的,所以使用指针的方式实现也是必须得会的。且引用和指针代码基本一样(以后也只写一种了)。

4.只有顺序表动态分配实现(C语音 指针)是有完整的 菜单和功能选择代码。其他的只是有各种功能的具体代码,并没有写菜单和功能选择。但有main函数中有各功能实现的测试代码。

演示:

~~菜单懒得弄了,有点丑,嘿嘿嘿~

插入函数:

删除函数:

修改函数:

查找函数:

在某值后插入新函数:

其余省略,自行调试。

1.顺序表-静态分配数据元素各功能实现(C语言 指针)

代码及注释如下:

/*
顺序表的实现,采用静态分配方式(C语言) 以.c结尾的C语言文件
由于C语言不支持引用 即无法书写 void InitList(SqList &L){} 这种形式
故:采用指针方式实现各种基本功能。
*/


#include <stdio.h>
#include <stdbool.h>        //在C99以后是GCC是有bool类型的定义的,但需引入stdbool.h头文件,其中false=0 true=1; 
#include <stdlib.h>            //因为动态分配需要使用malloc函数,故需引入其头文件stdlib.h 

#define ElemType int        //用ElemType 来代表int 方便以后修改数据类型
#define MaxSize 50            //定义线性表的最大长度


typedef struct {
    ElemType data[MaxSize];    //定义数据元素数组
    int length;                //顺序表长度(当前有效元素的个数,并非总体长度)
} SqList;

void PrintMenu();                                    //定义菜单函数
void FunSelect();                                     //定义功能选择函数
void InitList( SqList *L );                            //定义初始化一个顺序表 函数
bool SqListEmpty( SqList L );                        //定义判断顺序表是否为空 函数
bool SqListFull( SqList L );                        //定义判断顺序表是否满 函数
bool isEquality( ElemType e1, ElemType e2 );        //定义判断两元素值是否相等 函数
bool SqListInsert( SqList *L, int i, ElemType e );    //定义在顺序表L固定位置i插入一值e的 函数
bool SqListDelete( SqList *L, int i, ElemType *e );    //定义删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListUpdate( SqList *L, int i, ElemType e );    //定义修改顺序表中第i个元素的值 函数
int LocateByNum( SqList L, int i );                    //定义按位序查顺序表中元素的值 函数
ElemType LocateByElem( SqList L, ElemType e );        //定义按元素值查找在顺序表中的位置 函数
void PrintSqList( SqList L );                        //定义打印顺序表中各元素的值 函数
bool InsertElemAfterValue( SqList *L, ElemType value, ElemType e ); //定义在数据元素值为value的后面插入一个数据元素e 函数

SqList L;                //定义一个顺序表,名为L

int main() {

    SqList L1 = {
        {0,} ,
        0
    };                         //定义一个顺序表,名为L1,且初始化其data[0~MaxSize]=0,length=0,看不懂忽略,采用下面方法初始化

    InitList( &L );            //使用初始化函数将L初始化。  结果与上面直接初始化一样。这样初始化更加标准化。

    PrintMenu();            //打印菜单函数
    FunSelect();            //功能选择函数

    return 0;
}

//实现初始化一个顺序表 函数
void InitList( SqList *L ) {
    for( int i = 0; i < MaxSize; i++ ) {
        L->data[i] = 0;                    //将顺序表中每一个元素的值初始化为0
    }
    L->length = 0;                        //初始化顺序表现有表长为0
}

//实现判断顺序表是否为空 函数
bool SqListEmpty( SqList L ) {
    if( L.length == 0 )
        return true;
    else return false;
}

//实现判断顺序表是否满 函数
bool SqListFull( SqList L ) {
    if( L.length == MaxSize )
        return true;
    else return false;
}

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

//实现在顺序表L固定位置i插入一值e的函数
bool SqListInsert( SqList *L, int i, ElemType e ) {

    /*
        在插入函数中,需要对i值的合法性,以及表是否满进行判断,故有以下情况:
        ①i值非法: i≤0或i≥现有表长
        ②表满,则不可插入新值。
        ③若无①②情况,则可插入,在i插入一值时,需要将i及其之后的元素后移。
    */

    /*①
    若i的值 小于1或者大于L->length+1则返回false,即 i的值≤0或大于现有表长则返回错误!
    当i=length+1时,表示的是:在表尾插入一个元素e ,此时无需后移元素。
    因为顺序表的存储结构是一个接个的,所以i的取值范围为 1 ≤i ≤当前表长(即L->Length+1)
    */
    if( i < 1 || i > L->length + 1 )
        return false;

    /*②
        若现有表长≥最大表长Maxsize 则返回false, 告诉函数调用处插入失败
        因为此时顺序表元素已满,且因为是顺序表在定义时是采用静态分配的方式创建的,所以不可扩展。
        若再插入新值,会导致溢出,造成程序崩溃。
    */
    if( SqListFull( *L ) )
        return false;

    //注意j=L->length是定位在最后一个元素的后面一个,而不是最后一个元素。因为length是长度,是位序,是数组下标+1!!!
    for( int j = L->length; j >= i; j-- ) {    //在C99及C11标准下可以在for循环里写int i这种形式。不必纠结这种写法的正确性
        L->data[j] = L->data[j - 1];         //这个For循环将i及其之后的元素后移一位。一定要从最后一个元素开始后移,否则会全部替换成data[i]
    }
    L->data[i - 1] = e;                    //同理还是因为i是为序,是数组下标+1 ,所以插入的数组下标为i-1;
    //For循环和 L->data[i-1]=e; 不可颠倒,否则会第i个位置的值丢失,变成e

    L->length++;                        //插入完成后需对线性表表长+1
    return true;                        //返回true,给调用处一个反馈,告诉他插入成功!
}

//实现删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListDelete ( SqList *L, int i, ElemType *e ) {
    /*
    在删除函数中,需要对i值的合法性,故有以下情况:
    ①i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    ②若无①情况,则可删除,在i删除一值时,需要将i及其之后的元素前移。
    */

    /*①
    若i的值 小于1或者大于L->length则返回false,即 i的值≤0或≥现有表长length 则返回错误!
    若L->length==0则表示表空,也在此判断条件内,返回false;
    */

    if( i < 1 || i > L->length )        //注意与插入函数的区别
        return false;

    //利用指针传回第i个位置元素的值e;
    *e = L->data[i - 1];

    //将第i个位置后的元素前移。注意与插入函数的区别。
    for( int j = i; j < L->length; j++ ) {
        L->data[j - 1] = L->data[j];
    }
    /*
    考虑特殊情况:当i=1,且 L->length=1时
    For循环 j=i=1, j < L->length 即1<1显然是错误的,所以该循环不执行,直接跳出循环。
    之后 L->length--; 对长度减一,所以其实 L->data[j - 1]即L->data[0]的值还是原来那个值e,并没有变
    只是现有长度减一 变为0,成为一个标记的空表了而已。
    所以当我们正常打印顺序表的时候是看不到 L->data[0]的那个值e的。所以该函数是正确的。
    当然,如果你强行去输出L.data[0]的话 printf("%d",L.data[0]);  他会告诉你值依旧是e。
    */

    L->length--;                        //删除元素后将现有表长减一

    return true;
}

//实现修改顺序表中第i个元素的值
bool SqListUpdate( SqList *L, int i, ElemType e ) {

    /*
        在修改函数中,只需要对i值的合法性进行判定即可,无需移动元素
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    */
    if( i < 1 || i > L->length )
        return false;

    L->data[i - 1] = e;                //修改第i个位置的元素值为e。注意位序与下标的关系!
    return true;

}

//实现按位序查顺序表中元素的值 函数
ElemType LocateByNum( SqList L, int i ) {

    /*
        在查找函数中,只需要对i值的合法性进行判定即可。
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    */

    if( i < 1 || i > L.length )
        return 0;                    //若i值不合法则返回0表示未找到。

    return L.data[i - 1];            //若找到则返回该位序的值即可
}

//实现按元素值查找在顺序表中的位置 函数
int LocateByElem( SqList L, ElemType e ) {
    /*
        按顺序遍历顺序表,并一一比较顺序表中各数据元素的值即可
    */

    for( int i = 0; i < L.length; i++ ) {
        if( isEquality( L.data[i], e ) ) {    //判断是否相等,若相等则返回位序,即下标i+1
            return i + 1;
        }
    }
    return 0;            //若for循环走完则证明 未找到值为e的数据元素。返回0表示错误
}

//实现打印函数线性表L 函数
void PrintSqList( SqList L ) {
    int i;
    for( i = 0; i < L.length; i++ ) {
        printf( "%d ", L.data[i] );
    }
    if( i == 0 ) {
        printf( "NULL" );                //若为空表则输出NULL
    }
    printf( "\n" );
}

//实现在数据元素值为value的后面插入一个数据元素e 函数
bool InsertElemAfterValue( SqList *L, ElemType value, ElemType e ) {
    int order = LocateByElem( *L, value );
    if( !order ) {
        return false;
    }
    if( SqListInsert( L, order + 1, e ) ) {
        return true;
    } else return false;
}

//实现菜单函数
void PrintMenu() {
    printf( "\n☆数据结构-第二章-线性表-静态分配数据元素:\n\n" );
    printf( "\t————————————————————————————————\n" );
    printf( "\t| 1.判断顺序表是否为空\t2.判断顺序表是否已满\t\t\t|\n\n" );
    printf( "\t| 3.插入函数\t\t4.删除函数\t\t5.修改函数\t|\n\n" );
    printf( "\t| 6.按位序查找函数\t7.按元素值查找函数\t\t\t|\n\n" );
    printf( "\t| 8.打印顺序表中各元素的值\t\t\t\t\t|\n\n" );
    printf( "\t| 9.在值Value后插入一新值e 函数\t\t\t\t\t|\n\n" );
    printf( "\t| 0.退出\t\t\t\t\t\t\t|\n" );
    printf( "\t————————————————————————————————\n\n" );
}

//实现功能选择函数
void FunSelect() {
    int funNum;
    while( true ) {
        printf( "☆请输入功能函数序号:" );
        scanf( "%d", &funNum );
        fflush( stdin );

        switch( funNum ) {
            case 0:
                exit( 0 );
            case 1: {
                if( SqListEmpty( L ) ) {
                    printf( "顺序表为空表\n" );
                } else {
                    printf( "顺序表为非空表,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 2: {
                if( SqListFull( L ) ) {
                    printf( "顺序表已满\n" );
                } else {
                    printf( "顺序表未满,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 3: {
                printf( "请依次输入插入位置i和插入数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListInsert( &L, i, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            case 4: {
                printf( "请输入删除位序i:" );
                int i;
                ElemType e;
                scanf( "%d", &i );
                fflush( stdin );
                if( SqListDelete( &L, i, &e ) ) {
                    printf( "删除成功,删除元素的值为:%d\n当前表中元素值为:\n", e );
                    PrintSqList( L );
                } else {
                    printf( "删除失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 5: {
                printf( "请输入修改元素的位序i和修改数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListUpdate( &L, i, e ) ) {
                    printf( "修改成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "修改失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 6: {
                printf( "请输入查找元素的位序i:" );
                int i;
                scanf( "%d", &i );
                fflush( stdin );
                ElemType result = LocateByNum( L, i );
                if( result ) {
                    printf( "查找成功,该位序元素的值为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 7: {
                printf( "请输入查找元素的值e:" );
                ElemType e;
                scanf( "%d", &e );
                fflush( stdin );
                int result = LocateByElem( L, e );
                if( result ) {
                    printf( "查找成功,该数据元素的位序为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:未找到该数据元素\n" );
                }
                break;
            }
            case 8: {
                printf( "顺序表中各元素的值依次为:\n" );
                PrintSqList( L );
                break;
            }
            case 9: {
                printf( "请依次输入插入位置的数据元素值value和新插入数据元素值e:" );
                ElemType value, e;
                scanf( "%d%d", &value, &e );
                fflush( stdin );
                if( InsertElemAfterValue( &L, value, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            default:
                break;
        }
    }
}

2.顺序表-静态分配数据元素各功能实现(C语言 引用)

代码及注释如下:

/*
顺序表的实现,采用静态分配方式(C/C++语言) 以.cpp结尾的C++语言文件
由于C++语言支持引用,故已.cpp结尾,但仍采用C语言语法书写。
故:采用引用方式实现各种基本功能。
*/


#include <stdio.h>
#include <stdbool.h>        //在C99以后是GCC是有bool类型的定义的,但需引入stdbool.h头文件,其中false=0 true=1; 
#include <stdlib.h>            //因为动态分配需要使用malloc函数,故需引入其头文件stdlib.h 

#define ElemType int        //用ElemType 来代表int 方便以后修改数据类型
#define MaxSize 50            //定义线性表的最大长度


typedef struct {
    ElemType data[MaxSize];    //定义数据元素数组
    int length;                //顺序表长度(当前有效元素的个数,并非总体长度)
} SqList;

void PrintMenu();                                    //定义菜单函数
void FunSelect();                                     //定义功能选择函数
void InitList( SqList &L );                            //定义初始化一个顺序表 函数
bool SqListEmpty( SqList L );                        //定义判断顺序表是否为空 函数
bool SqListFull( SqList L );                        //定义判断顺序表是否满 函数
bool isEquality( ElemType e1, ElemType e2 );        //定义判断两元素值是否相等 函数
bool SqListInsert( SqList &L, int i, ElemType e );    //定义在顺序表L固定位置i插入一值e的 函数
bool SqListDelete( SqList &L, int i, ElemType &e );    //定义删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListUpdate( SqList &L, int i, ElemType e );    //定义修改顺序表中第i个元素的值 函数
int LocateByNum( SqList L, int i );                    //定义按位序查顺序表中元素的值 函数
ElemType LocateByElem( SqList L, ElemType e );        //定义按元素值查找在顺序表中的位置 函数
void PrintSqList( SqList L );                        //定义打印顺序表中各元素的值 函数
bool InsertElemAfterValue( SqList &L, ElemType value, ElemType e ); //定义在数据元素值为value的后面插入一个数据元素e 函数

SqList L;                //定义一个顺序表,名为L

int main() {

    SqList L1 = {
        {0,} ,
        0
    };                         //定义一个顺序表,名为L1,且初始化其data[0~MaxSize]=0,length=0,看不懂忽略,采用下面方法初始化

    InitList( L );            //使用初始化函数将L初始化。  结果与上面直接初始化一样。这样初始化更加标准化。

    PrintMenu();            //打印菜单函数
    FunSelect();            //功能选择函数

    return 0;
}

//实现初始化一个顺序表 函数
void InitList( SqList &L ) {
    for( int i = 0; i < MaxSize; i++ ) {
        L.data[i] = 0;                    //将顺序表中每一个元素的值初始化为0
    }
    L.length = 0;                        //初始化顺序表现有表长为0
}

//实现判断顺序表是否为空 函数
bool SqListEmpty( SqList L ) {
    if( L.length == 0 )
        return true;
    else return false;
}

//实现判断顺序表是否满 函数
bool SqListFull( SqList L ) {
    if( L.length == MaxSize )
        return true;
    else return false;
}

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

//实现在顺序表L固定位置i插入一值e的函数
bool SqListInsert( SqList &L, int i, ElemType e ) {

    /*
        在插入函数中,需要对i值的合法性,以及表是否满进行判断,故有以下情况:
        ①i值非法: i≤0或i≥现有表长
        ②表满,则不可插入新值。
        ③若无①②情况,则可插入,在i插入一值时,需要将i及其之后的元素后移。
    */

    /*①
    若i的值 小于1或者大于L.length+1则返回false,即 i的值≤0或大于现有表长则返回错误!
    当i=length+1时,表示的是:在表尾插入一个元素e ,此时无需后移元素。
    因为顺序表的存储结构是一个接个的,所以i的取值范围为 1 ≤i ≤当前表长(即L.Length+1)
    */
    if( i < 1 || i > L.length + 1 )
        return false;

    /*②
        若现有表长≥最大表长Maxsize 则返回false, 告诉函数调用处插入失败
        因为此时顺序表元素已满,且因为是顺序表在定义时是采用静态分配的方式创建的,所以不可扩展。
        若再插入新值,会导致溢出,造成程序崩溃。
    */
    if( SqListFull( L ) )
        return false;

    //注意j=L.length是定位在最后一个元素的后面一个,而不是最后一个元素。因为length是长度,是位序,是数组下标+1!!!
    for( int j = L.length; j >= i; j-- ) {    //在C99及C11标准下可以在for循环里写int i这种形式。不必纠结这种写法的正确性
        L.data[j] = L.data[j - 1];         //这个For循环将i及其之后的元素后移一位。一定要从最后一个元素开始后移,否则会全部替换成data[i]
    }
    L.data[i - 1] = e;                    //同理还是因为i是为序,是数组下标+1 ,所以插入的数组下标为i-1;
    //For循环和 L.data[i-1]=e; 不可颠倒,否则会第i个位置的值丢失,变成e

    L.length++;                        //插入完成后需对线性表表长+1
    return true;                        //返回true,给调用处一个反馈,告诉他插入成功!
}

//实现删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListDelete( SqList &L, int i, ElemType &e ) {
    /*
    在删除函数中,需要对i值的合法性,故有以下情况:
    ①i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    ②若无①情况,则可删除,在i删除一值时,需要将i及其之后的元素前移。
    */

    /*①
    若i的值 小于1或者大于L.length则返回false,即 i的值≤0或≥现有表长length 则返回错误!
    若L.length==0则表示表空,也在此判断条件内,返回false;
    */

    if( i < 1 || i > L.length )        //注意与插入函数的区别
        return false;

    //利用指针传回第i个位置元素的值e;
    e = L.data[i - 1];

    //将第i个位置后的元素前移。注意与插入函数的区别。
    for( int j = i; j < L.length; j++ ) {
        L.data[j - 1] = L.data[j];
    }
    /*
    考虑特殊情况:当i=1,且 L.length=1时
    For循环 j=i=1, j < L.length 即1<1显然是错误的,所以该循环不执行,直接跳出循环。
    之后 L.length--; 对长度减一,所以其实 L.data[j - 1]即L.data[0]的值还是原来那个值e,并没有变
    只是现有长度减一 变为0,成为一个标记的空表了而已。
    所以当我们正常打印顺序表的时候是看不到 L.data[0]的那个值e的。所以该函数是正确的。
    当然,如果你强行去输出L.data[0]的话 printf("%d",L.data[0]);  他会告诉你值依旧是e。
    */

    L.length--;                        //删除元素后将现有表长减一

    return true;
}

//实现修改顺序表中第i个元素的值
bool SqListUpdate( SqList &L, int i, ElemType e ) {

    /*
        在修改函数中,只需要对i值的合法性进行判定即可,无需移动元素
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    */
    if( i < 1 || i > L.length )
        return false;

    L.data[i - 1] = e;                //修改第i个位置的元素值为e。注意位序与下标的关系!
    return true;

}

//实现按位序查顺序表中元素的值 函数
ElemType LocateByNum( SqList L, int i ) {

    /*
        在查找函数中,只需要对i值的合法性进行判定即可。
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    */

    if( i < 1 || i > L.length )
        return 0;                    //若i值不合法则返回0表示未找到。

    return L.data[i - 1];            //若找到则返回该位序的值即可
}

//实现按元素值查找在顺序表中的位置 函数
int LocateByElem( SqList L, ElemType e ) {
    /*
        按顺序遍历顺序表,并一一比较顺序表中各数据元素的值即可
    */

    for( int i = 0; i < L.length; i++ ) {
        if( isEquality( L.data[i], e ) ) {    //判断是否相等,若相等则返回位序,即下标i+1
            return i + 1;
        }
    }
    return 0;            //若for循环走完则证明 未找到值为e的数据元素。返回0表示错误
}

//实现打印函数线性表L 函数
void PrintSqList( SqList L ) {
    int i;
    for( i = 0; i < L.length; i++ ) {
        printf( "%d ", L.data[i] );
    }
    if( i == 0 ) {
        printf( "NULL" );                //若为空表则输出NULL
    }
    printf( "\n" );
}

//实现在数据元素值为value的后面插入一个数据元素e 函数
bool InsertElemAfterValue( SqList &L, ElemType value, ElemType e ) {
    int order = LocateByElem( L, value );
    if( !order ) {
        return false;
    }
    if( SqListInsert( L, order + 1, e ) ) {
        return true;
    } else return false;
}

//实现菜单函数
void PrintMenu() {
    printf( "\n数据结构-第二章-线性表-静态分配数据元素\n\n" );
    printf( "————————————————————————————————\n" );
    printf( "| 1.判断顺序表是否为空\t2.判断顺序表是否已满\t\t\t|\n\n" );
    printf( "| 3.插入函数\t\t4.删除函数\t\t5.修改函数\t|\n\n" );
    printf( "| 6.按位序查找函数\t7.按元素值查找函数\t\t\t|\n\n" );
    printf( "| 8.打印顺序表中各元素的值\t\t\t\t\t|\n\n" );
    printf( "| 9.在值Value后插入一新值e 函数\t\t\t\t\t|\n\n" );
    printf( "| 0.退出\t\t\t\t\t\t\t|\n" );
    printf( "————————————————————————————————\n\n" );
}

//实现功能选择函数
void FunSelect() {
    int funNum;
    while( true ) {
        printf( "请输入功能函数序号:" );
        scanf( "%d", &funNum );
        fflush( stdin );

        switch( funNum ) {
            case 0:
                exit( 0 );
            case 1: {
                if( SqListEmpty( L ) ) {
                    printf( "顺序表为空表\n" );
                } else {
                    printf( "顺序表为非空表,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 2: {
                if( SqListFull( L ) ) {
                    printf( "顺序表已满\n" );
                } else {
                    printf( "顺序表未满,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 3: {
                printf( "请依次输入插入位置i和插入数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListInsert( L, i, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            case 4: {
                printf( "请输入删除位序i:" );
                int i;
                ElemType e;
                scanf( "%d", &i );
                fflush( stdin );
                if( SqListDelete( L, i, e ) ) {
                    printf( "删除成功,删除元素的值为:%d\n当前表中元素值为:\n", e );
                    PrintSqList( L );
                } else {
                    printf( "删除失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 5: {
                printf( "请输入修改元素的位序i和修改数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListUpdate( L, i, e ) ) {
                    printf( "修改成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "修改失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 6: {
                printf( "请输入查找元素的位序i:" );
                int i;
                scanf( "%d", &i );
                fflush( stdin );
                ElemType result = LocateByNum( L, i );
                if( result ) {
                    printf( "查找成功,该位序元素的值为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 7: {
                printf( "请输入查找元素的值e:" );
                ElemType e;
                scanf( "%d", &e );
                fflush( stdin );
                int result = LocateByElem( L, e );
                if( result ) {
                    printf( "查找成功,该数据元素的位序为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:未找到该数据元素\n" );
                }
                break;
            }
            case 8: {
                printf( "顺序表中各元素的值依次为:\n" );
                PrintSqList( L );
                break;
            }
            case 9: {
                printf( "请依次输入插入位置的数据元素值value和新插入数据元素值e:" );
                ElemType value, e;
                scanf( "%d%d", &value, &e );
                fflush( stdin );
                if( InsertElemAfterValue( L, value, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            default:
                break;
        }
    }
}

3.顺序表-动态分配数据元素各功能实现(C语言 指针)

代码及注释如下:

/*
顺序表的实现,采用动态分配方式(C语言) 以.c结尾的C语言文件
由于C语言不支持引用 即无法书写 void InitList(SqList &L){} 这种形式
故:采用指针方式实现各种基本功能。
*/


#include <stdio.h>
#include <stdbool.h>        //在C99以后是GCC是有bool类型的定义的,但需引入stdbool.h头文件,其中false=0 true=1; 
#include <stdlib.h>            //因为动态分配需要使用malloc函数,故需引入其头文件stdlib.h 

#define ElemType int        //用ElemType 来代表int 方便以后修改数据类型
#define InitSize 50            //定义最大长度为50 ,方便后期修改最大表长 


typedef struct {
    ElemType *data;            //指示动态分配数组的指针,动态分配可以避免溢出
    int MaxSize;            //指示顺序表的最大容量
    int length;                //顺序表长度(当前有效元素的个数,并非总体长度)
} SqList;

void PrintMenu();            //定义菜单函数
void FunSelect();             //定义功能选择函数
void InitList( SqList *L );                            //定义初始化一个顺序表 函数
bool IncreaseSize( SqList *L, int newLength );         //定义增加动态数组长度 函数
bool SqListEmpty( SqList L );                        //定义判断顺序表是否为空 函数
bool SqListFull( SqList L );                        //定义判断顺序表是否满 函数
bool isEquality( ElemType e1, ElemType e2 );        //定义判断两元素值是否相等 函数
bool SqListInsert( SqList *L, int i, ElemType e );    //定义在顺序表L固定位置i插入一值e的 函数
bool SqListDelete( SqList *L, int i, ElemType *e );    //定义删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListUpdate( SqList *L, int i, ElemType e );    //定义修改顺序表中第i个元素的值 函数
int LocateByNum( SqList L, int i );                    //定义按位序查顺序表中元素的值 函数
ElemType LocateByElem( SqList L, ElemType e );        //定义按元素值查找在顺序表中的位置 函数
void PrintSqList( SqList L );                        //定义打印顺序表中各元素的值 函数
bool InsertElemAfterValue( SqList *L, ElemType value, ElemType e ); //定义在数据元素值为value的后面插入一个数据元素e 函数

SqList L;                //定义一个顺序表,名为L

int main() {

    InitList( &L );            //使用初始化函数将L初始化。
    PrintMenu();            //打印菜单函数
    FunSelect();            //功能选择函数

    return 0;
}

//实现初始化一个顺序表 函数
void InitList( SqList *L ) {
    L->length = 0;                                                        //初始化当前表长为0
    L->MaxSize = InitSize;                                                //初始化最大长度为InitSize
    L->data = ( ElemType * ) malloc( L->MaxSize * sizeof( ElemType ) );    //为顺序表申请一块连续的存储空间,为最大表长*数据大小
    for( int i = 0; i < L->MaxSize; i++ ) {                                //将顺序表中每一个元素的值初始化为0
        L->data[i] = 0;
    }
}

//实现增加动态数组长度 函数
bool IncreaseSize( SqList *L, int incLength ) {
    ElemType *p = L->data;
    L->data = ( ElemType * ) malloc( ( L->MaxSize + incLength ) * sizeof( ElemType ) );    //数组指针指向新开辟的连续存储空间头部
    if( L->data == NULL ) {
        L->data = p;
        return false;        //若 L->data == NULL 则证明开辟新空间失败。 则需将指针重新指向原来的数组空间头部。
    }

    for( int i = 0; i < L->length; i++ ) {
        L->data[i] = p[i];        //将原来数组中的值全部复制到新空间中
    }
    for( int i = L->MaxSize; i < L->MaxSize + incLength; i++ ) {
        L->data[i] = 0;            //将新空间申请的空间中的元素全部初始化为0
    }
    L->MaxSize += incLength;    //修改最大表长
    free( p );                    //释放原来数组空间
    return true;
}

//实现判断顺序表是否为空 函数
bool SqListEmpty( SqList L ) {
    if( L.length == 0 )
        return true;
    else return false;
}

//实现判断顺序表是否满 函数
bool SqListFull( SqList L ) {
    if( L.length == L.MaxSize )
        return true;
    else return false;
}

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

//实现在顺序表L固定位置i插入一值e的函数
bool SqListInsert( SqList *L, int i, ElemType e ) {

    /*
        在插入函数中,需要对i值的合法性,以及表是否满进行判断,故有以下情况:
        ①i值非法: i≤0或i≥现有表长
        ②表满,则不可插入新值。
        ③若无①②情况,则可插入,在i插入一值时,需要将i及其之后的元素后移。
    */

    /*①
    若i的值 小于1或者大于L->length+1则返回false,即 i的值≤0或大于现有表长则返回错误!
    当i=length+1时,表示的是:在表尾插入一个元素e ,此时无需后移元素。
    因为顺序表的存储结构是一个接个的,所以i的取值范围为 1 ≤i ≤当前表长(即L->Length+1)
    */
    if( i < 1 || i > L->length + 1 )
        return false;

    /*②
        若现有表长≥最大表长Maxsize 则返回false, 告诉函数调用处插入失败
        因为此时顺序表元素已满,且因为是顺序表在定义时是采用静态分配的方式创建的,所以不可扩展。
        若再插入新值,会导致溢出,造成程序崩溃。
    */
    if( SqListFull( *L ) )
        return false;

    //注意j=L->length是定位在最后一个元素的后面一个,而不是最后一个元素。因为length是长度,是位序,是数组下标+1!!!
    for( int j = L->length; j >= i; j-- ) {    //在C99及C11标准下可以在for循环里写int i这种形式。不必纠结这种写法的正确性
        L->data[j] = L->data[j - 1];         //这个For循环将i及其之后的元素后移一位。一定要从最后一个元素开始后移,否则会全部替换成data[i]
    }
    L->data[i - 1] = e;                    //同理还是因为i是为序,是数组下标+1 ,所以插入的数组下标为i-1;
    //For循环和 L->data[i-1]=e; 不可颠倒,否则会第i个位置的值丢失,变成e

    L->length++;                        //插入完成后需对线性表表长+1
    return true;                        //返回true,给调用处一个反馈,告诉他插入成功!
}

//实现删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListDelete( SqList *L, int i, ElemType *e ) {
    /*
    在删除函数中,需要对i值的合法性,故有以下情况:
    ①i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    ②若无①情况,则可删除,在i删除一值时,需要将i及其之后的元素前移。
    */

    /*①
    若i的值 小于1或者大于L->length则返回false,即 i的值≤0或≥现有表长length 则返回错误!
    若L->length==0则表示表空,也在此判断条件内,返回false;
    */
    if( i < 1 || i > L->length )        //注意与插入函数的区别
        return false;

    //利用指针传回第i个位置元素的值e;
    *e = L->data[i - 1];

    //将第i个位置后的元素前移。注意与插入函数的区别。
    for( int j = i; j < L->length; j++ ) {
        L->data[j - 1] = L->data[j];
    }
    /*
    考虑特殊情况:当i=1,且 L->length=1时
    For循环 j=i=1, j < L->length 即1<1显然是错误的,所以该循环不执行,直接跳出循环。
    之后 L->length--; 对长度减一,所以其实 L->data[j - 1]即L->data[0]的值还是原来那个值e,并没有变
    只是现有长度减一 变为0,成为一个标记的空表了而已。
    所以当我们正常打印顺序表的时候是看不到 L->data[0]的那个值e的。所以该函数是正确的。
    当然,如果你强行去输出L.data[0]的话 printf("%d",L.data[0]);  他会告诉你值依旧是e。
    */

    L->length--;                        //删除元素后将现有表长减一

    return true;
}

//实现修改顺序表中第i个元素的值
bool SqListUpdate( SqList *L, int i, ElemType e ) {

    /*
        在修改函数中,只需要对i值的合法性进行判定即可,无需移动元素
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    */
    if( i < 1 || i > L->length )
        return false;

    L->data[i - 1] = e;                //修改第i个位置的元素值为e。注意位序与下标的关系!
    return true;

}

//实现按位序查顺序表中元素的值 函数
ElemType LocateByNum( SqList L, int i ) {

    /*
        在查找函数中,只需要对i值的合法性进行判定即可。
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L->length==0)的情况
    */

    if( i < 1 || i > L.length )
        return 0;                    //若i值不合法则返回0表示未找到。

    return L.data[i - 1];            //若找到则返回该位序的值即可
}

//实现按元素值查找在顺序表中的位置 函数
int LocateByElem( SqList L, ElemType e ) {
    /*
        按顺序遍历顺序表,并一一比较顺序表中各数据元素的值即可
    */

    for( int i = 0; i < L.length; i++ ) {
        if( isEquality( L.data[i], e ) ) {    //判断是否相等,若相等则返回位序,即下标i+1
            return i + 1;
        }
    }
    return 0;            //若for循环走完则证明 未找到值为e的数据元素。返回0表示错误
}

//实现打印函数线性表L 函数
void PrintSqList( SqList L ) {
    int i;
    for( i = 0; i < L.length; i++ ) {
        printf( "%d ", L.data[i] );
    }
    if( i == 0 ) {
        printf( "NULL" );                //若为空表则输出NULL
    }
    printf( "\n" );
}

//实现在数据元素值为value的后面插入一个数据元素e 函数
bool InsertElemAfterValue( SqList *L, ElemType value, ElemType e ) {
    int order = LocateByElem( *L, value );
    if( !order ) {
        return false;
    }
    if( SqListInsert( L, order + 1, e ) ) {
        return true;
    } else return false;
}

//实现菜单函数
void PrintMenu() {
    
    printf( "\n☆数据结构-第二章-线性表-动态分配数据元素:\n\n" );
    printf( "\t————————————————————————————————\n" );
    printf( "\t| 1.动态增加数组长度\t\t\t\t\t\t|\n\n" );
    printf( "\t| 2.判断顺序表是否为空\t3.判断顺序表是否已满\t\t\t|\n\n" );
    printf( "\t| 4.插入函数\t\t5.删除函数\t\t6.修改函数\t|\n\n" );
    printf( "\t| 7.按位序查找函数\t8.按元素值查找函数\t\t\t|\n\n" );
    printf( "\t| 9.打印顺序表中各元素的值\t\t\t\t\t|\n\n" );
    printf( "\t| 10.在值Value后插入一新值e 函数\t\t\t\t|\n\n" );
    printf( "\t| 0.退出\t\t\t\t\t\t\t|\n" );
    printf( "\t————————————————————————————————\n\n" );

}

//实现功能选择函数
void FunSelect() {
    int funNum;
    while( true ) {
        printf( "请输入功能函数序号:" );
        scanf( "%d", &funNum );
        fflush( stdin );

        switch( funNum ) {
            case 0:
                exit( 0 );
            case 1: {
                int incLength;
                printf( "请输入新增长度:" );
                scanf( "%d", &incLength );
                fflush( stdin );
                if( IncreaseSize( &L, incLength ) ) {
                    printf( "新增成功!\n" );
                } else {
                    printf( "新增失败,空间不足!\n" );
                }
                break;
            }
            case 2: {
                if( SqListEmpty( L ) ) {
                    printf( "顺序表为空表\n" );
                } else {
                    printf( "顺序表为非空表,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 3: {
                if( SqListFull( L ) ) {
                    printf( "顺序表已满\n" );
                } else {
                    printf( "顺序表未满,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 4: {
                printf( "请依次输入插入位置i和插入数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListInsert( &L, i, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            case 5: {
                printf( "请输入删除位序i:" );
                int i;
                ElemType e;
                scanf( "%d", &i );
                fflush( stdin );
                if( SqListDelete( &L, i, &e ) ) {
                    printf( "删除成功,删除元素的值为:%d\n当前表中元素值为:\n", e );
                    PrintSqList( L );
                } else {
                    printf( "删除失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 6: {
                printf( "请输入修改元素的位序i和修改数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListUpdate( &L, i, e ) ) {
                    printf( "修改成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "修改失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 7: {
                printf( "请输入查找元素的位序i:" );
                int i;
                scanf( "%d", &i );
                fflush( stdin );
                ElemType result = LocateByNum( L, i );
                if( result ) {
                    printf( "查找成功,该位序元素的值为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 8: {
                printf( "请输入查找元素的值e:" );
                ElemType e;
                scanf( "%d", &e );
                fflush( stdin );
                int result = LocateByElem( L, e );
                if( result ) {
                    printf( "查找成功,该数据元素的位序为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:未找到该数据元素\n" );
                }
                break;
            }
            case 9: {
                printf( "顺序表中各元素的值依次为:\n" );
                PrintSqList( L );
                break;
            }
            case 10: {
                printf( "请依次输入插入位置的数据元素值value和新插入数据元素值e:" );
                ElemType value, e;
                scanf( "%d%d", &value, &e );
                fflush( stdin );
                if( InsertElemAfterValue( &L, value, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
        }
    }
}

4.顺序表-动态分配数据元素各功能实现(C语言 引用)

代码及注释如下:

/*
顺序表的实现,采用动态分配方式(C/C++语言) 以.cpp结尾的C++语言文件
由于C++语言支持引用,故已.cpp结尾,但仍采用C语言语法书写。
故:采用引用方式实现各种基本功能。
*/


#include <stdio.h>            //标准输入输出头文件 
#include <stdbool.h>        //在C99以后是GCC是有bool类型的定义的,但需引入stdbool.h头文件,其中false=0 true=1; 
#include <stdlib.h>            //因为动态分配需要使用malloc函数,故需引入其头文件stdlib.h 

#define ElemType int        //用ElemType 来代表int 方便以后修改数据类型
#define InitSize 50            //定义最大长度为50 ,方便后期修改最大表长 


typedef struct {
    ElemType *data;            //指示动态分配数组的指针,动态分配可以避免溢出
    int MaxSize;            //指示顺序表的最大容量
    int length;                //顺序表长度(当前有效元素的个数,并非总体长度)
} SqList;

void PrintMenu();            //定义菜单函数
void FunSelect();             //定义功能选择函数
void InitList( SqList &L );                            //定义初始化一个顺序表 函数
bool IncreaseSize( SqList &L, int newLength );         //定义增加动态数组长度 函数
bool SqListEmpty( SqList L );                        //定义判断顺序表是否为空 函数
bool SqListFull( SqList L );                        //定义判断顺序表是否满 函数
bool isEquality( ElemType e1, ElemType e2 );        //定义判断两元素值是否相等 函数
bool SqListInsert( SqList &L, int i, ElemType e );    //定义在顺序表L固定位置i插入一值e的 函数
bool SqListDelete( SqList &L, int i, ElemType &e );    //定义删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListUpdate( SqList &L, int i, ElemType e );    //定义修改顺序表中第i个元素的值 函数
int LocateByNum( SqList L, int i );                    //定义按位序查顺序表中元素的值 函数
ElemType LocateByElem( SqList L, ElemType e );        //定义按元素值查找在顺序表中的位置 函数
void PrintSqList( SqList L );                        //定义打印顺序表中各元素的值 函数
bool InsertElemAfterValue( SqList &L, ElemType value, ElemType e ); //定义在数据元素值为value的后面插入一个数据元素e 函数

SqList L;                //定义一个顺序表,名为L

int main() {

    InitList( L );            //使用初始化函数将L初始化。
    PrintMenu();            //打印菜单函数
    FunSelect();            //功能选择函数

    return 0;
}

//实现初始化一个顺序表 函数
void InitList( SqList &L ) {
    L.length = 0;                                                        //初始化当前表长为0
    L.MaxSize = InitSize;                                                //初始化最大长度为InitSize
    L.data = ( ElemType * ) malloc( L.MaxSize * sizeof( ElemType ) );    //为顺序表申请一块连续的存储空间,为最大表长*数据大小
    for( int i = 0; i < L.MaxSize; i++ ) {                                //将顺序表中每一个元素的值初始化为0
        L.data[i] = 0;
    }
}

//实现增加动态数组长度 函数
bool IncreaseSize( SqList &L, int incLength ) {
    ElemType *p = L.data;
    L.data = ( ElemType * ) malloc( ( L.MaxSize + incLength ) * sizeof( ElemType ) );    //数组指针指向新开辟的连续存储空间头部
    if( L.data == NULL ) {
        L.data = p;
        return false;        //若 L.data == NULL 则证明开辟新空间失败。 则需将指针重新指向原来的数组空间头部。
    }

    for( int i = 0; i < L.length; i++ ) {
        L.data[i] = p[i];        //将原来数组中的值全部复制到新空间中
    }
    for( int i = L.MaxSize; i < L.MaxSize + incLength; i++ ) {
        L.data[i] = 0;            //将新空间申请的空间中的元素全部初始化为0
    }
    L.MaxSize += incLength;    //修改最大表长
    free( p );                    //释放原来数组空间
    return true;
}

//实现判断顺序表是否为空 函数
bool SqListEmpty( SqList L ) {
    if( L.length == 0 )
        return true;
    else return false;
}

//实现判断顺序表是否满 函数
bool SqListFull( SqList L ) {
    if( L.length == L.MaxSize )
        return true;
    else return false;
}

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

//实现在顺序表L固定位置i插入一值e的函数
bool SqListInsert( SqList &L, int i, ElemType e ) {

    /*
        在插入函数中,需要对i值的合法性,以及表是否满进行判断,故有以下情况:
        ①i值非法: i≤0或i≥现有表长
        ②表满,则不可插入新值。
        ③若无①②情况,则可插入,在i插入一值时,需要将i及其之后的元素后移。
    */

    /*①
    若i的值 小于1或者大于L.length+1则返回false,即 i的值≤0或大于现有表长则返回错误!
    当i=length+1时,表示的是:在表尾插入一个元素e ,此时无需后移元素。
    因为顺序表的存储结构是一个接个的,所以i的取值范围为 1 ≤i ≤当前表长(即L.Length+1)
    */
    if( i < 1 || i > L.length + 1 )
        return false;

    /*②
        若现有表长≥最大表长Maxsize 则返回false, 告诉函数调用处插入失败
        因为此时顺序表元素已满,且因为是顺序表在定义时是采用静态分配的方式创建的,所以不可扩展。
        若再插入新值,会导致溢出,造成程序崩溃。
    */
    if( SqListFull( L ) )
        return false;

    //注意j=L.length是定位在最后一个元素的后面一个,而不是最后一个元素。因为length是长度,是位序,是数组下标+1!!!
    for( int j = L.length; j >= i; j-- ) {    //在C99及C11标准下可以在for循环里写int i这种形式。不必纠结这种写法的正确性
        L.data[j] = L.data[j - 1];         //这个For循环将i及其之后的元素后移一位。一定要从最后一个元素开始后移,否则会全部替换成data[i]
    }
    L.data[i - 1] = e;                    //同理还是因为i是为序,是数组下标+1 ,所以插入的数组下标为i-1;
    //For循环和 L.data[i-1]=e; 不可颠倒,否则会第i个位置的值丢失,变成e

    L.length++;                        //插入完成后需对线性表表长+1
    return true;                        //返回true,给调用处一个反馈,告诉他插入成功!
}

//实现删除顺序表L固定位置i的值,并返回其值的 函数
bool SqListDelete( SqList &L, int i, ElemType &e ) {
    /*
    在删除函数中,需要对i值的合法性,故有以下情况:
    ①i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    ②若无①情况,则可删除,在i删除一值时,需要将i及其之后的元素前移。
    */

    /*①
    若i的值 小于1或者大于L.length则返回false,即 i的值≤0或≥现有表长length 则返回错误!
    若L.length==0则表示表空,也在此判断条件内,返回false;
    */
    if( i < 1 || i > L.length )        //注意与插入函数的区别
        return false;

    //利用指针传回第i个位置元素的值e;
    e = L.data[i - 1];

    //将第i个位置后的元素前移。注意与插入函数的区别。
    for( int j = i; j < L.length; j++ ) {
        L.data[j - 1] = L.data[j];
    }
    /*
    考虑特殊情况:当i=1,且 L.length=1时
    For循环 j=i=1, j < L.length 即1<1显然是错误的,所以该循环不执行,直接跳出循环。
    之后 L.length--; 对长度减一,所以其实 L.data[j - 1]即L.data[0]的值还是原来那个值e,并没有变
    只是现有长度减一 变为0,成为一个标记的空表了而已。
    所以当我们正常打印顺序表的时候是看不到 L.data[0]的那个值e的。所以该函数是正确的。
    当然,如果你强行去输出L.data[0]的话 printf("%d",L.data[0]);  他会告诉你值依旧是e。
    */

    L.length--;                        //删除元素后将现有表长减一

    return true;
}

//实现修改顺序表中第i个元素的值
bool SqListUpdate( SqList &L, int i, ElemType e ) {

    /*
        在修改函数中,只需要对i值的合法性进行判定即可,无需移动元素
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    */
    if( i < 1 || i > L.length )
        return false;

    L.data[i - 1] = e;                //修改第i个位置的元素值为e。注意位序与下标的关系!
    return true;

}

//实现按位序查顺序表中元素的值 函数
ElemType LocateByNum( SqList L, int i ) {

    /*
        在查找函数中,只需要对i值的合法性进行判定即可。
        即:i值非法: i≤0或i≥现有表长  此时已经包含表空(L.length==0)的情况
    */

    if( i < 1 || i > L.length )
        return 0;                    //若i值不合法则返回0表示未找到。

    return L.data[i - 1];            //若找到则返回该位序的值即可
}

//实现按元素值查找在顺序表中的位置 函数
int LocateByElem( SqList L, ElemType e ) {
    /*
        按顺序遍历顺序表,并一一比较顺序表中各数据元素的值即可
    */

    for( int i = 0; i < L.length; i++ ) {
        if( isEquality( L.data[i], e ) ) {    //判断是否相等,若相等则返回位序,即下标i+1
            return i + 1;
        }
    }
    return 0;            //若for循环走完则证明 未找到值为e的数据元素。返回0表示错误
}

//实现打印函数线性表L 函数
void PrintSqList( SqList L ) {
    int i;
    for( i = 0; i < L.length; i++ ) {
        printf( "%d ", L.data[i] );
    }
    if( i == 0 ) {
        printf( "NULL" );                //若为空表则输出NULL
    }
    printf( "\n" );
}

//实现在数据元素值为value的后面插入一个数据元素e 函数
bool InsertElemAfterValue( SqList &L, ElemType value, ElemType e ) {
    int order = LocateByElem( L, value );
    if( !order ) {
        return false;
    }
    if( SqListInsert( L, order + 1, e ) ) {
        return true;
    } else return false;
}

//实现菜单函数
void PrintMenu() {
    
    printf( "\n☆数据结构-第二章-线性表-动态分配数据元素:\n\n" );
    printf( "\t————————————————————————————————\n" );
    printf( "\t| 1.动态增加数组长度\t\t\t\t\t\t|\n\n" );
    printf( "\t| 2.判断顺序表是否为空\t3.判断顺序表是否已满\t\t\t|\n\n" );
    printf( "\t| 4.插入函数\t\t5.删除函数\t\t6.修改函数\t|\n\n" );
    printf( "\t| 7.按位序查找函数\t8.按元素值查找函数\t\t\t|\n\n" );
    printf( "\t| 9.打印顺序表中各元素的值\t\t\t\t\t|\n\n" );
    printf( "\t| 10.在值Value后插入一新值e 函数\t\t\t\t|\n\n" );
    printf( "\t| 0.退出\t\t\t\t\t\t\t|\n" );
    printf( "\t————————————————————————————————\n\n" );

}

//实现功能选择函数
void FunSelect() {
    int funNum;
    while( true ) {
        printf( "请输入功能函数序号:" );
        scanf( "%d", &funNum );
        fflush( stdin );

        switch( funNum ) {
            case 0:
                exit( 0 );
            case 1: {
                int incLength;
                printf( "请输入新增长度:" );
                scanf( "%d", &incLength );
                fflush( stdin );
                if( IncreaseSize( L, incLength ) ) {
                    printf( "新增成功!\n" );
                } else {
                    printf( "新增失败,空间不足!\n" );
                }
                break;
            }
            case 2: {
                if( SqListEmpty( L ) ) {
                    printf( "顺序表为空表\n" );
                } else {
                    printf( "顺序表为非空表,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 3: {
                if( SqListFull( L ) ) {
                    printf( "顺序表已满\n" );
                } else {
                    printf( "顺序表未满,其元素个数为%d\n", L.length );
                }
                break;
            }
            case 4: {
                printf( "请依次输入插入位置i和插入数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListInsert( L, i, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
            case 5: {
                printf( "请输入删除位序i:" );
                int i;
                ElemType e;
                scanf( "%d", &i );
                fflush( stdin );
                if( SqListDelete( L, i, e ) ) {
                    printf( "删除成功,删除元素的值为:%d\n当前表中元素值为:\n", e );
                    PrintSqList( L );
                } else {
                    printf( "删除失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 6: {
                printf( "请输入修改元素的位序i和修改数据元素值e:" );
                int i;
                ElemType e;
                scanf( "%d%d", &i, &e );
                fflush( stdin );
                if( SqListUpdate( L, i, e ) ) {
                    printf( "修改成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "修改失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 7: {
                printf( "请输入查找元素的位序i:" );
                int i;
                scanf( "%d", &i );
                fflush( stdin );
                ElemType result = LocateByNum( L, i );
                if( result ) {
                    printf( "查找成功,该位序元素的值为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:位序不合法\n" );
                }
                break;
            }
            case 8: {
                printf( "请输入查找元素的值e:" );
                ElemType e;
                scanf( "%d", &e );
                fflush( stdin );
                int result = LocateByElem( L, e );
                if( result ) {
                    printf( "查找成功,该数据元素的位序为:%d\n", result );
                } else {
                    printf( "查找失败! 原因:未找到该数据元素\n" );
                }
                break;
            }
            case 9: {
                printf( "顺序表中各元素的值依次为:\n" );
                PrintSqList( L );
                break;
            }
            case 10: {
                printf( "请依次输入插入位置的数据元素值value和新插入数据元素值e:" );
                ElemType value, e;
                scanf( "%d%d", &value, &e );
                fflush( stdin );
                if( InsertElemAfterValue( L, value, e ) ) {
                    printf( "插入成功,当前表中元素值为:\n" );
                    PrintSqList( L );
                } else {
                    printf( "插入失败! 原因:位序不合法或表已满\n" );
                }
                break;
            }
        }
    }
}

目录
相关文章
|
21天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
31 4
|
30天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
29 6
|
9天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
20 1
|
2月前
|
设计模式 安全 Java
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
假如有T1、T2两个线程同时对某链表扩容,他们都标记头结点和第二个结点,此时T2阻塞,T1执行完扩容后链表结点顺序反过来,此时T2恢复运行再进行翻转就会产生环形链表,即B.next=A;采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。JDK8中,HashMap采用尾插法,扩容时链表节点位置不会翻转,解决了扩容死循环问题,但是性能差了一点,因为要遍历链表再查到尾部。例如15(即2^4-1)的二进制为1111,31的二进制为11111,63的二进制为111111,127的二进制为1111111。
HashMap底层原理:数据结构+put()流程+2的n次方+死循环+数据覆盖问题
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
30天前
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
52 0
|
1月前
【数据结构】二叉搜索树的功能实现详解
【数据结构】二叉搜索树的功能实现详解
23 0
|
1月前
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
33 0

热门文章

最新文章