数据结构（ing）

学习内容 

指针

指针的定义：

指针是一种变量，它的值为另一个变量的地址，即内存地址。

指针在内存中也是要占据位置的。

指针类型：

指针的值用来存储内存地址，指针的类型表示该地址所指向的数据类型并告诉编译器如何解释该指针所指向的内存中的数据。

指针的初始化：

指针的赋值是运用&这个操作符完成的，用于产生操作数的内存地址。

指针的运用（取值）：

运用单目操作符*来取出指针所指向的内存块的值

	int a = 921; int* b = &a; // b取得a在内存中的起始位置 int c = *b; // 得到b指向的内存块的值printf("a在内存中的起始地址为 %p \n", (void*)b);printf("b指针在内存中所指向的值为 %d \n", c);

 练习：

*&a = 25 

理解：

&a表示取a的起始地址，*（&a）表示取（&a）所指向的内存块的值

所以其实这个意思就是a=25

---

线性表

概念

定义：

具有相同特性的数据元素的一个有限序列，由n (n >= 0) 个数据元素（结点）a1、a2、a3.....an组成的有限序列。包括起始节点、终端节点、数据元素......

存储结构：

1.顺序存储结构：

        把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

2.链式存储结构：

         结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。访问时只能通过头指针进入链表。

---

顺序存储结构（顺序表）

优点：以物理位置相邻表示逻辑关系，任一元素均可随机存取，存储密度大。

缺点：在插入、删除某一元素时，需要移动大量元素，浪费存储空间，属于静态存储形式，数据元素的个数不能自由扩充。

特点： 地址连续、依次存放、随机存取 、类型相同

存储表示

逻辑结构：（a1，a2，a3，...... an）

存储结构：

顺序表的定义

顺序表的数组下标是从0开始的

数组静态分配

#define N 100typedef struct {int e;
} Node;typedef struct {  Node element[N]; //静态分配数组int length; //存储顺序表的长度
} SqList;

数组动态分配

typedef struct {int e;
} Node;typedef struct {  Node *element; //动态分配数组int length; //存储顺序表的长度
} SqList;

顺序表的基本操作

初始化线性表

// 线性表的初始化
bool InitList_Sq(SqList &L, int n)
{// 分配内存L.element = (Node*)malloc(sizeof(Node)*n);	if (!L.element) return false; //分配失败L.length = 0; // 初始化空表长度为0return true; // 初始化成功
}

销毁线性表

// 销毁线性表
void DestroyList(SqList &L)
{if (L.element) delete L.element; // 释放存储空间
}

清空线性表

// 清空线性表
void ClearList(SqList &L)
{L.length = 0; //将线性表的长度置为0
}

求线性表的长度

// 求线性表的长度
int GetLength(SqList L) 
{return L.length;
}

判断线性表是否为空

// 判断线性表是否为空
bool IsEmpty(SqList L)
{if (L.length == 0) return true;else return false;
}

顺序表取值

// 顺序表的取值（根据位置获取元素）
bool GetElement(int idx, SqList L, Node &e) 
{if (idx < 1 || idx > L.length) return false;e = L.element[idx - 1];return true;
}

按值查找

// 按值查找
int LocateElem(SqList L, Node e) 
{for (int i = 0; i < L.length; i ++){if (L.element[i].e == e.e) return i + 1;}return 0; // 查找失败
}

顺序表的插入

// 顺序表的插入
bool ListInsert_Sq(SqList &L, int idx, Node e)
{if (idx < 1 || idx > L.length + 1) return false;for (int i = L.length - 1; i >= idx - 1; i --){L.element[i + 1] = L.element[i];}L.element[idx - 1] = e;L.length ++;return true;
}

顺序表的删除

// 顺序表的删除
bool ListDelete_Sq(SqList &L, int idx)
{if (idx < 1 || idx > L.length) return false;for (int i = idx; i < L.length; i ++){L.element[i - 1] = L.element[i];}L.length --;return true;
}

---

链式存储结构（链表）

定义：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

概念表示：

结点：

数据元素的存储映像称为结点，它由数据域和指针域两部分组成。

特殊结点：

• 头结点：在链表的首元结点之前额外设置的一个结点。
• 首元结点：链表中存储第一个数据元素a1的结点

数据域：存储当前结点的数据。

指针域：存储下一个节点的位置。 

头指针： 

指向链表中第一个节点的指针。

链表：

 链表分为单链表、双链表、循环链表。

• 单链表：结点只有一个指针域，存储的是下一个节点的地址。
• 双链表：结点有两个指针域。存储相邻两个结点的地址。
• 循环链表：是一种头尾相接的链表，表中的最后一个结点的指针域指向头结点，整个链表形成一个环。

