数据结构

h3110_w0r1d

发布于 2024-02-19 20:24:56

890

发布于 2024-02-19 20:24:56

文章被收录于专栏：用户9703952的专栏用户9703952的专栏

线性表

声明结构体用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

//单链表的插入操作，需要一个循环变量计数和一个循环指针，去找到应该循环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

二叉树

顺序存储

几个常考的基本操作
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;
    }
}