文章目录

0.顺序表

/*0.顺序表*/
typedef unsigned int SeqListNode;	//表节点
typedef struct _seq_header			//表头
{
	int capacity;
	int length;
	SeqListNode* node;
}SeqList;

/*****************【注意】*****************
1.创建时使用malloc；
2.插入元素时，后面所有元素需后移；
3.反转链表；
*****************************************/

1.单链表

/*1.单链表*/
typedef struct _link_node			//表节点
{
    LinkListNode* next;
}LinkListNode;
typedef struct _link_header			//表头
{
    LinkListNode header;
    int length;
}LinkList;

/*****************【注意】*****************
1.创建时使用malloc；
2.插入元素要遍历；
3.反转链表；
4.找中心元素（只遍历一次）--快慢指针；
5.可以无头；
*****************************************/

2.静态链表

/*2.静态链表*/
typedef struct _static_node			//表节点
{
    unsigned int data;
    int next;
}StaticListNode;
typedef struct _static_header		//表头
{
    int capacity;
    StaticListNode header;
    StaticListNode node[];	//柔性数组（缓冲元素）
}StaticList;

/*****************【注意】*****************
1.创建时使用malloc，大小为capacity+1；
2.可以无头（没有header）；
*****************************************/

3.循环链表–单链表的改进

3.1循环链表

/*3.循环链表*/
typedef struct _cir_node			//表节点
{
	CircleListNode* next;
}CircleListNode;
typedef struct _cir_header			//表头
{
	CircleListNode header;
	int length;
}CircleList;

/******************************【注意】*************************************
1.创建时使用malloc；
2.元素的插入：
	1）中间与尾部插入元素-----------------------遍历到pos处插入;
	2）原始插入元素，即slist->length==0时-------node->next=node;
	3）头插元素，即current=slist（即pos==0）时--last->next=node;
3.元素的删除：
	1）中间与尾部删除元素-----------------------遍历到pos处删除；
	2）删除后为原始状态，即slist->length==0-----slist->header.next=NULL;
	3）头删元素，即ret==first，两个步骤一起写就ok了：
		a）针对(pos!=0)&&(pos==length)情况----slist->header.next = ret->next;
		b）针对pos=0情况----------------------last->next = ret->next;
***************************************************************************/

3.1循环链表–slider

/*4.循环链表--slider*/
typedef struct _cir_node			//表节点
{
	CircleListNode* next;
}CircleListNode;
typedef struct _cir_header			//表头
{
	CircleListNode header;
    CircleListNode* slider;	//..
	int length;
}CircleList;
/******************************【注意】*************************************
1.创建时使用malloc；
2.元素的插入：
	1）原始插入元素，即slist->length==0时-----slist->slider=node;//默认指向首元素；
3.元素的删除：
	1）中间与尾部删除元素--遍历到pos处删除；
		if(ret == slist->slider)
			slist->slider = ret->next;
	2）删除后为原始状态，即slist->length==0
		if (slist->length == 0){
			slist->header.next = NULL;
			slist->slider = NULL;
		}
***************************************************************************/

3.3应用：约瑟夫问题如下

typedef struct _tag_value	//数据结点
{
	CircleListNode header;
	int v;
}value;

CircleList_Reset(list);
while (CircleList_Length(list) > 0)		//解决约瑟夫问题；
{
	value* p = NULL;
	for (index = 1; index < 3; index++){
		CircleList_Next(list);
    }	
	p = (value*)CircleList_Current(list);
	printf("%d\n", p->v);
	CircleList_DeleteNode(list, (CircleListNode*)p);
}

4.双向链表–单链表的改进

4.1双向链表

typedef struct _double_node			//表节点
{
    DLinkListNode* next;
    DLinkListNode* pre;
}DLinkListNode;
typedef struct _double_header			//表头
{
    DLinkListNode header;
    int length;
}DLinkList;


/*******************************插入流程*****************************/
	next = current->next;

	current->next = node;//第一步；-->>node
	node->next = next;	 //第二步；	   node-->>
	if (next != NULL){
		next->pre = node;//第三步；    node<<--
	}
	node->pre = current; //第四步; <<--node
	
	if (current == slist){		//包括pos=0或slist->length=0时
		node->pre = NULL;
	}
