数据结构第二章线性表以及顺序表实现线性表|越行勤‘s Blog

复习结构体

//此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c
//同时又声明了结构体变量s1
//这个结构体并没有标明其标签
struct 
{
    int a;
    char b;
    double c;
} s1;
 
//此声明声明了拥有3个成员的结构体，分别为整型的a，字符型的b和双精度的c
//结构体的标签被命名为SIMPLE,没有声明变量
struct SIMPLE
{
    int a;
    char b;
    double c;
};
//用SIMPLE标签的结构体，另外声明了变量t1、t2、t3
struct SIMPLE t1, t2[20], *t3;
 
//也可以用typedef创建新类型
typedef struct
{
    int a;
    char b;
    double c; 
} Simple2;
//现在可以用Simple2作为类型声明新的结构体变量
Simple2 u1, u2[20], *u3;

值得强调一点的是 struct SIMPLE t1, t2[20], *t3;
这样去命名实在太麻烦了，我们可以使用 typedef <数据类型> <别名> 简化一下名字，就如同上面最后一个方法，无需再写 struct了

线性表

基本概念

定义：线性表，具有相同数据类型的n(n>=0)个数据元素的有限序列。
其中n 为表长，n=0时，线性表为空表。如果使用L命令线性表，那么L=（a1,a2,a3...,an)
线性表中的元素从1开始，位序也就是指在第几个位置
除第一个元素，其余元素都有一个直接前驱
除最后一个元素，其余元素都有一个直接后继

基本操作

创销，增删改查

InitList(&L):初始化表，构造一个线性表，分配内存空间
DestroyList(&L):销毁操作，销毁一个线性表，释放所占的内存空间
ListInsert(&L,i,e),插入,在表的第i个位置上插入元素e
ListDelete(&L,i,&e):删除,删除表上第i个位置上的元素e
LocateElem(L,e):按值查找
GetElem(L,i):按位查找
Length(L),求表长
PrintList(L),输出
Empty(L)，判断是否为空表

线性表的物理结构之一 --- 顺序表

顺序表：用顺序存储的方式来实现线性表

顺序存储：逻辑上相邻的元素存储在物理位置上也相邻，元素之间的存储关系由数据单元的邻接关系来体现。

顺序表实现---静态分配

定义：

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];//开辟空间
    int length;//顺序表当前长度
} SqList;
SqList L;//定义顺序表

为了后续说明方便，我们统一规定，下标从1开始，并不是从0开始,也就意味着data数组下标会比实际下标小 1

初始化:

void InitList(SqList &L) //此处L为引用
{
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;//
    L.length = 0;//长度初始化
}

顺序表实现---动态分配

静态分配的大小一但定义下来的，大小就没办法改变了。

c语言就动态分配内存用的是 malloc()和free(),C++使用的就是 new 和delete.

malloc

需要引入库文件include <stdlib.h>

简单介绍一下malloc 函数 void *malloc(size_t size) 分配所需的内存空间，并返回一个指向它的指针。，

如果我们要开辟10个int大小的空间，int * data = (int *)malloc(InitSize * sizeof(int));,我们还需要把void*转换成 int*
如果申请失败，返回NULL

定义：

#define InitSize 10
// 动态分配
typedef struct
{
    int *data;   //顺序表动态分配的指针
    int maxSize; //顺序表最大容量
    int lenght;  // 顺序表当前长度
} SeqList;

初始化函数：

bool InitList(SeqList &L)
{
    L.data = (int *)malloc(InitSize * sizeof(int));
 //开辟内存空间
if(!L.data) return false;
    L.lenght = 0;                                   //当前长度为0
    L.maxSize = InitSize;                           //最大的长度为 initseize
return true;
}

动态顺序表增加长度

动态就体现在可以变换长度

void IncreateSize(SeqList &L, int len)
{
    int *p = L.data;                                        //保持原来数据的地址
    L.data = (int *)malloc((InitSize + len) * sizeof(int)); //开辟新的内存空间
    // 把原来的数据拷贝过来
    for (int i = 0; i < L.lenght; i++)
        L.data[i] = p[i];
    L.maxSize = L.maxSize + len; //重新定义最大长度
    free(p);                     //释放内存空间
}

malloc的亲戚 calloc 和 realloc

calloc
void* calloc(size_t numElements, size_t sizeOfElement);
与malloc相似，参数sizeOfElement为单位元素长度（例如：
sizeof(int)），numElements为元素个数，即在内存中申请numElements *
sizeOfElement字节大小的连续内存空间。
realloc
void* realloc(void* ptr, unsigned newsize);
功能为修改 malloc 和 calloc 分配的空间
ptr为修改空间的首地址，此时有4种情况