存储表示：

逻辑结构：（a1，a2，a3，...... an）

存储结构：

第一种 (无头结点) ：

第二种（有头结点）:

空表

1.无头结点时，头指针为空时表示空表，表示空表。

2.有头结点时，头结点的指针域为空时，表示空表。

单链表

数组模拟单链表：数组模拟单链表文章浏览阅读118次。数组模拟单链表https://blog.csdn.net/m0_73569492/article/details/128693718?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220bb3388a11ebbfdf7502eedcb53293d6%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=0bb3388a11ebbfdf7502eedcb53293d6&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128693718-null-null.nonecase&utm_term=%E5%8D%95%E9%93%BE%E8%A1%A8&spm=1018.2226.3001.4450

链表定义

定义了两种类型：LNode 为结构体类型；LinkList 为指向该结构体类型的指针类

typedef struct {int e;
} Data;typedef struct Lnode {Data data; // 结点的数据域struct Lnode *next; // 结点的指针域
} LNode, *LinkList; // 定义了两种类型：LNode 为结构体类型；LinkList 为指向该结构体类型的指针类型。

LinkList L; // 定义链表L
LNode *p; // 定义结点指针
LinkList q; //定义结点指针

链表操作

初始化单链表

1.生成新节点作为头结点

2.头指针指向头结点

3.头结点的指针域指向空

分配内存：

L = (LinkList)malloc(sizeof(LNode));

这一行代码调用了 malloc 函数来为一个新的 LNode 结构体分配内存。malloc 返回的是一个指向所分配内存块的指针（类型为 void*），然后通过 (LinkList) 强制转换为 LinkList 类型（即 LNode*）。此时，L 已经指向了这块新分配的内存，这块内存代表了一个新的链表节点。

// 单链表的初始化
bool InitList_L(LinkList &L) 
{L = (LinkList)malloc(sizeof(LNode)); L->next = NULL;return true;
}

 判断单链表是否为空

其实就是判断头结点的指针域是否为空，如果为空，则代表是空表，如果不为空，则代表不为空表。

// 判断链表是否为空
bool IsEmpty_List(LinkList L)
{if (L->next == NULL) return true;return false;
}

单链表的销毁

销毁过程如下：

// 单链表的销毁
void Destroy_List(LinkList &L)
{LNode *p;while (L){p = L;L = L->next;free(p);}
}

清空单链表

// 清空单链表
void Clear_List(LinkList &L)
{LNode *p;while (L->next) {p = L->next;L->next = p->next;free(p);}
}

求单链表的表长

// 求单链表的表长
int Caculate_Length(LinkList L)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next)cnt ++;return cnt;
}

根据位置获取元素

// 取值-取单链表中第idx个元素的内容
bool GetElement(LinkList L, Data &e, int idx)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next){cnt ++;if (cnt == idx) {e = p->data;return true;}	}return false;
}

按值查找

// 按值查找-根据数据获取该数据所在位置
int GetIdx(LinkList L, Data &element)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next){cnt ++;if (p->data.e == element.e) return cnt; }return -1;
}

单链表的插入（任意位置）

// 单链表的插入-在第i个元素之前插入
bool Insert(LinkList &L, int idx, Data element)
{int cnt = 0;for (LNode* p = L; p->next != NULL; p = p->next){if (cnt == idx - 1){LNode *e = (LNode*)malloc(sizeof(LNode));e->data = element;e->next = p->next;p->next = e;return true;}cnt ++;}	return false;
}

单链表删除元素

// 删除-删除第idx个元素
bool Delete(LinkList &L, int idx)
{int cnt = 0;for (LNode* p = L; p != NULL; p = p->next){if (cnt == idx - 1){LNode *q = p->next;p->next = q->next;free(q);return true;}cnt ++;}return false;	
}

头插法

// 头插法
bool Insert_Head(LinkList &L, Data element)
{LNode *cur = (LNode*)malloc(sizeof(LNode));cur->data = element;cur->next = L->next;L->next = cur;return true;
}

尾插法

// 尾插法
bool Insert_Tail(LinkList &L, Data element)
{LNode *p = L;while (p->next){p = p->next;}LNode *cur = (LNode*)malloc(sizeof(LNode));cur->data = element;cur->next = NULL;p->next = cur;return true;
}

输出单链表

// 输出单链表
void Print_List(LinkList &L)
{for (LNode* p = L->next; p != NULL; p = p->next){printf("%d ", p->data.e);}printf("\n");
}

---

循环链表

优点：

从表中任意节点出发都能够找到其他结点。

