首页 > 其他分享 >双链表

双链表

时间：2023-06-05 16:34:01浏览次数：73  
标签：Node head next tail 双链 NULL data


                                                                                    《目录》

  • 简介
  • 建模

辅助方法

  • 初始化
  • 出错处理
  • 空间申请
  • 迭代器

链表算法

  • 尾插
  • 遍历
  • 头插
  • 尾删
  • 头删
  • 按值插入 
  • 查找
  • 求长度
  • 按值删除
  • 排序
  • 清除与销毁
  • 逆置
  1. 单链表代双链表
  2. 数组转换为循环双链表
  3. 二叉树转换为循环双链表
  4. 双链表实现快排
  5. 双链表的大数计算



简介

      以 C++ 的 STL 的 list 为参考原型，实现一些偏门或看起来挺好玩的双链表。

 


双链表_List

list的原型图示

 

      first 、last、size 是此链表的头指针。

      first、last 的数据类型是 指针，first 表示一直指向链表的第一个结点，last 一直指向链表的最后一个结点。

      size 表示当前链表的结点数，上图中 size = 4，不计算头结点(没有存储数据的结点)。

      first 指向的无数据的结点为链表的头结点，设置 TA 可以简化代码，

  • 无论链表是否为 空 ，头指针始终保持不变。如果不设置头结点，空链表时需要单独写代码。

       首元结点：第一个有数据的结点，就是上图数字 1 那个。

  • 首元结点的地址存放在头结点的指针域中，对该结点的操作与其 ta 结点一致。如果不设置头结点，删除首元结点时，需要修改头指针。

建模

      此双链表的数据模型：头指针模型 + 结点模型。

      搭积木从小到大建模，结点模型：

#define T int
typedef struct Node
{
	T data;
	struct Node *prio, *next;    // 结点的前驱、后继  
}Node, *p_Node;

        头指针建模：

typedef struct Head
{
	size_t size;
        p_Node first, last;    // 头指针的首尾指针
}List;

   C++类版，上面是C语言结构体版：

template< typename T>
class List{
public:
    struct Node{    // 类中类(结构体)
    public:
        T data;
        Node *prio, *next;
    };
private:
    Node* Head;
    size_t size;
 };

辅助方法

       辅助方法会多次调用，所以先实现出来。

     初始化


双链表_链表_02

C版 

// C版
void Init(List *L)
{
	Node *s = (Node *)malloc(sizeof(Node));
	check_mem(s);
	L->first = L->last = s;
	L->last->next = NULL;
	L->first->prio = NULL;
	L->size = 0;
	
error:
    if(s)
         free(s), s = NULL;
}


双链表_链表_03

C++版 

// C++版，构造初始化，size = 0，头结点指向自己
List( ) : size( 0 )
{
    	Head = ( Node * ) malloc ( sizeof( Node ) );
        // 判断申请空间失败，错误处理代码在 "空间申请"
        // pass 
    	Head -> next = Head -> prio = Head;
}

 

出错处理

       这是我编写程序时，会用的一个错误处理的文件。

       使用只需要引入头文件即可，我把 ta 命名为 stddbg.h，当然也可以使用断言 assert.h 等 。

       作者：泽德 A.肖，热爱吉他、写作、敲代码。

#ifndef __dbg_h__
#define __dbg_h__

#include <stdio.h>
#include <errno.h>
#include <string.h>

/* 为 C++ 调用做准备，命名倾扎。
#ifdef __cplusplus
extern "C" {
#endif
*/

#ifdef NDEBUG
#define debug(M, ...)
#else
#define debug(M, ...) fprintf(stderr, "DEBUG %s:%d: " M "\n",\
        __FILE__, __LINE__, ##__VA_ARGS__)
#endif

#define clean_errno() (errno == 0 ? "None" : strerror(errno))

#define log_err(M, ...) fprintf(stderr,\
        "[ERROR] (%s:%d: errno: %s) " M "\n", __FILE__, __LINE__,\
        clean_errno(), ##__VA_ARGS__)

#define log_warn(M, ...) fprintf(stderr,\
        "[WARN] (%s:%d: errno: %s) " M "\n",\
        __FILE__, __LINE__, clean_errno(), ##__VA_ARGS__)

#define log_info(M, ...) fprintf(stderr, "[INFO] (%s:%d) " M "\n",\
        __FILE__, __LINE__, ##__VA_ARGS__)

#define check(A, M, ...) if(!(A)) {\
    log_err(M, ##__VA_ARGS__); errno=0; goto error; }

#define sentinel(M, ...)  { log_err(M, ##__VA_ARGS__);\
    errno=0; goto error; }

#define check_mem(A) check((A), "Out of memory.")

#define check_debug(A, M, ...) if(!(A)) { debug(M, ##__VA_ARGS__);\
    errno=0; goto error; }

#endif

/*
#ifdef __cplusplus
}
#endif
*/

  比起直接断言等错误处理，这会让代码更加紧凑有调理，大幅度减少出错时的代码量，速度更快，跨平台。

  但对小白不友好， 宏魔法用的很多(以 log宏、check宏 为主)。

  配套书籍：《苯方法学C语言》

空间申请

