复习结构体
//此声明声明了拥有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个位置上插入元素eListDelete(&L,i,&e)
:删除,删除表上第i个位置上的元素eLocateElem(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];
相当于后移数据。
当然,这个我们更加希望我们能够知道是否插入成功,所以最好加一个返回值。
插入失败的情况有:
- 插入点 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; 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.