数据结构 Day3

刺骨的言语ヽ痛彻心扉 2023-07-07 09:00 7阅读 0赞

/** * Name:test_3.c * Description:数据结构学习程序3 * https://www.bilibili.com/video/av18586085?p=1 * 链表的学习代码，从P14到P21 的练习代码 * Author:JianshuZhao * Version:V1.0.0 * Date:2020.2.22 */

### 顺序存储的插入及删除 ###

在顺序结构中，插入需要做的是从第i个位置将之后的所有数据向后移动，然后再在该位置插入，即先移动，再插入。注意移动的时候从数据的最后一项向前依次移动。  
最终实现代码如下：

//在线性表中的第i个位置插入元素x
     bool Insert(int x, int i, List_t Ptrl)
     { 
    	 int j;
    	 if (Ptrl->Last >= MAXSIZE - 1)
    	 { 
    		 printf("The list has been full");
    		 return false;
    	 }
    
    	 if ((i < 1) || (i > Ptrl->Last + 2))
    	 { 
    		 printf("unavailible location");
    		 return false;
    	 }
    
    	 for (j = Ptrl->Last; j >= i - 1; j--)
    	 { 
    		 Ptrl->Data[j + 1] = Ptrl->Data[j];
    	 }
    
    	 Ptrl->Data[i - 1] = x;
    	 Ptrl->Last++;
    	 return true;
     }
    
     //在线性表Ptrl中删除第i个元素
     bool Delete(int i, List_t Ptrl)
     { 
    	 int j;
    	 if ((i < 1) || (i > Ptrl->Last + 1))
    	 { 
    		 printf("the number of %d is unavailible", i);
    		 return false;
    	 }
    
    	 for (j = i; j < Ptrl->Last; j++)
    	 { 
    		 Ptrl->Data[j - 1] = Ptrl->Data[j];
    	 }
    	 Ptrl->Last--;
     }

### 链式存储的存储及查找 ###

链表的查找分为按内容查找和按位置查找。实现具体的操作之前，先说明一下所有的数据的定义如下：

#define ITEMMAXSIZE 100
    typedef struct { 
    	int Age;
    	char Name[ITEMMAXSIZE];
    }Item_t;
    
    typedef struct { 
    	Item_t Item;
    	struct Node_t *Next;
    }Node_t;
    
    typedef struct { 
    	Node_t *Node;
    	int Size;
    }List_t;

上述的定义，放在了test\_3.h文件中，其中该文件包括了main.h的头文件，而main.h的头文件则包括了相对应的库文件。

#include <stdio.h>
    #include <inttypes.h>
    #include <time.h>
    #include <math.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>

接下来将详细说明链表的存储和查找

int GetListLength(List_t* List)
    { 
    	Node_t* pTemp = List->Node;
    	int j = 0;
    	while (pTemp != NULL)
    	{ 
    		pTemp = List->Node->Next;
    		j++;
    	}
    	return j;
    }
    
    Node_t* FindListNum(int k, List_t* List)
    { 
    	Node_t* pTemp = List->Node;
    	int i = 1;
    	while ((pTemp != NULL) && (i < k))
    	{ 
    		pTemp = pTemp->Next;
    		i++;
    	}
    	if (i == k)
    	{ 
    		return pTemp;
    	}
    	else
    	{ 
    		return NULL;
    	}
    }
    
    Node_t* FindListItem(Item_t Item, List_t* List)
    { 
    	Node_t* pTemp = List->Node;
    	while ((pTemp != NULL) && (memcmp(&pTemp->Item, &Item,sizeof(Item_t)) != 0))
    	{ 
    		pTemp = pTemp->Next;
    	}
    
    	return pTemp;
    }

### 链式存储的插入和删除 ###

在插入节点的时候需要注意要先将链表中的下一个节点取出来，赋值到待插入的节点的Next中，然后再将前一个节点的Next指向待插入的节点中，注意上述的顺序不能错，如果出错会导致后一个节点的地址丢失。