// C
Node *Buy_node(T x)
{
	Node *s = (Node *)malloc(sizeof(Node));
	check_mem(s);
	s->data = x;
	s->next = s->prio = NULL;
	return s;
	
error:
    if(s)
         free(s), s = NULL;
}
// C++ 
Node *Buy_node( )
{
    	Node * S = ( Node * ) malloc ( sizeof( Node ) );
    	// 申请空间失败，错误处理，也可以用断言等代替。 
    	check_mem(S)    // check_mem 是检查内存
        S->next = S->prio = S;    // 采用的C++类版，如果是C结构体版改成 first、last
    	return S;

error:           // 与 check_mem 配套，里面有 goto 跳转语句，error 是跳转标签。
    if(S) 
      free(S); S = NULL;    
                 // 特别注意，goto语句(check_mem) 和 error的标签 之间 不能有 定义变量的操作 e.g. int a = 9, 但声明可 int a
    return S;    // 需要返回值，返回类型为 Node*，因为分配空间失败，S == NULL（指向NULL）
}

   STL 的空间申请不同于只申请了一个结点。

// C++ STL山寨
Node *Buy_node(Node *Narg = 0, Node *Parg = 0)
{       // Narg : next argument, Parg : prev argumet
    	Node * S = ( Node * ) malloc ( sizeof( Node ) );
    	// 申请空间失败，错误处理
    	check_mem(S);

        S -> next = ( Narg ? Narg : S );
        S -> prio = ( Parg ? Parg : S );

        // 调用 Buy_node( ) 时，无参数就只是申请了一个结点。
        // 调用 Buy_node(Head, Head->prio) 时，不仅申请了结点并把结点的前驱和后继指针与链表连接了起来。
    	return S;
   error:
        if(S) 
          free(S); S = NULL;
        return S; // S 指向了 NULL
}

迭代器

pass

链表算法

  •          尾插，push_back
  •          头插，push_front
  •          遍历，show_list
  •          尾删，pop_back
  •          头删，pop_front
  •          按值插入，insert_val
  •          按值删除，delete_val
  •          查找，find
  •          排序，sort
  •          求结点数，length
  •          逆置，resver

双链表的求长度、查找元素、遍历等，只需要涉及一个指针所以代码和单链表相同，主要是插入、删除需要特别注意。

许多链表算法都是建立在插入和删除方法上，代码实现时建议先实现插入和删除。

双链表中任意一个结点p，ta 前驱的后继、后继的前驱都是自己。

p->next->prio = p->prio->next = p

排序，实在不推荐用于链表。效率不高，建议转给数组排序，再转回来。

尾插


双链表_链表_04

C版 

// C版
void push_back(List *L, T x)
{
	Node *s = Buy_node(x);
	check_mem(s);
	s->prio = L->last;
	L->last->next = s;
	L->last = s;
	L->size++;

error:
    return;    // 不做处理，出错系统会提示。
}
// C++
void push_back( const T& v )
{
    	Node * S = Buy_node();
    	check_mem(S);

    	S -> data = v;
    	S -> prio = Head -> prio;
    	Head -> prio -> next = S;    // C++的头指针采用 prio、next，而不是C版的 first、last
    	S -> next = Head;
    	Head -> prio = S;
    	
    	size ++;
    	
error:
    return;    // 不做处理，出错系统会提示。
}

  结合STL的空间申请方法，可精简代码。

// C++ STL山寨版   
void push_back( const T& v )
{
    	Node * S = Buy_node(Head, Head->prio);
    	check_mem(S);

    	S -> data = v;
    	S->prio->next = S;
    	Head->prio = S;

    	size ++;
    	
error:
    return;    // 不做处理，出错系统会提示。
}

遍历

// C版
void show(List *L)
{
	Node *p = L->first->next;    // p 指向第一个结点(带数据的结点)
	while(p != NULL)
	{
		printf("%d <---> ",p->data);
		p = p->next;
	}
	printf("Nul.\n");
}

头插

     头插比尾插需要考虑的地方多点，申请好结点后再把结点放到头结点和第一个结点(存储数据)之间。

     需要考虑结点 4 个指针，为了保证正确衔接。

     不能先断开头结点与第一个结点的连接，所以先修改新结点的后继指针和第一个结点的前驱指针。

     头插有俩种情况，链表为空或者非空，空链表只有一个头结点。

void push_front(List *L, T x)
{
	Node *s = Buy_node(x);
        check_mem(s);
	if(L->first == L->last)    // 空链表，只有一个头结点
	{
		L->last = s;
	}else{
		s->next = L->first->next;
		s->next->prio = s;
	}

	s->prio = L->first;
	L->first->next = s;

	L->size++;

error:
    return;    // 不做处理，出错系统会提示。
}

尾删

void pop_back(List *L)
{
	if(L->size == 0)    // 空链表，size 不计头结点
		return;

	Node *p = L->first;
	while(p->next != L->last)    // 到最后的结点
		p = p->next;

	free(L->last);
	L->last = p;
	L->last->next = NULL;
	L->size--;
}

头删

    头删分俩种情况：只有一个结点和有 n(n>1, n为整数) 个结点。

    空链表的情况即不算头结点没有一个结点，不需要考虑。

void pop_front(List *L)
{
	if(L->size == 0)
		return;
	Node *p = L->first->next;

	if(L->first->next == L->last)    // 只有一个结点，链表非空。
	{
		L->last = L->first;
		L->last->next = NULL;
	}else{
		p->next->prio = L->first;
		L->first->next = p->next;
	}
	free(p);
	L->size--;
}

 按值插入 

