声明结构体用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);
}
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
//单链表的插入操作,需要一个循环变量计数和一个循环指针,去找到应该循环d
p指针后移: 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
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;
}
}
int count = 0;
void Count(BiTree T) {
if(T == NULL) {
return 0;
}
else {
count++;
Count(T->lchild);
Count(T->rchild);
}
}
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);
}
}
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]);
}
}
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;
}
}