1、线性表的定义和操作
1.1 线性表的基本概念
线性表的定义：
- 线性结构是简单而且常用的数据结构 ，而线性表则是一种典型的线性结构。
- 存储数据，最简单，最有效的方法是把它们存储在一个线性表中。
- 一个线性表是n个元素的有限序列。每个元素在不同的情况下有不同的含义，可以是整数，也可以是字符。
- 线性表：是具有相同数据类型的 n 个数据元素的有限序列。
线性表的特点：
- 存在唯一的第一个元素
- 存在惟一的最后一个元素
- 除第一个元素外，每一个元素只有一个直接前驱
- 除最后一个元素外，每一个元素均只有一个直接后继
线性表的存储结构：
- 顺序存储结构：顺序表
- 链式存储结构：链表
操作数据结构的思路：创销、增删改查
2、顺序表
2.1 顺序表的基本概念
1、定义：
- 就是把线性表中的所有元素按照其逻辑顺序依次存储到指定位置开始的一块连续的存储区域。
- 线性表中的第1个元素的存储位置就是指定的存储位置，第i个元素的存储位置紧接第i-1个元素的存储位置的后面。
2、顺序表的特点：
- 在顺序表中，各元素的逻辑顺序跟物理顺序一致，第i项就存在第i个位置。
- 对顺序表中的所有元素，既可以顺序访问，也可以随机访问。
- 插入删除操作不方便，需要移动大量元素
3、操作数据结构的思路：创销、增删改查
2.2 顺序表的实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LISTCOUNT 100
/*数据结构的相关概念：
//1、数据结构：是计算机存储数据、管理数据的方式
//2、数据结构主要研究的是数据的逻辑结构 和 存储结构
//3、数据的逻辑结构主要有4种：
(1)集合 元素之间没有任何关联
(2)线性结构 元素之间存在一对一的关系
(3)树型结构 元素之间存在一对多的关系(重点研究1对2)
(4)图型结构 元素之间存在多对多的关系
4、数据的物理结构也有4种:
(1)顺序存储
(2)链式存储
(3)索引存储
(4)散列存储
5、线性表 用来存储n个数据类型相同的数据有限序列
6、线性表的逻辑结构：线性结构
7、线性表的物理结构重点说2种
(1)顺序存储 顺序表
(2)链式存储 链式表
8、顺序表的特点：
0、元素是连续存储
1、线性结构，存在一对一关系
2、只有唯一的首元素，只有唯一尾元素
3、除第一个元素外，每一个元素只有一个直接前驱
4、除最后一个元素外，每一个元素均只有一个直接后继
9、顺序表的常用操作：创建、销毁、增删改查
10、顺序表的创建方式：通过数组创建 通过指针创建
*/
typedef int elementType;
//定义顺序表结构体类型
typedef struct Order_List
{
elementType data[MAX_LISTCOUNT];//数组存储顺序表的元素
int length;//顺序表的元素个数
}OrderList;
//函数声明
void print_menu(void); //
OrderList* init_List(void);
void append_list(OrderList* List, int val);
void show_all(OrderList* List);
void insert_List(OrderList* List, int index, int val);
void delete_List(OrderList* List, int index);
void edit_List(OrderList* List, int index, int val);
void destroy_List(OrderList* List);
int main()
{
print_menu();
int order = 0;//存储操作指令
int val = 0;
int index = 0;
//创建线性表指针 指向线性表
OrderList* List = NULL;
while (1)
{
printf("请输入你的操作指令:");
scanf("%d", &order);
switch (order)
{
case 1:
//创建一个空表
List = init_List();
break;
case 2:
//打印
show_all(List);
break;
case 3:
//追加
printf("请输入要追加的数据:");
scanf("%d", &val);
append_list(List, val);
break;
case 4:
//插入 从0开始
printf("请输入插入的位置(索引):");
scanf("%d", &index);
printf("请输入要插入的元素:");
scanf("%d", &val);
insert_List(List, index, val);
break;
case 5:
//删除
printf("请输入要删除的元素位置(索引):");
scanf("%d", &index);
delete_List(List, index);
break;
case 6:
//修改
printf("您要修改的元素的索引:");
scanf("%d", &index);
printf("您要修改后的值：");
scanf("%d", &val);
edit_List(List, index, val);
break;
case 7:
//销毁
destroy_List(&List);
break;
case 8:
//退出
return 0;
default:
printf("指令有误，重新输入!!!\n");
}
}
return 0;
}
//1、打印提示信息
void print_menu(void)
{
system("cls");// 系统函数 用于屏幕清空
printf("操作指令说明:\n");
printf("1:创建顺序表\n2:打印顺序表\n");
printf("3:追加一个节点\n4:插入一个节点\n");
printf("5:删除一个节点\n6:修改顺序表元素\n");
printf("7:销毁顺序表\n8:退出\n ");
}
//2、初始化空的 顺序表
OrderList* init_List(void)
{
OrderList* List = (OrderList *)malloc( sizeof(OrderList) );
if (List == NULL)
{
printf("内存申请失败 创建失败!!!\n");
return NULL;
}
//申请成功 清0
memset(List, 0, sizeof(OrderList));
printf("创建成功!!!\n");
return List;
}
//2、追加元素 尾部添加
void append_list(OrderList* List, int val)
{
if (!List)
{
printf("请先创建顺序表!!!\n");
return;
}
else if (List->length >= MAX_LISTCOUNT)
{
printf("顺序表已满!!!\n");
return;
}
else
{
//尾部追加
List->data[List->length] = val;
List->length++;
printf("追加成功!!!\n");
}
}
//3、打印顺序表
void show_all(OrderList* List)
{
if (!List)
{
printf("请先创建顺序表!!!\n");
return;
}
else if(List->length == 0 )
{
printf("空表 不要打印!!!\n");
return;
}
else {
for (int i = 0; i < List->length; i++)
{
printf("%d ", List->data[i]);
}
printf("\n");
}
}
//插入元素
void insert_List(OrderList* List, int index, int val)
{
if (!List)
{
printf("请先创建顺序表!!!\n");
return;
}
else if (List->length >= MAX_LISTCOUNT)
{
printf("顺序表已满!!!\n");
return;
}
else if (index < 0 || index > List->length-1)
{
printf("插入位置不合法！！！\n");
return;
}
else {
//插入操作 倒序遍历 位置后移
for (int i = List->length - 1; i >= index; i--)
{
List->data[i + 1] = List->data[i];
}
List->data[index] = val;
List->length++; //顺序表长度+1
printf("插入成功\n");
}
}
//4、删除
void delete_List(OrderList* List, int index)
{
if (!List)
{
printf("请先创建顺序表!!!\n");
return;
}
else if (index <0 || index > List->length - 1)
{
printf("位置不合法!!!\n");
return;
}
else {
//位置前移
for (int i = index; i < List->length; i++)
{
List->data[i] = List->data[i + 1];
}
List->length--;
printf("删除成功!!!\n");
}
}
//5、修改
void edit_List(OrderList* List, int index, int val)
{
if (!List)
{
printf("请先创建顺序表!!!\n");
return;
}
else if (index <0 || index > List->length - 1)
{
printf("位置不合法!!!\n");
return;
}
else {
List->data[index] = val;
printf("修改成功!!!\n");
}
}
//6、销毁
void destroy_List(OrderList** List)
{
free(*List);//销毁
*List = NULL; //置空
//printf("%p\n", *List);
}顺序表和数组的区别：
1、顺序表是在计算机内存中以数组的形式保存的一种线性表，可以用数组实现顺序表。
2、数组和顺序表都是在一段连续的内存空间，存储多个类型相同的数据
3、数组的长度不可变，顺序表的长度是可变的。可进行增删改查
顺序表的指针实现方式
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_MAX_COUNT 100
//用指针定义数组
typedef int elementType;
typedef struct List {
elementType* element; // 元素类型指针
int length; //元素个数
}OrderList;
void print_menu(void);
void Init_List(OrderList* List);
void append_List(OrderList* List, int val);
void show_all(OrderList List);
void insert_List(OrderList* List, int index, int val);
void delete_List(OrderList* List, int index);
void edit_List(OrderList* List, int index, int val);
void destroy_List(OrderList* List);
int main()
{
int order = 0;//操作指令
int val = 0;
int index = 0;
OrderList List = {NULL,0}; //创建一个结构体变量
print_menu();
while (1)
{
printf("请输入你的操作指令:");
scanf("%d", &order);
switch (order)
{
case 1:
//创建一个空表 初始化一个顺序表
Init_List(&List);
break;
case 2:
//打印
show_all(List);
break;
case 3:
//追加
printf("请输入要追加的元素:");
scanf("%d", &val);
append_List(&List, val);
break;
case 4:
//插入
printf("请输入要插入的元素:");
scanf("%d", &val);
printf("请输入要插入的位置：");
scanf("%d", &index);
insert_List(&List, index, val);
break;
case 5:
//删除
printf("请输入要删除的元素位置:");
scanf("%d", &index);
delete_List(&List, index);
break;
case 6:
//修改
printf("请输入要修改的位置：");
scanf("%d", &index);
printf("请输入修改后的元素:");
scanf("%d", &val);
edit_List(&List, index, val);
break;
case 7:
//销毁
destroy_List(&List);
break;
case 8:
//退出
return 0;
default:
printf("指令有误，重新输入!!!\n");
}
}
}
//1、打印提示信息
void print_menu(void)
{
system("cls");// 系统函数 用于屏幕清空
printf("操作指令说明:\n");
printf("1:创建顺序表\n2:打印顺序表\n");
printf("3:追加一个节点\n4:插入一个节点\n");
printf("5:删除一个节点\n6:修改顺序表元素\n");
printf("7:销毁顺序表\n8:退出\n ");
}
//2、顺序表初始化 一个空表
void Init_List(OrderList* List)
{
List->element = (elementType *) malloc(sizeof(elementType) * LIST_MAX_COUNT);
if (!List->element) {
printf("内存申请失败！ 初始化失败!!!\n");
return;
}
//清0操作
memset(List->element, 0, sizeof(elementType) * LIST_MAX_COUNT);
List->length = 0;
printf("初始化成功!!!\n");
}
//3、追加
void append_List(OrderList* List, int val)
{
if (List->element == NULL)
{
printf("请先建表!!1\n");
return;
}
else if (List->length >= LIST_MAX_COUNT)
{
printf("表已满，无法追加!!!\n");
return;
}
*(List->element + List->length) = val;
List->length++;
printf("追加成功\n");
}
//4、打印输出
void show_all(OrderList List)
{
if (List.element == NULL)
{
printf("请先建表!!!\n");
return;
}
else if (List.length == 0)
{
printf("表空，无法打印!!!\n");
return;
}
for (int i = 0; i < List.length; i++)
{
printf("%d ", *(List.element + i));
}
printf("\n");
}
//5、插入
void insert_List(OrderList* List, int index, int val)
{
if (List->element == NULL)
{
printf("请先建表!!1\n");
return;
}
else if (List->length >= LIST_MAX_COUNT)
{
printf("表已满，无法插入!!!\n");
return;
}
else if (index <0 || index > List->length - 1)
{
printf("插入的位置不合法!!!\n");
return;
}
//倒序遍历 位置后移
for (int i = List->length - 1; i >= index; i--)
{
*(List->element + i + 1) = *(List->element + i);
}
*(List->element + index) = val;
List->length++;
printf("插入成功!!!\n");
}
//6、删除
void delete_List(OrderList* List, int index)
{
if (List->element == NULL)
{
printf("请先建表!!1\n");
return;
}
else if (List->length == 0)
{
printf("空表 无法删除!!!\n");
return;
}
else if (index < 0 || index > List->length - 1)
{
printf("你要删除的元素不存在!!!\n");
return;
}
//删除 从index元素开始 位置前移
/*
1 3 5 7 9
*/
for (int i = index; i <= List->length - 1; i++)
{
*(List->element + i) = *(List->element + i + 1);
}
List->length--;
printf("删除成功!!!\n");
}
//7、修改
void edit_List(OrderList* List, int index, int val)
{
//省略几行代码
*(List->element + index) = val;
printf("修改成功!!!\n");
}
//8、
void destroy_List(OrderList* List)
{
free(List->element);//空间释放
List->element = NULL;
}3、链表
3.1 链表的介绍
定义：
链表是一种链式存储的线性表。
链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。链表的特点是可以动态添加和删除节点，而不需要预先知道数据的数量。与数组不同，链表中的节点不一定是连续的存储空间，因此可以有效地利用内存空间。
特点：
优点：不要求大片连续空间，改变容量方便。
可以动态的添加和删除节点
缺点：不方便可随机存取，要耗费一定空间存放指针。
3.2 链表的分类
链表可以分为三种类型：
- 单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。
- 双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。
- 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。
链表的种类其实有很多种，按照单双向、带头不带头、循环不循环，一共可以分为8种类型，但最常见就是单向链表和双向链表
3、链表的操作
链表的操作包括插入、删除、查找、遍历等。
- 插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。
- 删除操作：可以删除指定节点或按照值删除节点。
- 查找操作：可以查找指定节点或按照值查找节点。
- 遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作
链表在计算机科学中有广泛的应用，例如操作系统中的进程链表、文件系统中的目录链表、图论中的邻接表等。在C语言中，链表常常用于实现动态内存分配、函数调用栈、多项式运算等问题。
4、单向链表
单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
单链表的一个存储节点包含两部分：
data部分称为数据域，用于存储线性表的一个数据元素；
link部分称为指针域，用于存放一个指针，该指针指示链表下一个结点的开始存储地址
单链表的第一个结点也称为首结点，它的地址可以通过链表的头指针head找到，其他结点的地址通过前驱结点的link域名找到，链表的最后一个结点没有后继，则在link域放一个空指针NULL，图中用“^”表示
5、单链表的操作
5.1 创建链表结构体
创建结构体，其中有两个成员，一个用来存储数据，一个用来指向下一个空间
//1、定义链表的结构体类型
typedef struct ListNode {
int val;
struct ListNode* next;
}ListNode;
5.2 动态申请一个节点，初始化链表
申请节点我们用malloc函数，申请成功后返回空间地址，需要注意此时未和其他节点链接
注意：使用malloc函数，需要引入头文件 stdlib.h
//2、初始化一个链表节点
ListNode* CreateNode(int val) {
//分配一段内存
ListNode* ptr = (ListNode*)malloc(sizeof(ListNode));
if (ptr == NULL) {
printf("内存分配失败");
exit(-1);//终止程序退出 参数为0代表正常退出，非0代表异常退出
}
ListNode* List = ptr;
List->val = val;
List->next = NULL;
return List;
}5.3 链表打印，即遍历链表数据
先写打印函数，方便后续做测试
//3、打印输出链表 遍历链表
void printList(ListNode* List) {
ListNode* tail = List;
//while(1) {
// //非空
// printf("%d\n", tail->val);
// if (tail->next == NULL) {
// break;
// }
// tail = tail->next;
//}
//换一种写法：
while (tail) {
printf("%d,", tail->val);
tail = tail->next;
}
printf("NULL\n");
}5.4 链表头插
头插时要注意：
1、如果a链表中没有节点，我们要更新头结点。(本文给的例子没有体现）
2、核心：创建一个新节点，指向原先的头部，然后返回新的头部即可
5.5 链表尾插
链表尾插时要注意：
1、先创建一个空节点，
2、遍历找到原链表的尾节点，将原链表的尾节点的next指向新节点，即可
先判断链表是否为空，为空则直接为其创建一个节点即可，不为空则需要遍历到最后一个节点进行插入。
5.6 链表头删
当链表为空是直接返回空即可。
否则改变头节点的地址，将头指针指向第二个节点，同时释放原头结点内存，以防内存泄漏
5.7 链表尾删
链表的尾删就是将链表的最后一个节点删除。在实现这个功能时，我们应该考虑链表中的节点个数，当只有一个节点时。我们直接将该节点free掉，在将他置空。
否则，释放掉尾节点，新的尾节点的next应该指向空。
5.8 链表的查找
单链表查找主要是为了后面的中间插入删除，需要先找到要删的位置，遍历一遍链表就可以
返回的是要查找的元素地址
5.9 链表的中间插
由于单链表只能从前往后走，而想要从中间位置插入或者删除数据，则需要改变前一个结构体的指针，所以只能插入或者删除指定位置后面的数据。
5.10 单链表的中间删
5.11 单链表的销毁
遍历一遍，一个一个释放即可
附：完整可调试代码：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
//链表：
//单向链表
//节点有2部分组成： 数据域 地址域
//单链表的常用操作：创、销、增、删、改、查
//单向 无头 不循环链表
typedef int elementType;
//定义链表的结构体类型
typedef struct Link_List {
elementType val; //数据域 存放链表元素
struct Link_List* next;//指针域 指向下一个节点的地址
}LinkListNode;
void print_menu(void);
LinkListNode* Init_LinkList(elementType val);
void print_List(LinkListNode* Node);
void Head_Insert(LinkListNode** Node, elementType newval);
void Tail_Insert(LinkListNode* Node, elementType newval);
void Head_Delete(LinkListNode** Node);
void Tail_delete(LinkListNode* Node);
LinkListNode* Find_List(LinkListNode* Node, elementType val);
void midlle_delete(LinkListNode* itemptr);
void middle_insert(LinkListNode* itemptr, elementType newval);
void destroy_List(LinkListNode** Node);
LinkListNode* createNode(void);
int main()
{
print_menu();
LinkListNode* LinkNode = NULL; //头结点指针
int order = 0;
elementType val = 0;
LinkListNode* itemptr = NULL;
while (1)
{
printf("请输入您的操作指令:");
scanf("%d", &order);
switch (order)
{
case 1:
//链表初始化
printf("请输入头结点元素值:");
scanf("%d", &val);
LinkNode = Init_LinkList(val);
break;
case 2:
//打印
print_List(LinkNode);
break;
case 3:
//头插
printf("请输入头插结点元素值:");
scanf("%d", &val);
Head_Insert(&LinkNode, val);
break;
case 4:
//尾插(追加)
printf("请输入头插结点元素值:");
scanf("%d", &val);
Tail_Insert(LinkNode, val);
break;
case 5:
//头删
Head_Delete(&LinkNode);
break;
case 6:
//尾删
Tail_delete(LinkNode);
break;
case 7:
//查找
printf("请输入要查找的结点元素值:");
scanf("%d", &val);
找到了返回该元素的位置，找不到返回NULL
//Find_List(LinkNode, val) ? printf("11111") : printf("00000000");
LinkListNode* temp = Find_List(LinkNode, val);
printf("%d ", temp->val);
break;
case 8:
//中间删 已知删除元素的前一个元素的位置
printf("请输入您要删除的元素的前一个元素值:");
scanf("%d", &val);
itemptr = Find_List(LinkNode, val);
if (itemptr == NULL)
{
printf("没有此元素 无法删除!!!\n");
}
else
{
midlle_delete(itemptr);
}
break;
case 9:
//中间插
printf("您要在那个元素的后边插入:");
scanf("%d", &val);
printf("您要插入的新元素是：");
elementType newval = 0;
scanf("%d", &newval);
itemptr = Find_List(LinkNode, val);
assert(itemptr);
middle_insert(itemptr,newval);
break;
case 10:
//销毁
//思路：遍历所有节点，一个一个释放，然后修改头节点为NULL
destroy_List(&LinkNode);
break;
case 11:
//退出
return;
default:
printf("指令有误重新输入");
}
}
return 0;
}
void print_menu(void)
{
system("cls");//屏幕清空
printf("操作指令说明:\n");
printf("1:链表初始化\n2:打印链表\n");
printf("3:链表头插\n4:链表尾插\n");
printf("5:链表头删\n6:链表尾删\n");
printf("7:链表的查找\n8:链表的中间删\n");
printf("9:链表的中间插\n10:链表销毁\n");
printf("11:退出\n");
}
//初始化链表
LinkListNode* Init_LinkList(elementType val)
{
LinkListNode* Node = (LinkListNode *)malloc(sizeof(LinkListNode));
//if (Node == NULL)
//{
// printf("申请失败 初始化失败!!!\n");
// return NULL;
// //exit(-1);
//}
//assert() 常于于代码调试 ，如果条件为真，正常执行，条件为假，程序报错
//exit() 用于终止程序执行,一般输出0代表正常退出 非0异常退出
assert(Node);
Node->val = val;
Node->next = NULL;
printf("初始化成功!!!\n");
return Node;
}
//打印链表
void print_List(LinkListNode* Node)
{
assert(Node);
LinkListNode* ptr = Node;
while (1)
{
printf("%d ", ptr->val);
if (ptr->next == NULL) //最后一个节点
{
break;
}
ptr = ptr->next;
}
printf("\n");
}
//头插
void Head_Insert(LinkListNode** Node, elementType newval)
{
assert(*Node); //判断 是否是空表
//创建新节点
//LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
//assert(newNode); //判断内存是否申请失败
LinkListNode* newNode = createNode();
newNode->val = newval;
newNode->next = *Node;//新节点的next指向原来的头结点
*Node = newNode;//更新头节点
printf("头插成功!!!\n");
}
//尾插
void Tail_Insert(LinkListNode* Node, elementType newval)
{
assert(Node);
//创建新节点
//LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
//assert(newNode); //判断内存是否申请失败
LinkListNode* newNode = createNode();
newNode->val = newval;
newNode->next = NULL; //
//遍历找到尾节点
LinkListNode* ptr = Node;
while (1)
{
if (ptr->next == NULL) //尾节点
{
ptr->next = newNode;//把原来的尾节点指向新节点
break;
}
else
{
ptr = ptr->next;
}
}
printf("尾插成功!!!\n");
}
//头删
void Head_Delete(LinkListNode** Node) {
LinkListNode* ptr = *Node;
*Node = ptr->next;//更新头结点
free(ptr);//释放原来的头结点
printf("头删成功!!!\n");
}
//尾删
void Tail_delete(LinkListNode* Node)
{
assert(Node);
//遍历找到倒数第2个节点，更新尾节点 并释放原来的尾节点
LinkListNode* ptr = Node;
while(ptr->next->next != NULL)
{
ptr = ptr->next;
}
free(ptr->next); //释放最后一个节点
ptr->next = NULL; //更新尾节点
printf("尾删成功!!!\n");
}
//查找
LinkListNode* Find_List(LinkListNode* Node, elementType val)
{
assert(Node);
LinkListNode* ptr = Node;
//遍历查找
while (ptr)
{
if (ptr->val == val) //找到了
{
return ptr; //返回节点地址
}
else
{
ptr = ptr->next;
}
}
return NULL;
}
//中间删
void midlle_delete(LinkListNode* itemptr)
{
LinkListNode* ptr = itemptr->next->next;
free(itemptr->next);
itemptr->next = ptr;
printf("中间删除成功!!!\n");
}
//中间插
void middle_insert(LinkListNode* itemptr, elementType newval)
{
//创建新节点
LinkListNode* newNode = createNode();
newNode->val = newval;
//将新节点插入
newNode->next = itemptr->next;
itemptr->next = newNode;
printf("插入成功\n");
}
//销毁
void destroy_List(LinkListNode** Node)
{
assert(*Node);
while (*Node) {
LinkListNode* ptr = (*Node)->next; //保存下一节点
free(*Node);
*Node = ptr;
}
*Node = NULL;
printf("销毁成功!!\n");
}
//创建新节点
LinkListNode* createNode(void)
{
LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
//assert(newNode);
if (newNode == NULL)
{
printf("内存申请失败");
return NULL;
}
//清零
memset(newNode, 0, sizeof(LinkListNode));
return newNode;
}
/*
1、链表的单向和双向的区别
2、带头不带头的区别
3、循环不循环的区别
*/6、双向链表
双链表也是链表的一种，双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点。
双向，带头，循环。以上几种特性可以随机结合，生成一种链表。链表种类有很多，这里重点讲一下双向带头循环链表
6.1 双向带头循环链表
带头双向循环链表是链表中带头（哨兵位）、双向、循环三种属性的结合体；
带头即带哨兵位，哨兵位只负责存储第一个具有有效数据的节点，本身不存放数据，该处因为为双向循环链表，代表也可访问该链表的尾节点；
双向即表示，每个节点不仅能访问该节点的后一个节点，同时也可访问本节点的前一个节点；
循环即表示，第一个节点的prev指向尾节点；
带头双向循环链表虽然在结构中是所有链表中最为复杂的，但是相比较于单链表的优势在于不需要多次对链表为空进行判断，避免了边界问题；
同时如单链表所言，单链表在进行每次尾删或者尾插时，都需要遍历到尾节点且保存尾节点的前一个节点，而对于双向链表而言，只需要访问头节点的prev即可；
总而言之，双向带头循环链表而言，虽然在结构上要比单链表复杂的多，但是在操作上确是比单链表而言简单；
6.2 双向带头循环链表的操作
6.2.1 双向带头循环列表的 结构体声明
因该链表属于双向循环链表，故需要两个指针，一个指针指向下一个节点，一个指针指向上一个节点
6.2.2 头结点的创建 链表的初始化
- 链表为带头双向循环练表，因为存在哨兵位，所以在插入数据之前应给链表安排一个哨兵位，并对哨兵位进行初始化
- 在对哨兵位进行初始化时同时也要注意该链表的结构为双向循环链表，在只有哨兵位的情况下，哨兵位的next与prev都指向自己；
6.2.3 链表的打印
遍历链表节点，依次打印出来即可
6.2.4 头插
因为该链表存在哨兵位，故在进行头插时需要插入至头节点（哨兵位）之后
6.2.5 尾插
若是在单链表中，尾插需要遍历整个链表找到尾节点，而在该链表中，因为链表头节点（哨兵位）所指向的prev即为尾节点；
故在该链表进行尾插时，只需访问哨兵位的prev所指向的节点；
6.2.6 头删
同样的带头双向循环链表在进行头删时只需要删除头节点（哨兵位）后的节点即可；
6.2.7 尾删
在双链表中，链表的尾删只需释放头节点head内prev所指向的节点（尾节点）即可；
6.2.8 链表元素的查找
双链表的查找，利用while循环对链表进行遍历，循环条件为当指针指向不为哨兵位；
若为哨兵位，则代表链表已经遍历了一次，若是找到对应val的值，则返回节点的地址，否则返回空指针；
6.2.9 链表节点的修改
参数给定节点的地址，通过地址访问该节点所对应的val并对其进行修改；
6.2.10 链表的中间插入
相比较单链表来说，双向链表可以访问所给pos节点的后
一个节点，而单链表若是需要进行在pos节点前进行插入则各项消耗都会增大；
参数给定一个pos指针，指针指向为需要插入的节点位置，将新的数据（节点）插入pos所指向节点的prev所指向的位置；
6.2.11 链表的中间删除
链表的中间删除则不需要再进行pos之后或者pos之前，双向链表既可以访问pos节点的next，又可访问pos节点的prev；
即在进行中间删除时，可以直接将pos节点进行删除；
6.2.12 链表的销毁
当使用完空间并不需要再使用时，应及时将空间进行释放，避免出现内存泄漏等问题，在顺序表中，可直接将malloc后的空间进行释放，因为在物理因素上，顺序表为一块连续不断的空间；
而链表则只在逻辑上具有连续不断的属性，在物理上本质是一块一块不同位置的空间；
双链表的销毁也与单链表的销毁逻辑相同；
6.2.13 附：可调试完整代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
//双向、带头、循环链表
//双向链表节点组成：1个数据域 2个指针域
typedef int elementType;
//定义双链表结构体类型
typedef struct Link_List_Node
{
struct Link_List_Node* pre;
elementType val;
struct Link_List_Node* next;
}LinkNode;
void print_menu(void);
LinkNode* Init_List(void);
void print_List(LinkNode* List);
LinkNode* createNode(void);
void head_insert(LinkNode* List, elementType val);
void tail_insert(LinkNode* List, elementType val);
void head_delete(LinkNode* List);
void tail_delete(LinkNode* List);
LinkNode* find_list(LinkNode* List, elementType val);
void middle_delete(LinkNode* delptr);
//void DestroyList(LinkNode** List);
void edit(LinkNode* List, elementType val);
void middle_insert(LinkNode* List, elementType val, elementType newval);
void edit_list(LinkNode* List, elementType val, elementType newval);
void destroy(LinkNode** List);
int main()
{
print_menu();
int order = 0;//操作指令
int val = 0;
int newval = 0;
LinkNode* List = NULL; //用来存储哨兵为(头)
while (1)
{
printf("请输入你要操作的指令号:");
scanf("%d", &order);
switch (order)
{
case 1:
//链表初始化
List = Init_List();
break;
case 2:
//打印
print_List(List);
break;
case 3:
//头插
printf("请输入要插的元素:");
scanf("%d", &val);
head_insert(List, val);
break;
case 4:
//尾插(追加)
printf("请输入要插的元素:");
scanf("%d", &val);
tail_insert(List, val);
break;
case 5:
//头删
head_delete(List);
break;
case 6:
//尾删
tail_delete(List);
break;
case 7:
//查找
//思路：找到返节点地址 找不到返回NULL
printf("请输入要查询的元素:");
scanf("%d", &val);
//find_list(List, val) ? printf("查到了") : printf("没查到");
LinkNode* p = find_list(List, val);
if (p)
{
printf("查到的元素是：%d", p->val);
}
break;
case 8:
//中间删 删除指定元素
//思路：找到指定元素的地址 并删除
printf("请输入要删除的元素:");
scanf("%d", &val);
LinkNode* delptr = find_list(List, val);
if (!delptr)
{
printf("您要删除的元素不存在\n");
}
else
{
//进行删除操作
middle_delete(delptr);
}
break;
case 9:
//中间插 在指定元素的后边进行插入操作
printf("你要在哪个元素的后面插");
scanf("%d", &val);
printf("请输入要插入的元素:");
scanf("%d", &newval);
middle_insert(List,val, newval);
break;
case 10:
//修改 把指定元素修改成指定新值
printf("你要修改的元素是");
scanf("%d", &val);
printf("请输入要修改后的新值:");
scanf("%d", &newval);
edit_list(List, val, newval);
break;
case 11:
//销毁
destroy(&List);
break;
case 12:
//退出
return;
default:
printf("指令有误重新输入");
}
}
return 0;
}
//打印菜单项
void print_menu(void)
{
system("cls");//屏幕清空
printf("操作指令说明:\n");
printf("1:链表初始化\n2:打印链表\n");
printf("3:链表头插\n4:链表尾插\n");
printf("5:链表头删\n6:链表尾删\n");
printf("7:链表的查找\n8:链表的中间删\n");
printf("9:链表的中间插\n10:链表元素修改\n");
printf("11:销毁\n");
printf("12:退出\n");
}
//链表初始化
LinkNode* Init_List(void)
{
/*LinkNode* List = (LinkNode*)malloc(sizeof(LinkNode));
if (List == NULL)
{
printf("内存申请失败!!!\n");
return NULL;
}
printf("初始化成功!!!\n");*/
//代码优化
LinkNode* List = createNode();
List->next = List;
List->pre = List;
printf("初始化成功!!\n");
return List;
}
//打印链表元素
void print_List(LinkNode* List)
{
assert(List);
LinkNode* temp = List->next;// 存储当前节点
while (temp != List)
{
printf("%d ", temp->val);
temp = temp->next; //后移
}
printf("\n");
}
//头插
void head_insert(LinkNode* List, elementType val)
{
assert(List);
//创建新节点
LinkNode* newNode = createNode();
newNode->val = val;
//插入新节点
newNode->next = List->next;
List->next->pre = newNode;
List->next = newNode;
newNode->pre = List;
printf("头插成功!!\n");
}
//创建新节点
LinkNode* createNode(void)
{
LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
if (newNode == NULL)
{
printf("内存申请失败，新建失败!!!\n");
return NULL;
}
//清零
memset(newNode, 0, sizeof(LinkNode));
return newNode;
}
//尾插
void tail_insert(LinkNode* List, elementType val)
{
//创建新节点
LinkNode* newNode = createNode();
newNode->val = val;
//尾插新节点
newNode->pre = List->pre;
List->pre->next = newNode;
newNode->next = List;
List->pre = newNode;
printf("尾插成功!!!\n");
}
//头删
void head_delete(LinkNode* List)
{
LinkNode* temp = List->next;//保存头结点
List->next = temp->next;
temp->next->pre = List;
free(temp);//释放头结点
printf("头删成功\n");
}
//尾删
void tail_delete(LinkNode* List)
{
LinkNode* temp = List->pre;//保存尾节点
List->pre = temp->pre;
temp->pre->next = List;
free(temp);//释放尾节点
printf("尾删成功!!\n");
}
//查询指定元素的，查到返回指定元素节点地址 查不到返回NULL
LinkNode* find_list(LinkNode* List, elementType val)
{
assert(List);
//遍历链表元素节点 对比是否是指定的元素
LinkNode* temp = List->next;//当前节点
while (temp != List)
{
if (temp->val == val)
{
return temp;
}
temp = temp->next;
}
return NULL;
}
//中间删
void middle_delete(LinkNode* delptr)
{
delptr->pre->next = delptr->next;
delptr->next->pre = delptr->pre;
free(delptr);
}
//中间插 在链表的指定元素后边插入新元素元素
//分析：先找到指定元素的位置 find_list
// 创建新节点 createNode
// 进行插入操作
void middle_insert(LinkNode* List, elementType val, elementType newval)
{
assert(List);
//先找到指定元素的位置
LinkNode* ptr = find_list(List, val);
if (!ptr)
{
printf("位置不存在，无法插入!!!\n");
return;
}
//创建新节点
LinkNode* newNode = createNode();
newNode->val = newval;
//进行插入操作
newNode->next = ptr->next;
ptr->next->pre = newNode;
newNode->pre = ptr;
ptr->next = newNode;
printf("插入成功!!!\n");
}
//修改 把链表中指定元素修改成指定新值
//分析： 找到链表中指定元素val的位置
// 修改操作
void edit_list(LinkNode* List, elementType val, elementType newval)
{
LinkNode *ptr = find_list(List, val);
if (!ptr)
{
printf("你要修改的元素不存在");
return;
}
ptr->val = newval;
printf("修改成功\n");
}
//销毁
// 思路： 遍历列表节点，一个一个释放，然后修改头的值为NULL
void destroy(LinkNode** List)
{
LinkNode* temp = (*List)->next;// 保存当前节点
while (temp != *List)
{
LinkNode* ptr = temp->next;
free(temp);
temp = ptr;
}
free(*List);//释放头
*List = NULL;
}
面试题：对比一下顺序表和链表有什么异同点
1、相同点：顺序表和链表都是线性表，用来存储数据类型相同的有限序列，逻辑结构都是线性结构，也就是元素之间是一对一的关系。
2、不同点：
（1）从存储方式：顺序表是按顺序存储，所占的内存空间是连续的，链表是按照链式存储，所占的内存不在乎是否连续。
（2）从使用特点上来讲：顺表可进行随机访问或按顺序访问，但是在进行插入和删除操作时，不太方便，需要移动大量元素
链表最大的优点是可以动态的进行添加和删除操作，但是，访问时，需要遍历，时间复杂度为O(n)。
（3)内存利用率：
顺序表在创建时直接分配固定的内存空间，当空间不够时，可以重新申请内存。
链表是创建一个节点就动态申请一个节点内存，几乎不会出现空间内存不够的情况。
相对来讲，顺序表的空间利用率较高高，因为链表节点除了要存储节点元素外，还要存储指针。