标签：arr return 线性表 int pBase length parr 第二章

一、线性表的定义及具体操作

1.定义

线性表（Linear List）是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

若用L命名线性表，则其一般表示为：\(L=（a_1,a_2,\cdots,a_i,a_i+1,\cdots,a_n）\)。

\(a_i\)是线性表中的“第i个“元素线性表中的位序

位序，线性表的位序是从1开始的，C语言中数组的下标是从0开始的

\(a_1\)是表头元素；\(a_n\)是表尾元素

除了第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

2.具体操作

（1）初始化void InitList(Elemtype * L, int length)，构造一个length长度的线性表L，分配内存空间。

（2）插入操作bool ListInsert(Elemtype * L,Elemtype I,Elemtype e)，在表L中的第i个位置上插入指定元素e。

（3）删除操作bool ListDelete(Elemtype * L,Elemtype i,Elemtype * e)，删除表L中第I个位置的元素，并用e返回删除元素的值。

（4）输出操作void PrintList(Elemtype * L)，按前后顺序输出线性表L的所有元素值。

（5）判空操作bool is_empty(Elemtype * L)，若L为空表则返回true，否则返回false。

（6）判满操作bool is_full(Elemtype * L)，若L为满表则返回true，否则返回false。

（7）追加操作bool append_arr(Elemtype * L, int val)，在表L后面追加新的值。

（8）倒置操作void inversion_arr(Elemtype * L);将表L中的值的顺序倒置。

3.为什么要实现对数据结构的基本操作

（1）团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）

（2）将常用的操作/运算封装成函数，避免重复工作，降低出错风险

二、顺序表的定义

1.定义

顺序表指的是用顺序存储的方式实现线性表，顺序存储是指把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2.特点

1.随机访问，即可以在O(1)的时间内找到第i个元素。

2.存储密度高，每个节点只存储数据元素。

3.拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）。

4.插入删除操作不方便，需要移动大量元素。

3.代码实现

（1）静态数组实现

# include <stdio.h>

struct SqList
{
    int data[10];
    int length;//数组所能容纳的最大元素的个数
};

void InitList(SqList * L);//初始化

int main(void)
{
    SqList L;
    InitList(&L);
    return 0;
}

void InitList(SqList * L)
{
    int i;
    for(i=0; i<10; i++)
    {
        L->data[i] = 0;
    }
        L->length = 0;
}

（2）动态数组实现

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

typedef struct Arr
{
    int * pBase;//存储数组第一个元素的地址
    int len;//数组所能容纳的最大元素的个数
    int cnt;//当前数组的有效元素的个数
}Arr, *pArr;

void init_arr(pArr parr, int length);//初始化

int main(void)
{
    Arr arr;
    init_arr(&arr, 6);

}

void init_arr(pArr parr, int length)
{
    parr->pBase = (int *)malloc(sizeof(int) * length);
    if(NULL == parr->pBase)
    {
        printf("动态内存分配失败！\n");
        exit(-1);//终止整个程序
    }
    else
    {
        parr->len = length;
        parr->cnt = 0;
    }
    return;
}

三、顺序表的操作

1.顺序表的插入

（1）代码实现

静态数组实现