void insert_val(List *L, T x)
{
	Node *p = L->first;
	while(p->next != NULL && p->next->data < x)
		p = p->next;

	if(p->next == NULL)        // 插入值比链表中所有值都大
	{
		push_back(L,x);    // 尾插
	}else{
		Node *s = Buy_node(x);
		s->next = p->next;
		s->next->prio = s;
		s->prio = p;
		p->next = s;
		L->size ++;
	}
}

查找

Node* find(List *L, T key)
{
	Node *p = L->first->next;
	while(p != NULL && p->data != key)
		p = p->next;
	return p;
}

求长度

int length(List *L)
{
    return L->size;
}

 按值删除

void delete_val(List *L, T key)
{
	if(L->size == 0)
		return;
	Node *p = find(L, key);
	if(p == NULL)
	{
		puts("输入的值不存在");
		return;
	}

	if(p == L->last)
	{
		L->last = p->prio;
		L->last->next = NULL;
	}else{
		p->next->prio = p->prio;
		p->prio->next = p->next;
	}

	free(p);
        L->size --;
}

排序

void sort(List *L)
{
	if(L->size==0 || L->size==1)
		return;

	Node *s = L->first->next;
	Node *q = s->next;

	L->last = s;
	L->last->next = NULL;

	while(q != NULL)
	{
		s = q;
		q = q->next;

		Node *p = L->first;
		while(p->next != NULL && p->next->data < s->data)
			p = p->next;
		
		if(p->next == NULL)
		{
			s->next = NULL;
			s->prio = L->last;
			L->last->next = s;
			L->last = s;
		}else{
			s->next = p->next;
			s->next->prio = s;
			s->prio = p;
			p->next = s;
		}
	}
}

清除与销毁

void clear(List *L)
{
	if(L->size == 0)
		return;

	Node *p = L->first->next;
	while(p != NULL)
	{
		if(p == L->last)
		{
			L->last = L->first;
			L->last->next = NULL;
		}else{
			p->next->prio = L->first;
			L->first->next = p->next;
		}
		
		free(p);
		p = L->first->next;
	}
	L->size = 0;
}

void destroy(List *L)
{
	clear(L);
	free(L->first);
	L->first = L->last = NULL;
}

逆置

void resver(List *L)
{
	if(L->size==0 || L->size==1)
		return;

	Node *p = L->first->next;
	Node *q = p->next;

	L->last = p;
	L->last->next = NULL;

	while(q != NULL)
	{
		p = q;
		q = q->next;

		p->next = L->first->next;
		p->next->prio = p;
		p->prio = L->first;
		L->first->next = p;
	}
}

单链表代双链表

       每个结点都有俩个指针，结点多了占用内存会比较多。

双链表_结点_05

双链表_链表_06

思路来源于：《https://ke.qq.com/webcourse/index.html#cid=242707&term_id=100286249&taid=1573341010048019&vid=p14218kdqdk》 。

#include <stdio.h> 
#include <stdlib.h>
#include <stddbg.h>   // 错误处理的文件，文件内容在开头，stddbg.h 文件在目录里的 出错处理。

typedef struct Node 
{ 
	int data; 
	struct Node* npx; 
}node;

// 定义俩个指针，具体作用参考图示。
node * Head = NULL;
node *Tail = NULL;

struct Node* XOR (struct Node *a, struct Node *b) 
{ 
    // node : pl  <-->  p <-->  pr ( 左 中 右 )
    // p->next = pl ^ pr  
    // head->next = NULL ^ pr
    // tail->next = pl ^ NULL
    return (struct Node*) ((unsigned long) (a) ^ (unsigned long) (b)); 
} 

void insert(struct Node **head_ref, int data) 
{ 
	struct Node *s = (struct Node *) malloc (sizeof (struct Node) );
        check_mem(s);    // 判断内存是否正常，stddbg 函数 
	s->data = data; 
    
	s->npx = XOR(*head_ref, NULL); 
    
	if (*head_ref != NULL) 
	{ 
		struct Node* next = XOR((*head_ref)->npx, NULL); 
		(*head_ref)->npx = XOR(s, next); 
		Tail = s;
	}else{
		Head = s;
	}

	*head_ref = s; 

error:
    return;
} 

void _print (struct Node *Head) 
{ 
	struct Node *p = Head; 
	struct Node *pl = NULL; 
	struct Node *pr;

        printf ("从头到尾遍历:  Head");

	while (p != Tail){
		printf (" -> %d", p->data); 

		pr = XOR (pl, p->npx); 
		pl = p; 
		p = pr; 
	}
	printf(" -> %d\n", p->data);
} 

void print_ (struct Node *Tail) 
{ 
	struct Node *p = Tail;
	struct Node *pr = NULL;
	struct Node *pl;

        printf("从尾到头遍历:  Tail");
	while (p != Head) 
	{ 
		printf (" -> %d", p->data); 

		pl = XOR (pr, p->npx); 
		pr = p; 
		p = pl;
	} 
	printf(" -> %d\n", p->data);
} 


int main( int argc, const  char *argv[] ) 
{ 
	struct Node *head = NULL; 
	insert(&head, 1); 
	insert(&head, 2); 
	insert(&head, 3); 
	_print(Head); 
   
        struct Node *tail = NULL;
        insert(&tail, 1); 
	insert(&tail, 2); 
	insert(&tail, 3);
	print_(Tail);
	
	
	
	free(head), head = NULL;
        free(Tail), Tail = NULL;
	free(tail), tail = NULL;
	free(Head), Head = NULL;
	
	return (0); 
}

数组转换为循环双链表

#include<iostream> 
using namespace std; 

