数据结构与算法（一）
2021-03-02 04:29
标签：获取元素 表示 操作 center 函数 删除元素 组成 创建 最大 推到大O阶（时间复杂度）方法： 得到的最后结果就是大O阶 常见的时间复杂度 常用的时间复杂度所耗费的时间从小到大依次是：O(1)
线性表(List)：由零个或者多个数据元素组成的有限序列 抽象数据类型： ADT 线性表(List) 操作 示例代码 线性表的存储结构：顺序存储结构和链式存储结构 顺序存储的结构代码： 顺序存储结构封装需要三个属性： 获取元素操作 插入操作 删除操作 线性表顺序存储结构，插入和删除的时间复杂度，最好情况为O(1)，最坏情况为O(n)，平均情况为O(n)。适合元素个数比较稳定，不经常插入和删除元素，更多是存取数据的应用 顺序结构的优缺点 单链表 单链表存储结构 单链表的读取 单链表的插入 单链表的删除 假设元素a2的结点为q，要实现结点q删除单链表的操作，其实就是将它的前继结点的指针绕过指向后继结点即可 单链表的创建 单链表整表删除 单链表结构与顺序存储结构优缺点： 数据结构与算法（一） 标签：获取元素 表示 操作 center 函数 删除元素 组成 创建 最大 原文地址：https://www.cnblogs.com/zonkidd/p/14412203.html
例子
时间复杂度
术语
520
O(1)
常数阶
3n+4
O(n)
线性阶
3n^2+4n+5
O(n^2)
平方阶
3log(2)n+4
O(logn)
对数阶
2n+3nlog(2)n+14
O(nlogn)
nlogn阶
n^3+ 2n^2 + 4n + 6
O(n^3)
立方阶
2^n
O(2^n)
指数阶
//并集代码
//La表示A集合，Lb表示B集合
void unionL(list *La, list Lb)
{
int La_len, Lb_len, i;
ElemType e;
La_len = ListLength(*La);
Lb_len = ListLength(Lb);
for(i = 1; i
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length; //线性表当前长度
}SqList;
//顺序存储结构具有随机结构的特点，时间复杂度为O(1)
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函数的类型，其值时函数结果状态代码，如OK等
//初始条件：顺序线性表L已存在，1 L.length)
{
return ERROR;
}
*e = L.data[i-1];
return OK;
}
//插入算法的思路:
/*************************************
如果插入位置不合理，抛出异常；
如果线性表长度大于等于数据长度，则抛出异常或动态增加数组容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处；
线性表长+1。
*************************************/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if( L->Length == MAXSIZE) //顺序线性表已经满了
{
return ERROR;
}
if(i L->length + 1) //当i不在范围内时
{
return ERROR;
}
if(i length) //若插入数据位置不在表尾
{
//将要插入位置后数据元素向后移动一位
for (k=L->length - 1; k >= i-1; k--)
{
L -> data[k+1] = L -> data[k];
}
}
L -> data[i - 1] = e; //将新元素插入
L -> length++;
return OK;
}
/************************************
删除算法思路：
如果删除位置不合理，抛出异常
取出删除元素
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
表长-1
************************************/
Status ListDelete(SqList *L, int i, ElemType e)
{
int k;
if( L->Length == 0) //顺序线性表为空表
{
return ERROR;
}
if(i L->length) //当i不在范围内时
{
return ERROR;
}
*e = L->data[i-1];
if(i length)
{
for (k=i; k length; k++)
{
L -> data[k-1] = L -> data[k];
}
}
L -> length--;
return OK;
}
typedef struct Node
{
ElemType data; //数据域
struct Node* Next; //指针域
}Node;
typedef struct Node* LinkList;
//结点由存放数据元素的数据域和存放后继结点地址的指针域组成
/***************************************
获得链表第i个数据的算法思路：
声明一个结点p指向链表第一个结点，初始化j从1开始
当j next;
j = 1;
while( p && j next;
++j;
}
if( !p || j > i)
{
return ERROR;
}
*e = p->data;
return OK;
}
/***********************************************
单链表第i个数据插入结点的算法思路：
声明一结点p指向链表头结点，初始化j从1开始
当jdata
单链表的插入刚才两个标准语句
返回成功
***********************************************/
Status ListInsert( LinkList *L, int i, ElemType *e )//LinkList是结构体的指针，指针做形参时都要加*表示是指针
{
int j;
LinkList p, a;
p = *L;
j = 1;
while( p && j next;
j++;
}
if( !p || j > i)
{
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
/***********************************
单链表第i个数据删除结点的算法思路：
声明结点p指向链表第一个结点，初始化j=1
当jnext赋值给q
单链表的删除标准语句p->next = q->next
将q结点中的数据赋值给e，作为返回
释放q结点
************************************/
Status ListDelete(LinkList *L, int i, ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j next;
++j;
}
if(!(p->next) || j > i)
{
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
/*************************************
声明一结点p和计数器变量i
初始化一空链表L
让L的头结点的指针指向NULL，即建立一个带头结点的单链表
循环实现后继结点的赋值和插入
**************************************/
//头插法
void CreateListHead(LinkList *L, int n)
{
LinkList p;
int i;
srand(time(0)); //初始化随机数种子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for(i = 0; i data = rand()%100 + 1;
p->next = (*L)->next;
(*L)->next = p;
}
}
//尾插法
void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(i = 0; i data = rand()% 100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}
/******************************
声明结点p和q
将第一个结点赋值给p，下一个结点赋值给q
循环执行释放p和将q赋值给p的操作
*******************************/
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L) ->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}