数据结构课程设计1： 区块链

1.任务：

[问题描述]

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

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

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

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

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

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

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

[基本要求]

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

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

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

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

2.采用的数据结构：

采用单链表

3.算法设计思想：

        使用rand函数随机在文档中生成区块链内容，随后从文件中读入内容。对于区块链的校验码进行计算和校对。当链表中元素的发生添加与修改的操作时，同时对于各结点的校验码进行改动。空间复杂度：S(n)=O(n)，时间复杂度T(n)=O(n^2)。

4.源程序：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <sstream>
#include <ctime>
using namespace std;

typedef struct LNode
{
	int code;
	string data;
	int DataAscii;
	int check;
	LNode *next;
}*LinkList,LNode;

int num=0;
int Create()
{
	srand((unsigned)time(NULL));                      //随机生成区块链内容 

	ofstream out;
	out.open("demo1.txt", ios::out);
	if (!out.is_open()) 
	{
		printf("Init Errorn");
		return 0;
	}
    string H;
	int len = rand() % 30 + 1;
	for (int j = 0; j < len; ++j) 
	{
		H += rand() % 92+33;
	}
	H += '';
	out << H; 
	for (int i = 1; i < 1000; ++i) 
	{
		string str;
		int len = rand() % 30 + 1;
		for (int j = 0; j < len; ++j) 
		{
			str += rand() % 92+33;
		}
		str += '';
		out << endl<< str ;
	}
	out.close();                                      //在文档中生成完毕 
}

int input(LinkList &L)
{
	ifstream infile;
	char ch;
	infile.open("demo1.txt",ios::in);
	LNode *p=L;
	int asc=0;
	if(infile)
	{
		while(!infile.eof())
		{
			LNode *newNode=new LNode;
			p->next=newNode;
			p=p->next;
			p->next=NULL;
	    	p->code=num;
	    	num++;
			getline(infile,p->data);
			string k=p->data;
	        int s=0;
	        for(int i=0;k[i]!='';i++)
	        {
	        	s=s+int(k[i]);
        	}
            p->DataAscii=s;
            asc=(asc+s+num-1)%113;                  //计算校验码 
			p->check=asc;
		}
	}
	else
	{
		printf("打开失败.n");
		return 0;
	}
	infile.close();
	p=L->next;
	printf("链表的编号、信息的ASCII码和校验码依次为：n");
	while(p)
	{
		printf("%d %d %dn",p->code,p->DataAscii,p->check);
		p=p->next;
	}
	printf("--------------------------------------------------n");
}

void AddData(LNode* p,string s)                    //增加数据 
{
	LNode *t = p;
	while (t->next != NULL)
	{
		t=t->next;
	}
	int a=t->check;
	LNode* q = new LNode;
	q->code = num;
	num++;
	q->data = s;
	int sum = 0;
	for (int i = 0; i < q->data.size(); ++i)
	{
		sum += q->data[i];
	}
	q->DataAscii=sum;
	q->check = (sum + q->code + a) % 113;
	t->next = q;
	q->next = NULL;
	cout << "添加完成！n";
	cout<<"新增的结点为：n";
	cout<<q->code<<" "<<q->data<<" "<<q->DataAscii<<" "<<q->check<<endl;
		
}

void Correct(LinkList &L)                              //修改指定位置数据 
{
	printf("请输入需要修改的位置:n");
	int place;
	scanf("%d",&place); 
	LNode *p;
	p=L;
	for(int i=0;i<place;i++)
	{
		p=p->next;
	}
	cout << "请输入修改后的的信息:n";
	string s2="";
	cin>>s2;
	p->next->data=s2;
	int s=0;
	for(int i=0;s2[i]!='';i++)
	{
		s=s+int(s2[i]);
    }
    p->next->DataAscii=s;
	printf("是否需要修改校验码 是：1/否：0n");
	int h;
	cin>>h;
	if(h==1)
	{
		while(p->next)
		{
			p->next->check=(p->next->DataAscii+p->check+p->next->code) % 113;
			p=p->next;
		}
		cout<<"校验码修改完成！n";
	}			
}

int CheckCode(LinkList &L)                                 //核验校验码 
{
	LNode *p;
	p=L->next;
	while(p->next)
	{
		if(p->next->check==(p->next->DataAscii+p->check+p->next->code) % 113)
		{
			p=p->next;
			continue;
		}
		else
		{
			cout<<"该链表存在错误！"<<endl;
			return 0;
		}
	}
	cout<<"该链表有效！"<<endl;
}

void CorrectChoice(LinkList &L)                              //校正所有校验码 
{
	LNode *p;
	p=L;
	p->next->check=(p->next->DataAscii+p->next->code) % 113;
	p=p->next;
	while(p->next)
	{
		p->next->check=(p->next->DataAscii+p->check+p->next->code) % 113;
		p=p->next;
	}
	cout<<"校验码全部修改完成！n";
}

int main() 
{
	LinkList L;
	L=new LNode;
	L->next=NULL;
	Create();
	input(L);
	while(1)
	{
		system("pause");
		system("cls");
		cout << "请选择操作类型：n1.向链表中添加信息.n2.修改特定编号的结点内容"<<endl;
		cout<<"3.输出链表各个结点内容.n4.检查链表是否有效.n5.校正所有校验码.n6.退出n";
		int choice;
		scanf("%d",&choice);
		if(choice==1)
		{ 
		    LNode *p;
		    p=L;
		    string data;
			cout << "请输入要添加的信息:n";
			cin >> data;
			AddData(p, data);	
		} 
		else if(choice==2)
		{
			Correct(L);
		}
		else if(choice==3)
		{
			LNode *p;
			p=L->next;
	        printf("链表的编号、信息、信息的ASCII码和校验码依次为：n");
	        while(p)
        	{
	        	cout<<p->code<<" "<<p->data<<" "<<p->DataAscii<<" "<<p->check<<endl;
	        	p=p->next;
	        }
	        cout<<"输出完成！n";
		}
		else if(choice==4)
		{
			CheckCode(L);
		}
		else if(choice==5)
		{
			CorrectChoice(L);
		}
		else if(choice==6)
		{
			break;
		}
	}
	return 0;
}

5.源程序测试数据及结果

区块链测试用例

 区块链测试结果1

区块链测试结果2

区块链测试结果3