写在前面
寒假也快过去了，给自己的任务还算是完成了，因为之前有算法和数据结构的基础，数据结构对于我来说压力并不大吧，这个博客用来总结这段时间对于数据结构的学习。
线性表
一共9个操作:
- InitList（&L）;//初始化表
- Length()
- int locateElem/(sqList L, int e/);//按值查找
- int getElem/(sqList L, int i/);//按位置查找
- int listInsert/(sqList&L, int i, int e);//在第i个位置插入e
- int listDelete(sqList& L, int i);//
- void printList(sqList L);
- bool empty(sqList L);
- void DestroyList(sqList& L);//改变表的操作传入引用
顺序表
插入和删除操作需要移动大量元素，但查找效率很高
最大的特点是:随机访问,直接找到指定的元素，存储密度高
void initLIst(sqList& L)
{
L.length = 0;
}
int getLength(sqList L)
{
return L.length;
}
int locateElem(sqList L, int e) {
int loc = 0;
if (L.length == 0) {
return 0;
}
else {
while (L.data[loc] != e) {
loc++;
}
}
return loc;
}
int getElem(sqList L, int i) {
if (empty(L))return 0;
else if (i > L.length)return -1;
else return L.data[i];
}
int listInsert(sqList& L, int i, int e)
{
if (L.length + 1 > Max || L.length > Max) {
return 0;
}
else if (L.length == 0) {
L.data[0] = e;
L.length++;
return 1;
}
else if (i > L.length) {
L.data[L.length++] = e;
return L.length;
}
else {
for (int ind =L.length; ind > i; ind--) {
L.data[ind] = L.data[ind-1];
}
L.data[i] = e;
L.length++;
return L.length;
}
}
void printList(sqList L) {
for (int i = 0; i < L.length; i++) {
cout << L.data[i] << " ";
}
cout << endl;
}
bool empty(sqList L) {
if (L.length == 0)return true;
return false;
}
int listDelete(sqList& L, int i) {
if (empty(L))return 0;
else {
int e = L.data[i];
for (int ind = i; ind < L.length; ind++) {
L.data[ind] = L.data[ind + 1];
}
L.length--;
return e;
}
}
void DestroyList(sqList& L) {
memset(L.data, 0, sizeof(L.data) / sizeof(int));
L.length = 0;
}
单链表
单链表引入了头结点，这使得在头部的插入操作变得极其简单
查找操作的时间复杂度为O(n)
LinkList Head_insert(LinkList& L) {
LNode *newNode; int curVal=0;
L = (LinkList)malloc(sizeof(newNode) );
L->next = NULL;
cin >> curVal;
while (curVal >= 0) {
newNode = (LNode*)malloc(sizeof(LNode));
newNode->val = curVal;
newNode->next = L->next;
L->next = newNode;
cin >> curVal;
}
return L;
}
LinkList Tail_insert(LinkList& L) {
L = (LinkList)malloc(sizeof(LNode));
LNode *newNode,*r=L; int curval;
cin >> curval;
while (curval >= 0) {
newNode = (LNode*)malloc(sizeof(LNode));
newNode->next = NULL;
newNode->val = curval;
r->next = newNode;
r = newNode;
cin >> curval;
}
r->next = NULL;
return L;
}
LNode* GetElem(LinkList& L, int i) {
LNode* temp = L->next;
int ind = 0;
while (ind != i) {
temp = temp->next;
ind++;
}
return temp;
}
LinkList List_insert(LinkList& L) {
int i, curval;
cout << "位置 " << "值";
cin >>i>> curval;
LNode* temp = GetElem(L, i - 1);
LNode* p,*q;
p = (LNode*)malloc(sizeof(LNode));
p->val = curval;
q = temp->next;
temp->next = p;
p->next = q;
return L;
}
LinkList List_delete(LinkList& L, int i)
{
LNode* temp =GetElem(L,i-1);
LNode* q = temp->next;
temp->next = q->next;
free(q);
return L;
}头插法生成单链表
尾插法生成单链表
双链表
引入了前驱节点，使得可以逆转输出整个链表
并且删除操作可以直接找到前驱节点，操作的时间复杂度和单链表一样
DLinkList Head_insert(DLinkList& L) {
DNode* newNode; int curVal = 0;
L = (DLinkList)malloc(sizeof(newNode));
L->next = NULL;
cin >> curVal;
while (curVal >= 0) {
DNode* pre = L;
newNode = (DNode*)malloc(sizeof(DNode));
newNode->val = curVal;
newNode->next = L->next;
newNode->prior = pre;
if(L->next!=NULL)
L->next->prior = newNode;
L->next = newNode;
cin >> curVal;
}
return L;
}
DLinkList Dlist_delete(DLinkList& L, int i) {
DNode* p = GetElem(L, i);
DNode* q = p->prior;
p->next->prior = q;
q->next = p->next;
free(p);
return L;
}
DLinkList Dlist_insert_after(DLinkList& L, int i) {
DNode* p = GetElem(L,i);
DNode* newNode;
newNode = (DNode*)malloc(sizeof(DNode));
int curval; cin >> curval;
newNode->val = curval;
DNode *q = p->next;
newNode->next = q;
p->next = newNode;
newNode->prior = p;
q->prior = newNode;
return L;
}
DNode* GetElem(DLinkList& L,int i) {
DNode* temp = L->next;
int ind = 0;
while (ind != i) {
temp = temp->next;
ind++;
}
return temp;
}
void printList(DLinkList L)
{
while (L->next != NULL) {
DNode* cur = L->next;
cout << cur->val << " ";
L = L->next;
}
cout << endl;
}
循环链表
循环链表的最后一个节点的next节点指向头节点的next(头节点不存储)
所以判空条件变成最后一个节点是否是头节点，判满的条件是尾节点的next为头节点
对表头和表尾的操作都是O(1)
最好是用尾插法建立循环链表
CircleList Tail_insert(CircleList& L) {
CNode* newNode,*r; int curval;
L = (CircleList)malloc(sizeof(CNode));
r = L;
r->next = NULL;
cin >> curval;
while (curval >= 0) {
newNode = (CNode*)malloc(sizeof(CNode));
newNode->val = curval;
r->next = newNode;
newNode->next = L->next;
r = r->next;
cin >> curval;
}
return L;
}
void printList(CircleList L,int t)
{
while (L->next != NULL&&t!=0) {
CNode* cur = L->next;
cout << cur->val << " ";
L = L->next;
t--;
}
cout << endl;
}
void printList(CircleList L)
{
while (L->next != NULL) {
CNode* cur = L->next;
cout << cur->val << " ";
L = L->next;
}
cout << endl;
}
线性表总结:
- 顺序表可以随机存储，链表只能从表头顺序读取元素
- 顺序存储的数据物理位置也相邻，链式存储相邻元素物理位置不一定相邻
- 对于按值查找顺序表和链表都是O(n),按位置查找顺序表是O(1)
- 顺序表一旦容量满则不能扩容，链表可以动态增加存储空间
栈，队列，数组
顺序栈
栈是一种先进后出的数据结构
void InitStack(sqStack &S) {
memset(S.data, 0, MAX*sizeof(int));
S.top = -1;
}
bool StackEmpty(sqStack& S) {
if (S.top <= -1)return true;
return false;
}
int push_back(sqStack& S) {
int val;
cin >> val;
S.data[++S.top] = val;
return val;
}
void pop_out(sqStack& S) {
S.top--;
}
int Get_top(sqStack& S) {
return S.data[S.top];
}
void destroyStack(sqStack& S) {
free(S.data);
S.top = -1;
}
链栈
void InitStack(LinkStack& top)
{
top->next = NULL;
}
bool StackEmpty(LinkStack& top) {
if (top->next == NULL)return true;
return false;
}
void push_back(LinkStack& top)
{
int curval; cin >> curval;
top = (LinkStack)malloc(sizeof(LinkNode));
LinkNode *newnode;
newnode = (LinkStack)malloc(sizeof(LinkStack));
newnode->data = curval;
newnode->next = NULL;
top->next = newnode;
}
int pop_out(LinkStack& top) {
if (StackEmpty(top))return 0;
else {
LinkNode* temp = top->next;
top->next = temp;
/*free(temp);
temp->next = NULL;*/
return true;
}
}
void Get_top(LinkStack& top)
{
if (StackEmpty(top))cout << "空栈";
else
{
if (top->next != NULL) {
cout << top->next->data;
}
}
}
采用链式存储，便于节点的插入与删除，入栈和出栈的操作都在链表表头进行，需要注意的是，对于带表头的和不带表头的链栈，具体实现方法会不同
顺序队列
void InitQueue(sqQueue& Q) {
memset(Q.data, 0, sizeof(Q.data));
Q.front = 0;
Q.rear = 0;
}
bool QueueEmpty(sqQueue& Q) {
if (Q.front == Q.rear)return true;
return false;
}
void EnQueue(sqQueue& Q, int curval) {
Q.data[Q.rear++] = curval;
}
int DeQueue(sqQueue& Q) {
if (QueueEmpty(Q))return false;
Q.data[Q.front++];
return true;
}
int GetHead(sqQueue& Q) {
return Q.data[Q.front];
}
- 初始状态:front==rear==0
- 队满状态:rear-front==MAXSIZE
- 队空状态:rear==front
循环队列
void InitQueue(CircleQueue& Q) {
Q.front = Q.rear = 0;
memset(Q.data, 0, sizeof(Q.data)/sizeof(int));
}
void EnQueue(CircleQueue& Q, int curval=0) {
cin >> curval;
if (Q.rear + 1 % MAX == Q.front % MAX)//rear在front前面说明队满
{
DeQueue(Q);
Q.data[(Q.rear++)%MAX] = curval;
}
else {
Q.data[(Q.rear++) % MAX] = curval;
}
}
int DeQueue(CircleQueue& Q) {
if (IsEmpty(Q))return 0;
else {
Q.front++;
return 1;
}
}
bool IsEmpty(CircleQueue& Q) {
if (Q.rear%MAX == Q.front % MAX)
return true;
return false;
}
- 初始状态:rear==front==0
- 队满状态:(rear+1)%MAXSIZE==front//rear在front前面一个
- 队空状态:rear==front
- 队中元素个数(rear-front+Maxsize)%Maxsize
链队
void InitQueue(LinkQueue& Q) {
Q.front = Q.rear = (Node*)malloc(sizeof(Node));
Q.front->next = NULL;
}
void EnQueue(LinkQueue& Q, int curval=0) {
cin >> curval;
Node* newnode;
newnode = (Node*)malloc(sizeof(Node));
newnode->data = curval;
newnode->next = NULL;
Q.rear->next = newnode;
Q.rear = Q.rear->next;
}
int DeQueue(LinkQueue& Q) {
if (IsEmpty(Q))return 0;
else {
Node* temp = (Node*)malloc(sizeof(Node));
temp = Q.front;
Q.front = Q.front->next;
if (Q.rear == temp)//如果只剩一个元素删完则队列置空
Q.front = Q.rear;
free(temp);
return 1;
}
}
int GetHead(LinkQueue& Q) {
return Q.front->next->data;
}
bool IsEmpty(LinkQueue& Q) {
if (Q.front == Q.rear)return true;
return false;
}
用单链表表示的链式队列特别适合于树据元素变动比较大的情形，而且不存在队满且产生溢出的情况
括号匹配（栈的应用）
bool is(string ss) {
stack<char> ops;
for (int i = 0; i < ss.length(); i++) {
if (ss[i] == '(')ops.push(ss[i]);
if (ss[i] == ')') {
if (ops.empty())
{
return 0;
}
else ops.pop();
}
}
if (ops.empty())return 1;
return 0;
}中缀表达式转后缀表达式
王道P98-p99
队列的作用
- BFS
- FIFO
串
KMP算法
#include<iostream>
#include<string>
using namespace std;
string s, ss;//s主串，ss模式串
int next1[105];//next数组
void getnext()
{
next1[1] = 0;
int i = 1, j = 0;//i=j+1
while (i != ss.length()-1) {
if (j == 0 || ss[i] == ss[j]) {//第一个字母的next为1
//i表示当前在比较模式穿中前i个字符的最长公共字串
//j表示当前公共字串长度
next1[++i] = ++j;//当前第i个字符前的最长公共串长度
}
else {
j = next1[j];//如果发生失配就往前面找，直到j=0使得next[j]=1
}
}
}
int index_KMP() {
int i = 1, j = 1;//主串和模式串同时向前推动，发生失配模式串向前走
while (i <= s.length()-1 && j <= ss.length()-1) {
if (j == 0 || s[i] == ss[j]) {
++i; ++j;
}
else {
j = next1[j];
}
}
if (j > ss.length()-1)return i - ss.length()+1;//主串跑完了，模式串还没有匹配则return0
else return 0;
}
int main(void) {
getline(cin, s);
/*cout << s.length();*/
getline(cin, ss);
s.insert(s.begin(), ' ');
ss.insert(ss.begin(), ' ');
getnext();
cout << index_KMP();
return 0;
}树与二叉树
二叉树
- 度为2的树至少有3个节点，而二叉树可以为空
- 满二叉树高度为h，有2^h-1个节点，若父节点为i,左孩子为2*i，右节点为2*i-1
- 完全二叉树是满二叉树确实最下层最右边的一些连续的叶子节点,i
- 非空二叉树上的叶子节点数等于度为2的节点数+1，n0=n2+1
void initBiTree(BiTNode * &T) {
int curval; cin >> curval;
if (curval == -1)T = NULL;
else {
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = curval;
initBiTree(T->Lchild);
initBiTree(T->Rchild);
}
}
void PreOrder(Bitree *T) {
if (T != NULL) {
cout << T->data<<" ";
PreOrder(T->Lchild);
PreOrder(T->Rchild);
}
}
void InOrder(Bitree* T) {
if (T != NULL) {
InOrder(T->Lchild);
cout << T->data << " ";
InOrder(T->Rchild);
}
}
void afterOrder(Bitree* T) {
if (T != NULL) {
afterOrder(T->Lchild);
afterOrder(T->Rchild);
cout << T->data << " ";
}
}
void levelOrder(Bitree T) {
queue<BiTNode> q;
Bitree P;
q.push(T);
while (!q.empty()) {
P = q.front();
cout << P.data<<" ";
q.pop();
if (P.Lchild != NULL) {
q.push(*P.Lchild);
}
if (P.Rchild != NULL) {
q.push(*P.Rchild);
}
}
}
二叉树有n+1个空指针，线索二叉树用它来指向父节点
树与二叉树的转换
左孩子右兄弟
森林和二叉树的转换
并查集
#include<iostream>
#define MAXN 10005
using namespace std;
int fa[MAXN];
void initUnion(int n);//并查集初始有n个节点
int find(int x);//查找x的祖先节点
void Union(int x, int y);//让x和y节点的祖先合并
void initUnion(int n)
{
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (x == fa[x]) {
return x;
}
else
{
fa[x] = find(fa[x]);
return fa[x];
}
}
void Union(int x, int y) {
int fa_x = find(x);
int fa_y = find(y);
fa[fa_x] = fa_y;
}
//https://www.bilibili.com/video/BV1jv411a7LK?p=2
int main()
{
int m, n;
cin >> m >> n;
initUnion(m);
while (n--)
{
int x, y;
cin >> x >> y;
Union(x, y);
}
int Q;
cin >> Q;
while (Q--) {
int x, y;
cin >> x >> y;
if (fa[x] == y || fa[y] == x)cout << "yes";
else cout << "no";
}
return 0;
}图
BFS,DFS
BFS,DFS都可以进行图的无权遍历，但生成树不同
BFS
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct point {
int x;
int y;
point(int X = 0, int Y = 0) { x = X; y = Y; }
};
int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
char mp[105][105];
int vis[105][105];
int startx, starty;
int endx, endy;
point que[105]; int front = 0, rear = 0;
int BFS(int x, int y) {
vis[x][y] = 1;
point *p = new point(x, y);
que[++rear] = *p;
while (rear != front) {
point temp = que[++front];
if (temp.x == endx && temp.y == endy) {
return vis[endx][endy]-1;
}
/*vis[temp.x][temp.y] += 1;*/
for (int i = 0; i < 4; i++) {
int newx = temp.x + dir[i][0];
int newy = temp.y + dir[i][1];
if ((mp[newx][newy] == '-'||mp[newx][newy]=='E') && vis[newx][newy] == 0) {
vis[newx][newy] = vis[temp.x][temp.y]+1;
point* curp = new point(newx, newy);
que[++rear] = *curp;
}
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while (T--) {
memset(vis, 0,sizeof(vis)/sizeof(int));
front = rear = 0;
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> mp[i][j];
if (mp[i][j] == 'S') { startx = i; starty = j; }
if (mp[i][j] == 'E') { endx = i; endy = j; }
}
}
cout<<BFS(startx, starty);
}
return 0;
}DFS
#include<iostream>
#include<algorithm>
using namespace std;
int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
char mp[105][105];
int vis[105][105];
int startx, starty;
int endx, endy;
int flag = 0;
int ans[105]; int a = 0;
int an = 0;
void DFS(int x, int y) {
if (x == endx && y == endy) {
ans[a++] = an;
/*an = 0;*/
flag = 1; return;
}
/*if (flag == 1)return;*/
vis[x][y] = 1;
for (int i = 0; i < 4; i++) {
int newx = x + dir[i][0];
int newy = y + dir[i][1];
if ((mp[newx][newy] == '-' || mp[newx][newy] == 'E') && vis[newx][newy] == 0)
{
vis[newx][newy] = 1;
an++;
DFS(newx, newy);
vis[newx][newy] = 0;
an--;
}
}
}
int main()
{
int T;
cin >> T;
while (T--) {
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> mp[i][j];
if (mp[i][j] == 'S') { startx = i; starty = j; }
if (mp[i][j] == 'E') { endx = i; endy = j; }
}
}
DFS(startx, starty);
cout << *min_element(ans, ans + a);
}
return 0;
}详细见本博客前文章
最小生成树（Kruskal算法）
prim算法从头节点开始找邻接最短边，然后依次寻找直到联通
这里我们主要学习Kruskal算法
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int from, to, dis;
}edge[1005];//描述一条边
int fa[1005];//并查集数组
void initUnion(int n) {
for (int i = 0; i < n; i++)
{
fa[i] = i;
}
}
bool cmp(node &e1, node &e2) {
return e1.dis < e2.dis;
}
int find(int i) {
if (i == fa[i]) {
return i;
}
else {
fa[i] = find(fa[i]);
return find(fa[i]);
}
}
void unionn(int x, int y) {
int fa_x = find(x);
int fa_y = find(y);
fa[fa_x] = fa_y;
}
int main()
{
int n, m; cin >> n >> m;//n个顶点m条边
for (int i = 0; i < m; i++) {
cin >> edge[i].from >> edge[i].to >> edge[i].dis;
}
initUnion(n);
sort(edge, edge + m, cmp);//排序途中所有的边找到最小的边
int k = 0;
int total = 0;
for (int i = 0; i < m; i++) {
if (k == n - 1)break;
if (find(edge[i].from) != find(edge[i].to)) {//只要选择的边不同根就选择这条较小边
unionn(edge[i].from, edge[i].to);
total += edge[i].dis;
k++;
}
}
cout << total;
return 0;
}
最短单源路径算法
Dijkstra算法
Floyd算法
#include<iostream>
using namespace std;
int mp[105][105];
int main()
{
int n; cin >> n;
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++) {
cin>>mp[i][j];
if (mp[i][j] == -1)mp[i][j] = 99999;//表示无路径
}
for (int k = 0; k < n; k++) {//比较k次，每一次找到一个单源最短
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mp[i][j] > mp[i][k] + mp[k][j]) {
mp[i][j] = mp[i][k] + mp[k][j];
}
cout << mp[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
}
查找
折半查找
#include<iostream>
using namespace std;
//折半查找
int half_search(int a[], int len,int x) {
int t = 0;
int low = 0; int high = len - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] == x) { cout << "折半查找共查找" << t << "次"<<endl; return mid; }
else if (a[mid] > x)high = mid - 1;
else {
low = mid + 1;
}
t++;
}
cout << "折半查找共查找" << t << "次";
return -1;
}
int main()
{
int a[5] = { 12,18,20,39,102 };
cout << half_search(a, 5, 102);
return 0;
}BST排序二叉树查找
#include<iostream>
using namespace std;
typedef struct Node {
int data;
Node* Lchild, * Rchild;
}*Bitree;
void createTree(Node* & T) {
T = (Node*)malloc(sizeof(Node));
int curval; cin >> curval;
if (curval == -1)
T = NULL;
else if (curval != -1) {
createTree(T->Lchild);
T->data = curval;
createTree(T->Rchild);
}
}
void preOrder(Bitree& T) {
if (T == NULL)
return;
cout << T->data << " ";
preOrder(T->Lchild);
preOrder(T->Rchild);
}
Node* BST_search(Bitree T, int key) {
while (T != NULL && T->data != key) {
if (key > T->data)T = T->Rchild;
else T = T->Lchild;
}
return T;
}
int BST_insert(Bitree& T, int num) {
if (T == NULL) {
T = (Bitree)malloc(sizeof(Node));
T->data = num;
T->Lchild = T->Rchild = NULL;
return 1;
}
else if (num == T->data)
return 0;
else if (num > T->data) {
return BST_insert(T->Rchild, num);
}
else {
return BST_insert(T->Lchild, num);
}
}
int main()
{
Bitree T;
createTree(T);
cout << BST_search(T, 2)->Lchild->data<<" "<< BST_search(T, 2)->Rchild->data<<endl;
BST_insert(T, 5);
preOrder(T);
return 0;
}如果是平衡二叉树时间复杂度为logn，如果直接线性排成一排则n
红黑树
蛮重要的，等会学
B树
最后一次更新于2022-02-21
《德军占领的卢浮宫》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/54338.html
By jeqcpckrgg at November 15th, 2024 at 11:06 am.