[数据结构与算法]链表结构描述哈希

我们要实现这样一个效果：

?

纵向排列的数据的个位数按顺序依次递增，每一个纵向节点都有一条分支，而且各自横向排列的分支的个位数都相同，并且横向分支排列按顺序从左往右依次递增。

所以需要创建下面这样的哈希链式结构

?它们由两部分不同类型的节点组成，一种是有两个指针指向的节点

?另一种是普通的节点，由数据域和指针域组成

接下来代码部分就是封装节点的过程

首先定义普通类型的结构体，包括数据域和指向下一个节点的指针

typedef struct Node {
	int dataNum;
	Node* next;
}*LPNODE;

?然后封装它们的创建对象以及初始化过程，方便后续创建新节点

LPNODE CreateNewNode(int dataNum) {
	LPNODE newNode = new Node;
	newNode->dataNum = dataNum;
	newNode->next = NULL;
	return newNode;
}

?然后就是两个指针的纵向结构体

包括结构体的数据域，指向Node类型的指针firstNode和指向下一个节点的指针

typedef struct kipListNode {
	int dataNum;
	Node* firstNode;
	kipListNode* next;
}*LPKINODE;

?同样的封装创建新节点和头节点的创建以及的初始化过程，这里采用头节点的方式排序，所以需要另外封装一个头节点的创建过程

LPKINODE CreatekipheadNode() {//头节点的封装
	LPKINODE headNode = new kipListNode;
	headNode->firstNode = NULL;
	headNode->next = NULL;
	return headNode;
}
LPKINODE CreatekipNewNode(int dataNum) {//新节点的封装
	LPKINODE newNode = new kipListNode;
	newNode->dataNum =dataNum;
	newNode->firstNode = NULL;
	newNode->next = NULL;
	return newNode;
}

?接下来就是创建链表的过程，同样用一个结构体封装一个链表结构

因为要求要对个位数进行排序。比如数字23，当divisor等于10的时候我们采用取余运算23%divisor

就能够获取个位数的数值了

typedef struct List {
	LPKINODE headNode;//头节点
	int CurSize;//当前节点个数
	int divisor;//哈希特殊处理的值
}*HASHLIST;

接下来就同样的封装创建过程

HASHLIST CreateHashList() {
	HASHLIST list = new List;
	list->CurSize = 0;
	list->divisor = 10;
	list->headNode= CreatekipheadNode();//初始化头节点
	return list;
}

然后就是哈希表的插入

通过头节点一个个地纵向查找

先获取到传进来的dataNum值的个位数

然后定义两个指针一个指向头节点，另一个指向头节点的下一个，两个指针循环移动，直到找到余数比自己大的值，然后把值在两个指针指向的位置中间插入

如果是找到了余数相等的位置，就把数据插入到分支后面

然后就是完成各个分支类的排序

如果纵向没有找到比它大的余数，就直接把数值插入到最后面

void insertHashTable(HASHLIST list,int dataNum) {
	int posData = dataNum % list->divisor;
	LPKINODE kipLeftNode = list->headNode;
	LPKINODE kipMoveNode = list->headNode->next;
	while (kipMoveNode && kipMoveNode->dataNum%list->divisor<posData) {
		kipLeftNode = kipMoveNode;
		kipMoveNode = kipMoveNode->next;
	}
	if (kipMoveNode !=NULL&&posData == kipMoveNode->dataNum % list->divisor) {
		if (kipMoveNode->firstNode == NULL)//如果结点的firstNode为NULL就直接插在后面
			kipMoveNode->firstNode = CreateNewNode(dataNum);
		else {
			LPNODE newNode = CreateNewNode(dataNum);
			if (dataNum < kipMoveNode->firstNode->dataNum) {//如果数值比firstNode指向的数值小，就插入入到它前面
				newNode->next = kipMoveNode->firstNode;
				kipMoveNode->firstNode = newNode;
			}
			else {
				LPNODE LeftNode = kipMoveNode->firstNode;
				LPNODE MoveNode = kipMoveNode->firstNode->next;//定义两个指针一直找
				while (MoveNode && MoveNode->dataNum < dataNum) {
					LeftNode = MoveNode;
					MoveNode = MoveNode->next;
				}//找到比它大的数值，就插入到两个值中间
				LeftNode->next = newNode;
				newNode->next = MoveNode;
			}
		}
		return;
		}
	LPKINODE kipnewNode = CreatekipNewNode(dataNum);//纵向链表的插入
		kipLeftNode->next = kipnewNode;
		kipnewNode->next = kipMoveNode;
		list->CurSize++;
}

最后就是链表的打印部分

定义两个移动的指针每次纵向指针移动到横向的头节点处，就循环打印横向的链表，循环往复，直到纵向链表的数据全部打印完毕

void printList(HASHLIST list) {
	LPKINODE kipMove = list->headNode->next;
	LPNODE pMove = kipMove->firstNode;
	while (kipMove) {
		pMove = kipMove->firstNode;
		printf("%d\t", kipMove->dataNum);
		while (pMove) {
			printf("%d\t", pMove->dataNum);
			pMove = pMove->next;
		}
		kipMove = kipMove->next;
		printf("\n");
	}
}

关注博主即可阅读全文