复习结构体

//此声明声明了拥有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;//定义顺序表
初始化:
void InitList(SqList &L) //此处L为引用
{
    for (int i = 0; i < MaxSize; i++)
        L.data[i] = 0;//
    L.length = 0;//长度初始化
}

简单使用C++实现一下：

这个是我自我感觉写的，仅仅供个人学习。

#include <iostream>

using namespace std;

const int MaxSize = 10;
template <class T>
class SqList
{
public:
    SqList()
    {
        for (int i = 0; i < MaxSize; i++)
            data[i] = 0;
        length = 0; //长度初始化
    }
    int ListInsert(T e, int i = 0); //插入数据
    void PrintList();               //输出当前列表所有数据
    int operator[](int i);          //重载[]
private:
    T data[MaxSize];
    int length; //顺序表当前长度
};

template <class T>
void SqList<T>::PrintList()
{
    if (length == 0)
    {
        cout << "当前列表为空" << endl;
    }
    for (int i = 0; i < length; i++)
    {
        cout << data[i] << endl;
    }
}

template <class T>
int SqList<T>::operator[](int i)
{
    if (i > length)
    {
        cout << "索引超过长度" << endl;
        return 0;
    }
    return data[i];
}
template <class T>
int SqList<T>::ListInsert(T e, int i)
{
    if (i > MaxSize)
    {
        cout << "索引超出最大范围" << endl;
        return length;
    }

    if (length >= MaxSize)
    {
        cout << "该序列已满" << endl;
        return length;
    }
    //现在是加入数据模式
    if (i == 0)
    {
        data[length] = e;
    }
    else //插入模式
    {
        for (int j = length; j >= i; j--)
        {
            data[j] = data[j - 1];
        }
        data[i - 1] = e;
    }

    length++;
    return length;
}
//简单验证一下
int main()
{
    SqList<int> L;
    L.PrintList();
    for (int i = 0; i < 10; i++)
    {
        L.ListInsert(i);
    }
    L.ListInsert(16, 2);
    L.PrintList();
    getchar();
    return 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*

定义：
#define InitSize 10
// 动态分配
typedef struct
{
    int *data;   //顺序表动态分配的指针
    int maxSize; //顺序表最大容量
    int lenght;  // 顺序表当前长度
} SeqList;
初始化函数：
void InitList(SeqList &L)
{
    L.data = (int *)malloc(InitSize * sizeof(int)); //开辟内存空间
    L.lenght = 0;                                   //当前长度为0
    L.maxSize = InitSize;                           //最大的长度为 initseize
}
动态顺序表大小

对于静态的来说那么就会多一个增加最大长度。

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);                     //释放内存空间
}
顺序表的特点
  • 随机访问，即可以在O(1) 时间内找到第i个元素。
  • 存储密度高，每个节点仅仅存储 数据元素
  • 拓展容量很麻烦，即使使用动态分配的方法,拓展长度的时间复杂度还是比较高
  • 插入，删除操作，不方便，需要移动大量元素。
顺序表的实现 ---- 插入，删除

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

插入

我们要在第i的位置上插入指定元素e，那么就需要把第i个位置后面数据向后移动。

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

注意for循环时把先把插入点数据向后移动一位，注意我们顺序表的编号时从0开始的，所以 L.data[j] = L.data[j - 1];相当于后移数据。

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

插入失败的情况有：

  1. 插入点 i 不合理， i>L.length+1;||i<1
  2. 顺序表已满 ， 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; j > i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    //  在把给插入点赋值
    L.data[i - 1] = e;
    L.length++;
}

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

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

问题规模：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);

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

最好最坏都一样，所以平均复杂度等于他们等于 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;
}

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

Q.E.D.

努力学习的小菜鸟