注意：

当执行遍历操作时，条件与单链表不同，结束条件需要看当前节点的指针域是不是等于头结点。

链表定义：

typedef struct {int e;
} Data;typedef struct Lnode {Data data; // 结点的数据域struct Lnode *next; // 结点的指针域
} LNode, *LinkList; // 定义了两种类型：LNode 为结构体类型；LinkList 为指向该结构体类型的指针类型。

链表操作：

带头指针的：

// 循环链表的初始化
bool InitList_L(LinkList &L) 
{L = (LinkList)malloc(sizeof(LNode));L->next = L;return true;
}
// 判断循环链表是否为空
bool IsEmpty_List(LinkList L)
{if (L->next == L) return true;return false;
}
// 循环链表的销毁
void Destroy_List(LinkList &L)
{LNode *p = L->next;while (p->next != L){L = L->next;free(p);p = L->next;}free(L);
}
// 清空循环链表
void Clear_List(LinkList &L)
{LNode *p;while (L->next != L){p = L->next;L->next = p->next;free(p);}
}
// 求循环链表的表长
int Caculate_Length(LinkList L)
{int len = 0;LNode *p = L;while (p->next != L){len ++;p = p->next;}return len;
}
// 取值-取循环链表中第idx个元素的内容
bool GetElement(LinkList L, Data &e, int idx)
{int len = 0;LNode *p = L;while (p->next != L){len ++;p = p->next;if (len == idx){e = p->data;return true;}}return false;
}
// 按值查找-根据数据获取该数据所在位置
int GetIdx(LinkList L, Data &element)
{int len = 0;LNode *p = L;while (p->next != L){len ++;p = p->next;if (p->data.e == element.e){return len;}}return -1;
}
// 循环链表的插入-在第i个元素之前插入
bool Insert(LinkList &L, int idx, Data element)
{int len = 0;LNode *p = L;while (p->next != L){if (len == idx - 1){LNode *q = (LNode*)malloc(sizeof(LNode));q->data = element;q->next = p->next;p->next = q;return true;}len ++;p = p->next;}return false;
}
// 删除-删除第idx个元素
bool Delete(LinkList &L, int idx)
{int len = 0;LNode *p = L;while (p->next != L){len ++;p = p->next;if (len == idx - 1){LNode *q = p->next;p->next = q->next;free(q);return true;}}return false;
}// 头插法
bool Insert_Head(LinkList &L, Data element)
{LNode *p = (LNode*)malloc(sizeof(LNode));p->data = element;p->next = L->next;L->next = p;return true;
}// 尾插法
bool Insert_Tail(LinkList &L, Data element)
{LNode *p = L;while (p->next != L){p = p->next;}LNode *q = (LNode*)malloc(sizeof(LNode));q->data = element;q->next = p->next;p->next = q;return true;
}
// 输出循环链表
void Print_List(LinkList &L)
{for (LNode* p = L->next; p != L; p = p->next){printf("%d ", p->data.e);}printf("\n");
}

带尾指针的：

// 循环链表的初始化
bool InitList_R(LinkList &R) 
{R->next = R;return true;
}
// 判断循环链表是否为空
bool IsEmpty_List(LinkList R)
{if (R->next == R) return true;return false;
}
// 循环链表的销毁
void Destroy_List(LinkList &R)
{LNode *p;while (R->next != R){p = R->next;R->next = p->next;free(p);}free(R);
}
// 清空循环链表
void Clear_List(LinkList &R)
{LNode *p;while (R->next != R){p = R->next;R->next = p->next;free(p);}
}
// 求循环链表的表长
int Caculate_Length(LinkList R)
{LNode *p = R;int len = 0;while (p->next != R){len ++;p = p->next;}return len;
}
// 取值-取循环链表中第idx个元素的内容
bool GetElement(LinkList R, Data &e, int idx)
{int len = 0;LNode *p = R;while (p->next != R){len ++;p = p->next;if (len == idx){e = p->data;return true;}}return false;	
}
// 按值查找-根据数据获取该数据所在位置
int GetIdx(LinkList R, Data &element)
{int len = 0;LNode *p = R;while (p->next != R){len ++;p = p->next;if (p->data.e == element.e){return len;}}return -1;
}	
// 循环链表的插入-在第i个元素之前插入
bool Insert(LinkList &R, int idx, Data element)
{int len = 0;LNode *p = R;while (p->next != R){if (len == idx - 1){LNode *q = (LNode*)malloc(sizeof(LNode));q->data = element;q->next = p->next;p->next = q;return true;}len ++;p = p->next;}return false;	
}
// 删除-删除第idx个元素
bool Delete(LinkList &R, int idx)
{int len = 0;LNode *p = R;while (p->next != R){len ++;p = p->next;if (len == idx - 1){LNode *q = p->next;p->next = q->next;free(q);return true;}}return false;	
}// 头插法
bool Insert_Head(LinkList &R, Data element)
{LNode *p = (LNode*)malloc(sizeof(LNode));p->data = element;p->next = R->next;R->next = p;return true;
}// 尾插法
bool Insert_Tail(LinkList &R, Data element)
{LNode *p = R;while (p->next != R){p = p->next;}LNode *q = (LNode*)malloc(sizeof(LNode));q->data = element;q->next = R;p->next = q;return true;
}
// 输出循环链表
void Print_List(LinkList &R)
{for (LNode* p = R->next; p != R; p = p->next){printf("%d ", p->data.e);}printf("\n");
}

