2019 September 02 CPP基础

C/CPP与数据结构-第一节 线性表（三）

循环链表

  1. 定义： 将单链表中最后一个数据元素的next指针指向第一个元素
  2. 特点：
    1. 循环链表拥有单链表的所有操作
      1. 销毁链表、获取链表长度、清空链表、获取第pos个元素操作、插入元素到位置pos、删除位置pos处的元素
    2. 新增功能：
      1. 游标的定义: 在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。

      图4

  3. 循环链表新的操作：

     //将游标重置指向链表中的第一个数据元素
 CircleListNode* CircleList_Reset(CircleList* list);
    
 //获取当前游标指向的数据元素
 CircleListNode* CircleList_Current(CircleList* list);
    
 //将游标移动指向到链表中的下一个数据元素
 CircleListNode* CircleList_Next(CircleList* list);
    
 //直接指定删除链表中的某个数据元素 
 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);  
 // 根据元素的值 删除 元素 pk根据元素的位置 删除 元素
  4. 如何确定一个链表是循环链表？
    1. 将这个链表遍历打印2次
  5. 设计与实现
    1. 插入分析：
      1. 普通插入元素（和单链表是一样的）
      2. 尾插法（和单链表是一样的，单链表的写法支持尾插法；因：辅助指针向后跳length次，指向最后面那个元素）
      3. 头插法（要进行头插法，需要求出尾结点，和单链表不一样的地方，保证是循环链表）第一次插入元素时，让游标指向0号结点
      4. 第一次插入元素

      图4

    2. 删除分析：
      1. 删除普通结点
      2. 删除头结点（删除0号位置处元素），需要求出尾结点

      图4

    3. 代码实现

       //CircleList.h
 #ifndef _CIRCLELIST_H_
 #define _CIRCLELIST_H_
        
 typedef void CircleList;
        
 typedef struct _tag_CircleListNode
 {
 	struct _tag_CircleListNode * next;
 }CircleListNode;
        
 CircleList* CircleList_Create();
        
 void List_Destroy(CircleList* list);
        
 void CircleList_Clear(CircleList* list);
        
 int CircleList_Length(CircleList* list);
        
 int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);
        
 CircleListNode* CircleList_Get(CircleList* list, int pos);
        
 CircleListNode* CircleList_Delete(CircleList* list, int pos);
        
 //add
        
 //根据结点的值 进行数据的删除
 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
        
 CircleListNode* CircleList_Reset(CircleList* list);
        
 CircleListNode* CircleList_Current(CircleList* list);
        
 //游标指向2号位置 
 //把2号位置返回出来,同时让游标下移到3号位置
 CircleListNode* CircleList_Next(CircleList* list);
        
 #endif
        
 //CircleList.c
 #include <stdio.h>
 #include <malloc.h>
 #include "CircleList.h"
        
 typedef struct _tag_CircleList
 {
 	CircleListNode header;
 	CircleListNode* slider; //新增了一个游标功能
 	int length;
 } TCircleList;
        
 CircleList* CircleList_Create() // O(1)
 {
 	TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));
 	if (ret == NULL)
 	{
 		return NULL;
 	}
        	
 	ret->length = 0;
 	ret->header.next = NULL;
 	ret->slider = NULL;
 	return ret;
 }
        
 void CircleList_Destroy(CircleList* list) // O(1)
 {
 	if (list == NULL)
 	{
 		return ;
 	}
 	free(list);
 }
        
 void CircleList_Clear(CircleList* list) // O(1)
 {
 	TCircleList* sList = (TCircleList*)list;
 	if (sList == NULL)
 	{
 		return ;
 	}
 	sList->length = 0;
 	sList->header.next = NULL;
 	sList->slider = NULL;
 }
        
 int CircleList_Length(CircleList* list) // O(1)
 {
 	TCircleList* sList = (TCircleList*)list;
 	int ret = -1;
 	if (list == NULL)
 	{
 		return ret;
 	}
 	ret = sList->length;
 	return ret;
 }
        
 int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n)
 { 
 	int ret = 0, i=0;
 	TCircleList* sList = (TCircleList*)list;
        
 	if (list == NULL || node== NULL || pos<0)
 	{
 		return -1;
 	}
 	//if( ret )
 	{
 		//仍然需要引入富足指针变量
 		CircleListNode* current = (CircleListNode*)sList;
        
 		for(i=0; (i<pos) && (current->next != NULL); i++)
 		{
 			current = current->next;
 		}
        
 		//current->next 0号节点的地址
 		node->next = current->next; //1
 		current->next = node; //2
        
 		//若第一次插入节点
 		if( sList->length == 0 )
 		{
 			sList->slider = node;
 		}
 		sList->length++;
        
 		//注意点：
 		//若头插法 current仍然指向头部
 		//（原因是：跳0步，没有跳走）
 		if( current == (CircleListNode*)sList )
 		{
 			//获取最后一个元素，让最后一个元素指向新插入的节点
 			CircleListNode* last = CircleList_Get(sList, sList->length - 1); 
 			last->next = current->next; //3
 		}
 	}
        
 	return ret;
 }
        
 CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
 	int i = 0;
        
 	if (list==NULL || pos<0)
 	{
 		return NULL;
 	}
 	//if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )
 	{
 		CircleListNode* current = (CircleListNode*)sList;
        
 		for(i=0; i<pos; i++)
 		{
 			current = current->next;
 		}
        
 		ret = current->next;
 	}
        
 	return ret;
 }
        
 CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
 	int i = 0;
        
 	if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )
 	{
 		CircleListNode* current = (CircleListNode*)sList;
 		CircleListNode* last = NULL;
        
 		for(i=0; i<pos; i++)
 		{
 			current = current->next;
 		}
        
 		//若删除第一个元素（头结点）
 		if( current == (CircleListNode*)sList )
 		{
 			last = (CircleListNode*)CircleList_Get(sList, sList->length - 1);
 		}
        
 		//求要删除的元素
 		ret = current->next;
 		current->next = ret->next;
        
 		sList->length--;
        
 		//判断链表是否为空
 		if( last != NULL )
 		{
 			sList->header.next = ret->next;
 			last->next = ret->next;
 		}
        
 		//若删除的元素为游标所指的元素
 		if( sList->slider == ret )
 		{
 			sList->slider = ret->next;
 		}
        
 		//若删除元素后，链表长度为0
 		if( sList->length == 0 )
 		{
 			sList->header.next = NULL;
 			sList->slider = NULL;
 		}
 	}
        
 	return ret;
 }
        
 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) // O(n)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
 	int i = 0;
        
 	if( sList != NULL )
 	{
 		CircleListNode* current = (CircleListNode*)sList;
        		
 		//查找node在循环链表中的位置i
 		for(i=0; i<sList->length; i++)
 		{
 			if( current->next == node )
 			{
 				ret = current->next;
 				break;
 			}
        
 			current = current->next;
 		}
        		
 		//如果ret找到，根据i去删除	
 		if( ret != NULL )
 		{ 
 			CircleList_Delete(sList, i); //根据结点的值 求出结点的位置 ,根据位置删除元素
 		}
 	}
        
 	return ret;
 }
        
 CircleListNode* CircleList_Reset(CircleList* list) // O(1)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
        
 	if( sList != NULL )
 	{
 		sList->slider = sList->header.next;
 		ret = sList->slider;
 	}
        
 	return ret;
 }
        
 CircleListNode* CircleList_Current(CircleList* list) // O(1)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
        
 	if( sList != NULL )
 	{
 		ret = sList->slider;
 	}
        
 	return ret;
 }
        
 //把当前位置返回，并且游标下移
 //把当前游标所指的位置的元素返回出去
 //游标下移
 CircleListNode* CircleList_Next(CircleList* list) // O(1)
 {
 	TCircleList* sList = (TCircleList*)list;
 	CircleListNode* ret = NULL;
        
 	if( (sList != NULL) && (sList->slider != NULL) )
 	{
 		ret = sList->slider;
 		sList->slider = ret->next;
 	}
        
 	return ret;
 }
        
 //应用main.c
 #include <stdio.h>
 #include <stdlib.h>
 #include "CircleList.h"
        
 struct Value
 {
 	CircleListNode circlenode;
 	int v;
 };
        
 int main11()
 {
 	CircleList* list = CircleList_Create();
        
 	struct Value v1;
 	struct Value v2;
 	struct Value v3;
 	struct Value v4;
 	struct Value v5;
 	struct Value v6;
 	struct Value v7;
 	struct Value v8;
        
 	int i = 0;
 	v1.v = 1;
 	v2.v = 2;
 	v3.v = 3;
 	v4.v = 4;
 	v5.v = 5;
 	v6.v = 6;
 	v7.v = 7;
 	v8.v = 8;
        
 	CircleList_Insert(list, (CircleListNode*)&v1, 0);
 	CircleList_Insert(list, (CircleListNode*)&v2, 0);
 	CircleList_Insert(list, (CircleListNode*)&v3, 0);
 	CircleList_Insert(list, (CircleListNode*)&v4, 0);
        
 	for(i=0; i<2*CircleList_Length(list); i++) //怎么样证明是循环链表
 	{
 		struct Value* pv = (struct Value*)CircleList_Get(list, i);
        
 		printf("%d\n", pv->v);
 	}
        
 	while( CircleList_Length(list) > 0 )
 	{
 		CircleList_Delete(list, 0);
 	}
        
 	printf("\n");
        
 	CircleList_Destroy(list);
        
 	system("pause");
        
 	return 0;
 }