struct node 
{ 
	int data; 
	struct node *next; 
	struct node *prev; 
}; 

struct node* getNode() 
{ 
	return ((struct node *)malloc(sizeof(struct node))); 
} 

int show(struct node *temp) 
{ 
	struct node *t = temp; 
	if(temp == NULL) 
		return 0; 
	else
	{ 
		cout << "The list is: "; 
		
		while(temp->next != t) 
		{ 
			cout<<temp->data<<" "; 
			temp = temp->next; 
		} 
		
		cout << temp->data; 
		
		return 1; 
	} 
} 

// 数组转链表
void createList(int arr[], int n, struct node **start) 
{ 
	struct node *newNode, *temp; 

	for(int i=0; i<n; i++) 
	{ 
		newNode = getNode(); 
		
		newNode->data = arr[i]; 
		
		// 如果是第一个元素，则将节点prev和next设置为start，因为ta是循环的
		if( i==0 ) 
		{ 
			*start = newNode; 
			newNode->prev = *start; 
			newNode->next = *start; 
		}else{ 
			// 查找最后一个结点
			temp = (*start)->prev; 
			
			// 添加最后一个结点
			// 组成圆形即循环双链表
			temp->next = newNode; 
			newNode->next = *start; 
			newNode->prev = temp; 
			temp = *start; 
			temp->prev = newNode; 
		} 
	} 
} 