如果ptr为NULL，则函数相当于malloc(new_size)
如果 ptr 所占的空间比 newsize 小增加ptr空间到newsize 并且把数据也拷贝过去
如果 ptr 所占的空间比 newsize 大减小ptr的空间到newsize 只保留到newsize内的数据
如果 ptr 所占的空间比 newsize 相等啥都不做

bool IncreateSize_SqList(SqList& L, int len)
{
    if (len < 0)
        return false;
    int* new_base = (int*)realloc(L.data, (L.SqListSize + len) * sizeof(int));
    if (!new_base) //如果分配空间失败
    {
        return false;
    }
    L.data = new_base;
    L.SqListSize += len;
    return true; 
}

顺序表的特点

随机访问，即可以在O(1) 时间内找到第i个元素。
存储密度高，每个节点仅仅存储数据元素
拓展容量很麻烦，即使使用动态分配的方法,拓展长度的时间复杂度还是比较高
插入，删除操作，不方便，需要移动大量元素。

顺序表的实现 ---- 插入，删除

下面的都是基于静态分配顺序表

在第i插入位置上插入数据

我们要在第i的位置上插入指定元素e，那么就需要把第i个位置后面数据向后移动（从最后一个开始移动）。
注意for循环时把先把插入点数据向后移动一位，注意我们顺序表的编号时从0开始的，所以最后一个元素的数组下标是 Lenght-1 ，被插入点的元素数组下标是i-1

void ListInsert(SqList &L, int e, int i)
{
        // 先把插入点数据向后移动一位
        for (int j = L.length-1; j >= i-1; j--)
        {
            L.data[j+1] = L.data[j];//后移元素一个位置
        }
        //  在把给插入点赋值
        L.data[i-1] = e;
        L.length++;
}

当然，这个我们更加希望我们能够知道是否插入成功，所以最好加一个返回值。

插入失败的情况有：

插入点 i 不合理， i>L.length+1;||i<1
顺序表已满， L.length>=MaxSize;

bool ListInsert(SqList &L, int e, int i)
{
    if (i > = L.length || i < 1)
        return false;
    if (L.length> =MaxSize)
        return false;
    // 先把插入点数据向后移动一位
    for (int j = L.length-1; j > =i-1; j--)
    {
        L.data[j+1] = L.data[j];
    }
    //  在把给插入点赋值
    L.data[i-1] = e;
    L.length++;
return true;
}

当然这是对静态顺序表来说的，动态顺序表如果存储空间不够了，应该自动增加存储空间。

// 插入元素
bool Insert_SqList(SqList& L, int i, int e)
{
    if (i < 0 || i>L.Lenght)
        return false;
    //当顺序表满时 增加空间
    if (L.Lenght == L.SqListSize)
        if(!IncreateSize_SqList(L, AddSize))//如果分配失败返回 false
            return false;
    //插入元素
    int* q=L.data+i-1;   //q为插入的位置
    //开始将插入点和后面的元素向后移动一位
    for (int* p = L.data + L.Lenght - 1; p >= q; p--) //从最后一个元素 向后移动一个位置 直到插入点元素
        *(p + 1) = *p;
    *q = e;
    L.Lenght++;
    return true;
}

这里主要使用的指针，练习自己的对指针的熟悉程度。

我们现在分析一下时间复杂度。

根据第一章的知识，我们只需要关注最深层次的循环即可。

问题规模：L.length

最好的情况就是，j=i-1,也就是 i =length+1,循环一次就好了。即最好时间复杂度为O(1);
最坏的的情况就是，i=1;要循环n次，即最坏时间复杂度为O(n);
平均的情况就是每一次的几率相等，也就是 1，2，3.....length+1 每一次出现的概率为 1/n+1;

那么也就说平均循环次数：（n+1)n/2*1/(n+1)=n/2 ，也就是 T(n)为O(n);

删除第i个位置元素并返回删除元素

用传入参数 &e 带回删除的元素。
值得强调的是删除第i个元素需要移动第i个元素后面的所有元素（从数组下标i开始）提前一个位置（直到表尾元素序号length结束）。