/*******************************删除流程*****************************/
	ret = current->next;	
	next = ret->next;

	current->next = next;	//第一步；
	if (next!=NULL){		//第二步；
		next->pre = current;
        
        if (current == slist){
		next->pre = NULL;
		}
	}
**********************************************************************/

4.2双向链表–slider

typedef struct _double_node			//表节点
{
    DLinkListNode* next;
    DLinkListNode* pre;
}DLinkListNode;
typedef struct _double_header		//表头
{
    DLinkListNode header;
    DLinkListNode* slider;
    int length;
}DLinkList;

5.静态链表–空闲链表

typedef struct _static_node			//表节点
{
    unsigned int data;
    int next;
}StaticListNode;
typedef struct _static_header		//表头
{
    int capacity;
    StaticListNode header;
    StaticListNode nullheader;
    StaticListNode node[];
}StaticList;

/*******************************获取空闲节点*****************************
index = StaticList_GetAvailable(slist);
**********************************************************************/

6.双向+循环链表

6.1双向循环链表

typedef struct _doublecircle_node		//表节点
{
    DCircleListNode* next;
    DCircleListNode* pre;
}DCircleListNode;
typedef struct _doublecircle_header
{
    DCircleListNode header;				//表头
    int length;
}DCircleList;


/************************************插入节点**********************************/
								//情况1
	current->next = node;		//1
	node->next = next;			//2
	if (next != NULL){			//3
		next->pre = node;		
	}
	node->pre = current;		//4

	if (slist->length == 0){	//情况2
		node->next = node;
		node->pre = node;
	}

	slist->length++;

	if (current == slist){		//情况3，只针对pos==0条件时；
		DCircleListNode* last = DCircleList_Get(slist, slist->length - 1);
		last->next = node;
		node->pre = last;
	}
/********************************************************************************/
/************************************删除节点*************************************/
	ret = current->next;
	next = ret->next;

	if (ret == first){
		last = DCircleList_Get(slist, DCircleList_Length(slist) - 1);
	}

	current->next = next;
	next->pre = current;	//循环链表（next不可能为空）

	slist->length--;

	if (last != NULL) {		//即if (ret == first)
		slist->header.next = next;
		last->next = next;

		if (next != NULL){
			next->pre = last;
		}
	}

	if (slist->length == 0){
		slist->header.next = NULL;
		slist->header.pre = NULL;
	}
/********************************************************************************/

6.2双向循环链表–slider

typedef struct _doublecircle_node		//表节点
{
    DCircleListNode* next;
    DCircleListNode* pre;
}DCircleListNode;
typedef struct _doublecircle_header
{
    DCircleListNode header;				//表头
    DCircleListNode* slider;
    int length;
}DCircleList;

6.3总结

【注意】循环链表（包括单、双向循环）除了中间、尾部操作外，一定要注意以下情况！

在插入时：

（1）slist->length == 0 初始状态

（2）current == slist 头插（只针对pos==0条件）

在删除时：

（1）slist->length == 0 删除后为初始状态

（2）ret == first 头删

7.栈

7.1顺序栈

7.2链式栈

7.3实现符号匹配–链式栈

7.4实现中缀转后缀–链式栈

​ 对于数字：直接输出；

​ 对于符号：’(‘号进栈；符号优先级大则入栈，小则弹出栈顶符号，直到要入栈符号的优先级最大；’)‘号弹出栈顶直至遇到’(’；

​ 遍历结束：弹出栈中所有元素；

7.5实现后缀表达式计算–链式栈

​ 对于数字：进栈；

​ 对于符号：先后弹出右、左操作数，运算后结果再进栈；

​ 遍历结束：栈中唯一数字为计算结果

7.6实现中缀转后缀+后缀表达式计算

8.栈与递归

程序栈空间：本质上是一种顺序栈；

栈溢出：局部递归过深或局部数组过大；

void reverse(char* p) 函数示例

更新中…

【注意】本文为个人整理，转载请声明，欢迎交流~

# 数据结构 # 链表 # 算法 # c语言
Logo
华为开发者空间

华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。

更多推荐

cover

深化产教融合协同创新，华为云HCSD校园沙龙走进山西职业技术学院

avatar 华为开发者空间
cover

2024华为开发者盛典，海外开发者代表团走进华为

avatar 华为开发者空间
cover

华为“行业AI应用创新孵化营”走进中国医科大学，共探人才培养新模式

avatar 华为开发者空间