Node_t* InsertList(int i, Item_t Item, List_t* List)
    { 
    	Node_t *p, *s;
    	if (i == 1)
    	{ 
    		s = (Node_t *)malloc(sizeof(Node_t));
    		memcpy(&s->Item, &Item, sizeof(Item_t));
    		s->Next = List->Node;
    		return s;
    	}
    	p = FindListNum(i-1, List);
    	if (p == NULL)
    	{ 
    		printf("The parameter i is wrong!");
    		return NULL;
    	}
    	else 
    	{ 
    		s = (Node_t *)malloc(sizeof(Node_t));
    		memcpy(&s->Item, &Item, sizeof(Item_t));
    		s->Next = p->Next;
    		p->Next = s;
    		return s;
    	}
    }
    
    Node_t* DeleteList(int i, Item_t Item, List_t* List)
    { 
    	Node_t *p, *s;
    	if (i == 1)
    	{ 
    		s = List->Node;
    		if (List->Node != NULL)
    		{ 
    			List->Node = List->Node->Next;
    		}
    		else
    		{ 
    			return NULL;
    		}
    		free(s);
    		return List->Node;
    	}
    	p = FindListNum(i - 1, List);
    	if (p == NULL)
    	{ 
    		printf("The parameter i-1: %d is wrong!", i-1);
    		return NULL;
    	}
    	else if (p->Next == NULL)
    	{ 
    		printf("The parameter i-1: %d is wrong!", i);
    	}
    	else
    	{ 
    		s = List->Node;
    		List->Node = List->Node->Next;
    		free(s);
    		return List->Node;
    	}
    }

其实在这一章的内容到目前为止建议参照C primer Plus中的内容，由于C primer plus中的相关代码在公司，因此在这里记录一下当时的几个点。  
注意几点：  
1、用malloc分配内存的时候应注意sizeof()中应为待分配内存的结构体，而不是一个结构体指针。  
2、定义了函数实现时，实际上调用了双重指针，即List\_t \* List，之所以这么定义的原因是因为在函数实现操作链表时，如果不传一个指针类型的操作时，是无法改变链表的内容的，例如在初始化、插入、删除等操作时，均需操作该链表的实际内容。其中，List\_t中又包括了一个Node\_t \*的结构体指针类型，指向了该链表开始的第一个地址。

### 广义链表与多重链表 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]  
通过标志Tag和union进行区分，但个人觉得这种方式不是很好。  
![在这里插入图片描述][20200222181837104.png]

在视频中提供了一个例子用于理解多重链表——二维数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
为了更好的理解，有如下的一个多重链表图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]  
其中每一个节点的定义表示为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]  
可以看到在这个链表中，有横向（right）和纵向（down）两个方向，因此也叫十字链表，在这种情况下，我们为了区分不同的情况，在整个矩阵的最外侧可以理解为又建了一层，用来表示这个多重链表的参数，因此这个矩阵可以用两种结构和一起表示，一种为矩阵中非0元素的节点，另一种为矩阵中的头节点，即外侧的那一层。  
在这里其十字链表的定义如下：

typedef struct { 
    	int row;		//行号
    	int col;		//列号
    	struct MatNode_t *right;
    	struct MatNode_t *down;
    	union 
    	{ 
    		Item_t *Item;		//数据节点
    		struct MatNode_t *link;		//行/列节点
    	}Tag;
    }MatNode_t;

### 堆栈 ###

**后缀表达式的求值**：  
处理逻辑为：从左向右逐个扫描，判断是运算数还是运算符号；  
1、若为运算数：即依次缓存当前的运算数；  
2、若为运算符号：即按照当前的运算符号操作最近的两个运算数。  
6 2 / 3- 4 2 \* + = ？  
该式的计算依次为6/2=3，3-3=0， 0缓存、4缓存、2缓存，4\*2=8,0+8=8，最后的输出结果为8。  
其时间复杂度为T(N)

**堆栈**  
从这个定义中推导出来了一种数据结构，即为堆栈（这里的堆栈实际上是指的栈（Stack）而并非堆（Heap））：  
需要有一种数据结构，能够顺序存储运算数，并且在碰到运算符号的时候“倒序输出”，即先进后出。

对于堆栈的抽象数据类型描述如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

### 堆栈的顺序存储实现 ###

在这里该结构的定义如下：