bool ListDelete(SqList &L, int i，int &e)
{
    if (i >= L.length || i < 1)
        return false;
    // 把删除点后面的数据向前移动一格
    e=L.data[i-1];
    for (int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

时间复杂度，和前面差不多，

最好的情况：删除表位的元素，不需要移动元素 T(n)=0=O(1)
最坏的情况：删除表头的元素，需要把后续的n-1个元素都移动

循环n-1; T(n)=O(n)
平均的情况：循环 0,1，2，3.....n-1次的概率都是为 1/n,平均循环次数为 n(n-1)/2n =(n-1)/2

T(n)=O(n)

查找

按位查找

int GetElem(SqList L, int i)
{
    if (i < 1 || i > L.length + 1)
        return 0;
    return L.data[i];
}

最好最坏都一样，所以平均复杂度等于他们等于 O(1)

按数据查找

// 数据查找
int LocateElem(SqList L, int e)
{
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
        {
            return i + 1;
        }
    }
    return 0;
}

时间复杂度，其实和插入的情况一致的，不再赘述了。

顺序表简答实现

分享我自己简单使用c语言实现了一下动态顺序表，

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

/*** 动态顺序表  下标从1 开始***/

// 动态顺序表
#define InitSize 20 // 顺序表初始空间分配大小
#define AddSize 5   // 顺序表存储空间分配增量

//顺序表的定义
typedef struct
{
    int* data;      //存储空间的基地址
	int Lenght;     //顺序表的长度
    int SqListSize; //当前顺序表的存储容量
} SqList;

bool Init_SqList(SqList& L);                  //初始化顺序表
bool IncreateSize_SqList(SqList& L, int len); //增加顺序表的存储空间大小len
bool Insert_SqList(SqList& L, int i, int e);  //在第i个位置上插入元素e
bool Delete_SqList(SqList& L, int i, int& e); //删除第i个元素，并用e返回删除元素
bool GetElem_SqList(SqList L,int i,int& e);         //获取第i个位置上的元素
bool Empty_SqList(SqList L);                  //判断顺序表是否为空
bool Destory_SqList(SqList& L);               //销毁顺序表

//简单测试一下
void test()
{
    SqList L;
    int e;
    Init_SqList(L);
    printf("L初始化完成 ^_^\n");
    for (int i = 1; i <= 25; i++)
    {
        Insert_SqList(L, i, i);
    }
    printf("添加数据完成,L.lenght :%d\n",L.Lenght);
    for (int i = 1; i <= L.Lenght; i++)
    {
        GetElem_SqList(L, i, e);
        printf(" 在第%3d个位置上数据为        %3d   \n", i, e);
    }
    
    Delete_SqList(L, 5, e);
    printf("完成删除第5个数据 \n \n");
    for (int i = 1; i <= L.Lenght; i++)
    {
        GetElem_SqList(L, i, e);
        printf(" 在第%3d个位置上数据为        %3d   \n", i, e);
    }
    Destory_SqList(L);
}
int main()
{
    test();
    getchar();
    return 0;
}

//初始化
bool Init_SqList(SqList& L)
{
    //分配空间失败则返回false
    L.data = (int*)malloc(InitSize * sizeof(int));
    if (L.data == NULL)
        return false;
    L.Lenght = 0;
    L.SqListSize = InitSize;
    return true;
}
// 增加顺序表的长度
bool IncreateSize_SqList(SqList& L, int len)
{
    if (len < 0)
        return false;
    int* new_base = (int*)realloc(L.data, (L.SqListSize + len) * sizeof(int));
    if (!new_base) //如果分配空间失败
    {
        return false;
    }
    L.data = new_base;
    L.SqListSize += len;
    return true; 
}
// 判空
bool Empty_SqList(SqList L)
{
    if (L.Lenght == 0)
        return true;
    return false;
}

// 插入元素
bool Insert_SqList(SqList& L, int i, int e)
{
    if (i < 1)
        return false;
    //当顺序表满时 增加空间
    if (L.Lenght >= L.SqListSize)
        if(!IncreateSize_SqList(L, AddSize))//如果分配失败返回 false
            return false;
    //插入元素
    int* q=L.data+i-1;   //q为插入的位置
    //开始将插入点和后面的元素向后移动一位
    for (int* p = L.data + L.Lenght - 1; p >= q; p--) //从最后一个元素 向后移动一个位置 直到插入点元素
        *(p + 1) = *p;
    *q = e;
    L.Lenght++;
    return true;
}

bool Delete_SqList(SqList& L, int i, int& e)
{
    if (i<1 || i>L.Lenght)
		return false;
    int * q = L.data + i - 1;//删除元素的位置
    e = *q;
    int* p = L.data + L.Lenght - 1;
    for (q++; q <= p; q++)// 将删除点后面的元素向前移动一位 直到最后一位；
        *(q - 1) = *q;
    L.Lenght--;
    return false;
}

bool GetElem_SqList(SqList L, int i, int& e)
{
    if (i<1 || i>L.Lenght)
        return false;
    e = *(L.data + i - 1);
    return false;
}

bool Destory_SqList(SqList& L)
{
    if (!(L.data||L.data==0))//如果L.data 已经被销毁了 
        return false;
    free(L.data);
    L.data = NULL;
    L.Lenght = 0;
    L.SqListSize = 0;
    return true;
}