双向链表

  1. 为什么需要双向链表？
    1. 单链表的结点都只有一个指向下一个结点的指针
    2. 单链表的数据元素无法直接访问其前驱元素

    3. 逆序访问单链表中的元素是极其耗时的操作！

       len = LinkList_Length(list);
 for (i=len-1; len>=0; i--) //O(n)
 {
 LinkListNode *p = LinkList_Get(list, i); //O(n)
 //访问数据元素p中的元素
 //
 }
 //时间复杂度为O(n2)
  2. 定义：
    1. 在单链表的结点中增加一个指向其前驱的pre指针
  3. 特点：
    1. 双向链表拥有单链表的所有操作

  4. 结构图如下：

    图4

  5. 设计与分析

    1. 插入分析：

      图4

    2. 删除分析 图4

    3. 双向链表的新操作

       //直接指定删除链表中的某个数据元素
 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
 //将游标重置指向链表中的第一个数据元素
 DLinkListNode* DLinkList_Reset(DLinkList* list);
 //获取当前游标指向的数据元素
 DLinkListNode* DLinkList_Current(DLinkList* list);
 //将游标移动指向到链表中的下一个数据元素
 DLinkListNode* DLinkList_Next(DLinkList* list);
 //将游标移动指向到链表中的上一个数据元素
 DLinkListNode* DLinkList_Pre(DLinkList* list);
  6. 优点和缺点
    1. 优点：
      1. 双向链表在单链表的基础上增加了指向前驱的指针
      2. 功能上双向链表可以完全取代单链表的使用
      3. 双向链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素
    2. 缺点：
      1. 代码复杂

  7. 代码示例：

     //dLinkList.h
 #ifndef _MY_DLINKLIST_H_
 #define _MY_DLINKLIST_H_
    
 typedef void DLinkList;
    
 typedef struct _tag_DLinkListNode
 {
 	struct _tag_DLinkListNode* next;
 	struct _tag_DLinkListNode * pre;
 }DLinkListNode;
    
 DLinkList* DLinkList_Create();
    
 void DLinkList_Destroy(DLinkList* list);
    
 void DLinkList_Clear(DLinkList* list);
    
 int DLinkList_Length(DLinkList* list);
    
 int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);
    
 DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
    
 DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
    
 //-- add
 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
    
 DLinkListNode* DLinkList_Reset(DLinkList* list);
    
 DLinkListNode* DLinkList_Current(DLinkList* list);
    
 DLinkListNode* DLinkList_Next(DLinkList* list);
    
 DLinkListNode* DLinkList_Pre(DLinkList* list);
    
 #endif
    
 //dLinkList.c
 #include <stdio.h>
 #include <malloc.h>
 #include "DLinkList.h"
    
 typedef struct _tag_DLinkList
 {
 	DLinkListNode header;
 	DLinkListNode* slider;
 	int length;
 } TDLinkList;
    
 DLinkList* DLinkList_Create() 
 {
 	TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));
    
 	if( ret != NULL )
 	{
 		ret->length = 0;
 		ret->header.next = NULL;
 		ret->header.pre = NULL;
 		ret->slider = NULL;
 	}
    
 	return ret;
 }
    
 void DLinkList_Destroy(DLinkList* list) 
 {
 	if (list != NULL)
 	{
 		free(list);
 	}
 }
    
 void DLinkList_Clear(DLinkList* list) 
 {
 	TDLinkList* sList = (TDLinkList*)list;
    
 	if( sList != NULL )
 	{
 		sList->length = 0;
 		sList->header.next = NULL;
 		sList->header.pre = NULL;
 		sList->slider = NULL;
 	}
 }
    
 int DLinkList_Length(DLinkList* list) 
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	int ret = -1;
    
 	if( sList != NULL )
 	{
 		ret = sList->length;
 	}
    
 	return ret;
 }
    
 //大家一定要注意：教科书不会告诉你 项目上如何用；哪些点是项目的重点
 int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) 
 { 
 	int ret = 0, i = 0;
 	TDLinkList* sList = (TDLinkList*)list;
    	
 	if (list==NULL || node==NULL || pos<0)
 	{
 		return -1;
 	}
    	
 	{
 		DLinkListNode* current = (DLinkListNode*)sList;
 		DLinkListNode* next = NULL; //需要增加next指针
    
 		for(i=0; (i<pos) && (current->next != NULL); i++)
 		{
 			current = current->next;
 		}
    
 		next = current->next;
    
 		//步骤1-2
 		current->next = node;
 		node->next = next;
    
 		//步骤3-4 
 		if( next != NULL ) //当链表插入第一个元素，需要特殊处理
 		{
 			next->pre = node;
 		}
 		node->pre = current;
    
 		if( sList->length == 0 )
 		{
 			sList->slider = node; //当链表插入第一个元素处理游标
 		}
    
 		//若在0位置插入，需要特殊处理 新来结点next前pre指向null
 		if( current == (DLinkListNode*)sList )
 		{
 			node->pre = NULL;
 		}
    
 		sList->length++;
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_Get(DLinkList* list, int pos) 
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
 	int i = 0;
    
 	if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
 	{
 		DLinkListNode* current = (DLinkListNode*)sList;
    
 		for(i=0; i<pos; i++)
 		{
 			current = current->next;
 		}
    
 		ret = current->next;
 	}
    
 	return ret;
 }
    
 //插入第一个节点
 //删除的是最后一个结点，该是如何处理
 DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) 
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
 	int i = 0;
 	if (sList == NULL || pos <0 )
 	{
 		return NULL;
 	}
 	//if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
 	{
 		DLinkListNode* current = (DLinkListNode*)sList;
 		DLinkListNode* next = NULL; //需要增加next指针
    
 		for(i=0; i<pos; i++)
 		{
 			current = current->next;
 		}
    
 		ret = current->next;
 		next = ret->next;
    
 		//步骤1
 		current->next = next;
    
 		//步骤2 
 		if( next != NULL )//需要特殊处理
 		{
 			next->pre = current;
    
 			if( current == (DLinkListNode*)sList ) //若第0个位置，需要特殊处理
 			{
 				next->pre = NULL;
 			}
 		}
    
 		if( sList->slider == ret )
 		{
 			sList->slider = next;
 		}
    
 		sList->length--;
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
 	int i = 0;
    
 	if( sList != NULL )
 	{
 		DLinkListNode* current = (DLinkListNode*)sList;
    
 		for(i=0; i<sList->length; i++)
 		{
 			if( current->next == node )
 			{
 				ret = current->next;
 				break;
 			}
    
 			current = current->next;
 		}
    
 		if( ret != NULL )
 		{
 			DLinkList_Delete(sList, i);
 		}
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_Reset(DLinkList* list)
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
    
 	if( sList != NULL )
 	{
 		sList->slider = sList->header.next;
 		ret = sList->slider;
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_Current(DLinkList* list)
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
    
 	if( sList != NULL )
 	{
 		ret = sList->slider;
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_Next(DLinkList* list)
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
    
 	if( (sList != NULL) && (sList->slider != NULL) )
 	{
 		ret = sList->slider;
 		sList->slider = ret->next;
 	}
    
 	return ret;
 }
    
 DLinkListNode* DLinkList_Pre(DLinkList* list)
 {
 	TDLinkList* sList = (TDLinkList*)list;
 	DLinkListNode* ret = NULL;
    
 	if( (sList != NULL) && (sList->slider != NULL) )
 	{
 		ret = sList->slider;
 		sList->slider = ret->pre;
 	}
    
 	return ret;
 }
    
 //main.c
 #include <stdio.h>
 #include <stdlib.h>
 #include "DLinkList.h"
    
 struct Value
 {
 	DLinkListNode node;
 	int v;
 };
    
 int main()
 {
 	int i = 0;
 	DLinkList* list = DLinkList_Create();
 	struct Value* pv = NULL;
 	struct Value v1, v2, v3, v4, v5;
    
 	v1.v = 1;	v2.v = 2;	v3.v = 3;	v4.v = 4;
 	v5.v = 5;
    
 	DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));
 	DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));
 	DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));
 	DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));
 	DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));
    
 	for(i=0; i<DLinkList_Length(list); i++)
 	{
 		pv = (struct Value*)DLinkList_Get(list, i);
    
 		printf("%d\n", pv->v);
 	}
    
 	printf("\n");
    
 	DLinkList_Delete(list, DLinkList_Length(list)-1);
 	DLinkList_Delete(list, 0);
 	//DLinkList_Delete(list, 3);
    	
    
 	for(i=0; i<DLinkList_Length(list); i++)
 	{
 		pv = (struct Value*)DLinkList_Next(list);
    
 		printf("%d\n", pv->v);
 	}
    
 	printf("\n");
    
 	DLinkList_Reset(list);
 	DLinkList_Next(list);
    
 	pv = (struct Value*)DLinkList_Current(list);
    
 	printf("%d\n", pv->v);
    
 	DLinkList_DeleteNode(list, (DLinkListNode*)pv);
    
 	pv = (struct Value*)DLinkList_Current(list);
    
 	printf("%d\n", pv->v);
    
 	DLinkList_Pre(list);
    
 	pv = (struct Value*)DLinkList_Current(list);
    
 	printf("%d\n", pv->v);
    
 	printf("Length: %d\n", DLinkList_Length(list));
    
 	DLinkList_Destroy(list);
 	system("pause");
 	return 0;
 }

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents