3.29:数据结构-绪论线性表-上

一、时间复杂度

1、ADT

2、定义法计算时间复杂度：统计核心语句的总执行次数

 （1）例题1，与2022年的真题对比着写

此题关键在于求和公式的转化，类型为：线性循环嵌套非线性循环

2022年那道题如果考场上实在脑子不清楚，直接代数也行。

（2）例题2：非线性循环嵌套线性循环

2022年真题

注意：可能会考究竟执行了多少次数，而非只是简单的求出时间复杂度。

（3）三重循环

（4）思考题

（5）歪门邪道

二、线性表

1、

三、rw1000题时间复杂度纠错

1、斐波那契的递归时间复杂度

可以视为一颗二叉树，求二叉树的节点个数，或者：

数一的话会求斐波那契的通项，其中一项就是他的复杂度， O  （根号5-1）/2的n次方；

若返回F(n-1)，时间复杂度就是O(n)

2、

四、转王道C语言督学营：13.4

1、有关顺序栈的操作

#include<iostream>using namespace std;//顺序栈定义
typedef struct
{int Stack[100];int top;
}SqStack;//初始化栈
void InitStack(SqStack &S)
{S.top = -1;
}//判断栈是否为空
bool IsEmpty(SqStack& S)
{if (S.top == -1) return false;else return true;
}//元素入栈
void Push(SqStack& S, int x)
{S.top++;S.Stack[S.top] = x;
}//元素出栈
int Pop(SqStack& S)
{int x = S.Stack[S.top];S.top--;return x;
}//判断栈是否满
bool IsFull (SqStack& S)
{if (S.top == 99) return true;else return false;
}int main()
{SqStack S;InitStack(S);bool flag = IsEmpty(S);Push(S, 4);Push(S, 5);int y = Pop(S);int y2 = Pop(S);cout << y << endl;cout << y2 << endl;
}

2、13.5：队列-循环队列原理解析

队头队尾这个概念也可以与“排队”类比，排队就是从队尾插入，从队头出来；

（1）循环队列实现

数据结构定义：

typedef struct
{int data[MaxSize];int front;int rear;
}SqQueue;SqQueue Q;

主要操作：

//循环队列入队
bool EnQUeue(SqQueue& Q, int x)
{//首先判断队列是否满了if ((Q.rear + 1) % MaxSize == Q.front) return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;
}//循环队列出队
bool DeQueue(SqQueue& Q, int& y)
{//判断队列是否为空if (Q.front == Q.rear) return false;y = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;
}//循环队列初始化
void InitQueue(SqQueue& Q)
{Q.front = Q.rear = 0;
}

（2）队列的链式存储，注意：还是带头结点的

定义：

同时带有队头指针与队尾指针的单链表，头指针指向队头节点，尾指针指向队尾节点，既：单链表的最后一个节点。

注意：对链表实现队列并不需要判断链表是否满了，而只需判断链表是否为空。

数据结构：

//首先定义链表节点
typedef struct
{int val;LinkNode* next;
}LinkNode,*LinkList;//链表结构体
typedef struct
{LinkNode* front;LinkNode* rear;
}QueueList;QueueList Q;

注意一下：以上第一个结构体会报错，原因是省略了 LinkNode，因为内部要用。

改正：

//首先定义链表节点
typedef struct LinkNode
{int val;LinkNode *next;
}LinkNode;//链表结构体
typedef struct
{LinkNode* front;LinkNode* rear;
}QueueList;QueueList Q;

主要操作：

//队列的链式存储//首先定义链表节点
typedef struct LinkNode
{int val;LinkNode *next;
}LinkNode;//链表结构体
typedef struct
{LinkNode* front;LinkNode* rear;
}QueueList;QueueList Q;//首先进行初始化，带头节点
void Init_LinstQueue(QueueList &Q)
{//定义头节点LinkNode* p = new LinkNode();Q.front = Q.rear = p;Q.front->next= NULL;
}//入队
void EnQueue_Link(QueueList &Q, int x)
{LinkNode* p = new LinkNode();p->val = x;//这一步容易忘p->next = NULL;Q.rear->next = p;Q.rear = p;
}//出队
bool DeQueue_Link(QueueList& Q, int& y)
{//首先判断链表是否为空if (Q.front == Q.rear) return false;LinkNode* p = Q.front->next;y = p->val;Q.front->next = p->next;//判断删除过后是否为空，毕竟如果为空的话rear指针要进行改变if (p == Q.rear) Q.rear = Q.front;delete(p);
}int main()
{Init_LinstQueue(Q);EnQueue_Link(Q, 1);EnQueue_Link(Q, 2);EnQueue_Link(Q, 3);EnQueue_Link(Q, 4);int x;bool e = DeQueue_Link(Q, x);cout << x << endl;
}

结束！