数据结构
线性表
声明结构体用typedef
静态分配方式用静态数组
length存放顺序表的当前长度
线性表要存放 数据元素 和 顺序表当前长度
可以理解为一个数据域：数据元素 和 一个指针域：顺序表当前长度
typedef struct { int data[MaxSize]; int length; }SqList;结构体变量作函数参数时，用引用
初始化线性表时，第一，要把每个元素都赋值为0；第二，要把线性表的长度赋值为0
void Init(SqList &L) { for(int i = 0;i < MaxSize;i++) { L.data[i] = 0; } L.length = 0; }在main函数中的初始化
int main(void) { SqList L; //初始化一个结构体变量，用类型 名称来写，int a一样 InitList(L); }插入元素，头插法
插入的位置后，从后往前，前一个元素往后挪一个位置，为待插入的元素留出空间
注意下标的起始，线性表从1开始，而数组下标从0开始。操作数 i 是从1开始，存到数组中应该是从 i-1 开始
插入元素一共要提供三个参数：插入的线性表，插入的位置，插入的元素值
void ListInsert(SqList &L,int i,int e) { for(int j = L.length;j >= i;j--) { // 插入第i-1号位置，所以要从i到Length末尾都要后移一位 L.data[j] = L.data[j-1]; } L.data[i-1] = e; L.length++; }插入元素应该加上对插入位置的判断
合法的插入范围是1->length+1,即数组中的0->length; length+1是添加到末尾的后一个位置
bool ListInsert(SqList &L,int i,int e) { if(i < 1 || i > length+1) return false; if(L.length >= MaxSize) return false; for(int j = L.length;j >= i;j--) { L.data[j] = L.data[j-1]; } L.data[i-1] = e; L.length++; return true; }按值查找，一个一个地比较
一定要明确循环的是什么，这个地方循环的是数组下标,而不是线性表的实际位置，从0->length
int LocateElem(SqList &L,int e) { for(int i = 0;i < length;i++) { if(L.data[i] == e) return i+1; // 返回的是线性表中的实际位置，数组下标+1 } return -1; }线性表是随机存取，不需要一个一个地比较，直接根据数组下标去寻找即可
int GetElem(SeqList &L,int i) { //传入的是线性表的位置 return data[i-1]; //返回的是数组中的位置对应的数据，要-1 }线性表元素删除
bool ListDelete(SeqList &L,int i,int &e) { if(i < 1||i > L.length) { //给出的删除位置为线性表的位置1-length，而不是数组下标 return false; // 首先判断要删除的元素是否合法 } e=L.data[i-1]; //将要被删除的元素赋值给e，后面返回 for(int j = i;j < L.length;j++) { L.data[j-1] = L.data[j]; //将删除元素后面的元素，从后往前移动 } L.length--; //别忘记修改指针域，即length return true; }动态拓展内存空间
初始化动态空间的线性表时，用malloc
malloc返回的是一个指针，指向了多大的内存空间的地址
malloc返回的内存空间指针指向线性表的数据域
#define InitSize 10 typedef struct { int *data; //数据域用指针 int MaxSize; int length; }SeqList; void InitList(SeqList &L) { L.data=(int*)malloc(InitSize*sizeof(int)); // malloc的参数是，多少个元素*每个元素的大小 L.length = 0; L.MaxSize = InitSize; } void IncreaseSize(SeqList &L,int len) { // 传入两个参数，一个是哪个线性表，另一个是拓展多长的内存空间 int *p = L.data; //扩展内存空间时，先用一个指针指向原有的指针，作为备份 L.data = (int*)malloc((L.MaxSize+len) * sizeof(int)); //给L重新申请一段更大的内存空间，相当于清零 for(int i = 0;i < L.length;i++) { L.data[i] = p[i]; //将原有的p指针指向的内存空间元素依次赋值给新地址L } L.MaxSize = L.MaxSize + len; free(p); }
单链表
单链表是next指针，二叉树是左右孩子lchild和rchild
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//相当于typedef struct LNode{} LNode;与typedef struct LNode{} *LinkList;
typedef struct LNode LNode;
typedef struct LNode *LinkList;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;LNode * L 与 LinkList L效果相同，都是声明一个指向单链表第一个节点的指针
强调这是一个单链表，用LinkList
强调这是一个节点，用LNode *
typedef struct LNode { int data; struct LNode * next; }LNode,*LinkList; typedef struct LNode { int data; struct LNode *next; //不要忘记在定义next指针时，用struct关键字，struct LNode *next，定义同类型内部指针时，要带struct,struct LNode* next; }LNode,*LinkList;typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; //初始化一个单链表，带头节点 bool InitList(LinkList &L) { L = (LNode *)malloc(sizeof(LNode)); // 分配一个头节点 if(L == NULL) { //如果申请后，L仍为NULL，则内存不足，申请失败 return false; } L -> next = NULL; //头节点之后暂时还没有节点 return true; } bool Empty(LinkList L) { if(L -> next == NULL) return true; //头指针指向头节点，如果头指针的下一个为空，则单链表为空 return false; } void test() { LinkList L; InitList(L); }malloc返回的是一个指针，需要强制类型转换为对应指针类型，传入的参数是多少个元素*每个元素的大小
带头节点的单链表 1. 申请一个节点大小的内存空间 2.判断L是否为NULL，内存够不够 3.将头节点的下一个节点地址域指向空 4.如果申请成功，返回true
在第i个位置插入元素e
bool ListInsert(LinkList &L,int i,int e) { if(i < 1) return false; LNode *p; //指针p指向当前扫描到的节点 int j = 0; //循环变量，用来判断当前是第几个节点 p = L; //初始状态下，L指向头节点，头节点是第0个节点 while(p!=NULL && j < i-1) { //p不是空，说明没循环到末尾，j<i-1说明还没有循环到第i-1个位置 p = p->next; j++; } if(p == NULL) { //循环到末尾也没有找到，返回false return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); //重新开辟一个节点的内存大小,申请的是节点的指针 s -> data = e; s -> next = p -> next; p -> next = s; return true; } // 1.判断插入位置是否合法 // 2.声明循环指针p指向当前扫描到的节点，循环变量j判断当前是第几个节点，这里p强调是一个节点，所以用LNode * // 3.初始状态下，循环指针p指向头指针 // 4.循环指针后移，直到移动到循环变量j和i-1相等且没到末尾 // 5.循环到末尾也没找到，p==NULL,返回false // 6.申请一个节点大小的内存单元s，申请的是节点的指针 // 7.改变s和p指针的指向关系 // 8.成功返回true //单链表的插入操作，需要一个循环变量计数和一个循环指针，去找到应该循环dp指针后移： p = p-> next; 下一个指针的地址域赋给上一个，令上一个节点后移一个单位
删除节点：首先要找到第i-1个节点，将其指针指向第i+1个节点，并释放第i个节点
bool ListDelete(LinkList &L,int i,ElemType e) { if(i < 1) return false; LNode *p; int j = 0; p = L; while(p != NULL && j < i-1) { //删除第i-1后面的第i号节点的位置 p = p -> next; j++; } if(p == NULL) { return false; } if(p -> next == NULL) { //第i-1号节点后面再无节点 return false; } LNode *q = p -> next; //令指针q指向被删除节点，p循环到删除节点的上一个节点 e = q -> data; p->next = q -> next; free(q); return true; } // 1. 找位置 // 2. 改节点，将被删除节点的上一个节点的next指针指向被删除节点的next // 3. 释放内存，将被删除节点的内存释放掉单链表求长度
int length(LinkList &L) { int len = 0; LNode *p = L; //将循环指针p指向头节点L while(p -> next != NULL) { //带头节点，头节点不算入长度的话 p = p -> next; len ++; } return len; } int length(LinkList &L) { int len = 0; LNode *p = L -> next; //跳过头节点 while(p != NULL) { p = p -> next; } return len; }尾插法建立单链表
LinkList List_TailInsert(LinkList &L) {
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r = L;
scanf("%d",&x);
while(x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s -> data = x;
r -> next = s;
r = s;
scanf("%d",&x);
}
r -> next = NULL;
return L;
}
// 后插操作
// 1. 将指针r指向要插入节点的上一个位置
// 2. 申请插入节点s并赋值
// 3. r的next指针指向s
// 4. r后移一步指向s，为下一步的操作做准备
// 最后将最后一个节点的nextz
二叉树
顺序存储
- 几个常考的基本操作
- i的左孩子
- i的右孩子
- i的父节点
- i所在的层次
-
-
- 二叉树的顺序存储中，一定要把二叉树的节点编号和完全二叉树一一对应起来
链式存储
二叉链表
- 找到节点p的左右孩子节点时间复杂度低
- 但是找某个节点的父节点，只能从根节点开始遍历
struct ElemType {
int value;
}
typedef struct BiTNode {
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //指针域
}BiTNode,*BiTree; //节点和树根节点的指针
//BiTNode* 和 BiTree等价，但是侧重方面不同
//定义一棵空树
//声明一个指向根节点的指针，初始为NULL
BiTree root = NULL;
//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;
//插入新节点
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作为根节点的左孩子节点
//插入新节点：分配一个节点大小的内存空间，给数据域赋值，并修改左右孩子和父指针三叉链表
- 包含左右孩子节点和父节点指针
- 三叉链表的目的是为了方便寻找父节点
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild,*rchild;
struct BiTNode *parent;
}BiTNode,*BiTree;求树的深度
int treeDepth(BiTree T) { //接收二叉树的节点作为参数，通常是根节点
if(T == NULL) { //如果传入的节点是NULL，则返回0，因为空树的高度为0
return 0;
}
//if T == NULL 一个是判断这棵树是否为空树，另一个是当递归到叶子节点时，可以返回0+1=1
else {
int l = treeDepth(T->lchild);
int r = treeDepth(T->rchild);
//是根据左右子树高度的最大值，应该包含根节点，所以应该+1
if(l > r) return l+1;
else return r+1;
}
}- 递归左右子树高度：treeDepth(T -> lchild); treeDepth(T -> rchild);
判断节点总数
int count = 0;
void Count(BiTree T) {
if(T == NULL) {
return 0;
}
else {
count++;
Count(T->lchild);
Count(T->rchild);
}
}- 判断节点总数，递归左右子树，并在递归左右子树之前要count++
- 二叉树判断左右子树高度和统计节点总数，都要递归实现，并递归返回的条件是传入的节点为空
设计算法按前序次序打印二叉树中的叶子结点
void PrintLeaves(BiTree T) {
if(T == NULL) {
return;
}
if(T -> lchild == NULL && T -> rchild == NULL) { //判断是否为叶子节点
printf("%d",T->data); // 只打印叶子节点
}
PrintLeaves(T -> lchild); //递归处理左子树
PrintLeaves(T -> rchild); //递归处理右子树
}前序序列打印所有节点
和只打印叶子节点相比，少了一个对是否为叶子节点的判断，即
if(T -> lchild == NULL && T -> rchild == NULL) {} if(T -> lchild == NULL && T -> rchild == NULL){} //叶子节点有一个判断，即左右孩子是否为空 if(T -> lchild == NULL && T -> rchild == NULL){} if(T -> lchild -- NULL && T -> rchild == NULL){}void PrintPreorder(BiTree T) { if(T == NULL) { return; } else { printf("%d",T -> data); PrintPreorder(T -> lchild); PrintPreorder(T -> rchild); } }
已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为偶数，右边所有元素为奇数，并要求算法的时间复杂度为Ｏ(n)
void Array_reverse() {
int i = 0,j = n-1;
while(i < j) { //i是左侧，j是右侧，只有当i指针在j指针的左侧时，才继续进行交换操作
while(a[i] % 2 == 0) i++; //a[i]满足要求，i指针后移,直到遇到一个奇数
while(a[j] % 2 != 0) j--; //a[j]满足要求，j指针前移，直到遇到一个偶数停止
if(i < j) swap(a[i],a[j]);
}
}- 从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。
试写出带头节点的单链表逆置算法，请写出结点结构???
LinkList Reverse(LinkList L) {
LNode *p,*r; //前指针和后指针
p = L -> next;
L -> next = NULL;
while(p != NULL) {
r = p -> next;
p -> next = L -> next;
L -> next = p;
p = r;
}
return L;
}
//第一步，设置前后指针
//第二步，p为第一个元素位置，断开头节点的下一个位置，断链
//第三步，判断p是否为空
//第四步，r指针后移
//第五步，p->next = L->next;
//第六步，L->next = p;
//第七步，p指针后移指向r
//zui'ho关键路径每次都取最大值
插入排序
void InsertSort(int a[],int len) {
for(int j = 1;j < len;j++) { //外部循环，从数组的第二个位置遍历到最后一个位置，外部循环控制我们要将哪个元素插入到已经排序的子数组中
int key = a[j];
int i = j - 1; //i从当前元素的前一个元素开始
while(i >= 0 && a[i] > key) {
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}堆排序
- 堆必须是一颗完全二叉树
-
- 在小根堆中，每个父节点都必须小于子节点元素
- 在大根堆中，每个父节点都必须大于子节点元素
-
- 按照层序遍历的顺序来给节点编号
-
上滤
- 当叶子节点破坏了堆序性，让他和他的父元素比较,若大于父节点则交换，直到无法上移为止，
-
下滤
- 将破坏堆序性的元素跟他的最大的子节点比较，如果小于他的最大子节点，则交换
- 持续比较，直到该元素大于他的子节点位置，或者移动到底部为止
总之，上滤是和父节点比较，下滤是和子节点比较，只能父子之间交换
建堆
- 自顶向下建堆法
- 将元素一个一个插入到堆内，将新元素放到堆的最后一位，然后对其进行上滤操作
-
取最值调整
- 在大根堆中，如果父节点比两个子节点都要小，则选最大的往上走
- 在小根堆中，如果父节点比两个子节点都要大，则选最小的往上走
排序顺序：从最后一个父节点开始往上找
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 h3110w0r1d's Blog！