【数据结构】链表(C++)

链表

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机中的内存位置不必须相邻，给每一个元素 加一个指针域，指向下一个元素的位置。

如下图所示:

链表的核心要素：

• 每个结点由数据域和指针域组成
• 指针域指向下一个结点的内存地址

单链表

链表的结点均单项指向下一个结点，形成一条单项访问的数据链。

相关接口实现

typedef int DataType;

//结构体定义
typedef struct LinkNode
{
	DataType data;
	struct LinkNode* next;
}LinkNode,LinkList;//LinkList为头结点
//初始化就是初始化头结点
bool initLinkList(LinkList*& linklist)
{
	linklist = new LinkList;
	if (!linklist)
	{
		return false;
	}
	linklist->next = NULL;
	return true;
}
//前插法
bool pushFront(LinkList*& L, LinkNode* node)
{
	if (!L || !node)
	{
		return false;
	}
	node->next = L->next;//头结点默认的next是NULL
	L->next = node;//与头结点相连接
	return true;
}
//尾插法
bool pushBack(LinkList*& L, LinkNode* node)
{
	if (!L || !node)
	{
		return false;
	}
	
	LinkNode* tempnode = L;//从头结点开始
	//通过循环找到最后一个结点
	while (tempnode->next)//直到循环到下一个结点为空，就进不去这个循环了，此时的tempnode就是最后一个结点
	{
		tempnode = tempnode->next;
	}
	//注意:如果只有一个头结点会直接到达这里。因为头结点的next指向空
	tempnode->next = node;
	node->next = NULL;
	return true;
}
//指定位置插入
bool insertLinkList(LinkList*& L,int index,DataType num)
{
	if (!L || index <= 0)
	{
		return false;
	}
	if (index == 1)
	{
		LinkNode* newnode = new LinkNode;
		newnode->data = num;
		pushFront(L, newnode);
		return true;
	}

	//循环遍历寻找
	int count = 0;
	LinkList* p, * newNode;
	p = L;

	while (p && count < index-1)//count<index-1条件控制，最后执行完这段代码，count就是index前一个位置
	{
		//p最后就是要插入位置的前一个结点
		p = p->next;
		count++;
	}

	//与新的结点链接
	newNode = new LinkNode;//生成新的结点
	newNode->data = num;
	newNode->next = p->next;  
	p->next = newNode;
	return true;

}
//访问指定位置的元素 
bool getElems(LinkList*& L, int postion,int& e)
{
	if (!L || postion <= 0 || !L->next)
	{
		return false;
	}
	//为什么这样写因为本链表头结点无数据
	int count = 0;
	LinkList* tempnode = L;
	while (count < postion  && tempnode)
	{
		count++;
		tempnode = tempnode->next;
	}
	//错误的postion必定导致tempnode为null
	if (!tempnode)
	{
		return false;
	}
	e = tempnode->data;
	return true;
}
//查找元素-按值
bool findElems(LinkList*& L, int e,int &index)
{
	if (!L || !L->next)
	{
		return false;
	}
	LinkList* tempnode = L;
	int count = 0;
	while (tempnode && tempnode->data != e)
	{
		tempnode = tempnode->next;
		count++;
	}
	//一遍下来没查到，tempnode为NULL
	if (!tempnode)
	{
		return false;
	}
	
	index = count;
	return true;

}
//删除元素-下标
bool deleteElems(LinkList*& L, int index)
{
	if (!L || !L->next || index <= 0)
	{
		return false;
	}
	int count = 0;                                                    
	LinkNode* tempnode = L;
	//补充:也能再创建个接口来遍历链表统计结点数
	while (tempnode && count != index-1)//找到要删除结点的前一个结点
	{
		count++;
		tempnode = tempnode->next;
	}
	if (!tempnode->next)//找到的前一个结点是最后一个结点，说明index的下标过大，reture false
	{
		return false;
	}
	//成功找到
	LinkNode* removeNode = tempnode->next;
	tempnode->next = removeNode->next;
	delete removeNode;
	return true;
}
//销毁链表
bool destoryList(LinkList*& L)
{
	LinkList* tempnode = L;
	while (tempnode)
	{
		L = L->next;
		delete tempnode;
		tempnode = L;//不断的往下取都结点，依次释放。
	}
	return true;
}

//打印输出表中元素
void printLinkList(LinkList*& L)
{
	LinkNode* p = NULL;//用它拿到第一个结点
	if (!L)
	{
		return;
	}
	p = L->next;
	while (p)
	{
		cout << p->data <<" ";
		p = p->next;//访问下一个结点 
	}
	cout << endl;
}

循环链表

在单链表的基础上让最后一个结点指向第一个结点。