双链表

数组模拟双链表：数组模拟双链表文章浏览阅读92次。数组模拟双链表_;.ir=k,8https://blog.csdn.net/m0_73569492/article/details/128704895?ops_request_misc=%257B%2522request%255Fid%2522%253A%25221c13d05d054d65bc8bd9b7e25466efa9%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=1c13d05d054d65bc8bd9b7e25466efa9&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128704895-null-null.nonecase&utm_term=%E5%8F%8C%E9%93%BE%E8%A1%A8&spm=1018.2226.3001.4450

链表定义

typedef struct {int e;
} Data;typedef struct Lnode {struct Lnode *pre; // 指向前驱结点Data data; // 结点的数据域struct Lnode *next; // 指向后继结点
} LNode, *LinkList; // 定义了两种类型：LNode 为结构体类型；LinkList 为指向该结构体类型的指针类型。

链表操作

// 双链表的初始化
bool InitList_L(LinkList &L) 
{L = (LinkList)malloc(sizeof(LNode));L->pre = NULL;L->next = NULL;return true;
}
// 判断链表是否为空
bool IsEmpty_List(LinkList L)
{if (L->next == NULL) return true;return false;
}
// 双链表的销毁
void Destroy_List(LinkList &L)
{LNode *p;while (L){p = L;L = L->next;free(p);}	
}
// 清空双链表
void Clear_List(LinkList &L)
{LNode *p;while (L->next != NULL) {p = L->next;L->next = p->next;free(p);}	
}
// 求双链表的表长
int Caculate_Length(LinkList L)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next)cnt ++;return cnt;
}
// 取值-取双链表中第idx个元素的内容
bool GetElement(LinkList L, Data &e, int idx)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next){cnt ++;if (cnt == idx) {e = p->data;return true;}	}return false;
}
// 按值查找-根据数据获取该数据所在位置
int GetIdx(LinkList L, Data &element)
{int cnt = 0;for (LNode* p = L->next; p != NULL; p = p->next){cnt ++;if (p->data.e == element.e) return cnt; }return -1;	
}
// 双链表的插入-在第i个元素之前插入
bool Insert(LinkList &L, int idx, Data element)
{int cnt = 0;for (LNode* p = L; p->next != NULL; p = p->next){if (cnt == idx - 1){LNode *e = (LNode*)malloc(sizeof(LNode));e->data = element;e->next = p->next;e->pre = p;p->next->pre = e;p->next = e;}cnt ++;}	return false;	
}
// 删除-删除第idx个元素
bool Delete(LinkList &L, int idx)
{int cnt = 0;for (LNode* p = L; p != NULL; p = p->next){if (cnt == idx - 1){LNode *q = p->next;if (!q->next) {p->next = NULL;free(q);return true; 	}p->next = q->next;q->next->pre = p;free(q);return true;}cnt ++;}return false;	
}// 头插法
bool Insert_Head(LinkList &L, Data element)
{LNode *p = (LNode*)malloc(sizeof(LNode));p->data = element;if (L->next) {p->pre = L;p->next = L->next;L->next->pre = p;L->next = p;}else{L->next = p;p->pre = L;p->next = NULL;}return true;
}// 尾插法
bool Insert_Tail(LinkList &L, Data element)
{LNode *p = L;while (p->next != NULL){p = p->next;}// 在p后面插入curLNode *cur = (LNode*)malloc(sizeof(LNode));cur->data = element;if (p->next){cur->pre = p;cur->next = p->next;p->next->pre = cur;p->next = cur;}else{p->next = cur;cur->pre = p;cur->next = NULL;}return true;
}
// 输出链表
void Print_List(LinkList &L)
{for (LNode* p = L->next; p != NULL; p = p->next){printf("%d ", p->data.e);}printf("\n");	
}

---