数据结构(无图版)
数据结构与算法(无图版,C语言实现)
1、绪论
1.1、数据结构的研究内容
一般应用步骤:分析问题,提取操作对象,分析操作对象之间的关系,建立数学模型。
1.2、基本概念和术语
数据:是能输入计算机且能被计算机处理的各种符号的集合。
数据元素:是数据的基本单位,也可称为元素、记录、结点或顶点。
数据项:构成数据元素的最小单位。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
数据结构:是指相互之间存在一种或多种特定关系的数据元素集合。
● 逻辑结构
● 物理结构
四种基本的存储结构:顺序、链式、索引和散列存储。
数据类型(Data Type) 定义:数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
1.3、抽象数据类型的表示与实现
1.4、算法和算法分析
算法的定义:对特定问题求解方法和步骤的一种描述,它是指令的有限序列(每个指令表示一个或多个操作)
算法特性:
● 有穷性(算法在有穷步结束,且每一步都在有穷时间内完成)
● 确定性(算法中每一条指令必须有确切的含义,没有二义性)
● 可行性(算法是可执行的)
● 输入(一个算法有零个或多个输入)
● 输出(一个算法有一个或多个输出)
考虑算法的效率问题:
1.时间复杂度,一般情况下,不必计算所有操作的执行次数,而只考虑算法中的基本语句执行次数(比较主要的数量级),它是问题规模n的某个函数,用T(n)表示(T(n)=O(f(n)))
2.空间复杂度,算法所需存储空间的度量,记作:S(n)=O(f(n)),其中n为问题的规模(或大小),算##法要占据的空间(输入/输出,指令,常数,变量等)以及要使用的辅助空间
2、线性表
2.1、线性表的定义和特点
线性表(Linear List)是具有相同特性的数据元素的一个有限序列
2.2、案例引入
多项式求和(指数相同项可以进行相加减)
图书管理系统(图书表可以看作是一个线性表,每本图书可以看作是线性表的数据元素)
2.3、线性表的类型定义
基本操作:1、InitList (&L)构造一个空的线性表;2、DestroyList (&L)销毁线性表;3、ClearList (&L)重置为空表…
2.4、线性表的顺序表示和实现
顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
地址计算公式:LOC(ai)=LOC(a1>)+(i-1)*L
2.4.1、顺序表的顺序存储表示
顺序表(元素),可以用一维数组表示顺序表
2.4.2、顺序表基本操作的实现
例如:构造一个空的顺序表L,为顺序表分配空间,存储分配失败处理,空表长度为0.
顺序表的插入,时间复杂度是O(n) (n*(n+1)/(n+1)/2)
顺序表的删除,(1、判断删除的位置是否合法(1<=i<=n);2、将欲删除的元素保留在e中;3、将第i+1至第n位的元素一次向前移动一个位置;4、表长减1,删除成功返回OK)
顺序表的删除,时间复杂度是O(n) (n*(n-1)/n/2)
小结:
线性表的逻辑结构和存储结构是一致的(连续)
● 时间复杂度:查找、插入、删除算法的平均时间复杂度为O(n)
● 空间复杂度:显然,顺序表操作算法的空间复杂度S(n)=O(1),没有占用辅助空间
优点:可存储密度大;可以随机存储表中任一元素。
缺点:在插入,删除某一元素时,需要移动大量元素;浪费存储空间;属于静态存储形式,数据元素的个数不能自由扩充。
//template <typename 类型参数>
//class 类名{
// 类成员声明
//};
//或者
//template <class 类型参数>
//class 类名{
// 类成员声明
//};
typedef int Rank; //秩
#define ListNodePosi(T) ListNode<T>* //列表节点位置template <typename T> struct ListNode { //列表节点模板类(以双向链表形式实现)// 成员T data; ListNodePosi(T) pred; ListNodePosi(T) succ; //数值、前驱、后继//构造函数ListNode() {}; //针对header和trailer的构造ListNode(T e, ListNodePosi(T) p = nullptr, ListNodePosi(T) s = nullptr) : data(e), pred(p), succ(s) {} //默认构造器//操作接口ListNodePosi(T) insertAsPred(T const& e); //紧靠当前节点之前插入新节点ListNodePosi(T) insertAsSucc(T const& e); //紧靠当前节点之后插入新节点
};
2.5 、线性表的链式表示和实现
链表=结点+数据
首元结点:开始存储第一个数据的结点;头节点则是预设的、其指针指向首元结点。
2.5.1 、单链表的定义和表示
2.5.2、单链表基本操作的实现
单链表的初始化:步骤1、生成新节点作为头节点,用头指针L指向头节点;2、将头节点的指针域置空。
单链表的销毁:从头指针开始,一次释放所有的结点。
清空链表:(链表任然存在,但是链表中无元素成为了空链表)依次释放所有节点,并将头节点指针域设置为空
结束条件:p==nullptr;循环条件:p!=nullptr.
取值-取单链表中第i个元素的内容
bool GetElem(const LinkList &L, const int &i, ElemType &e)
{if(i < 0){cerr << "out of range" << endl;return false;}Lnode *p = L->next;for (int j = 1; j < i + 1; ++j){p = p->next;if(!p){cerr << "out of range" << endl;return false;//如果此时p为空,意味着已经到达链表尾端,停止循环}}e = p->data;return true;
}
先分析下算法步骤,算法描述;对于取值、查找、删除等基本操作要熟练!
删除链表的某个结点
bool ListDelete_L(LinkList &L, int i, ElemType &e)
{LinkList p = L;int j = 0;while (p->next && j < i - 1) {p = p->next; j++;} //寻找第i个结点,并令p指向其前驱if (!(p->next) || j > i - 1) {cerr << "out of range" << endl;return false; //删除位置不合理}Lnode *q = p->next; //临时保存被删结点的地址以备释放p->next = q->next; //改变删除结点前驱结点的指针域e = q->data; //保存删除结点的数据域delete q; //释放删除结点的空间return true;
} //时间复杂度为O(n)
建立单链表,有头插法和尾插法(元素插入到链表头部还是尾部)
头插法创建单向链表
void CreateListhead(LinkList &L, int n)
{for (int i = 0; i < n; i++){Lnode *p = new Lnode; //生成新结点cin >> p->data;p->next = L->next; //插入到表头L->next = p;}
}
尾插法创建单向链表
void CreateListTail(LinkList &L, int n)
{
Lnode *r = L;for (int i = 0; i < n; i++){Lnode *p = new Lnode; //生成新结点,输入元素值cin >> p->data;p->next = nullptr; r->next = p; //插入到表尾r = p; //指向新的尾结点}
}
2.5.3、循环链表
头指针表示时间复杂度O(n),尾指针表示时间复杂度O(1)。
2.5.4、双向链表
双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior,这样的链表中就形成了有两个方向不同的链,故称为双向链表。
bool ListInsert_DuL(DuLinkList &L, const int i, const ElemType &e)
{//移动指针到i处DuLnode *p = L->next;int j = 1;while (p->next && j < 1){++j;p=p->next;}if (j > i || j < 1){cerr << "out of range" << endl;return false;}//在堆区创建要插入的结点DuLnode *s = new DuLnode();s->data = e;//重新建立链表关系s->prior = p->prior; //第一步,s的前驱等于p的前驱p->prior->next = s; //第二步,用p的前驱结点的后继指向插入元素s,更改了第一条链s->next = p; //第三步,s的后继指向pp->prior = s; //第四步,p的前驱指向s,更改了第二条链return ture;
}
一些概念:
存储密度:指结点数据本身所占的存储量和整个结点占用的空间总量
因此,顺序表存储密度=1,链表存储密度一般<1
2.6、顺序表和链表的比较
2.7、线性表的应用
2.7.1、有序表
线性表的合并之两个有序链表的合并
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{Lnode *pa = La->next;Lnode *pb = Lb->next;Lc = La;Lnode *pc = Lc;while (pa && pb){if (pa->data <= pb->data) //尾插法,插入元素{//pc的指针域指向小元素的地址pc->next = pa;//移动pc指针,使得pc永远都指向最后链表Lc的最后一个元素pc = pc->next;//pa的元素使用过后,要向后移动papa = pa->next;}else{//pc的指针域指向小元素的地址pc->next = pb;//移动pc指针,使得pc永远都指向最后链表Lc的最后一个元素pc = pc->next;//pb的元素使用过后,要后向移动papb = pb->next;}}//上面的while循环执行完毕后,较长的链表还会余留一段元素,这段元素的起始地址为pa或者pbpc->next = (pa ? pa : pb);//链表合并完毕,释放Lb的头结点delete Lb;
}
这个算法的复杂度为O(n),但是空间复杂度为O(1),巧妙的地方在于不需要在堆区申请新的内存空间组成合并链表。
2.7.2、有序表的合并
算法步骤[(1) 创建一个空表Lc;(2) 依次从La或Lb中摘取元素值较小的结点插入到Lc表的最后,直至其中一个表变为空为止;(3) 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后。]
2.8、案例分析与实现
一元多项式的运算:实现两个多项式加、减、乘等运算
void OperatePoly(SqList &L1, SqList &L2, SqList &L3)
{for (int i = 0; i < L1.length && i < L2.length; i++){L3.elem[i] = L1.elem[i] + L2.elem[i];L3.length += 1;}if (L1.length <= L2.length){for (int j = L1.length; j < L2.length; j++){L3.elem[j] = L2.elem[j];L3.length += 1;}}else {for (int j = L2.length; j < L1.length; j++){L3.elem[j] = L1.elem[j];L3.length += 1;}}
}
稀疏多项式的相加
合并两个有序顺序表(变形)
void SequSum(SqList &L1, SqList &L2, SqList &L3)
{ElemType *p1 = L1.index;ElemType *p1_last = L1.index + L1.length - 1;ElemType *p2 = L2.index;ElemType *p2_last = L2.index + L2.length - 1;ElemType *p3 = L3.index;ElemType *p3_last = L3.index + L3.length - 1;while (p1 <= p1->last && p2 <= p2->last){if (p1->expo < p2->expo){p3->expo = p1->expo;p3->coef = p1->coef;++p1;++p3;++L3.length;}else if (p2->expo < p1->expo){p3->expo = p2->expo;p3->coef = p2->coef;++p2;++p3;++L3.length;}else{p3->expo = p1->expo; //p1->expo与p2->expo值相等p3->coef = p1->coef + p2->coef;++p1;++p2;++p3;++L3.length;}}while (p1 <= p1_last){p3->expo = p1->expo;p3->coef = p1->coef;++p1;++p3;++L3.length;}while (p2 <= p2_last){p3->expo = p2->expo;p3->coef = p2->coef;++p2;++p3;++L3.length;}
}
合并两个有序链表(变形)
void LinkSum(LinkedList &La, LinkedList &Lb, LinkedList &Lc)
{Lnode *pa = La->next; //指向空结点Lnode *pb = Lb->next;Lc = La;Lnode *pc = Lc->next;while (pa && pb){if (pa->data.expo < pb->data.expo){pc->next = pa;pc = pc->next;pa = pa->next;}else if(pa->data.expo > pb->data.expo){pc->next = pb;pc = pc->next;pb = pb->next;}else if(pa->data.expo == pb->data.expo){pa->data.coef += pb->data.coef;pc->next = pa;pc = pc->next;pa = pa->next;pb = pb->next;}}pc->next = (pa ? pa : pb);delete Lb;
}
图书管理系统 - 单链表实现
结构体定义
typedef struct Book
{string isbn;string name;float price;
} ElemType;
struct Lnode
{ElemType data;Lnode *next;
} *LinkList;
其他操作,例如对图书的添加、删除、查找等操作,和单链表基本上一样的,这里就不赘述了。不过,受到《C++ Primer》的启发,我们可以添加两个这样的函数,简化程序:
//使用read函数向ElemType的对象写入数据
istream &read(istream &in, ElemType &rhs)
{in>>rhs.isbn;in>>rhs.name;in>>rhs.price;return in;
}//使用print函数打印ElemType对象
ostream &print(ostream &out, ElemType &rhs)
{out<<rhs.isbn<<" "<<rhs.name<<" "<<rhs.price<<endl;return out;
}
如何使用这两个函数?
//读
read(cin, L->data);
//写
print(cout, L->data);
本篇完~
3、栈和队列
3.1、 栈和队列的定义和特点
栈和队列是限定插入和删除只能在表的“端点”进行的线性表
栈——后进先出
队列——先进先出
3.1.1 栈的定义和特点
栈(stack)
插入元素到栈顶(即表尾)的操作,称为入栈。
从栈顶(即表尾)删除最后一个元素的操作,称为出栈。
3.1.2 队列的定义和特点
队列(queue)
在表一端(表尾)插入,在另一端(表头)删除
3.2 案例
十进制与八进制的转换(反向取值)
括号匹配的检验(([{}])的匹配检索)
表达式求值(数值入栈,运算符入栈)
舞伴问题(配对问题)
3.3 栈的表示和操作的实现
空栈:base==top 是栈空标志
栈满:top-base==stacksize 是栈满标志
#define MAXSIZE 100 //顺序栈的表示
typedef struct {SElemType *base; //栈底指针SELemType *top; //栈顶指针int stacksize; //栈可用最大容量
} SqStack;顺序栈的初始化bool InitializeStack (SqStack &S)
{S.base = new ElemType(MAXSIZE);if (!S.base){cerr << "fail to get memory" << endl;return false;}S.top = S.base;;S.stacksize = MAXSIZE;return true;
}
顺序栈的入栈
bool Push (SqStack &S, SElemType &e)
{//判断栈是否满if (S.top - S.base == S.stacksize){cerr << "full stack" << endl;return false;}*S.top = e;S.top++;return true;
}顺序栈的出栈bool Pop (SqStack &S, SElemType &e)
{//判断栈是否空if (S.top == S.base){cerr << "empty stack" << endl;return false;}S.top--;e = *S.top;return true;
}
链栈:运算受限的单链表,只能在链表头部进行操作
链栈的入栈(视频)
bool Push(LinkStack &S, SElemType &e)
{p = new StackNode; //生成新结点p->data = e; //将新结点数据置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针return true;
}
链式栈的定义
typedef struct StackNode
{ElemType data;StackNode *next;
} * LinkStack;
栈的初始化
void InitStack(LinkStack &S)
{//创建头结点S = new StackNode;S->next = nullptr;S->data = 0; //表示栈的元素个数
}
//王老师的视频中没有设置头结点
//由于ELemType等价于int,因此我设置了一个头结点,在头结点的数据域中保存栈的元素个数
压栈
void Push(LinkStack &S, const ElemType &e)
{//插入元素StackNode *temp = new StackNode;temp->data = e;temp->next = S;S = temp;++(S->data);//元素个数加一
}
弹栈
void Pop(LinkStack &S, ElemType &e)
{//删除元素StackNode *p = S;e = p->data;S->next = p->next;--(S->data);delete p;
}
创建栈
void CreatStack(LinkStack &S, const int n)
{ElemType input;for (int i = 0; i < n;++i){cin >> input;Push(S, input);}
}
获取栈的元素个数
int StackLength(LinkStack &S)
{return S->data;
}
判断栈是否为空
bool IsEmpty(LinkStack &S)
{if(!(S->next)){return true;}else {return false;}
}
3.4 栈与递归
分治法:对于一个复杂问题,分解成几个相对简单的问题
long Fact(long n)
{if (n == 0) return 1; //基本项else return n * Fact(n - 1); //归纳项
}
● 函数调用过程:调用前,系统完成:保存参数、地址、局部变量等;调用后,系统完成:释放数据等。
3.5 队列的表示和操作的实现
队列(Queue)是仅在表尾进行插入操作,在表头进行删除操作的线性表
3.5.1 队列的抽象数据类型定义
队列的物理存储可以用顺序存储结构,也可以用链式存储结构
3.5.2 队列的顺序表示和实现
#define MAXQSIZE 100 //最大队列长度
Typedef struct
{QElemType *base; //初始化的动态分配存储空间int front; //头指向int rear; //尾指向
} SqQueue;front == rear (队空还是队满)
循环队列的初始化
bool InitQueue (SqQueue &Q)
{Q.base = new QElemType[MAXQSIZE]; //分配数组空间if (!Q.base) exit (OVERFLOW); //存储分配失败Q.front = Q.rear = 0; //头指针尾指针置为0,队列为空return true;
}
求队列的长度
int QueueLength (SqQueue &Q)
{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
3.5.3 链队——队列的链式表示和实现
#define MAXQSIZE 100 //最大队列长度
typedef struct Qnode
{QElemType data;struct Qnode *next;
} QNode, *QueuePtr;typedef struct
{QueuePtr front; //队头指针QueuePtr rear; //队尾指针
} LinkQueue;
打印链队
void PrintQueue (LinkQueue &Q)
{Qnode *p = Q.front->next;while (p){cout << p->data << endl;p = p->next;}
}
4 串、数组和广义表
4.1 串的定义
串(String)----零个或多个任意字符组成的有限序列
子串:串中任意个连续字符组成的子序列称为该串的子串
4.2 案例引入
病毒检测(aab,aba,baa)
4.3 串的类型定义、存储结构及运算
按照存储结构划分(顺序则是顺序串,链式则是链串)
顺序存储结构
#define MAXLEN 255
typedef struct
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度
} SString;
串的链式存储结构
#define MAXLEN 255
typedef struct
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度char *head; //指向链串的头结点
} LString *L;
串的模式匹配算法----BF(Brute Force)算法
简单匹配算法,采用穷举法
int index_BF (SString S, SString T, int pos)
{int i = pos, j = 1;while (i <= S.length && j <= T.length){if (s.ch[i] == t.ch[j]) {+=i; ++j;} //主串和子串依次匹配下一个字符else {i = i - j + 2; j = 1;} //主串、子串指针回溯重新开始下一次匹配}if (j >= T.length) return i - T.length; //返回匹配的第一个字符的下标else return 0; //模式匹配不成功
}
时间复杂度O(n*m)
KMP算法(Knuth Morris Pratt):时间复杂度O(n+m)
void get_next(SString T, int &next[])
{int i = 1; next[1] = 0; j = 0;while (i < T.length){if (j == 0 || T.ch[i] == T.ch[j]){++i; ++j;next[i] = j;}elsej = next[j];}
}
int Index_KMP(SString, SString T, int pos)
{i = pos, j = 1;while (i <= S.length && j <= T.length){if (j == 0 || S.ch[i] == T.ch[j]){i++;j++;next[i] = j;}elsej = next[j];}if (j >= T.length) return i - T.length; //匹配成功else return 0; //返回不匹配标志
}
4.4 数组
按照一定格式排列起来的,具有相同类型的数据元素集合
数组特点:结构固定——维数和维界不变
数组的基本操作:初始化、销毁、修改元素(一般没有插入和删除操作)
页、行、列三维数据进行陈列
矩阵可以描述为一个二维数组
对称矩阵
稀疏矩阵存储:非零元素很少,( <= 5%)
例如元素12,9的表示
1 2 12
1 3 9
4.5 广义表
广义表(又称为列表Lists)是n个元素的有限序列。其中一个元素是原子,或是一个广义表。
5 树和二叉树
5.1 树和二叉树的定义
非线性结构(前驱和后继并不是1:1的比例)
树是n个结点的有限集
5.1.1 树的定义
5.1.2 树的基本术语
根据树中结点的各子树有无次序可以分为:1、有序树 2、无序树。
森林:是m棵互不相交的树的集合。
5.1.3 二叉树的定义
二叉树是n个结点的有限集,或者是空集,或者由一个根节点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树构成。(二叉树结构简单,规律性强)
特点:1、每个结点最多有两孩子;2、子树有左右之分,其次序不能颠倒;3、二叉树可以是空集合,根可以有空的左子树或者是空的右子树。
5.2 案例引入
数据压缩问题:将数据文件转换成0、1组成的二进制串,称之为编码。
5.3 树和二叉树的抽象数据类型定义
ADT(abstract data type) 中序遍历、先序遍历、后序遍历
5.4 二叉树的性质和存储结构
在二叉树的第i层至多有2i-1个结点,至少有1个结点;深度为k的二叉树最大结点数为2k-1,至少有k个结点
性质3:对于任何一棵二叉树(叶子数,度为2的结点数存在关系)
满二叉树:一棵深度为k的二叉树拥有结点数为2k-1,叶子结点全在最底层,满二叉树编号规则(从上到下,从左到右)
完全二叉树:深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号1~n的结点一一对应时,称之为完全二叉树。
二叉树顺序存储表示
#define MAXTSIZE 100 //设置最大容量
Typedef TElemType SqBiTree[MAXTSIZE]
SqBiTree bt;
利用数组进行存储(没有的分支用0来表示)
二叉树的链式存储结构
typedef struct BiNode
{TElemType data;struct BiNode *lchild, *rchild; //左右孩子指针
} BiNode, *BiTree; //嵌套递归调用
5.5 遍历二叉树和线索二叉树
5.5.1 遍历二叉树
先序遍历:若为空树,空操作;不然先访问根结点,再左结点,最后右结点。
中序遍历:若为空树,空操作;不然先访问左结点,再根结点,最后右结点。
后序遍历:若为空树,空操作;不然先访问左结点,再右结点,最后根结点。
例题:已知先序和中序序列求二叉树,先确定根节点~ 再确定左子树和右子树
前后序确定根结点,中序辨别树结构
二叉树先序遍历算法
bool PreOrderTraverse(BiTree T)
{if (T == nullptr) return true; //空二叉树else //cout << T->data << endl;{visit(T); //访问根结点PreOrderTraverse(T->lchild); //递归遍历左子树PreOrderTraverse(T->rchild); //递归遍历右子树}
}
二叉树中序遍历算法
bool PreOrderTraverse(BiTree T)
{if (T == nullptr) return true; //空二叉树else //cout << T->data << endl;{PreOrderTraverse(T->lchild); //递归遍历左子树visit(T); //访问根结点 PreOrderTraverse(T->rchild); //递归遍历右子树}
}
二叉树后序遍历算法
bool PreOrderTraverse(BiTree T)
{if (T == nullptr) return true; //空二叉树else //cout << T->data << endl;{PreOrderTraverse(T->lchild); //递归遍历左子树PreOrderTraverse(T->rchild); //递归遍历右子树visit(T); //访问根结点 }
}
中序遍历非递归算法
bool InOrderTraverse(BiTree T)
{BiTree p, q;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{Pop(S, q);cout << q->data;p = q->rchild;}}return true;
}
二叉树的层次遍历
利用队列的方式
void LevelOrder(BTNode *b)
{BTNode *p;SqQueue *qu;InitQueue(qu); //初始化队列enQueue(qu, b); //根结点指针进入队列while (!QueueEmpty(qu)) //队不为空,则循环{deQueue(qu, p); //出队结点pcout << p->data; //访问结点pif (p->lchild != nullptr) enQueue(qu, p->lchild); //有左孩子时将其进队if (p->rchild != nullptr) enQueue(qu, p->rchild); //有右孩子时将其进队}
}
复制二叉树
int Copy(BiTree T, BiTree &NewT)
{if (T == nullptr) //如果是空树返回0{NewT = nullptr;return 0;}else {NewT = new BiTNode;NewT->data = T->data;Copy(T->lChild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
}
计算二叉树深度
int Depth(BiTree T)
{if (T == nullptr) return 0; //如果是空树返回0else{m = Depth(T->lChild);n = Depth(T->rChild);if (m > n) return(m + 1);else return(n + 1)}
}
计算二叉树结点总数
int NodeCount(BiTree T)
{if (T == nullptr) return 0;else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
计算二叉树叶子结点总数
int LeafCount(BiTree T)
{if (T == nullptr) return 0;if (T->lchild == nullptr && T->rchild == nullptr) return 1;else return LeafCount(T->lchild) + LeafCount(T->rchild);
}
5.5.2 线索二叉树
改变空指针域的指向称为线索
5.6 树和森林
5.6.1 树的存储结构
结点结构和树结构的定义
typedef struct PTNode
{TElemType data;int parent; //双亲位置域
} PTNode;#define MAX_TREE_SIZE 100
typedef struct
{PTNode nodes[MAX_TREE_SIZE];int r, n; //根结点的位置和结点个数
} PTree;
5.6.2 二叉树的转换
将树转换为二叉树:(1)加线:在兄弟之间加一连线;(2)抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系;(3)旋转:以树的根结点为轴心,将整树顺时针旋转45°。
树变二叉树:兄弟相连留长子
森林变二叉树:树变二叉根相连
5.6.3 树和森林的遍历
5.7 哈夫曼树及其应用
5.7.1 哈夫曼树的基本概念
判断树:用于描述分类过程的二叉树
哈夫曼树(最优二叉树,更确切地说是最小的带权路径长度树)
路径:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。结点的路径长度:两结点路径上的分支数。
● 树的路径长度(所有结点的路径总和)、权(给结点赋一个有着某种含义的数值)
● 树的带权路径长度:树中所有叶子结点的带权路径长度之和
5.7.2 哈夫曼树的构造算法
算法实现:
void CreateHuffman Tree(HuffmanTree HT, int n) //构造哈夫曼树——哈夫曼算法
{if (n <= 1) return;m = 2 * n - 1; //数组共2n-1个元素HT = new HTNode[m + 1]; //0号单元未用,HT[m]表示根结点for (int i = 1; i <= m; ++i) //将2n-1个元素的lch、rch、parent置为0{HT[i].lch = 0;HT[i].rch = 0;HT[i].parent = 0;}for (int i = 1; i <= n; ++i){cin >> HT[i].weight; //输入前n个元素的weight值}//初始化结束,下面开始建立哈夫曼树for (int i = n + 1; i <= m; i++) //合并产生n-1个结点——构造Huffman树{Select(HT, i - 1, s1, s2); //在HT[k](1<=k<=i-1)中选择两个其双亲域为0且//权值最小的结点,并返回它们在HT中的序号s1和s2HT[s1].parent = i; HT[s2].parent = i; //表示从F中删除s1,s2HT[i].lch = s1; HT[i].rch = s2; //s1,s2分别作为i的左右孩子HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权值为左右孩子权值之和}
}
5.7.3 哈夫曼编码
二进制编码(A——00,B——01,C——10,D——11),但是位数太多
哈夫曼编码:利用出现概率大小决定编码长短,左0右1,根到结点经过的数字形成编码
由于没有一片树叶是另一片树叶的祖先,所以每个叶结点的编码不可能是其它叶结点编码的前缀;因为哈夫曼树的带权路径长度最短,故字符编码的总长最短。
● 性质1 哈夫曼编码是前缀码
● 性质2 哈夫曼编码是最优前缀码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{//从叶子到根逆向求每个字符的哈夫曼编码,存储在编码表HC中HC = new char*[n + 1]; //分配n个字符编码的头指针矢量cd = new char[n]; //分配临时存放编码的动态数组空间cd[n - 1] = '\0'; //编码结束符for (int i = 1; i <= n; ++i){//逐个字符求哈夫曼编码start = n - 1;c = i;f = HT[i].parent;while (f != 0){//从叶子结点开始向上回溯,直到根结点--start; //回溯一次start向前指一个位置if (HT[f].lchild == c) cd[start] = '0'; //结点c是f的左孩子,则生成代码0else cd[start] = '1'; //结点c是f的右孩子,则生成代码1c = f; HT[f].parent; //继续向上回溯,求出第i个字符的编码}HC[i] = new char[n - start]; //为第i个字符串编码分配空间strcpy(HC[i], &cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中}delete cd; //释放临时空间
} //CreatHuffanCode
6 图
6.1 图的定义和术语
图:G=(V, E),其中 V:顶点(数据元素)的有穷非空集合;E:边的有穷集合
完全图:任意两个点都有一条边相连(有向和无向)
稀疏、稠密图
网:边/弧带权的图
邻接:有边/弧相连的两个顶点之间的关系
顶点的度:与该顶点相关联的边的数目,记为TD(v)
路径:接续的边构成的顶点序列
路径长度:路径上边或弧的数目/权值之和
回路(环):第一个顶点和最后一个顶点相同的路径
简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径
简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径
6.2 案例引入
六度空间理论
6.3 图的类型定义
ADT:图的创建,BFS,DFS
6.4 图的存储结构
图的逻辑结构:多对多
6.4.1 邻接矩阵
邻接矩阵的存储表示:用两个数组分别存储顶点表和邻接矩阵
#define MaxInt 32767 //表示极大值,即inf
#define MVNum 100 //最大顶点数
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整形typedef struct {VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum; //图的当前点数和边数
} AMGraph; //Adjacency Matrix Graph
算法6.1 采用邻接矩阵表示法创建无向图
bool CreateUDN(AMGraph &G)
{ //采用邻接矩阵表示法,创建无向网Gcin >> G.vexnum >> G.arcnum; //输入总顶点数,总边数for (i = 0; i < G.vexnum; ++i)cin >> G.vexs[i]; //依次输入点的信息for (i = 0; i < G.vexnum; ++i) //初始化邻接矩阵for (j = 0; j < G.vexnum; ++j)G.arcs[i][j] = MaxInt; //边的权值均置为极大值for (k = 0; k < G.arcnum; ++k) //构造邻接矩阵{cin >> v1 >> v2 >> w; //输入一条边所依附的顶点及权值i = LocateVex(G, v1);j = LocateVex(G, v2); //确定v1和v2在G中的位置G.arcs[i][j] = w; //边<v1, v2>的权值置为wG.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w}return true;
}
int LocateVex(AMGraph G, VertexType u)
{int i;for (i = 0; i < G.vexnum; ++i)if (u == G.vexs[i]) return i;return -1;
}
6.4.2 邻接表
邻接表的表示法(链表)
typedef struct VNode //结点结构
{VerTexType data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum]; //AdjList表示邻接表类型#define MVNum 100 //最大顶点数
typedef struct ArcNode //边结点结构
{int adjvex; //该边所指向的顶点的位置struct ArcNode *nextarc; //指向下一条边的指针OtherInfo info; //和边相关的信息
} ArcNode;
算法6.2 采用邻接表表示法创建无向网
bool CreateUDG(ALGraph &G) //采用邻接表表示法,创建无向图G
{cin >> G.vexnum >> G.arcnum; //输入总顶点数,总边数for (int i = 0; i < G.vexnum; ++i) //输入各点,构造表头结点表{cin >> G.vertices[i].data; //输入顶点值G.vertices[i].firstarc = nullptr; //初始化表头结点的指针域}for (int k = 0; k < G.arcnum; ++k) //输入各边,构造邻接表{cin >> v1 >> v2; //输入一条边依附的两个顶点i = LocateVex(G, v1);j = LocateVex(G, v2);}p1 = new ArcNode; //生成一个新的边结点*p1p1->adjvex = j; //邻接点序号为jp1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1; //将新结点*p1插入到顶点vi的边表头部//若为有向边,则不用p2p2 = new ArcNode; //生成另一个对称的新的边结点*p2p2->adjvex = i; //邻接点序号为ip2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2; //将新结点*p2插入顶点vj的边表头部return true;
}
6.4.3 十字链表——用于有向图
6.4.4 邻接多重表(无向图的另一种链式存储结构)
6.5 图的遍历
深度优先遍历(DFS)
连通图的深度优先遍历类似于先序遍历
算法6.5 采用邻接矩阵表示图的深度优先搜索遍历
void DFS(AMGraph G, int v) { //图G为邻接矩阵类型cout << v; visited[v] = true; //访问第v个顶点for (int w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在的行if ((G.arcs[v][w] != 0) && (!visited[w]))DFS(G, w);//w是v的邻接点,如果w未访问,则递归调用DFS
}
广度优先搜索(BFS)
算法6.7 按照广度优先非递归遍历连通图G
void BFS(Graph G, int v) { //按广度优先非递归遍历连通图Gcout << v; visited[v] = true; //访问第v个顶点InitQueue(Q); //辅助队列Q初始化,置空EnQueue(Q, v); //v进队while (!QueueEmpty(Q)) { //队列非空DeQueue(Q, u); //队头元素出队并置为ufor (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))if (!visited[w]) { //w为u的尚未访问的邻接顶点cout << w; visited[w] = true;EnQueue(Q, w); //w进队} //if} //while
} //BFS
6.6 图的应用
6.6.1 最小生成树
生成树:所有顶点均由边连接在一起,但不存在回路的图
MST性质可以用于构造最小生成树
构造最小生成树的一些算法:
6.6.2 最短路径
有向图(区别于最小生成树的无向图),不需要遍历所有结点!
一、单源最短路径-用Dijkstra(迪杰斯特拉)算法
二、所有顶点间的最短路径-用Floyd(弗洛伊德)算法
Dijkstra:
Floyd:
6.6.3 拓扑排序和关键路径
拓扑排序:
例如:排课表中课程存在先后顺序。
关键路径:
7 查找
7.1 查找的基本概念
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或记录。
主关键字:可以唯一标识一个记录
7.2 线性表的查找
一、顺序查找(线性查找)
二、折半查找(二分或对分查找)
三、分块查找
7.2.1 顺序查找
算法7.2 时间效率分析
int Search_Seq(SSTable ST, KeyType key) {ST.R[0].key = key;for (int i = ST.length; ST.R[i].key != key; --i);return i;
}
● 时间复杂度为O(n)
● 空间复杂度:一个辅助空间-O(1)
7.2.2 折半查找
每次将待查找记录所在区间缩小一半(mid = (low + high) / 2)
算法7.3 折半查找
int Search_Bin(SSTable ST, KeyType key) {int low = 1, high = ST.length; //置区间初值while (low <= high) {mid = (low + high) / 2;if (ST.R[mid].key == key) return mid; //找到待查元素else if (key < ST.R[mid].key) //缩小查找区间high = mid - 1; //继续在前半区间进行查找else low = mid + 1; //继续在后半区间进行查找}return 0; //顺序表中不存在待查元素
} //Search_Bin
时间复杂度:O(logN) 对数级
空间复杂度:O(1)常数级
7.2.3 分块查找
例如:字典中(A~Z)分块搜索
折中方法,平均查找长度位于中间,插入删除方便,但是分块需要分别排序(块间有序,块内无序)
7.3 树表的查找
二叉排序树的操作
算法7.4 二叉排序树的递归查找
BSTree SearchBST(BSTree T, KeyType key) {if (!T || key == T->data.key) return T;else if (key < T->data.key)return SearchBST(T->lchild, key); //在左子树中继续查找else return SearchBST(T->rchild, key); //在右子树中继续查找
} //SearchBST
还有一些插入和删除操作~
7.3.1 二叉排序树
问题:如何提高形态不均衡的二叉排序树的查找效率?
解决办法:做“平衡化”处理,尽量让二叉树的形态均衡!
7.3.2 平衡二叉树
平衡因子:左子树高度-右子树高度(-1,0,1)
平衡类型的四种类型
调整原则:1)降低高度 2)保持二叉排序树性质
7.4 散列表的查找
7.4.1 散列表的基本概念
基本思想:记录的存储位置与关键字之间存在对应关系
冲突:不同的关键码映射到同一个散列地址
同义词:具有相同函数值的多个关键字
7.4.2 散列函数的构造方法
7.4.3 处理冲突的方法
- 开放定址法(开地址法)
- 链地址法(拉链法)
- 再散列法(双散列函数法)
- 建立一个公共溢出区
7.4.4 散列表的查找
8 排序
8.1 概述
8.2 插入排序
基本思想:每步将一个待排序的对象,插入到已经排好顺序的序列中
● 直接插入排序——采用顺序查找法查找插入位置
void InsertSort(SqList &L) {int i, j;for (i = 2; i < L.length; ++i) {if (L.r[i].key < L.r[i - 1].key) { //若“<”,需将L.r[i]插入到有序子表L.r[0] = L.r[i]; //复制为哨兵for (j = i - 1; L.r[0].key < L.r[j].key; --j) {L.r[j + 1] = L.r[j]; //记录后移}L.r[j + 1] = L.r[0]; //插入到正确位置}}
}
● 折半插入排序
void BInsertSort(SqList &L) {for (int i = 2; i <= L.length; ++i) { //依次插入第2~n个元素L.r[0] = L.r[i]; //当前插入元素存在“哨兵”位置int low = 1, high = i - 1; //采用二分查找法查找插入元素while (low < high) {mid = (low + high) / 2;if (L.r[0].key < L.r[mid].key) high = mid - 1;else low = mid + 1;} //循环结束,high + 1则为插入位置for (j = i - 1; j > high + 1; --j) L.r[j + 1] = L.r[j]; //移动元素L.r[high + 1] = L.r[0]; //插入到正确位置}
} //BInsertSort
● 希尔插入排序
定义增量序列,分块排序后形成有序序列
void ShellInsert(SqList &L, int dk) {//对顺序表L进行一趟增量为dk的Shell排序,dk为步长因子for (int i = dk + 1; i <= L.length; ++i)if(r[i].key < r[i - dk].key) {r[0] = r[i];for (int j = i - dk; j > 0 && (r[0].key < r[j].key); j = j -dk)r[j + dk] = r[j];r[j + dk] = r[0];}
}
8.3 交换排序
8.3.1 冒泡排序
基本思想:每趟不断将记录两两比较,并按前小后大的规则交换
void bubble_sort(SqList &L) { //冒泡排序算法int m, i, j; RedType x; //交换时临时存储for (int m = 1; m <= n - 1; m++) { //总共需要m趟for (int j = 1; j <= n - m; j++)if (L.r[j].key > L.r[j + 1]) {//发生交换x = L.r[j]; L.r[j] = L.r[j + 1]; L.r[j + 1] = x; //交换} //endif} //for
}
8.3.2 快读排序
基本思想:1、任取一个元素为中心(pivot:枢轴、中心点);2、所有比它小的元素一律放前,比它大的一律放后;3、对子表重复操作直到排序完毕
void main() { //对顺序表L快速排序QSort(L, 1, L.length);
}
void QSort(SqList &L, int low, int high) { //对顺序表L快速排序if (low < high)pivotloc = Partition(L, low, high);QSort(L, low, pivotloc - 1); //对低位递归排序QSort(L, pivotloc + 1, high); //对高位递归排序
}
8.4 选择排序
8.4.1 简单选择排序
基本思想:在待排序的数据中选出最大(小)的元素放在最终位置
8.4.2 堆排序
完全二叉树:深度为k,而且k-1层为满的二叉树
8.5 归并排序
基本思想:将两个或两个以上有序序列归并成一个有序序列
8.6 基数排序
基本思想:分配+收集
也叫桶排序或箱排序,设置若干个箱子,将关键字为k的记录放入第k个箱子,然后再按照序号将非空的连接。
8.7 各种排序方法的综合比较
相关文章:
数据结构(无图版)
数据结构与算法(无图版,C语言实现) 1、绪论 1.1、数据结构的研究内容 一般应用步骤:分析问题,提取操作对象,分析操作对象之间的关系,建立数学模型。 1.2、基本概念和术语 数据:…...
软件测试中的顶级测试覆盖率技术
根据 CISQ 报告,劣质软件每年给美国公司造成约2.08 万亿美元的损失。虽然软件工具是企业和行业领域的必需品,但它们也容易出现严重错误和性能问题。人类手动测试不再足以检测和消除软件错误。 因此,产品或软件开发公司必须转向自动化测试&am…...
vscode使用技巧
常用快捷键 代码格式 Windows系统。格式化代码的快捷键是“ShiftAltF” Mac系统。格式化代码的快捷键是“ShiftOptionF” Ubuntu系统。格式化代码的快捷键是“CtrlShiftI”配置缩进 点击左上角的“文件”菜单,然后选择“首选项”>“设置”,或者使用…...
JSP
概念:Java Server Pages,Java服务端页面 一种动态的网页技术,其中既可以定义HTML、JS、CSS等静态内容,还可以定义Java代码的动态内容 JSP HTML Java 快速入门 注:Tomcat中已经有了JSP的jar包,因此我们…...
Mybatis--TypeHandler使用手册
TypeHandler使用手册 场景:想保存user时 teacher自动转String ,不想每次保存都要手动去转String;从DB查询出来时,也要自动帮我们转换成Java对象 Teacher Data public class User {private Integer id;private String name;priva…...
网络编程(TCP、UDP)
文章目录 一、概念1.1 什么是网络编程1.2 网络编程中的基本知识 二、Socket套接字2.1 概念及分类2.2 TCP VS UDP2.3 通信模型2.4 接口方法UDP数据报套接字编程TCP流套接字编程 三、代码示例3.1 注意点3.2 回显服务器基于UDP基于TCP 一、概念 首先介绍了什么是网络编程ÿ…...
Python快速入门系列-7(Python Web开发与框架介绍)
第七章:Python Web开发与框架介绍 7.1 Flask与Django简介7.1.1 Flask框架Flask的特点Flask的安装一个简单的Flask应用示例7.1.2 Django框架Django的特点Django的安装一个简单的Django应用示例7.2 前后端交互与数据传输7.2.1 前后端交互7.2.2 数据传输格式7.2.3 示例:使用Flas…...
最长对称子串
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空字符串。 输出格式&…...
【大模型】大模型 CPU 推理之 llama.cpp
【大模型】大模型 CPU 推理之 llama.cpp llama.cpp安装llama.cppMemory/Disk RequirementsQuantization测试推理下载模型测试 参考 llama.cpp 描述 The main goal of llama.cpp is to enable LLM inference with minimal setup and state-of-the-art performance on a wide var…...
异地组网怎么管理?
在当今信息化时代,随着企业的业务扩张和员工的分布,异地组网已经成为越来越多企业的需求。异地组网管理相对来说是一项复杂而繁琐的任务。本文将介绍一种名为【天联】的管理解决方案,帮助企业更好地管理异地组网。 【天联】组网的优势 【天联…...
Kafka参数介绍
官网参数介绍:Apache KafkaApache Kafka: A Distributed Streaming Platform.https://kafka.apache.org/documentation/#configuration...
如何利用待办事项清单提高工作效率?
你是否经常因为繁重的工作量而感到不堪重负?你是否在努力赶工期或经常忘记重要的电子邮件?你并不是特例。如何利用待办事项清单提高工作效率?这里有一个简单的方法可以帮你理清混乱并更高效地完成任务—待办事项清单。 这种类型的清单可以帮…...
力扣经典150题第二题:移除元素
移除元素问题详解与解决方法 1. 介绍 移除元素问题是 LeetCode 经典题目之一,要求原地修改输入数组,移除所有数值等于给定值的元素,并返回新数组的长度。 问题描述 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等…...
55555555555555
欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab,机器人运动控制、多机器人协作,智能优化算法,滤波估计、多传感器信息融合,机器学习,人工智能等相关领域的知识和…...
用Skimage学习数字图像处理(018):图像形态学处理(上)
本节开始讨论图像形态学处理,这是上篇,将介绍与二值形态学相关的内容,重点介绍两种基本的二值形态学操作:腐蚀和膨胀,以及三种复合二值形态学操作:开、闭和击中击不中变换。 目录 9.1 基础 9.2 基本操作…...
MySQL中 in 和 exists 区别
在MySQL中,IN和EXISTS都是用于在子查询中测试条件的操作符,但它们在处理和效率上有一些重要的区别。MySQL中的in语句是把外表和内表作hash连接,⽽exists语句是对外表作loop循环,每次loop循环再对内表进⾏查询。⼤家⼀直认为exists…...
Java基础 - 代码练习
第一题:集合的运用(幸存者) public class demo1 {public static void main(String[] args) {ArrayList<Integer> array new ArrayList<>(); //一百个囚犯存放在array集合中Random r new Random();for (int i 0; i < 100; …...
【Redis】redis集群模式
概述 Redis集群,即Redis Cluster,是Redis 3.0开始引入的分布式存储方案。实际使用中集群一般由多个节点(Node)组成,Redis的数据分布在这些节点中。集群中的节点分为主节点和从节点:只有主节点负责读写请求和集群信息的维护&#…...
基于opencv的猫脸识别模型
opencv介绍 OpenCV的全称是Open Source Computer Vision Library,是一个跨平台的计算机视觉库。OpenCV是由英特尔公司发起并参与开发,以BSD许可证授权发行,可以在商业和研究领域中免费使用。OpenCV可用于开发实时的图像处理、计算机视觉以及…...
基于注意力整合的超声图像分割信息在乳腺肿瘤分类中的应用
基于注意力整合的超声图像分割信息在乳腺肿瘤分类中的应用 摘要引言方法 Segmentation information with attention integration for classification of breast tumor in ultrasound image 摘要 乳腺癌是世界范围内女性最常见的癌症之一。基于超声成像的计算机辅助诊断&#x…...
数据库重点知识(个人整理笔记)
目录 1. 索引是什么? 1.1. 索引的基本原理 2. 索引有哪些优缺点? 3. MySQL有哪几种索引类型? 4. mysql聚簇和非聚簇索引的区别 5. 非聚簇索引一定会回表查询吗? 6. 讲一讲前缀索引? 7. 为什么索引结构默认使用B…...
[技术闲聊]checklist
电路设计完成后,需要确认功能完整性,明确是否符合设计规格需求;需要确认电路设计是否功能符合但是系列项不符合设计规则,如果都没有问题,那么就可以发给layout工程师。 今天主要讲讲电路设计规则,涉及到一…...
力扣刷题 二叉树的迭代遍历
题干 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。 示例 1: 输入:root [1,null,2,3] 输出:[1,2,3]示例 2: 输入:root [] 输出:[]示例 3: 输入:root [1] 输…...
【二】Django小白三板斧
今日内容 静态文件配置 request对象方法初识 pycharm链接数据库(MySQL) django链接数据库(MySQL) Django ORM简介 利用ORM实现数据的增删查改 【一】Django小白三板斧 HttpResponse 返回字符串类型的数据 render 返回HTML文…...
MyBatis的基本应用
源码地址 01.MyBatis环境搭建 添加MyBatis的坐标 <!--mybatis坐标--><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.9</version></dependency><!--mysql驱动坐…...
Day80:服务攻防-中间件安全HW2023-WPS分析WeblogicJettyJenkinsCVE
目录 中间件-Jetty-CVE&信息泄漏 CVE-2021-34429(信息泄露) CVE-2021-28169(信息泄露) 中间件-Jenkins-CVE&RCE执行 cve_2017_1000353 CVE-2018-1000861 cve_2019_1003000 中间件-Weblogic-CVE&反序列化&RCE 应用金山WPS-HW2023-RCE&复现&上线…...
使用generator实现async函数
我们先来看一下async函数是怎么使用的 const getData (sec) > new Promise((resolve) > {setTimeout(() > resolve(sec * 2), sec * 1000);})// aim to get this asycnFun by generator async function asyncFun() {const data1 await getData(1);const data2 awa…...
go并发请求url
sync.WaitGroup写法 package mainimport ("database/sql""fmt""net/http""sync""time"_ "github.com/go-sql-driver/mysql" )func main() {//开始计时start : time.Now()//链接数据库,用户名…...
刷题之Leetcode704题(超级详细)
704. 二分查找 力扣题目链接(opens new window)https://leetcode.cn/problems/binary-search/ 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标&am…...
leetcode热题100.前k个高频元素
作者:晓宜 🌈🌈🌈 个人简介:互联网大厂Java准入职,阿里云专家博主,csdn后端优质创作者,算法爱好者 ❤️❤️❤️ 你的关注是我前进的动力😊 Problem: 347. 前 K 个高频元…...
开发网站的流程/北京网
自动化项目群订单 | 技术 | 干货 | 社群关注可加入项目对接群!接单非标自动化设备的发展现状随着劳动力成本的不断提高,越来越多的企业开始关注工业自动化设备这一领域,特别是非标自动化设备,精锐达认为它不像传统普标设备那样制作…...
家居企业网站建设公司/电商培训心得体会
数组Array 定义数组的格式:var<varName> [n] <type> , n>0 数组长度也是类型的一部分,因此具有不同长度的数组为不同类型 注意区分指向数组的指针和指针数组 数组在Go中为值类型 数组之间可以使用或者!进行比较ÿ…...
营销型网站./新媒体
基于MQTT协议的消息传输为什么MQTT?之前刚写了一篇关于socket的文章,为什么又来一个MQTT?因为MQTT协议就是socket接口实现的啊(socket和MQTT只是层级不一样而已),并且感觉发布/订阅模式非常棒,于…...
网站怎样做301/深圳网站关键词优化公司
package cn.itcast; import java.io.FileWriter; import java.io.IOException; import java.io.Writer;/* 字符流入数据 writer発中的方法: void write(int ch),; 一次写一个字符 void write(charll chs, int index, int l ; 一次写一个指定的字符敷组en) ; void write (Strine…...
国外平面设计/优化网站做什么的
BCD码一般在时钟芯片中会采用,比如2019-03-29 15:42:54会表示为 0x20 0x19 0x03 0x29 0x15 0x42 0x54,具体十进制跟BCD码的关系可以百度;BCD转为十进制 int BCDToInt(unsigned char value) {int temp 0;temp (value>>4)*10;temp va…...
拼多多网站在那里做/百度一下1688
比以前就多了一点: 创建多个缓冲区,传入到顶点着色器中; attribute float a_PointSize;//传入点的尺寸 gl_Position a_Position;//设置点的尺寸 用bufferData把数据给a_PointSize 如图: 具体代码如下: <!DOCTY…...