相关接口实现

typedef int DataType;

//循环链表
typedef struct LinkNode
{
	DataType data;
	struct LinkNode* next;
}LinkNode, LinkList;
//初始化
bool inintLinkList(LinkList*& L)
{
	L = new LinkList;
	if (!L)
	{
		return false;
	}
	L->next = L;
	L->data = -1;
	return true;
}
//尾插法
bool pushBack(LinkList*& L,LinkNode *node)
{
	if (!L || !node)
	{
		return false;
	}
	//头结点的指针域指针指向自己的时候就是空的循环链表，本头结点不存数值
	if (L == L->next)
	{
		L->next = node;
		node->next = L;
	}
//非空的循坏链表
	LinkNode* tempnode = NULL;
	tempnode = L->next;
	while (tempnode->next != L)//找到最后一个结点
	{
		tempnode = tempnode->next;
	}
	tempnode->next = node;
	node->next = L;
	return true;
}
//头插法
bool pushFront(LinkList*& L, LinkNode* node)
{
	if (!L || !node)
	{
		return false;
	}
	LinkNode* tempnode = L->next;
	L->next = node;
	node->next = tempnode;
	return false;
}
//输出
void printList(LinkNode*& L)
{
	if (!L || L == L->next)
	{
		return;
	}



	LinkNode* tempnode = NULL;
	tempnode = L->next;
	while (tempnode != L)
	{
		cout << tempnode->data << " ";
		tempnode = tempnode->next;
	}
	cout << endl;
}

约瑟夫环问题

定一个数，从头开始依次报数，报道这个数的就delete,直到求出最后一个出局的编号是多少。

//约瑟夫环问题
//注意i 和 j的作用  
bool Joseph(LinkNode*& L,int val)
{

	LinkNode* p, * q;//p负责向下指，q负责与临时保存要删除的结点，链接到后面的结点
	p = L;

	if (!L || p->next == L)
	{
		return false;
	}
	if (val < 1)
	{
		return false;
	}
    
	int i = 0;//定位要删除结点的位置
    //通过i和j的不断增加，来定位位置
    //j是不断叠加的
	int j = 0;
	int times = 0;
	int num = 0;//记录最后一个出圈者的编号
	//该结点的值即为编号。
	do
	{
		//i为第一个要删除的结点位置
		i += val;
		
		//查找第i个结点，p指向该结点的上一个结点
        //能够进行这里，这个while循环的条件肯定是成立的
        //作用就是通过对j增加，然后与i进行比较。
		//注意是从头开始，头结点不存数值
        //每次遍历都能遍历到头结点
        //如果头结点存数值的话，那j的条件就得修改
        //随便想了一下，应该是j < i
        while (p->next)
		{
            //这两个判断的位置要注意一下
			if (p->next != L)
			{
				j++;
			}
			if (j >= i)
			{
				break;
			}
			p = p->next;
		}
		times++;//进行了几轮
		q = p->next;
		num = q->data;

		//重新连接起来
		p->next = q->next;
		delete q;//释放被删除结点空间
		printList(L);	
	} while (L->next != L);//删到最后就剩自己指向自己了
	cout << "最后被删除的结点位置是第" << num << "个" << endl;
	return true;
}

双向链表

在单链表的基础上添加一个指向前一个结点的指针。

相关接口实现

typedef int dataType;

typedef struct doubleNode
{
	dataType data;
	struct doubleNode* prev;
	struct doubleNode* next;
}LinkNode,LinkList;

//初始化
bool initLinkList(LinkList*& L)
{
	L = new LinkList;
	if (!L)
	{
		return false;
	}
	L->next = NULL;
	L->prev = NULL;
	L->data = -1;
	return true;
}
//尾插法
bool pushBack(LinkList*& L,LinkNode*& node)
{
	if (!L || !node)
	{
		return false;
	}
	LinkList* tempnode = NULL;
	tempnode = L;
	while (tempnode->next)
	{
		tempnode = tempnode->next;
	}
	//第一次进行尾插就直接来到这里
	tempnode->next = node;
	node->prev = tempnode;
	node->next = NULL;
	return true;
}
//前插
bool pushFront(LinkList* &L, LinkNode* &node)
{
	if (!L || !node)
	{
		return false;
	}
	
	if (L->next == NULL)
	{
		L->next = node;
		node->next = NULL;
		node->prev = L;
	}
	else
	{
		LinkNode* tempnode = NULL;
		tempnode = L->next;
		L->next = node;
		node->prev = L;
		node->next = tempnode;
		tempnode->prev = node;
	}

	return true;
}


