大一下学习计划
C++ 学习C++的基本用法,如面向对象、STL等、主要是为了看懂网上的教程后续再考虑深入学习。
数据结构和算法 学习数据结构的基本用法,链表,队列,数,图论,排序等。基本原理都基本了解,目前在不断练习各种有关数据结构的算法题,主要是leetcode和教材课后习题,争取能熟练掌握各种数据结构,熟悉代码的写法。 若学有余力再学习更多的算法并多参加竞赛。
排序
折半插入排序思路: 先用折半查找找到应该插入的位置,再移动元素;
为了保证稳定性,当查找到和插入元素关键字一样的元素时,应该继续在这个元素的右半部分继续查找以确认位置; 即当 A[mid] == A[0] 时,应继续在mid所指位置右边寻找插入位置
当low>high时,折半查找停止,应将[low,i-1]or[high+1,i-1]内的元素全部右移,并将A[0]复制到low所指的位置;
代码实现
void InsertSort(int A[], int n){ int i,j,low,high,mid; for(i=2;i<=n;i++){ A[0] = A[i]; //将A[i]暂存到A[0] low = 1; high = i-1; //折半查找的范围
while(low<=high){ //折半查找
...
操作受限线性表
栈只允许在一端进行插入或删除操作的线性表操作与普通顺序表区别不大特点:先进后出,后进先出
顺序栈#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶元素}SqStack;
//初始化栈void InitStack(SqStack &S){ S.top = -1; //初始化栈顶指针}
//判栈空bool StackEmpty(SqStack S){ if(S.top == -1) //栈空 return true; else //栈不空 retu ...
树
二叉树的遍历先序typedef struct BiTnode{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;
void PreOrder(BiTree T){if(T!=NULL){ visit(T); //访问根结点(可改变访问顺序、中序、后序) PreOrder(T->lchild); //递归遍历左子树 PreOrder(T->rchild); //递归遍历右子树}}
层序遍历
一个队列层层入队
typedef struct BiTnode{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;
//链式队列结点typedef struct LinkNode{BiTNode * data;typedef LinkNode *next;}LinkNode;
t ...
顺序表
顺序表
静态顺序表
#include
#define MaxSize 10//定义最大长度
typedef struct {
int data[MaxSize];//定义静态数组
int length;//顺序表当前长度
}SqList;
void InitList(SqList& L) {
for (int i = 0;i < MaxSize;i++) {
L.data[i] = 0;//所以数据初始值为0
}
L.length = 0;//顺序表初始长度为0
}
int main() {
SqList L;//声明顺序表
InitList(L);//调用函数,初始化顺序表
return 0;
}
动态分配
#include
#include
#define InitSize 10;
//定义顺序表
...