二、链表：
初识
链表基础知识：
什么是链表：
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
链表的类型：
单链表
双链表
单链表中的指针域只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
如图所示：
循环链表
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
链表的定义
链表的操作
链表性能分析
#include
#include
#include
#include
#define ElemType int
typedef struct ListNode
{
ElemType data;
struct ListNode* next;//指针域（自身类型的指针类型），保存的地址是节点的地址，所以我们给出的是自身节点类型的next指针，即1节点指向的地址是2节点，节点1和2的类型是完全一样的
}ListNode;
typedef ListNode* List;
void InitList(List* head)//head相当于是 ListNode **head(二级指针，因为List本身就是节点的指针类型)
{
//(*head) = NULL;//一旦初始化完成，就是一个空链表，内部都是随机信息
//增加头节点(*head)就不能为空了，而是要指向头节点
(*head) = (ListNode *)malloc(sizeof(ListNode));
//申请空间之后，一定要进行断言
assert(*head != NULL);
(*head)->next = NULL;
}
//有多种形式去创建链表
//[1].尾插法创建
void CreateList_back(List* head)
{
*head = (ListNode*)malloc(sizeof(ListNode));
//断言，判断头节点创建是否成功
assert(*head != NULL);
(*head)->data = 1;//由于指向->的优先级高于星号 * ，因此要使用()
(*head)->next = NULL;
ListNode* p = *head;
for (int i = 2; i <= 10; ++i)//头节点1已经创建过，因此从2开始
{
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
//断言，判断节点创建是否成功
assert(s != NULL);
s->data = i;
s->next = NULL;
p->next = s;//p的next指针指向s
p = s;//p指向下一个节点s
//1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->Nul.
}
}
//[2].头插法创建
//顺序表只需要下标就能找到元素，而对链表来说，要想找到下边的数据，就只能靠next指针
//如果指针指向1而不是3，要想从1找到2和3，是不可能的，要从3找到1，是可以的，但是也需要通过2，然后2通过next找到1
//因此，在头插中，一定要对头指针保护好
//每做一个节点的插入，head就要更改，以保证head永远指向的整个链表的第一个节点
/*
void CreateList_front(List* head)
{
*head = (ListNode*)malloc(sizeof(ListNode));
assert(&head != NULL);
(*head)->data = 1;
(*head)->next = NULL;
for (int i = 2; i <= 10; ++i)//头节点1已经创建过，因此从2开始
{
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
//断言，判断节点创建是否成功
assert(s != NULL);
s->data = i;
s->next = *head;
*head = s;//此时head不再指向1
//10-->9-->8-->7-->6-->5-->4-->3-->2-->1-->Nul.
}
}
*/
//头节点：在链表之前会增加一个多余的节点，这个节点有一个特性，它不保存数据，但它是提领整个链表的开始
//最主要的作用是，会使某些算法做一个统一的处理。
//现在结构是没有头节点的结构
//[3].使用头插法创建带头节点的链表
//此时head永远指向第一个节点
//链表想要安全性高，全靠头节点
/*
void CreateList_front(List* head)
{
for (int i = 1; i <= 10; ++i)//头节点是head，因此从1开始
{
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
//断言，判断节点创建是否成功
assert(s != NULL);
s->data = i;
s->next = (*head)->next;//使用的是头插法，那么s->next，永远在头节点和第一个节点之间插入
(*head)->next = s;//此时head不再指向1
//10-->9-->8-->7-->6-->5-->4-->3-->2-->1-->Nul.
}
}
*/
//[4].使用头插法创建带头节点的链表
void CreateList_front(List* head)
{
ListNode* p = *head;
for (int i = 1; i <= 10; ++i)//头节点是head，因此从1开始
{
p = p->next = (ListNode*)malloc(sizeof(ListNode));
//断言，判断节点创建是否成功
assert(p != NULL);
p->data = i;
p->next = NULL;//使用的是头插法，那么s->next，永远在头节点和第一个节点之间插入
//1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->Nul.
}
}
//显示链表
void ShowList(List head)
{
//ListNode* p = head;//不带头节点的显示
ListNode *p = head->next;//带头节点,却不显示头节点的显示
while (p != NULL)
{
printf("%d-->", p->data);
p = p->next;
}
printf("Nul.\n");//在链表尾给一个空的信息，以标识链表已经结束
}
//单链表的操作不难，但它的诀窍只有一点:
//必须要能分清楚，一个指针指向节点时，它的next是谁、data是谁，next->next是谁，或者这些指针如何来表示，此时对链表的操作就成功一大半了
void main()
{
List mylist;//定义了一个单链表，未初始化，内部信息都是随机值，无可用信息；
//InitList(mylist);为什么不能用mylist值传递？因为如果使用值传递，那么一旦出了InitList函数，mylist仍然还是随机值；值传递的内部的改变不会影响到外部的实参
//InitList(mylist);传递的mylist，虽然mylist是ListNode的指针，但是相对于List，就是值；
//只有对mylist取地址 &mylist才相对于List是地址形式传递
InitList(&mylist);//想要内部的改变希望影响到外部的实参，因此用地址传递
//CreateList_back(&mylist);
//ShowList(mylist);//因为不需要对其更改，就直接传mylist一级指针传递就行
CreateList_front(&mylist);
ShowList(mylist);//因为是尾插，所以是倒序，
system("pause");
}
单链表
Slist.h
#ifndef __SLIST_H__
#define __SLIST_H__
#include
#include
#include
/*
对于单链表来说，我们首先得有节点的类型 typedef struct Node
其次，我们增加了链表的管理方式，first、last、size。因此，我们需要定义相对应的List结构
这个结构有fist指针（指向头节点）、last指针（指向尾节点）、size（记录链表中有效节点的个数），任何的操作都要满足这种情况。
*/
#define ElemType int
typedef struct Node//这个是节点
{
ElemType data;
struct Node* next;
}Node, *PNode;//不光定义了节点的类型，还定义了节点指针的类型是 *PNode
typedef struct List//这个就是单链表
{
PNode first;
PNode last;
size_t size;
}List;
void InitList(List* list);
void push_back(List* list, ElemType x);
void show_list(List* list);
void push_front(List* list, ElemType x);
void pop_back(List* list);
void pop_front(List* list);
void insert_val(List* list, ElemType x);
Node* find(List* list, ElemType x);
int length(List* mylist);
void delete_val(List* list, ElemType key);
void sort(List *list);
void reverse(List *list);
void clear(List *list);
void destory(List *list);
//////////////////////////////////////////////////////////////////优化代码(C++思想)：
Node * _buynode(ElemType x);
//对于头插和尾插的优化：
typedef Node* It;//迭代器
It begin(List *list);//返回头节点
It end(List *list);//返回最后一个节点的下一个节点
void insert(List *list, It pos, ElemType x);//在链表的某个位置插入
#endif //__SLIST_H__
Slist.cpp
#include"SList.h"
//初始化单链表
void InitList(List* list)
{
list->first = list->last = (Node*)malloc(sizeof(Node));//初始化，使first、last都指向同一个头节点
assert(list->first != NULL);
list->first->next = NULL;//如果first->next不初始化为空，那么在进行头插时，直接让 s->next = list->first->next; 会导致s->next->data是一个随机值
list->size = 0;
}
void push_back(List *list, ElemType x)
{
insert(list, end(list), x);//C++中更简单，只需要insert(begin(),x);就可以了
}
void push_front(List *list, ElemType x)
{
insert(list, begin(list), x);
}
/*
//[1]尾插法插入数据到链表
void push_back(List* list, ElemType x)
{
//所有的代码，一旦谈到开辟空间，就可以这样子做：
//Node *s = _buynode(x);
//
//Node* s = (Node*)malloc(sizeof(Node));//首先申请到所要插入的节点空间
//assert(s != NULL);
//s->data = x;
//s->next = NULL;
list->last->next = s;//这里的last原本指向的是头节点，此时要让last->next指向s使 新节点s 链接到链表上（last代表的是添加新节点前的最后一个节点）
list->last = s;//新节点s连接到链表上之后，last原本指向的节点就不再是最后一个节点了，因此要让last指向s，以保证last永远指向最后一个节点
list->size++;
}
//[2]头插法插入节点
//头节点的作用是提领整个链表，头插法是在第一个节点和头节点之间插入，而并非在头节点之前插入，例如： head->1->2->3，就是在head 和 1之间插入
//在头插的时候，一定要注意，所插入的是否为第一个节点；
//而尾插就不需要，永远都要更改last
void push_front(List* list, ElemType x)
{
Node *s = _buynode(x);
//Node* s = (Node*)malloc(sizeof(Node));
//assert(s != NULL);
//s->data = x;
//s->next = NULL;
s->next = list->first->next;
list->first->next = s;
if (list->size == 0)
{
list->last = s;//让last指针指向新创建的节点s
}
list->size++;
//考虑last指针
//如果现在的链表已经有数据了，那么头插入不会造成错误；
//如果是刚开始的时候，链表一个数据都没有，此时last指针和first指针都指向头节点
//此时，当头插插入节点 s 时，s->next指向空，first->next指向 s，就链接起来了
//但是，我们忽略了一个问题，如果头插法插入的节点是第一个节点的时候，就要考虑我们要修改last指针，让其指向我们所插入的第一个节点
//如果我们修改完成，其它的节点在头插的时候，就没有任何问题了，因为其它节点进行头插入，而1将永远是最后一个节点
//但是，如果头插完再进行尾插呢？
}
*/
//[3]遍历显示链表
void show_list(List* list)
{
Node* p = list->first->next;//要想访问一个链表，就要让它指向first的第一个有效节点
while (p != NULL)
{
printf("%d-->", p->data);
p = p->next;
}
printf("Nul.\n");
}
//[4]尾删
//要读考虑边界条件，如果链表为空，就不需要删除了
//尾删就是找到last然后free(list->last)就可以了，关键是last指向的是最后一个节点，要先让last指向倒数第二个节点，才能删除最后一个节点
void pop_back(List* list)
{
if (list->size == 0)
return;
Node* p = list->first;//定义p指针指向头节点
while (p->next != list->last)//先遍历单链表，使其能够指向倒数第二个节点; 当while循环结束的时候，p就指向了倒数第二个节点
p = p->next;
free(list->last);//
list->last = p;//修改last的指向，使其指向删除后的最后一个节点，之前的指向就没了，即被修改；
list->last->next = NULL;//为最后一个节点赋空
list->size--;
}
//[5]头删
//相当于删除第一个节点
//应充分考虑如下情况：
//当链表里只有一个节点时，就会发现，此时头删法只能删除最后一个节点（也是第一个节点）
//此时last的指向就变成了一个随机值；因此要更改指向，使其指向head
//因此，头删法删除时需要考虑删除的是否是最后一个节点
//如果是，就要更改last指向
void pop_front(List* list)
{
if (list->size == 0)
return;
Node* p = list->first->next;//指向第一个节点
list->first->next = p->next;//p就被从链表上摘下来了
free(p);//释放掉该节点
if (list->size == 1)//说明删除的是最后一个节点
list->last = list->first;
list->size--;
}
//[6]插入数据
//这个方法有一个前提：
//既然要按照值插入，那么这个值插入的关系是：假如是按照升序的顺序插入
//这就要求，在插入之前的数据，一定要是一个有序的数据
//同时还要考虑到着一种情况：要插入的位置，是整个链表的末尾（即，要插入的值，比链表里的值都大）
//此时，直接
void insert_val(List* list, ElemType x)
{
Node *s = _buynode(x);
//Node* s = (Node*)malloc(sizeof(Node));
//assert(s != NULL);
//s->data = x;
//s->next = NULL;
Node* p = list->first;
while (p->next != NULL && p->next->data < x)
p = p->next;
//
if (p->next == NULL)//说明p已经找到了最后一个节点
list->last = s;//更改last指向
s->next = p->next;
p->next = s;
list->size++;
}
//[7]查找数据
//命名习惯：
//插入值，用x；
//获取值，用v；
//查找，用key；
Node* find(List* list, ElemType key)
{
Node* p = list->first->next;
while (p != NULL && p->data != key)//这个循环条件就会把找到和没找到，都包含进去；没有找到p = NULL返回，如果找到了，p指向当前的节点，就会把当前节点的地址返回
p->next;
return p;
//注意：不能这样写：while(p->data != key && p!=NULL)
//while(p->data != key && p!=NULL) 和 while (p != NULL && p->data != key)天壤之别
//如果真找不到数据，p=NULL，就没有p->data这个指向关系了，但是由于 p->data != key 条件在前面，就会导致程序崩溃
//换句话说，p能够指向->data求值的前提条件是：p != NULL
}
//[8]求长度
int length(List* list)
{
return list->size;
}
//[9]根据data删除节点
void delete_val(List* list, ElemType key)
{
if (list->size == 0)
return;
Node* p = find(list, key);
if (p == NULL)
{
printf("要删除的数据不存在.\n");
return;
}
else
{
//p指针从第一个节点开始，p移动，最后指向当前要删除的节点；
//比如要删除的是 2，那么要做的工作就是把 2 的前驱节点1的后继指向 2 本身的后继3
//但问题在于，2的前驱节点1的指针不太好寻找，除非再遍历一遍找出（p->next = key的p就是该节点），但是太麻烦了没有必要
//可以直接删除掉
//1.直接对2进行删除：直接把3的值拷贝一份，覆盖掉2节点的数据，此时原本要删除节点2，就变成了要删除节点3（p->next = q->next）
//2.还有一个方法就是，不使用find()查找，而是另外写一个查找方法，该方法返回当前节点的前一个节点的地址
//此时代码还有一个错误，即如果所要删除的是最后一个节点，last指针
//那么倒数第二个节点删除是否要考虑进来呢？
if (p == list->last)
{
pop_back(list);//在pop_back中删除完就会list->size--；
}
else
{
Node* q = p->next;
p->data = q->data;
p->next = q->next;
free(q);//释放q指针指向的节点
list->size--;
}
}
}
//[10]排序
//这里不是对数据进行交换，而是真正的交换节点
void sort(List *list)
{
if (list->size == 0 || list->size == 1)//0是空链表，1是只有一个结点的链表，都不用排
return;
//在非0和1个节点的情况加，就将当前链表分割为2个
Node* s = list->first->next;//先让指针s，指向链表的第一个节点
Node* q = s->next;
//1.把链表断开
list->last = s;//last指向s节点，last就不再指向原先的最后一个节点了
list->last->next = NULL;//last->NULL，那么后面的节点就从这个链表断开了
//2.把q链表中的每一个节点摘下来放到原先链表，并按照值大小顺序插入
while (q != NULL)//q只要不为空，就说明q之后，还有链表节点的存在
{
s = q;
q = q->next;
//这就相当于是，指针s，指向现在新有的链表，然后q = q->next
//那么s所值的结点，就可以断下来进行插入
//3.把节点摘下
Node *p = list->first;//构造指针p，指向头节点
while (p->next != NULL && p->next->data < s->data)
p = p->next;
//p->next != NULL，p->next->data < s->data，此时p = p->next，从头节点移动，指向了第一个节点
//此时p->next == NULL，因此，此时就相当于在尾部插入数据
//更改last指向，
if (p->next == NULL)
{
list->last = s;
}
//完成插入操作
s->next = p->next;
p->next = s;
}//1-->2-->3-->4-->5-->6-->7-->8-->9-->Nul.
}
//[11]单链表逆置
//这里不同于顺序表的首位两两交换，一般来说，牵扯到链表的顺序表，我们很少对链表的节点数据进行交换、操作
//一般逆置、排序都是针对节点整体进行操作
void reverse(List *list)
{
if (list->size == 0 || list->size == 1)
return;
Node *p = list->first->next;//创建指针s，指向第一个节点
Node *q = p->next;//创建指针q指向将要断开的节点的头节点
//断开链表
list->last = p;
list->last->next = NULL;
//遍历断开后的链表，使得指针q指向最后一个节点
while (q != NULL)
{
p = q;
q = q->next;
p->next = list->first->next;
list->first->next = p;
}
}
//[12]清除链表
//清除和销毁的区别是：
//清除：释放掉有效节点，保留头节点
//销毁：清除有效节点 和 头节点
void clear(List *list)
{
if (list->size == 0)
return;
Node *p = list->first->next;
while (p != NULL)
{
list->first->next = p->next;
free(p);
p = list->first->next;
}
list->last = list->first;
list->size = 0;
}
//[13]销毁链表
//销毁：清除有效节点 和 头节点
void destory(List *list)
{
clear(list);
free(list->first);
list->first = list->last = NULL;//预防野指针
}
//////////////////////////////////////////////////////////////////优化代码(C++思想)：
Node * _buynode(ElemType x)
{
Node *s = (Node *)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}
It begin(List *list)
{
return list->first->next;//返回第一个节点
}
It end(List *list)
{
return list->last->next;//返回最后一个节点的下一个节点，单链表中为NULL
}
void insert(List *list, It pos, ElemType x)
{
//原先的位置指的是是0、1、2下标
//而现在的位置，指的是单链表中某个节点的地址，现在往往是根据该节点的前驱进行插入
//所谓的pos，指的是某个节点的地址；如果指明要在2的位置插入，其实说明的是，要在2的前面进行插入，而非后面
Node *p = list->first;
while (p->next != pos)
{
p = p->next;
}
Node *s = _buynode(x);//先把节点购买出来
//购买完成，进行连接
s->next = p->next;
p->next = s;
if (pos == NULL)//现在插入的位置是在最后一个结点之后插入，那么一定要注意更改last的指向
list->last = s;
list->size++;
}
pop_front
insert_val
自己画图动手试试
代码不是背出来的，一定是编写出来的
要掌握这种排序思想：
这里的是：把整个单链表断开，然后从剩下的链表当中每次取一个节点进来，按照有效的顺序进行插入，
最终形成一个所需要的，升序或者降序的排序！
自己画图动手试试
逆置：
自己画图动手试试
清除：
Main.cpp
#define _CRT_SECURE_NO_WARNINGS //这个要放到最上面
#include"SList.h"
void main()
{
List mylist;
InitList(&mylist);
ElemType item;
Node* p = NULL;
int select = 1;
while (select)
{
printf("**************************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] reverse [12] clear *\n");
printf("* [13] destory [0] quit_system *\n");//destory这个方法不应该由客户来调动；而是应该在退出程序时摧毁
printf("**************************************************\n");
printf("请选择:>");
scanf("%d", &select);
if (select == 0)
break;
switch (select)
{
case 1:
printf("请输入要尾插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_back(&mylist, item);
}
break;
case 2:
printf("请输入要进行头插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_front(&mylist, item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入的数据:>");
scanf("%d", &item);
insert_val(&mylist, item);
break;
case 7:
printf("请输入要查找的数据:>");
scanf("%d", &item);
p = find(&mylist, item);//如果找到了，就把该节点的地址返回，找不到就返回NULL;
if (p == NULL)
{
printf("要查找的数据在链表中，不存在\n");
}
break;
case 8:
printf("单链表的长度为：%d \n", length(&mylist));
break;
case 9:
printf("请输入要删除的值:>");
scanf("%d", &item);
delete_val(&mylist, item);
break;
case 10:
sort(&mylist);
break;
case 11:
reverse(&mylist);
break;
case 12:
clear(&mylist);
break;
//case 13:
//destory(&mylist);//摧毁不应该由用户在菜单里调用，而是应该在退出系统时调用
//break;
default:
printf("输入的选择错误，请重新输入");
break;
}
}
destory(&mylist); //在退出程序时调用
}
静态链表
StaticList.cpp
StaticList.h
Main.cpp
单循环链表
SCList.h
#ifndef __SCLIST_H__
#define __SCLIST_H__
#include
#include
#include
#define ElemType int
typedef struct Node
{
ElemType data;
struct Node* next;
}Node, *PNode;//定义好节点和节点的指针
typedef struct List
{
PNode first;
PNode last;
int size;
}List;
Node* _buynode(ElemType x);
void InitSCList(List* list);
void push_back(List* list, ElemType x);
void show_list(List* list);
void push_front(List* list, ElemType x);
void pop_back(List* list);
void pop_front(List* list);
void insert_val(List* list, ElemType x);
Node* find(List* list, ElemType x);
int length(List* mylist);
void delete_val(List* list, ElemType key);
void sort(List* list);
void reverse(List* list);
void clear(List* list);
void destory(List* list);
#endif //__SCLIST_H__
SCList.cpp
#include"SCList.h"
Node* _buynode(ElemType x)
{
Node* s = (Node*)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}
void InitSCList(List* list)
{
Node* s = (Node*)malloc(sizeof(Node));
assert(s != NULL);
list->first = list->last = s;//由于现在没有真实节点，链表只有一个头结点，first、last都指向头节点，然后list->next 指向NULL
//此时，由于是循环链表，要让最后一个节点的next域指向头节点，
//因此不能让其指向空，因为就算只有一个头节点，也要保持循环特性,
//因此要让list->next也指向头节点
list->last->next = list->first;
list->size = 0;
}
/*
插入节点时，要考虑插入的是不是第一个节点
删除节点时，要考虑删除的是不是最后一个节点
检查插入程序：
头插、尾插、中间插入各试一次，没有问题基本OK
*/
void push_back(List* list, ElemType x)
{
//1.先创建出要插入的节点
Node* s = _buynode(x);
//2.把节点在尾部进行连接
list->last->next = s;//不能list->last = s; 要永远保证最后一个节点的next指向新的s节点
//3.修改last的指向
list->last = s;
//4.让最后一个节点的next域指向头节点
list->last->next = list->first;
//size++
list->size++;
}
void push_front(List* list, ElemType x)
{
//1.先创建要插入的节点
Node* p = _buynode(x);
//2.插入
p->next = list->first->next;
list->first->next = p;
//3.需要考虑到插入前链表为空的情况,链表为空时，一定要更改last的指向，否则就不能保证链表结构的正确性
if (list->first == list->last)
{
list->last = p;
list->last->next = list->first;
}
list->size++;
}
void show_list(List* list)
{
Node* p = list->first->next;
while (p != list->first)//转了一圈之后，只要不为头，就说明整个链表还没结束 //如果访问到最后一个，p->next指向的是头节点，说明访问完了
{
printf("%d-->", p->data);
p = p->next;
}
printf("Nul.\n");//表示链表结束
}
void pop_back(List* list)
{
if (list->size == 0)
return;
Node* p = list->first;
while (p->next != list->last)
{
p = p->next;
}
free(list->last);
list->last = p;
list->last->next = list->first;//这行代码到底有没有必要存在呢？
list->size--;
}
void pop_front(List* list)
{
if (list->size == 0)
return;
Node* p = list->first->next;
list->first->next = p->next;
free(p);
if (list->size == 1)//说明现在删除的是最后一个节点，要让改变last的指向
{
list->last = list->first;
}
//list->last = p->next;//不对，这么写，那么last永远指向的都是第二个节点
list->size--;
}
//[6]插入
//按值插入说明目前的链表已经有序了
void insert_val(List* list, ElemType x)
{
Node* p = list->first;//先申请一个指针，指向头节点
//要先判断，是否到了最后一个节点
//p->next == list->last 说明要插入的数据在尾部
while (p->next != list->last && p->next->data < x)//开始循环遍历
{
p = p->next;
}
if (p->next == list->last && p->next->data < x)//其实这p->next->data < x已经不用再判断了，前面while循环已经把符合这个条件的筛出来了
{
//说明需要尾部插入
push_back(list, x);
}
else
{
Node* s = _buynode(x);
s->next = p->next;
p->next = s;
list->size++;
}
}
//[7]查找
Node* find(List* list, ElemType key)
{
if (list->first == list->last)
return NULL;
Node* p = list->first->next;
while (p != list->first && p->data != key)
{
p = p->next;
}
if (p == list->first)//找了一圈之后，p == list->first，就说明没有找到
return NULL;
return p;
}
//[8]长度
int length(List* list)
{
return list->size;//只要结构控制得好，很多信息非常得出来
}
//[9]按值删除
void delete_val(List* list, ElemType key)
{
if (list->size == 0)
return;
Node* p = find(list, key);//查找成功返回的是该数值节点得地址，失败返回NULL
if (p == NULL)
{
printf("要删除得数据不存在.\n");
return;
}
if (p == list->last)
{
pop_back(list);
}
else
{
//两种方式删除：
//1.循环遍历找到该节点的前驱，然后删除
//2.将待删除节点的后继的data域复制到删除节点的data域，覆盖掉它，然后删除该节点就转化成了删除该节点的后继节点
Node* q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
list->size--;
//还要再考虑倒数第二个节点
}
}
void sort(List *list)
{
if (list->size == 0 || list->size == 1)
return;
Node* s = list->first->next;
Node* q = s->next;//保留断开后链表的头节点
list->last->next = NULL;//list->last->next原本是指向list->first的，这么做是让其先不再循环
list->last = s;//
list->last->next = list->first;//即p.next不再指向第二个节点，而是指向头节点，使让其再次成循环
//接下来就是按值插入
while (q != NULL)//由于之前把list->last->next = NULL，因此q跟NULL的比较就是标志；这就是给list->last->next赋值为空的原因，否则其还指向头，就还得用头节点来判断
{
s = q;//s指向q
q = q->next;
Node* p = list->first;
while (p->next != list->last && p->next->data < s->data)
{
p = p->next;
}
if (p->next == list->last && p->next->data < s->data)
{
s->next = list->last->next;
list->last->next = s;
list->last = s;
}
else
{
s->next = p->next;
p->next = s;
list->size++;
}
}
}
/*
命名习惯：
申请节点：Node *s，以s来命名
遍历链表、或者充当临时变量的指针：Node *p
删除一把用：Node *q，以q来命名
变量不够了：Node *t，以t来补充
*/
void reverse(List *list)
{
if (list == 0 || list->size == 1)
return;
Node *p = list->first->next;
Node *q = p->next;
//先断开链表
list->last->next = NULL;
list->last = p;
list->last->next = list->first;//尾节点的next指向头节点，就是构成循环，清晰明了！
//为啥不用p->next = list->first?//用这个的话，还要先分析出p是最后一个节点
//这两种方式功能上一样，但是在语义上不一样；上一个一目了然，而下面这个需要通过分析才能知道它是干啥的
while (q != NULL)
{
p = q;
q = q->next;
p->next = list->first->next;
list->first->next = p;
}
}
void clear(List *list)
{
Node *p = list->first->next;
while (p != list->first)//p != list->first 时，说明没有释放完成
{
list->first->next = p->next;
free(p);
p = list->first->next;
}
list->last = list->first;
list->last->next = list->first;
list->size = 0;
}
void destory(List *list)
{
clear(list);
free(list->first);
list->first = list->last = NULL;
}
Main.cpp
#define _CRT_SECURE_NO_WARNINGS //这个要放到最上面
#include"SCList.h"
void main()
{
List mylist;
InitSCList(&mylist);
ElemType item;
Node* p = NULL;
int select = 1;
while (select)
{
printf("**************************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] reverse [12] clear *\n");
printf("* [13] destory [0] quit_system *\n");//destory这个方法不应该由客户来调动；而是应该在退出程序时摧毁
printf("**************************************************\n");
printf("请选择:>");
scanf("%d", &select);
if (select == 0)
break;
switch (select)
{
case 1:
printf("请输入要尾插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_back(&mylist, item);
}
break;
case 2:
printf("请输入要进行头插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_front(&mylist, item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入的数据:>");
scanf("%d", &item);
insert_val(&mylist, item);
break;
case 7:
printf("请输入要查找的数据:>");
scanf("%d", &item);
p = find(&mylist, item);//如果找到了，就把该节点的地址返回，找不到就返回NULL;
if (p == NULL)
{
printf("要查找的数据在链表中，不存在\n");
}
break;
case 8:
printf("单链表的长度为：%d \n", length(&mylist));
break;
case 9:
printf("请输入要删除的值:>");
scanf("%d", &item);
delete_val(&mylist, item);
break;
case 10:
sort(&mylist);
break;
case 11:
reverse(&mylist);
break;
case 12:
clear(&mylist);
break;
//case 13:
// destory(&mylist);//摧毁不应该由用户在菜单里调用，而是应该在退出系统时调用
// break;
default:
printf("输入的选择错误，请重新输入");
break;
}
}
//destory(&mylist); //在退出程序时调用
}
双向链表
DList.h
#ifndef __DLIST_H__
#define __DLIST_H__
#include
#include
#include
#define ElemType int //定义出元素的类型
typedef struct Node
{
ElemType data;
struct Node *pre;//前驱结点
struct Node *next;//后继节点
}Node,*PNode;
//对双向链表同样采用单向链表的管理模式
//定义出list结构，让last指向最后一个节点，first指向头节点，size记录真实节点的个数
typedef struct List
{
PNode first;
PNode last;
int size;
}List;
Node* _buynode(ElemType x);
void InitSCList(List* list);
void push_back(List* list, ElemType x);
void show_list(List* list);
void push_front(List* list, ElemType x);
void pop_back(List* list);
void pop_front(List* list);
void insert_val(List* list, ElemType x);
Node* find(List* list, ElemType x);
int length(List* mylist);
void delete_val(List* list, ElemType key);
void sort(List* list);
void reverse(List* list);
void clear(List* list);
void destory(List* list);
void InitDList(List *list);
#endif
DList.cpp
#include"DList.h"
Node* _buynode(ElemType x)
{
Node* s = (Node*)malloc(sizeof(Node));
assert(s != NULL);
s->data = x;
s->pre = s->next = NULL;
return s;
}
//由于链表是带有头节点的，因此创建头节点的任务在链表初始化时完成
void InitDList(List* list)
{
Node* s = (Node*)malloc(sizeof(Node));
assert(s != NULL);//断言成功才代表此头节点创建成功
list->first = list->last = s;
list->first->pre = list->last;
list->last->next = list->first;
list->size = 0;
}
void push_back(List* list, ElemType x)
{
Node* s = _buynode(x);
s->next = list->last->next;
s->next->pre = s;
s->pre = list->last;
list->last->next = s;
list->last = s;
list->size++;
}
//在只有一个头结点的时候进行头插，必须要考虑到list->last的情况
//list->first->next 为NULL，NULL是没有前驱pre的，因此代码在运行时就会崩溃！
//因此，要考虑链表中之后一个头结点（无有效节点）的情况
void push_front(List* list, ElemType x)
{
Node* s = _buynode(x);
s->next = list->first->next;
s->next->pre = s;
s->pre = list->first;
list->first->next = s;
if (list->first == list->last)
list->last = s;
list->size++;
}
void show_list(List* list)
{
Node* p = list->first->next;
while (p != list->first)
{
printf("%d-->", p->data);
p = p->next;
}
printf("Nul.\n");
}
void pop_back(List* list)
{
if (list->size == 0)
return;
Node* p = list->last;
list->last = list->last->pre;
p->next->pre = p->pre;
p->pre->next = p->next;
free(p);
list->size--;
}
//要考虑到头删最后一个节点的情况
//因为如果时最后一个节点，诸侯一个节点的后继为NULL，是没有前驱的
void pop_front(List* list)
{
if (list->size == 0)
return;
Node* p = list->first->next;
p->next->pre = p->pre;
p->pre->next = p->next;
if (list->size == 1)
list->last = list->first;
free(p);
list->size--;
}
//按值插入的前提是链表是有序的（这里是升序），按照升序的方式插入
void insert_val(List* list, ElemType x)
{
Node* p = list->first;
while (p->next != list->last && p->next->data < x)
p = p->next;
if (p->next == list->last && p->next->data < x)
{
push_back(list, x);
}
else//这种情况是，找到了待插入的位置，且这个位置不是最后，此时p指针指向的是待插入位置的前一个结点
{
Node* s = _buynode(x);
s->next = p->next;
p->next->pre = s;
s->pre = p;
p->next = s;
list->size++;
}
}
Node* find(List* list, ElemType key)
{
Node* p = list->first->next;
while (p != list->first && p->data != key)//p == NULL退出循环，说明没有找到，p->data == key退出循环说明找到了
p = p->next;
if (p == list->first)
return NULL;
return p;
}
int length(List* list)
{
return list->size;
}
void delete_val(List* list, ElemType key)
{
if (list->size == 0)//链表就是空链表，不必删除
return;
Node* p = find(list, key);//要删除的前提是查找到该元素
if (p == NULL)
{
printf("要删除的数据是不存在的.\n");
return;
}
//删除节点只需要考虑两点：
//被删除的是普通节点，还是尾节点
if (p == list->last)//尾节点
{
pop_back(list);
}
else//普通节点
{
//修改其中的指针就行了
p->pre->next = p->next;
p->next->pre = p->pre;
free(p);
list->size--;
}
}
//排序就是先把链表从第一个节点处断开，
//然后从剩下的链表中提取节点，按着值插入的方式插入到原链表中即可
void sort(List* list)
{
if (list->size == 0 || list->size == 1)
return;
Node* s = list->first->next;
Node* q = s->next;
//断开
list->last->next = NULL;
list->last = s;
//循环
list->last->next = list->first;
list->first->pre = list->last;
while (q != NULL)
{
s = q;
q = q->next;
Node* p = list->first;
//先将指针移动到尾节点的前一个位置
while (p->next != list->last && p->next->data < s->data)
p = p->next;
if (p->next == list->last && p->next->data < s->data)
{
//进行尾插
s->next = list->last->next;//s->next就是最后节点的next
s->next->pre = s;//p->next的前驱，即相当于是list->last的前驱
s->pre = list->last;
list->last->next = s;
list->last = s;
}
else
{
s->next = p->next;
s->next->pre = s;
s->pre = p;
p->next = s;
}
}
}
void reverse(List* list)
{
if (list->size == 0 || list->size == 1)
return;
Node* p = list->first->next;
Node* q = p->next;
//断开
list->last->next = NULL;
list->last = p;
//循环
list->last->next = list->first;
list->first->pre = list->last;
while (q != NULL)
{
p = q;
q = q->next;
p->next = list->first->next;
p->next->pre = p;
p->pre = list->first;
list->first->next = p;
}
}
void clear(List* list)
{
if (list->size == 0)
return;
Node* p = list->first->next;
while (p != list->first)
{
p->next->pre = list->first;
list->first->next = p->next;
free(p);
p = list->first->next;
}
list->last = list->first;
list->size = 0;
}
void destory(List* list)
{
clear(list);
free(list->first);
list->first = list->last = NULL;
}
Main.cpp
#define _CRT_SECURE_NO_WARNINGS
#include"DList.h"
void main()
{
List mylist;
InitDList(&mylist);
ElemType item;
Node* p = NULL;
int select = 1;
while (select)
{
printf("**************************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list [4] pop_back *\n");
printf("* [5] pop_front [6] insert_val *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_val [10] sort *\n");
printf("* [11] reverse [12] clear *\n");
printf("* [13] destory [0] quit_system *\n");//destory这个方法不应该由客户来调动；而是应该在退出程序时摧毁
printf("**************************************************\n");
printf("请选择:>");
scanf("%d", &select);
if (select == 0)
break;
switch (select)
{
case 1:
printf("请输入要尾插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_back(&mylist, item);
}
break;
case 2:
printf("请输入要进行头插的数据(-1结束):>");
while (scanf("%d", &item), item != -1)
{
push_front(&mylist, item);
}
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("请输入要插入的数据:>");
scanf("%d", &item);
insert_val(&mylist, item);
break;
case 7:
printf("请输入要查找的数据:>");
scanf("%d", &item);
p = find(&mylist, item);//如果找到了，就把该节点的地址返回，找不到就返回NULL;
if (p == NULL)
{
printf("要查找的数据在链表中，不存在\n");
}
break;
case 8:
printf("单链表的长度为：%d \n", length(&mylist));
break;
case 9:
printf("请输入要删除的值:>");
scanf("%d", &item);
delete_val(&mylist, item);
break;
case 10:
sort(&mylist);
break;
case 11:
reverse(&mylist);
break;
case 12:
clear(&mylist);
break;
//case 13:
//destory(&mylist);//摧毁不应该由用户在菜单里调用，而是应该在退出系统时调用
//break;
default:
printf("输入的选择错误，请重新输入");
break;
}
}
destory(&mylist); //在退出程序时调用
}