1.任务:
[问题描述]
使用链表设计一个保存信息的系统,该系统拥有类似区块链的设计以防止信息被轻易篡改。
该题目使用一个链表。信息保存在链表的每一个节点中,每个节点需要包含该节点的编号、信息和校验码。其中:
+ 每个节点的编号按照顺序递增,从0开始。
+ 节点中包含的信息是字符串,且每个字符的ASCII码范围为0-127,以\0结束。
+ 每个节点的校验码等于上一个节点的校验码+本节点的节点编号+本节点信息中字符串各字符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 Error\n");
return 0;
}
string H;
int len = rand() % 30 + 1;
for (int j = 0; j < len; ++j)
{
H += rand() % 92+33;
}
H += '\0';
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 += '\0';
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]!='\0';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 %d\n",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]!='\0';i++)
{
s=s+int(s2[i]);
}
p->next->DataAscii=s;
printf("是否需要修改校验码 是:1/否:0\n");
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
文章来源:https://www.toymoban.com/news/detail-415004.html
区块链测试结果3文章来源地址https://www.toymoban.com/news/detail-415004.html
到了这里,关于数据结构课程设计1: 区块链的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!