1、区块链（必做）（链表）

[问题描述]

使用链表设计一个保存信息的系统，该系统拥有类似区块链的设计以防止信息被轻易篡改。

该题目使用一个链表。信息保存在链表的每一个节点中，每个节点需要包含该节点的编号、信息和校验码。其中：

+ 每个节点的编号按照顺序递增，从0开始。

+ 节点中包含的信息是字符串，且每个字符的ASCII码范围为0-127，以\0结束。

+ 每个节点的校验码等于上一个节点的校验码+本节点的节点编号+本节点信息中字符串ASCII码之和 mod 113。

+ 首个节点的校验码则是本节点信息中字符串ASCII码之和 mod 113。

+ 有效的链表要求所有节点的校验码都能够成功按照上述算法得出。

[基本要求]

（1）要求从文本文件中输入；

（2）给定链表，检查链表是否有效。若无效，输出首个无效节点的节点编号；

（3）允许向链表中添加信息，要求保证链表始终有效；

（4）篡改一个有效的链表中特定编号的节点信息内容，保持篡改后的链表仍然有效。注意，可能需要篡改多个节点以达到此要求。

#include <iostream>
#include <fstream>
#include <queue>
#include <math.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>

#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0

#define MAXSIZE 128
#define QSIZE 128
#define QINCREMENT 128

using namespace std;

typedef string DataType; 
typedef int ElemType;
typedef int Status;

const char *fileName = "text1.txt";

typedef struct LNode{
	int order_node;
	DataType data;
	int check_node;
	struct LNode *next;	
}LNode,*LinkList;

typedef struct SListInfo{
	LinkList head;
	LinkList tail;
	LNode *pCurNode;
	int length;
}SListInfo;

Status ListLength(LinkList L){//单链表长度
	int n=0;
	LNode *p;
	p = L->next;
	while (p)
	{
		n++;
		p = p->next;
	}
	return n;
}

string st = "";

Status InitList(LinkList &L){//初始化单链表 
	L = (LNode*) malloc (sizeof(LNode));
	if(L == NULL) exit(OVERFLOW);
	L->next = NULL;
//	L->data = st;
//	L->order_node = 0;
//	L->check_node = 0;
	return OK; 
}

Status FirstInsert(LinkList &L){
	L->data = st;
	L->order_node = 0;
	L->check_node = 0;
}

Status InsertElem(LinkList &L, int i, DataType e){	//在第i个位置插入e

	LNode *s =(LNode*)malloc(sizeof(LNode));    //申请新的节点
	
	if(s == NULL)	exit(0);    //申请节点失败 
	
	for(int j = 0; j <MAXSIZE;j++){
		s->data = e;
	} 
	
	LNode *p;
	p = L->next;
	if(i == 1)
	{
		s->next = p;
		L->next = s;
	}
	else if(i>1  &&  i <= ListLength(L))
	{
		for(int j = 0;j<i-2;j++)
		{
			p = p->next;
		}
		s->next = p->next;
		p->next = s;
	}
	else if(i == ListLength(L)+1)
	{
		for(int j = 0;j<i-2;j++)
		{
			p = p->next;
		}
		p->next = s;
		s->next = NULL;
	}
	else
	{
		cout<<"No Position"<<endl;
	}
	return OK;
}

//string ss[MAXSIZE];

Status CreateList(LinkList &L){//在这里读文件string输入，e改为文件输入的string (思路) 
	
	int num = 0;
	int i,len = 0;
	DataType e;
	
	cout<<"scanf len again"<<endl;
	cin>>len;
/*
	fstream readFile;
	char input[MAXSIZE];
	readFile.open("text1.txt",ios::in);
	if(readFile.fail()){
		cout<<"open fail"<<endl;
		exit(0);
	}
	while(!readFile.eof()){
			readFile.getline(input,MAXSIZE+1,'\n');
		
			if(readFile.fail()){
					break;
			}
			ss[num] = input;
			cout<<ss[num]<<endl;
//			e = ss[num];
			num++;
	}
	*/ 
//	for(i = 1; i < len+1; i++){	
//		cout<<"scanf string e to insert"<<endl;
//		cin>>e;
//		InsertElem(L,i,e);
//	}
//	cout<<ss[0]<<endl;
//	readFile.close();
	return OK;
}

int after = 0;
//void CheckNode1(LinkList &L);

void CheckNode(LinkList &L,string str,int ord){
	
	L->data = str;
	L->order_node = ord;

	int sum = 0;
    for(int i = 0; i < L->data.length(); i++) {
        sum += L->data[i];
    }
	
	L->check_node = ( L->order_node + sum + after)%113;
	
	after = L->check_node;
	cout<<L->order_node<<" "<<L->check_node<<endl;
//	L = L->next;
//	L->order_node++;
//	CheckNode(L,str);
//	return 0;
}

int main()
{
	LinkList L;
	InitList(L);
	
	string s;
	int num = 0;
	int length;
	
//	cout<<"scanf len 3 for test"<<endl;
	cout<<"scanf the file's len"<<endl;
	cin>>length;
	
	CreateList(L);	
	fstream readFile;
	char input[MAXSIZE];
	readFile.open("text1.txt",ios::in);
	
	if(readFile.fail()){
		cout<<"open fail"<<endl;
		exit(0);
	}
		
	while(!readFile.eof()){
		readFile.getline(input,MAXSIZE+1,'\n');
		
		s = input;
		cout<<s<<endl;
		InsertElem(L,num+1,s);
		num++;
		if(readFile.fail()){
			break;
		}
	}	
//	CreateList(L);
/*
	L = L->next;
	cout<<L->data<<endl;
	cout<<L->order_node<<endl;
	CheckNode(L,L->data);
	L = L->next;
	L->order_node +=1;
	CheckNode(L,L->data);
	L = L->next;
	L->order_node +=1;
	CheckNode(L,L->data);
*/

	for(int i = 0; i < length; i++){
		L = L->next;
		L->order_node == i;
		CheckNode(L,L->data,i);
	}

//	cout<<L.check_node<<endl;
//	FILE *file = fopen(fileName,"rt");
//	for(int i = 0;i <MAXSIZE;i++){
//		char tmp = file.get();
	//	if(tmp == '\n'||tmp == ' '||EOF==true)
	//		return;
	//	L->data[i] = tmp;
//		cout<<tmp<<" ";
		 
//	}
	readFile.close();
	return 0;
}


/*
void CheckNode1(LinkList &L){
	int first = 0;
	
	L->order_node = first;
	std::ifstream file(fileName);
	
	char buff[1024];
/*	while(file.getline(buff,1024)){
		for(int i = 0; i <1024; i++){
			char tmp = buff[i];
			if(tmp == '\0'){
				break;
			}
			L->data[i] = tmp;
		}
	}

	file.open(fileName,ios::in);
	for(int i = 0;i <MAXSIZE;i++){
		char tmp = file.get();
		if(tmp == '\n'||tmp == ' '||EOF==true)
			return;
		L->data[i] = tmp;
		 
	}
	int sum1 = 0;
	for(int k = 0;k < L->data.length();k++){
		sum1 += L->data[k];
	}
	L->check_node = (0 + L->order_node + sum1 + after)%113;
	after = L->check_node;
	L = L->next;
	CheckNode1(L);
//	return L->chack_node;
}*/