首页 > 其他分享 >链表基础

链表基础

时间:2023-02-09 00:22:38浏览次数:46  
标签:last 基础 list next 链表 List 节点 first

二、链表:

初识

链表基础知识:

什么是链表

链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。

链表的入口节点称为链表的头结点也就是head。

链表1

链表的类型:

单链表

链表1

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示: 链表2

循环链表

循环链表,顾名思义,就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

链表4

链表的定义
链表的操作
链表性能分析
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>

#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<stdio.h>
#include<malloc.h>
#include<assert.h>

/*
对于单链表来说,我们首先得有节点的类型 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<stdio.h>
#include<malloc.h>
#include<assert.h>

#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<stdio.h>
#include<malloc.h>
#include<assert.h>

#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); //在退出程序时调用
}

标签:last,基础,list,next,链表,List,节点,first
From: https://www.cnblogs.com/Epiephany/p/17103832.html

相关文章

  • 1.两个排序链表归并(Leetcode 21)
    1.两个排序链表归并(Leetcode21)#include<stdio.h>structListNode{ intval; ListNode*next; ListNode(intx):val(x),next(NULL){}};classSolution{p......
  • Matplotlib基础
    Matplotlib1.什么是matplotlib​ 专门用于开发2D图表(包括3D图表,但不怎么擅长3D图表)以渐、交互式实现数据可视化2.hello_matplotlib简单折线图的绘制importmatp......
  • 02.java基础(一)java的基础、方法和数组
    目录Java基础Java特性Java程序运行机制Java基础语法1.数据类型基本类型引用类型数据类型扩展String类型内存分配过程转义字符类型转换变量常量2.运算符逻辑运算符、位运算......
  • 03java基础(二)java面向对象
    目录类和对象的基本使用基础概念类的初始化用new关键字创建对象创建对象的内存分析OOP的三大特征类的封装类的继承继承的基础使用继承基本概念extends关键字的基本使用supe......
  • 第2章 信息系统项目管理基础
    项目管理基础项目的概念项目是为提供一项独特产品、服务或成果所做的临时性努力。项目的特点主要特点(PMI归纳的)临时性(一次性)独特的产品、服务或成果逐......
  • 从0到1一步一步玩转openEuler--openEuler基础配置-设置语言环境和键盘
    8.1设置语言环境您可以通过localectl修改系统的语言环境,对应的参数设置保存在/etc/locale.conf文件中。这些参数会在系统启动过程中被systemd的守护进程读取。8.1.1显示......
  • 阿里云天池 零基础入门NLP - 新闻文本分类 2种做法,F1=0.87
    problem1、赛题理解数据集:在NLP_data_list_0715.csv中,有三个链接。分别可以下载训练集,测试集A,测试样例。f1_score介绍:F1分数(F1-score)是分类问题的一个衡量指标。一些多......
  • Jupyter notebook基础教程(启动,汉化,操作)
    1、启动进入需要启动的目录,shift+右键启动终端然后在终端中输入命令即可启动jupyter到当前目录(通过终端的链接访问程序)jupyternotebookjupyternotebook--port9999#......
  • 数据库基础操作 - 4
    6、事物6.1、什么是事物要么都成功,要么都失败一一一一一1、SQL执行A给B转账A1000-->200B2002、SQL执行B收到A的钱A800B400一一一一一将一组SQL放......
  • Java基础知识点(idea的项目结构、制表符、变量以及其使用
    1.idea的项目结构;project(项目)、module(模块)、package(包)、class(类)​2.制表符;\t;再打印的时候,把前面字符串的长度补齐到8,或者8的整数倍。最少补一个空格,最多补8个空格......