int main() 
{ 
	int arr[] = {1,2,3,4,5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	
	struct node *start = NULL; 
	
	createList(arr, n, &start); 
	
	show(start); 
	
	return 0; 
}

link

二叉树转换为循环双链表

  • 节点中的左右指针分别用作转换的循环链接列表中的前一个和下一个指针。
  • List中节点的顺序必须与给定二进制树的顺序相同。
  • Inorder遍历的第一个节点必须是循环列表的头节点。
#include<iostream> 
using namespace std; 

struct Node 
{ 
	struct Node *left, *right; 
	int data; 
}; 

Node *concatenate(Node *leftList, Node *rightList) 
{ 
	// 如果一个链表为空，就返回另一个。
	if (leftList == NULL) 
		return rightList; 
	if (rightList == NULL) 
		return leftList; 

	// 存储左链表的最后一个结点
	Node *leftLast = leftList->left; 

	// 存储右链表的最后一个结点
	Node *rightLast = rightList->left; 

	// 选择连接左链表的最后一个结点和右链表的第一个结点
	leftLast->right = rightList; 
	rightList->left = leftLast; 

	// 第一个结点指向链表的最后一个结点
	leftList->left = rightLast; 

	// 最后一个结点指向链表的第一个结点
	rightLast->right = leftList; 

	return leftList; 
} 


Node *bTreeToCList(Node *root) 
{ 
	if (root == NULL) 
		return NULL; 

	// 递归左右子树
	Node *left = bTreeToCList(root->left); 
	Node *right = bTreeToCList(root->right); 
	
	root->left = root->right = root; 

	// Step 1 将左侧链表与当前结点的链表连接起来
	// Step 2 将 concatenate 返回的链表和右链表连接起来
	return concatenate(concatenate(left, root), right); 
} 

void show(Node *head) 
{ 
	cout << "Circular Linked List is :\n"; 
	Node *itr = head; 
	do
	{ 
		cout << itr->data <<" "; 
		itr = itr->right; 
	} while (head!=itr); 
	cout << "\n"; 
} 


// 创建新结点并返回地址
Node *newNode(int data) 
{ 
	Node *temp = new Node(); 
	temp->data = data; 
	temp->left = temp->right = NULL; 
	return temp; 
} 

int main() 
{ 
	Node *root = newNode(10); 
	root->left = newNode(12); 
	root->right = newNode(15); 
	root->left->left = newNode(25); 
	root->left->right = newNode(30); 
	root->right->left = newNode(36); 

	Node *head = bTreeToCList(root); 
	show(head); 

	return 0; 
}

link

双链表实现快排

        链表排序面临成千上万的数据时，速度十分缓慢。建议先转放到数组排序再转回链表。

#include <iostream> 
using namespace std;

struct Node 
{ 
	int data; 
	Node *next; 
	Node *prev; 
}; 

void swap ( int* a, int* b )  
{ int t = *a; *a = *b; *b = t; } 

// 查找链表最后一个元素
Node *lastNode(Node *root) 
{ 
	while (root && root->next) 
		root = root->next; 
	return root; 
} 

/*
将最后一个元素视为枢轴，
把主元(做基准)放在它的位置
排序数组中的正确位置，
所有小于枢轴的元素放到枢轴的左边
所有大于枢纽的元素放到枢纽的右边
*/
Node* partition(Node *l, Node *h) 
{ 
	// 设定主元
	int x = h->data; 

	// 同数组的 i = l-1
	Node *i = l->prev; 

	// 同数组的 for (int j = l; j <= h- 1; j++)
	for (Node *j = l; j != h; j = j->next) 
	{ 
		if (j->data <= x) 
		{ 
			// 同数组的 i++ 
			i = (i == NULL)? l : i->next; 

			swap(&(i->data), &(j->data)); 
		} 
	} 
	i = (i == NULL)? l : i->next;   // 同 i++ 
	swap(&(i->data), &(h->data)); 
	return i; 
} 

/* 递归版快排 */
void _quickSort(Node* l, Node *h) 
{ 
	if (h != NULL && l != h && l != h->next) 
	{ 
		Node *p = partition(l, h); 
		_quickSort(l, p->prev); 
		_quickSort(p->next, h); 
	} 
} 

void quickSort(Node *head) 
{ 
	Node *h = lastNode(head); 

	_quickSort(head, h); 
} 

void show(Node *head) 
{ 
	while (head) 
	{ 
		cout << head->data << " "; 
		head = head->next; 
	} 
	cout << endl; 
} 

void push(Node** head_ref, int new_data) 
{ 
	Node* new_node = new Node; 
	new_node->data = new_data; 
	
	new_node->prev = NULL; 

	new_node->next = (*head_ref); 
	
	if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; 

	(*head_ref) = new_node; 
} 

int main() 
{ 
	Node *a = NULL; 
	push(&a, 5); 
	push(&a, 20); 
	push(&a, 4); 
	push(&a, 3); 
	push(&a, 30); 

	cout << "Linked List before sorting \n"; 
	show(a); 

	quickSort(a); 

	cout << "Linked List after sorting \n"; 
	show(a); 

	return 0; 
}

link

双链表的大数计算

#include <iostream> 
using namespace std; 
 
struct node { 
    int data; 
    struct node* next, * prev; 
    node(int); 
}; 
  
node::node(int val) 
{ 
    data = val; 
    next = prev = NULL; 
} 
  
class HugeInt { 
public: 
    HugeInt(); 
    ~HugeInt(); 
 
    void insertInFront(int);
  
    void insertInEnd(int); 
  
    void display(); 
  
    int length(); 
    void add(HugeInt*, HugeInt*); 
    void mul(HugeInt*, HugeInt*); 
    void dif(HugeInt*, HugeInt*); 
    void quo(HugeInt*, HugeInt*); 
    int cmp(HugeInt*, HugeInt*); 
    node* head; 
    node* tail; 
    int size; 
}; 
  
HugeInt::HugeInt() 
{ 
    head = tail = NULL; 
    size = 0; 
} 
 
void HugeInt::insertInFront(int value) 
{ 
    node* temp = new node(value); 
      
    if (head == NULL) 
        head = tail = temp; 
    else { 
        head->prev = temp; 
        temp->next = head; 
        head = temp; 
    } 
    size++; 
} 
  
void HugeInt::insertInEnd(int value) 
{ 
    node* temp = new node(value); 
      
    if (tail == NULL) 
        head = tail = temp; 
    else { 
        tail->next = temp; 
        temp->prev = tail; 
        tail = temp; 
    } 
    size++; 
} 
void HugeInt::display() 
{ 
    node* temp = head; 
      
    while (temp != NULL) { 
        cout << temp->data; 
        temp = temp->next; 
    } 
} 
  
int HugeInt::length() 
{ 
    return size; 
} 
 
void HugeInt::add(HugeInt* a, HugeInt* b) 
{ 
    int c = 0, s; 
    HugeInt* a1 = new HugeInt(*a); 
    HugeInt* b1 = new HugeInt(*b); 
  
    this->head = NULL; 
    this->tail = NULL; 
    this->size = 0; 
  
    while (a1->tail != NULL || b1->tail != NULL) { 
        if (a1->tail != NULL && b1->tail != NULL) { 
            s = ((a1->tail->data) + (b1->tail->data) + c) % 10; 
            c = ((a1->tail->data) + (b1->tail->data) + c) / 10; 
            a1->tail = a1->tail->prev; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail == NULL && b1->tail != NULL) { 
            s = ((b1->tail->data) + c) % 10; 
            c = ((b1->tail->data) + c) / 10; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail != NULL && b1->tail == NULL) { 
            s = ((a1->tail->data) + c) % 10; 
            c = ((a1->tail->data) + c) / 10; 
            a1->tail = a1->tail->prev; 
        } 
          
        insertInFront(s); 
    } 
 
    if (c != 0) 
        insertInFront(c); 
} 
void HugeInt::dif(HugeInt* a, HugeInt* b) 
{ 
    int c = 0, s; 
    HugeInt* a1 = new HugeInt(*a); 
    HugeInt* b1 = new HugeInt(*b); 
  
    this->head = NULL; 
    this->tail = NULL; 
    this->size = 0; 
      
    while (a1->tail != NULL || b1->tail != NULL) { 
        if (a1->tail != NULL && b1->tail != NULL) { 
            if ((a1->tail->data) + c >= (b1->tail->data)) { 
                s = ((a1->tail->data) + c - (b1->tail->data)); 
                c = 0; 
            } 
            else { 
                s = ((a1->tail->data) + c + 10 - (b1->tail->data)); 
                c = -1; 
            } 
            a1->tail = a1->tail->prev; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail != NULL && b1->tail == NULL) { 
            if (a1->tail->data >= 1) { 
                s = ((a1->tail->data) + c); 
                c = 0; 
            } 
            else { 
                if (c != 0) { 
                    s = ((a1->tail->data) + 10 + c); 
                    c = -1; 
                } 
                else
                    s = a1->tail->data; 
            } 
            a1->tail = a1->tail->prev; 
        } 
        insertInFront(s); 
    } 
} 
int HugeInt::cmp(HugeInt* a, HugeInt* b) 
{ 
    if (a->size != b->size) 
        return ((a->size > b->size) ? 1 : 0); 
    else { 
        HugeInt* a1 = new HugeInt(*a); 
        HugeInt* b1 = new HugeInt(*b); 
        while (a1->head != NULL && b1->head != NULL) { 
            if (a1->head->data > b1->head->data) 
                return 1; 
            else if (a1->head->data < b1->head->data) 
                return 0; 
            else { 
                a1->head = a1->head->next; 
                b1->head = b1->head->next; 
            } 
        } 
        return 2; 
    } 
} 
 
void HugeInt::quo(HugeInt* a, HugeInt* b) 
{ 
    HugeInt* a1 = new HugeInt(*a); 
    HugeInt* b1 = new HugeInt(*b); 
    HugeInt* ex = new HugeInt(); 
    HugeInt* mp = new HugeInt(); 
    HugeInt* pr = new HugeInt(); 
    int i = 0; 
    for (i = 0; i < b1->size; i++) { 
        ex->insertInEnd(a1->head->data); 
        a1->head = a1->head->next; 
    } 
  
    for (i = 0; i < 10; i++) { 
        HugeInt* b2 = new HugeInt(*b); 
        mp->insertInEnd(i); 
        pr->mul(b2, mp); 
        if (!cmp(ex, pr)) 
            break; 
        mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
    } 
  
    mp->head = mp->tail = NULL; 
    pr->head = pr->tail = NULL; 
    mp->size = pr->size = 0; 
  
    mp->insertInEnd(i - 1); 
    pr->mul(b1, mp); 
    ex->dif(ex, pr); 
    insertInEnd(i - 1); 
    mp->head = mp->tail = NULL; 
    pr->head = pr->tail = NULL; 
    mp->size = pr->size = 0; 
  
    while (a1->head != NULL) { 
        ex->insertInEnd(a1->head->data); 
        while (ex->head->data == 0) { 
            ex->head = ex->head->next; 
            ex->size--; 
        } 
        for (i = 0; i < 10; i++) { 
            HugeInt* b2 = new HugeInt(*b); 
            mp->insertInEnd(i); 
            pr->mul(b2, mp); 
            if (!cmp(ex, pr)) 
                break; 
            mp->head = mp->tail = NULL; 
            pr->head = pr->tail = NULL; 
            mp->size = pr->size = 0; 
        } 
  mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
  
        mp->insertInEnd(i - 1); 
        pr->mul(b1, mp); 
        ex->dif(ex, pr); 
  
        insertInEnd(i - 1); 
  
        mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
  
        a1->head = a1->head->next; 
    } 
  
    cout << endl 
        << "\nModulus :" << endl; 
    ex->display(); 
} 

void HugeInt::mul(HugeInt* a, HugeInt* b) 
{ 
    int k = 0, i; 
    HugeInt* tpro = new HugeInt(); 
    while (b->tail != NULL) { 
        int c = 0, s = 0; 
        HugeInt* temp = new HugeInt(*a); 
        HugeInt* pro = new HugeInt(); 
        while (temp->tail != NULL) { 
            s = ((temp->tail->data) * (b->tail->data) + c) % 10; 
            c = ((temp->tail->data) * (b->tail->data) + c) / 10; 
            pro->insertInFront(s); 
            temp->tail = temp->tail->prev; 
        } 
        if (c != 0) 
            pro->insertInFront(c); 
  
        for (i = 0; i < k; i++) 
            pro->insertInEnd(0); 
  
        add(this, pro); 
        k++; 
        b->tail = b->tail->prev; 
        pro->head = pro->tail = NULL; 
        pro->size = 0; 
    } 
} 
  


struct Node 
{
    int data; 
    struct Node* next, * prev; 
    Node(int); 
}; 

Node::Node(int val) 
{ 
    data = val; 
    next = prev = NULL; 
} 
  
class HugeIntLL 
{ 
public: 
    HugeIntLL(); 
    ~HugeIntLL(); 
 
    void insertInFront(int); 
  
    void insertInEnd(int); 
  
    void display(); 
  
    int length(); 
    void add(HugeIntLL*, HugeIntLL*); 
    void mul(HugeIntLL*, HugeIntLL*); 
    void dif(HugeIntLL*, HugeIntLL*); 
    void quo(HugeIntLL*, HugeIntLL*); 
    int cmp(HugeIntLL*, HugeIntLL*); 
    Node* head; 
    Node* tail; 
    int size; 
}; 
  
HugeIntLL::HugeIntLL() 
{ 
    head = tail = NULL; 
    size = 0; 
} 
  
void HugeIntLL::insertInFront(int value) 
{ 
    Node* temp = new Node(value); 
  
    if (head == NULL) 
        head = tail = temp; 
    else
    { 
        head->prev = temp; 
        temp->next = head; 
        head = temp; 
    } 
    size++; 
} 

void HugeIntLL::insertInEnd(int value) 
{ 
    Node* temp = new Node(value); 
  
    if (tail == NULL) 
        head = tail = temp; 
    else
    { 
        tail->next = temp; 
        temp->prev = tail; 
        tail = temp; 
    } 
    size++; 
} 
void HugeIntLL::display() 
{ 
    Node* temp = head; 
  
    while (temp != NULL) 
    { 
        cout << temp->data; 
        temp = temp->next; 
    } 
} 
int HugeIntLL::length() 
{ 
    return size; 
} 
  
void HugeIntLL::add(HugeIntLL* a, HugeIntLL* b) 
{ 
    int c = 0, s; 
    HugeIntLL* a1 = new HugeIntLL(*a); 
    HugeIntLL* b1 = new HugeIntLL(*b); 
  
    this->head = NULL; 
    this->tail = NULL; 
    this->size = 0; 
  
    while (a1->tail != NULL || b1->tail != NULL) 
    { 
        if (a1->tail != NULL && b1->tail != NULL) 
        { 
            s = ((a1->tail->data) + (b1->tail->data) + c) % 10; 
            c = ((a1->tail->data) + (b1->tail->data) + c) / 10; 
            a1->tail = a1->tail->prev; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail == NULL && b1->tail != NULL) 
        { 
            s = ((b1->tail->data) + c) % 10; 
            c = ((b1->tail->data) + c) / 10; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail != NULL && b1->tail == NULL) 
        { 
            s = ((a1->tail->data) + c) % 10; 
            c = ((a1->tail->data) + c) / 10; 
            a1->tail = a1->tail->prev; 
        } 
 
        insertInFront(s); 
    } 
  
    if (c != 0) 
        insertInFront(c); 
} 
 
void HugeIntLL::dif(HugeIntLL* a, HugeIntLL* b) 
{ 
    int c = 0, s; 
    HugeIntLL* a1 = new HugeIntLL(*a); 
    HugeIntLL* b1 = new HugeIntLL(*b); 
  
    this->head = NULL; 
    this->tail = NULL; 
    this->size = 0; 
  
    while (a1->tail != NULL || b1->tail != NULL) 
    { 
        if (a1->tail != NULL && b1->tail != NULL) 
        { 
            if ((a1->tail->data) + c >= (b1->tail->data)) 
            { 
                s = ((a1->tail->data) + c - (b1->tail->data)); 
                c = 0; 
            } 
            else
            { 
                s = ((a1->tail->data) + c + 10 - (b1->tail->data)); 
                c = -1; 
            } 
            a1->tail = a1->tail->prev; 
            b1->tail = b1->tail->prev; 
        } 
        else if (a1->tail != NULL && b1->tail == NULL) 
        { 
            if (a1->tail->data >= 1) 
            { 
                s = ((a1->tail->data) + c); 
                c = 0; 
            } 
            else
            { 
                if (c != 0) 
                { 
                    s = ((a1->tail->data) + 10 + c); 
                    c = -1; 
                } 
                else
                    s = a1->tail->data; 
            } 
            a1->tail = a1->tail->prev; 
        } 
        insertInFront(s); 
    } 
} 
int HugeIntLL::cmp(HugeIntLL* a, HugeIntLL* b) 
{ 
    if (a->size != b->size) 
        return ((a->size > b->size) ? 1 : 0); 
  
    HugeIntLL* a1 = new HugeIntLL(*a); 
    HugeIntLL* b1 = new HugeIntLL(*b); 
    while (a1->head != NULL && b1->head != NULL) 
    { 
        if (a1->head->data > b1->head->data) 
            return 1; 
        else if (a1->head->data < b1->head->data) 
            return 0; 
        else
        { 
            a1->head = a1->head->next; 
            b1->head = b1->head->next; 
        } 
    } 
    return 2; 
} 

void HugeIntLL::quo(HugeIntLL* a, HugeIntLL* b) 
{ 
    HugeIntLL* a1 = new HugeIntLL(*a); 
    HugeIntLL* b1 = new HugeIntLL(*b); 
    HugeIntLL* ex = new HugeIntLL(); 
    HugeIntLL* mp = new HugeIntLL(); 
    HugeIntLL* pr = new HugeIntLL(); 
    int i = 0; 
    for (i = 0; i < b1->size; i++) 
    { 
        ex->insertInEnd(a1->head->data); 
        a1->head = a1->head->next; 
    } 
  
    for (i = 0; i < 10; i++) 
    { 
        HugeIntLL* b2 = new HugeIntLL(*b); 
        mp->insertInEnd(i); 
        pr->mul(b2, mp); 
        if (!cmp(ex, pr)) 
            break; 
        mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
    } 
  
    mp->head = mp->tail = NULL; 
    pr->head = pr->tail = NULL; 
    mp->size = pr->size = 0; 
  
    mp->insertInEnd(i - 1); 
    pr->mul(b1, mp); 
    ex->dif(ex, pr); 
    insertInEnd(i - 1); 
    mp->head = mp->tail = NULL; 
    pr->head = pr->tail = NULL; 
    mp->size = pr->size = 0; 
  
    while (a1->head != NULL) 
    { 
        ex->insertInEnd(a1->head->data); 
        while (ex->head->data == 0) 
        { 
            ex->head = ex->head->next; 
            ex->size--; 
        } 
        for (i = 0; i < 10; i++) 
        { 
            HugeIntLL* b2 = new HugeIntLL(*b); 
            mp->insertInEnd(i); 
            pr->mul(b2, mp); 
            if (!cmp(ex, pr)) 
                break; 
            mp->head = mp->tail = NULL; 
            pr->head = pr->tail = NULL; 
            mp->size = pr->size = 0; 
        } 
  
        mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
  
        mp->insertInEnd(i - 1); 
        pr->mul(b1, mp); 
        ex->dif(ex, pr); 
  
        insertInEnd(i - 1); 
  
        mp->head = mp->tail = NULL; 
        pr->head = pr->tail = NULL; 
        mp->size = pr->size = 0; 
  
        a1->head = a1->head->next; 
    } 
  
    cout << endl 
         << "\nModulus :" << endl; 
    ex->display(); 
} 
 
void HugeIntLL::mul(HugeIntLL* a, HugeIntLL* b) 
{ 
    int k = 0, i; 
    HugeIntLL* tpro = new HugeIntLL(); 
    while (b->tail != NULL) 
    { 
        int c = 0, s = 0; 
        HugeIntLL* temp = new HugeIntLL(*a); 
        HugeIntLL* pro = new HugeIntLL(); 
        while (temp->tail != NULL) 
        { 
            s = ((temp->tail->data) * (b->tail->data) + c) % 10; 
            c = ((temp->tail->data) * (b->tail->data) + c) / 10; 
            pro->insertInFront(s); 
            temp->tail = temp->tail->prev; 
        } 
        if (c != 0) 
            pro->insertInFront(c); 
  
        for (i = 0; i < k; i++) 
            pro->insertInEnd(0); 
  
        add(this, pro); 
        k++; 
        b->tail = b->tail->prev; 
        pro->head = pro->tail = NULL; 
        pro->size = 0; 
    } 
} 
int main() 
{ 
    HugeIntLL* m = new HugeIntLL(); 
    HugeIntLL* n = new HugeIntLL(); 
    HugeIntLL* s = new HugeIntLL(); 
    HugeIntLL* p = new HugeIntLL(); 
    HugeIntLL* d = new HugeIntLL(); 
    HugeIntLL* q = new HugeIntLL(); 
  
    string s1 = "12345678912345678912345678"
                 "9123456789123456789123456789"; 
    string s2 = "45678913456789123456789123456"
                 "789123456789123456789"; 
  
    for (int i = 0; i < s1.length(); i++) 
        m->insertInEnd(s1.at(i) - '0'); 
  
    for (int i = 0; i < s2.length(); i++) 
        n->insertInEnd(s2.at(i) - '0'); 
  
    HugeIntLL* m1 = new HugeIntLL(*m); 
    HugeIntLL* n1 = new HugeIntLL(*n); 
    HugeIntLL* m2 = new HugeIntLL(*m); 
    HugeIntLL* n2 = new HugeIntLL(*n); 
    HugeIntLL* m3 = new HugeIntLL(*m); 
    HugeIntLL* n3 = new HugeIntLL(*n); 
  
    cout << "Product :" << endl; 
    s->mul(m, n); 
    s->display(); 
    cout << endl; 
  
    cout << "Sum :" << endl; 
    p->add(m1, n1); 
    p->display(); 
    cout << endl; 
  
    cout << "Difference (m-n) : m>n:" << endl; 
  
    d->dif(m2, n2); 
    d->display(); 
    q->quo(m3, n3); 
    cout << endl; 
  
    cout << "Quotient :" << endl; 
    q->display(); 
    return 0; 
}

link

标签：Node,head,next,tail,双链,NULL,data
From： https://blog.51cto.com/u_13937572/6417562

相关文章

  • 初级数据结构--双链表、循环链表
    双链表结构体内含有两个指针域。相比单链表，双链表每个节点多了一个存储前一节点的指针。对节点的增加、删除操作比单链表便捷，不用独立指针记录前一节点voidInitDNodeList(DNode**D){ *D=(DNode*)malloc(sizeof(DNode)); if(!*D) return; (*D)->front=NULL; (*D)->nex......
  • 双链表和队列-->gcc编译
    双链表队列doublueList.h#include<stdlib.h>#include<stdio.h>#include<assert.h>#include<stdbool.h>typedefintLTDataType;typedefstructDList{ LTDataTypedata; structDList*next; structDList*prev;}LTNode;LTNode*init();......
  • P1160 队列安排-双链表
    碰到了一道题发现忘了数组模拟双链表怎么实现了，顺便复习了一下。然后解决问题。双链表模板题:实现一个双链表，双链表初始为空，支持 5 种操作：在最左侧插入一个数；在最右侧插入一个数；将第 k 个插入的数删除；在第 k 个插入的数左侧插入一个数；在第 k 个插入的数右侧插入一......
  • 用双链表实现双端队列
    //双链表publicstaticclassNode<V>{publicVvalue;publicNode<V>last;publicNode<V>next;publicNode(Vv){value=v;last=null;next=null;}}//双端队列前后皆可进出publicstaticclassMyDequ......
  • 单双链表
    单链表定义//单链表publicstaticclassNode{publicintvalue;publicNodenext;publicNode(intdata){value=data;}}单链表反转新增1、2、3三个节点publicstaticNodereverseLinkedList(Nodehead){Nodepre=null;Nodenext=......
  • 双链表
    双链表双链表有两个指针，一个指向前一个指向后，数组模拟链表实现思想双链表有两个指针，一个指向前一个指向后，故定义三个数组\(l[N],r[N],val[N]\)\(l[N]指向的是当前......
  • 基于API+MQ消息双链路数据同步中间件技术方案
    一、数据同步的背景及意义随着公司业务的发展，业务系统也会变得越来越复杂繁多，业务数据或分散、或冗余于各个业务系统中，增加了数据的管理难度和维护成本。因此，中心......
  • 双链表
    图示：  代码：  1importlombok.Data;23publicclassDoubleLinkedListTest{4publicstaticvoidmain(String[]args){5Doubl......
  • list双链表
    structlistnode{structlistnode*next;structlistnode*prev;void*data;};structlist_head{ structlist_head*next,*prev;};/*Linkedlistof......
  • 双链表实现双端队列
    双链表实现双端队列双端队列是一个从两端都可以进行进队出队的队列。代码：/***使用双链表实现双端队列*双端队列也就是在队列的两端都可以进行出队列以及入队列......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99