1.任務：

[問題描述]

使用鏈表設計一個保存信息的系統(tǒng)，該系統(tǒng)擁有類似區(qū)塊鏈的設計以防止信息被輕易篡改。

該題目使用一個鏈表。信息保存在鏈表的每一個節(jié)點中，每個節(jié)點需要包含該節(jié)點的編號、信息和校驗碼。其中：

+ 每個節(jié)點的編號按照順序遞增，從0開始。

+ 節(jié)點中包含的信息是字符串，且每個字符的ASCII碼范圍為0-127，以\0結(jié)束。

+ 每個節(jié)點的校驗碼等于上一個節(jié)點的校驗碼+本節(jié)點的節(jié)點編號+本節(jié)點信息中字符串各字符ASCII碼之和 mod 113。

+ 首個節(jié)點的校驗碼則是本節(jié)點信息中字符串各字符ASCII碼之和 mod 113。

+ 有效的鏈表要求所有節(jié)點的校驗碼都能夠成功按照上述算法得出。

[基本要求]

（1）要求從文本文件中輸入；

（2）給定鏈表，檢查鏈表是否有效。若無效，輸出首個無效節(jié)點的節(jié)點編號；

（3）允許向鏈表中添加信息，要求保證鏈表始終有效；

（4）篡改一個有效的鏈表中特定編號的節(jié)點信息內(nèi)容，保持篡改后的鏈表仍然有效。注意，可能需要篡改多個節(jié)點以達到此要求。

2.采用的數(shù)據(jù)結(jié)構(gòu)：

采用單鏈表

3.算法設計思想：

? ? ? ? 使用rand函數(shù)隨機在文檔中生成區(qū)塊鏈內(nèi)容，隨后從文件中讀入內(nèi)容。對于區(qū)塊鏈的校驗碼進行計算和校對。當鏈表中元素的發(fā)生添加與修改的操作時，同時對于各結(jié)點的校驗碼進行改動?？臻g復雜度：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));                      //隨機生成區(qū)塊鏈內(nèi)容 

	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)                    //增加數(shù)據(jù) 
{
	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<<"新增的結(jié)點為：\n";
	cout<<q->code<<" "<<q->data<<" "<<q->DataAscii<<" "<<q->check<<endl;
		
}

void Correct(LinkList &L)                              //修改指定位置數(shù)據(jù) 
{
	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.修改特定編號的結(jié)點內(nèi)容"<<endl;
		cout<<"3.輸出鏈表各個結(jié)點內(nèi)容.\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.源程序測試數(shù)據(jù)及結(jié)果

區(qū)塊鏈測試用例

?區(qū)塊鏈測試結(jié)果1

區(qū)塊鏈測試結(jié)果2

區(qū)塊鏈測試結(jié)果3文章來源地址http://www.zghlxwxcb.cn/news/detail-415004.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)課程設計1： 區(qū)塊鏈的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！