typedef struct { 
    	int Data[ITEMMAXSIZE];
    	int Top;		//记录栈顶元素位置的变量
    }Snode_t;
    typedef Snode_t	* Stack_t;

其入栈和出栈的实现方式如下：

bool PushStack(Stack_t Stack, int item)
    { 
    	if (Stack->Top == ITEMMAXSIZE - 1)
    	{ 
    		printf("堆栈已满");
    		return false;
    	}
    	else
    	{ 
    		Stack->Top++;
    		Stack->Data[Stack->Top] = item;
    		return true;
    	}
    }
    
    int PopStack(Stack_t Stack)
    { 
    	if(Stack->Top == 0)
    	{ 
    		printf("堆栈为空");
    		return false;
    	}
    	else
    	{ 
    		return (Stack->Data[Stack->Top--]);
    	}
    }

在这里有一个练习程序需要去实现：  
**请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间，入栈操作就可以成功**  
个人思考：一个数组实现两个堆栈，那也就是说一个的栈底为数组的第一个元素，另一个栈底为数组的最后一个元素。判断数据是否仍然可以入栈的操作，即判断这个数组是否还有空间，即判断两个堆栈的Top值相等的时候，即表示堆栈已经满了。  
数据结构的定义如下：

typedef struct { 
    	int Data[MAXSIZE];
    	int Top1;
    	int Top2;
    }Sexample_t;

具体的出栈和入栈的实现如下：

bool PushExStack(Sexample_t * stack, int item, int tag)
    { 
    	if (stack->Top2 - stack->Top1 == 1)
    	{ 
    		printf("堆栈满了");
    		return false;
    	}
    
    	if (tag == 1)
    	{ 
    		stack->Data[++(stack->Top1)] = item;
    	}
    	else
    	{ 
    		stack->Data[++(stack->Top2)] = item;
    	}
    	return true;
    }
    
    
    int PopExStack(Sexample_t * stack, int tag)
    { 
    	
    
    	if (tag == 1)
    	{ 
    		if (stack->Top1 == -1)
    		{ 
    			printf("堆栈为空");
    			return NULL;
    		}
    		return (stack->Data[(stack->Top1)--]);
    	}
    	else
    	{ 
    		if (stack->Top2 == MAXSIZE)
    		{ 
    			printf("堆栈为空");
    			return NULL;
    		}
    		return (stack->Data[(stack->Top2)--]);
    	}
    }

### 堆栈的链式存储实现 ###

注意：用链表表示堆栈的时候，其堆栈的Top为链表的Head，这样要方便其出栈和入栈。  
结构定义如下：

typedef struct { 
    	int data;
    	struct Stack_Node_t *Next;
    }Stack_Node_t;
    
    typedef Stack_Node_t * Stack_List_t;

实现方式如下：

Stack_List_t CreatStackList()
    { 
    	Stack_List_t S;
    	S = (Stack_List_t)malloc(sizeof(Stack_Node_t));
    	S->Next = NULL;
    	return S;
    }
    
    int StackListIsEmpty(Stack_List_t S)
    { 
    	return (S->Next == NULL);
    }
    
    void StackListPush(int item, Stack_List_t S)
    { 
    	Stack_Node_t *nTemp;
    	nTemp = (Stack_Node_t *)malloc(sizeof(Stack_Node_t));
    
    	//插入的时候实际上是新建了一个节点，然后插入到了第二个节点
    	//在这种实现方法中第二个节点才是最开始的第一个元素，头节点为一个空节点
    	nTemp->data = item;
    	nTemp->Next = S->Next;
    	S->Next = nTemp;
    }
    
    int StackListPop(Stack_List_t S)
    { 
    	Stack_Node_t *nTemp;
    	int temp;
    
    	if (S->Next == NULL)
    	{ 
    		printf("该链表堆栈为空");
    		return NULL;
    	}
    
    	nTemp = S->Next;
    	temp = nTemp->data;
    	S->Next = nTemp->Next;
    	free(nTemp);
    	return temp;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020022218153148.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200222181837104.png]: https://img-blog.csdnimg.cn/20200222181837104.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200222183223321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200222184046326.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200222191104178.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200222193423935.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70