bool ListInsert(SqList * L, int i, int e)
{
    if(i<1 || i>L->length+1)
        return false;
    if(L->length >= MaxSize)
        return false;
    int j;
    for(j = L->length; j>=i; j--)
    {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}

动态数组实现

bool insert_arr(pArr parr, int pos, int val)
{
    if(is_full(parr))
    return false;
    if(pos<0 || pos>parr->cnt)
    return false;

    for(int i=parr->cnt-1; i>=pos; i--)
    {
        parr->pBase[i+1] = parr->pBase[i];
    }
    parr->pBase[pos] = val;
    return true;
    parr->cnt++;
}

（2）时间复杂度分析

问题规模n=L->length，即表长

最好情况：新元素插入到表尾，不需要移动元素

i=n+1，循环0次；最好时间复杂度=O(1)

最坏情况：新元素插入到表头，需要将原有的n个元素全部向后移动

i=1，循环n次；最坏时间复杂度=O(n)

平均情况：假设新元素插入到任何一个位置的概率相同，即\(i=1,2,3，\cdots，length+1\)的概率都是\(p=\frac{1}{n+1}\)；

i=1时，循环n次；i=2时，循环n-1次；i=3时，循环n-2次；\(\cdots\)；i=n+1时，循环0次；

平均循环次数=\((n)p+(n-1)p+(n-2)p+\cdots+1*p = \frac{n(n+1)}{2}*\frac{1}{n+1}=\frac{n}{2}\)=>平均时间复杂度=O(n)

2.顺序表的删除

（1）代码实现

静态数组实现

bool ListDelete(SqList * L, int i, int * e)
{
    int j;
    if(i<1||i>L->length)
        return false;
    *e = L->data[i-1];
    for(j=i; j<L->length; j++)
    {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return true;
}

动态数组实现

bool delete_arr(pArr parr, int pos, int * pVal)
{
    if(is_empty(parr))
    return false;
    if(pos<0 || pos>parr->cnt)
    return false;

    *pVal = parr->pBase[pos];
    for(int i=pos; i<parr->cnt; ++i)
    {
        parr->pBase[i] = parr->pBase[i+1];
    }
    parr->cnt--;
    return true;
}

（2）时间复杂度分析

问题规模n=L->length，即表长

最好情况：删除表尾元素，不需要移动元素

i=n+1，循环0次；最好时间复杂度=O(1)

最坏情况：删除表头元素，需要将后面的n个元素全部向前移动

i=1，循环n-1次；最坏时间复杂度=O(n)

平均情况：假设新元素插入到任何一个位置的概率相同，即\(i=1,2,3，\cdots，length\)的概率都是\(p=\frac{1}{n}\)；

i=1时，循环n-1次；i=2时，循环n-2次；i=3时，循环n-3次；\(\cdots\)；i=n时，循环0次；

平均循环次数=\((n-1)p+(n-2)p+\cdots+1*p = \frac{n(n-1)}{2}*\frac{1}{n}=\frac{n-1}{2}\)=>平均时间复杂度=O(n)

四、顺序表的实现及相关操作的完整代码

1.静态数组实现

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

typedef struct
{
    int data[10];
    int length;
}SqList;

void InitList(SqList * L);//初始化
bool ListInsert(SqList * L, int i, int e);//插入
bool ListDelete(SqList * L, int i, int * e);//删除

int main(void)
{
    SqList L;
    InitList(&L);
    int e = -1;
    if(ListInsert(&L, 1, 3))
        printf("插入元素成功\n");
    else
        printf("位序i不合法，插入失败！\n");

    if(ListDelete(&L, 1, &e))
        printf("已删除第1个元素，删除的元素值为%d\n", e);
    else
        printf("位序i不合法，删除失败！\n");
    return 0;
}

void InitList(SqList * L)
{
    int i;
    for(i=0; i<10; i++)
    {
        L->data[i] = 0;
    }
        L->length = 0;
}

bool ListInsert(SqList * L, int i, int e)
{
    if(i<1 || i>L->length+1)
        return false;
    if(L->length >= 10)
        return false;
    int j;
    for(j = L->length; j>=i; j--)
    {
        L->data[j] = L->data[j-1];
    }
    L->data[i-1] = e;
    L->length++;
    return true;
}

bool ListDelete(SqList * L, int i, int * e)
{
    int j;
    if(i<1||i>L->length)
        return false;
    *e = L->data[i-1];
    for(j=i; j<L->length; j++)
    {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return true;
}

2.动态数组实现

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

typedef struct Arr
{
    int * pBase;//存储数组第一个元素的地址
    int len;//数组所能容纳的最大元素的个数
    int cnt;//当前数组的有效元素的个数
}Arr, *pArr;

void init_arr(pArr parr, int length);//初始化
bool append_arr(pArr parr, int val);//追加
bool insert_arr(pArr parr, int pos, int val);//插入
bool delete_arr(pArr parr, int pos, int * pVal);//删除
bool is_empty(pArr parr);//判断空
bool is_full(pArr parr);//判断满
void show_arr(pArr  parr);//输出
void inversion_arr(pArr parr);//倒置

int main(void)
{
    Arr arr;
    int val;

    init_arr(&arr, 6);

    if(append_arr(&arr, 1))
    printf("追加成功！\n");
    else
    printf("追加失败，数组已满！\n");

    if(append_arr(&arr, 2))
    printf("追加成功！\n");
    else
    printf("追加失败，数组已满！\n");

    if(append_arr(&arr, 3))
    printf("追加成功！\n");
    else
    printf("追加失败，数组已满！\n");

    if(append_arr(&arr, 4))
    printf("追加成功！\n");
    else
    printf("追加失败，数组已满！\n");

    if(append_arr(&arr, 5))
    printf("追加成功！\n");
    else
    printf("追加失败，数组已满！\n");

    if(insert_arr(&arr, 0, 99))
    printf("插入成功！\n");
    else
    printf("插入失败!\n");

    if(delete_arr(&arr, 6, &val))
    printf("删除成功，被删除的数据是：%d！\n", val);
    else
    printf("删除失败!\n");
    inversion_arr(&arr);
    show_arr(&arr);
    free(arr.pBase);
}

void init_arr(pArr parr, int length)
{
    parr->pBase = (int *)malloc(sizeof(int) * length);
    if(NULL == parr->pBase)
    {
        printf("动态内存分配失败！\n");
        exit(-1);//终止整个程序
    }
    else
    {
        parr->len = length;
        parr->cnt = 0;
    }
    return;
}

void show_arr(pArr parr)
{
    if(is_empty(parr))
    {
        printf("数组为空!\n");
    }
    else
    {
        for (int i=0; i<=parr->cnt; ++i)
        {
            printf("%d ", parr->pBase[i]);
        }
        printf("\n");
    }
}

bool is_empty(pArr parr)
{
    if(0 == parr->cnt)
        return true;
    else
        return false;
}

bool append_arr(pArr parr, int val)
{
    if(is_full(parr))
        return false;

        parr->pBase[parr->cnt]=val;
        parr->cnt++;
    return true;
}

bool is_full(pArr parr)
{
    if(parr->cnt == parr->len)
        return true;
    else
        return false;
}

bool insert_arr(pArr parr, int pos, int val)
{
    if(is_full(parr))
    return false;
    if(pos<0 || pos>parr->cnt)
    return false;

    for(int i=parr->cnt-1; i>=pos; i--)
    {
        parr->pBase[i+1] = parr->pBase[i];
    }
    parr->pBase[pos] = val;
    return true;
    parr->cnt++;

}

bool delete_arr(pArr parr, int pos, int * pVal)
{
    if(is_empty(parr))
    return false;
    if(pos<0 || pos>parr->cnt)
    return false;

    *pVal = parr->pBase[pos];
    for(int i=pos; i<parr->cnt; ++i)
    {
        parr->pBase[i] = parr->pBase[i+1];
    }
    parr->cnt--;
    return true;
}

void inversion_arr(pArr parr)
{
    int i = 0;
    int j = parr->cnt;
    int t;

    while(i < j)
    {
    t = parr->pBase[i];
    parr->pBase[i] = parr->pBase[j];
    parr->pBase[j] = t;

    ++i;
    --j;
    }
    return;
}

标签：arr,return,线性表,int,pBase,length,parr,第二章
From： https://www.cnblogs.com/renren-note/p/17038971.html

第二章线性表（上）

一、线性表的定义及具体操作

1.定义

2.具体操作

3.为什么要实现对数据结构的基本操作

二、顺序表的定义

1.定义

2.特点

3.代码实现

三、顺序表的操作

1.顺序表的插入

2.顺序表的删除

四、顺序表的实现及相关操作的完整代码

1.静态数组实现

2.动态数组实现

相关文章

赞助商

阅读排行

第二章 线性表（上）

一、线性表的定义及具体操作

1.定义

2.具体操作

3.为什么要实现对数据结构的基本操作

二、顺序表的定义

1.定义

2.特点

3.代码实现

三、顺序表的操作

1.顺序表的插入

2.顺序表的删除

四、顺序表的实现及相关操作的完整代码

1.静态数组实现

2.动态数组实现

相关文章

赞助商

阅读排行

第二章线性表（上）