//打印输出
void printLinkList(LinkList*& L)
{
	if (!L || !L->next)
	{
		return ;
	}
	LinkList* tempnode = NULL;
	tempnode = L->next;
	while (tempnode)
	{
		cout << tempnode->data << " ";
		tempnode = tempnode->next;
	}
	cout << endl;
}
//指定位置插入元素
bool insertLinkList(LinkList*& L,int index,int num)
{
	if (!L || !L->next || index < 1)
	{
		return false;
	}

	int  count = 1;
	LinkNode* tempnode = NULL;
	tempnode = L->next;
	while (tempnode)
	{
		if (count == index)
		{
			break;
		}
		tempnode = tempnode->next;
		count++;
	}
	if (!tempnode)
	{
		return false;
	}
	LinkNode* newnode = new LinkNode;
	newnode->data = num;
	LinkNode* tempnodeII = tempnode->prev;
	tempnodeII->next = newnode;
	newnode->prev = tempnodeII;
	newnode->next = tempnode;
	tempnode->prev = newnode;
	return true;
}

//删除指定位置元素
bool deleteLinkList(LinkList*& L, int index)
{
	if (!L || !L->next || index < 1)
	{
		return false;
	}
	
	int count = 1;
	LinkNode* tempnode = NULL;
	tempnode = L->next;
	//同在指定位置插入元素,先定位到这个结点
	while (tempnode)
	{
		if (index == count)
		{
			break;
		}
		count++;
		tempnode = tempnode->next;
	}
	if (!tempnode->next)
	{
		tempnode->prev->next = NULL;
		delete tempnode;
	}
	else
	{
		tempnode->prev->next = tempnode->next;
		tempnode->next->prev = tempnode->prev;
		delete tempnode;
	}
	return true;
}

//得到某个位置的值
bool getElems(LinkList*& L, int index, int& e)
{
	if (!L || !L->next || index < 1)
	{
		return false;
	}
	int  count = 1;
	LinkNode* tempnode = NULL;
	tempnode = L->next;
	while (tempnode)
	{
		if (count == index)
		{
			break;
		}
		tempnode = tempnode->next;
		count++;
	}
	if (!tempnode)
	{
		return false;
	}
	e = tempnode->data;
	return true;
}
//销毁
void  destoryLinkList(LinkList*& L)
{
	LinkNode* tempnode = NULL;
	tempnode = L;
	//找到下一个，删除前一个、从前往后删
	while (tempnode)
	{
		//L移动到真正的第一个结点
		L = L->next;
		//删除他原来的
		delete tempnode;

		tempnode = L;
	}
}

实际应用

Linux内核共享双向链表

在 linux 内核中，有大量的数据结构需要用到双向链表，例如进程、文件、模块、页面等。

若采用双向链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都

要设计插入、删除等操作函数。因为用来维持链表的 next 和 prev 指针指向对应类型的对

象，因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。

有没有一种方式让多个链表共享同一套链表操作呢？

——将结点中的指针域和数据域分离。

例如:

typedef struct LinkNode
{
	struct LinkNode* next;
	struct LinkNode* prev;
}LinkNode;

typedef	struct
{
	int fd;
	time_t timeout;
	LinkNode node;//挂件
}ConnTimeOut;

特殊访问：

——取到结构体中挂件的的偏移量，得到结构体的地址，然后进行访问。

ConnTimeOut* ct = new ConnTimeOut;
ct->fd = 3;
LinkNode* p = &(ct->node);
int offset = offsetof(ConnTimeOut, node);//node成员在内存中距结构体起始位置16个字节
ConnTimeOut* tmp = (ConnTimeOut*)((size_t)p - offset);
cout <<tmp->fd;

//相关接口示例
bool initLinkNode(LinkNode& L)
{
	
	L.next = NULL;
	L.prev = NULL;

	return true;
}
int main(void)
{
	ConnTimeOut* cL = NULL;
	//初始化一个空的双向链表
	cL = new ConnTimeOut;
	cL->fd = -1;
	initLinkNode(cL->node);

	return 0;
}

怎么个共享法呢?

重新解释：

将一个结点中的指针域剥离出来，创建一个新的结构体，来存放这个指针域，也就是说结构体嵌套。不同的结点(结构体数据内容不同，但是都有这个剥离出来的指针域。)，使用同一个接口进行操作，靠的就是他们中相同的”指针域”结构体，就是对这个结构体中的”指针域结构体”进行操作。

例如：
不同的结构体，但是但是他们都有上面LinkNode node这个挂件，那么他们就共用同一个初始化指针指向的函数。

传递这个共有的内容给函数，这个函数对他们进行操作。

例如: 将结点链接起来。不同链表使用同一个函数进行插入操作。