《目录》
简介建模
辅助方法
初始化出错处理空间申请迭代器
链表算法
尾插遍历头插尾删头删按值插入 查找求长度按值删除排序清除与销毁逆置
单链表代双链表数组转换为循环双链表二叉树转换为循环双链表双链表实现快排双链表的大数计算
简介
以 C++ 的 STL 的 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;
};
辅助方法
辅助方法会多次调用，所以先实现出来。
初始化
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;
}
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
排序，实在不推荐用于链表。效率不高，建议转给数组排序，再转回来。
尾插
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;
}
}
单链表代双链表
每个结点都有俩个指针，结点多了占用内存会比较多。
思路来源于：《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
