Arect和他的……
数据结构第一次上机实验

单链表的操作

  • 创建单链表
  • 单链表排序
  • 打印并统计单链表(遍历)
  • 转化为双链表
#include<iostream>
#include<Windows.h>
#include<vector>
#include<string.h>
using namespace std;
//单链表
/******************************/
class link {
protected:
	int data = 0;
public:
	link* next = NULL;
	link();
	link(int num);
	link(bool a){}
	int OutPut() {
		return data;
	}
	void InPut(int a) {
		data = a;
	}
};
link* head = NULL;
link* tail = NULL;
link* DescendingOrderListHead = NULL;
link* DescendingOrderListTail = NULL;
link::link() {
	//如果链表为空,则头指针指向第一个结点
	if (head == NULL && tail == NULL) {
		head = this;
		tail = this;
	}
	//如果链表不为空,则连接前后
	else if (head != NULL && tail != NULL) {
		(*tail).next = this;
		tail = this;
	}
	else {
		system("cls");
		cout << "Wrong-1";
		system("pause");
	}
}
link::link(int num) {
	if (head == NULL && tail == NULL) {
		data = num;
		head = this;
		tail = this;
	}
	else if (head != NULL && tail != NULL) {
		data = num;
		(*tail).next = this;
		tail = this;
	}
	else {
		system("cls");
		cout << "Wrong-1";
		system("pause");
	}
}
//双向链表
/******************************************************************/
class link_ {
protected:
	int data = 0;
public:
	link_* left = NULL;
	link_* right = NULL;
	link_();
	link_(int a);
	int OutPut() {
		return data;
	}
	void InPut(int a) {
		data = a;
	}
};
link_* head_ = NULL;
link_* tail_ = NULL;
link_::link_() {
	//同上
	if (head_ == NULL && tail_ == NULL) {
		head_ = this;
		tail_ = this;
	}
	else if (head_ != NULL && tail_ != NULL) {
		(*tail_).right = this;
		(*this).left = tail_;
		tail_ = this;
	}
	else {
		system("cls");
		cout << "Wrong-2";
		system("pause");
	}
}
link_::link_(int a) {
	//同上
	if (head_ == NULL && tail_ == NULL) {
		data = a;
		head_ = this;
		tail_ = this;
	}
	else if (head_ != NULL && tail_ != NULL) {
		data = a;
		(*tail_).right = this;
		(*this).left = tail_;
		tail_ = this;
	}
	else {
		system("cls");
		cout << "Wrong-2";
		system("pause");
	}
}
//输出函数
/******************************************************************/
bool OutputLinkList(int a) {
	//正序单链
	if (a == 1) {
		if (head == NULL && tail == NULL) {
			cout << "单链表为空\n";
			return false;
		}
		else if (head != NULL && tail != NULL) {
			link* work = head;//工作指针,不影响链表
			while (work != NULL) {
				cout << " [" << (*work).OutPut() << "] ";
				//如果后面还有数据,则输出箭头
				if ((*work).next != NULL) {
					cout << "->";
				}
				work = (*work).next;
			}
			return true;
		}
	}
	//正序双链
	if (a == 2) {
		if (head_ == NULL && tail_ == NULL) {
			cout << "单链表为空\n";
			return false;
		}
		else if (head_ != NULL && tail_ != NULL) {
			link_* work_ = head_;//工作指针,不影响链表
			while (work_ != NULL) {
				cout << " [" << (*work_).OutPut() << "] ";
				//如果后面还有数据,则输出箭头
				if ((*work_).right != NULL) {
					cout << "->";
				}
				work_ = (*work_).right;
			}
			return true;
		}
	}
	//升序单链
	if (a == 3) {
		if (DescendingOrderListHead == NULL && DescendingOrderListTail == NULL) {
			cout << "单链表为空\n";
			return false;
		}
		else if (DescendingOrderListHead != NULL && DescendingOrderListTail != NULL) {
			link* work = DescendingOrderListHead;//工作指针,不影响链表
			while (work != NULL) {
				cout << " [" << (*work).OutPut() << "] ";
				//如果后面还有数据,则输出箭头
				if ((*work).next != NULL) {
					cout << "->";
				}
				work = (*work).next;
			}
			return true;
		}
	}
	//倒序单链
	if (a == 4) {
		//计数
		int i = 0;
		link* work = head;
		if (head == NULL) {
			cout << "-!-单链表为空,无法倒序输出";
			return false;
		}
		while (work != NULL) {
			i++;
			work = work->next;
		}
		int n = 0;
		for (; i > 0; i--) {
			work = head;
			n = i;
			while (n-- > 1) {
				work = work->next;
			}
			cout << " [" << work->OutPut() << "] ";
			if (i != 1) {
				cout << "->";
			}
		}
		return true;
	}
	//最值
	if (a == 5) {
		if (DescendingOrderListHead == NULL && DescendingOrderListTail == NULL) {
			cout << "单链表为空,无法输出最值\n";
			return false;
		}
		else if (DescendingOrderListHead != NULL && DescendingOrderListTail != NULL) {
			cout << "-!-最小值:" << DescendingOrderListHead->OutPut() << " 最大值:" << DescendingOrderListTail->OutPut();
		}
		return true;
	}
	return false;
}
bool OutPutList(link* work) {
	if (work->next != NULL) {
		OutPutList(work->next);
	}
	cout << " [" << work->OutPut() << "] ";
	if (work != head) {
		cout << "<-";
	}
	return true;
}
//降序排列
/******************************************************************/
bool Descending() {
	//首先复制
	if (head == NULL && tail == NULL) {
		cout << "单链表为空,无法降序排列\n";
		return false;
	}
	else if (head != NULL && tail != NULL) {
		link* work = head;//工作指针,不影响链表
		if (work != NULL) {
			DescendingOrderListHead = new(link)(true);//给头指针申请空间
			DescendingOrderListTail = DescendingOrderListHead;//同时赋值给尾指针
			DescendingOrderListHead->InPut((*work).OutPut());//得到数据
			work = (*work).next;
		}
		while (work != NULL) {
			(*DescendingOrderListTail).next = new(link)(true);//申请下一个空间
			DescendingOrderListTail = (*DescendingOrderListTail).next;//移动尾指针
			DescendingOrderListTail->InPut((*work).OutPut());
			work = (*work).next;
		}
	}
	bool judge = false;
	link* work1 = NULL;
	link* work2 = NULL;
	link* work3 = NULL;
	do {
		judge = false;
		//漏网之鱼
		if (DescendingOrderListHead == NULL) {
			return false;
		}
		work2 = DescendingOrderListHead;//比较1
		work1 = work2;//前指针
		work3 = work2->next;//比较2
		//只有一个数值无需比较
		if (work3 == NULL) {
			return true;
		}
		//单独比较前两个,因为头指针可能需要更改
		else {
			if (work2->OutPut() > work3->OutPut()) {
				work2->next = work3->next;
				work3->next = work2;
				DescendingOrderListHead = work3;
				work3 = work2->next;
				work1 = DescendingOrderListHead;
				judge = true;
			}
			else {
				work2 = work3;
				work3 = work3->next;
			}
		}
		//当到结尾时停止两两比较的循环
		while (work3 != NULL) {
			if (work2->OutPut() > work3->OutPut()) {
				work2->next = work3->next;
				work3->next = work2;
				work1->next = work3;
				work1 = work3;
				work3 = work2->next;
				judge = true;
			}
			else {
				work1 = work2;
				work2 = work3;
				work3 = work3->next;
			}
		}
	} while (judge);
	DescendingOrderListTail = DescendingOrderListHead;
	while (DescendingOrderListTail->next != NULL) {
		DescendingOrderListTail = DescendingOrderListTail->next;
	}
	return true;
}
//求和等
/******************************************************************/
bool sum() {
	int sum = 0;
	link* work = DescendingOrderListHead;
	int i = 0;
	while (work != NULL) {
		i++;
		sum += work->OutPut();
		work = work->next;
	}
	cout << "-!-链表长度为" << i << ",和为:" << sum;
	return true;
}
//双链表
/******************************************************************/
bool import_() {
	//首先复制
	if (head == NULL && tail == NULL) {
		cout << "单链表为空,无法导入至双链表\n";
		return false;
	}
	else if (head != NULL && tail != NULL) {
		link* work = head;//工作指针,不影响链表
		while (work != NULL) {
			new(link_)(work->OutPut());
			work = work->next;
		}
		return true;
	}
}
bool finder(int a) {
	link_* work = head_;
	int i = 0;
	while (work != NULL) {
		i++;
		if (work->OutPut() == a) {
			cout << "-!-数字" << a << "在双链表中第一次出现的位置是" << i << "\n";
			link_* work_ = work;
			while (work_ != NULL) {
				cout << " [" << work_->OutPut() << "] ";
				work_ = work_->right;
				if (work_ != work) {
					cout << "<->";
				}
			}
			work_ = head_;
			while (work_ != work) {
				cout << " [" << work_->OutPut() << "] ";
				work_ = work_->right;
				if (work_ != work) {
					cout << "<->";
				}
			}
			return true;
		}
		work = work->right;
	}
}
int main() {
	cout << "-!-创建单链表\n";
	cout << "-?-输入数据的个数为:";
	int a = 0;
	cin >> a;
	int TempData = 0;
	for (int i = 0; i < a; i++) {
		cout << ">>>" << i + 1 << "/" << a << "  ";
		cin >> TempData;
		new(link)(TempData);
	}
	cout << "-!-输入完成\n";
	OutputLinkList(1);
	cout << "\n" << "-!-排序";
	Descending();
	cout << "\n";
	OutputLinkList(3);
	cout << "\n";
	sum();
	cout << "\n";
	cout << "-!-倒序输出\n";
	OutPutList(head);
	cout << "\n";
	OutputLinkList(5);
	import_();
	cout << "\n";
	cout << "-?-查找的数据为:";
	cin >> a;
	finder(a);
	cout << "\n";
	system("pause");
}

验证KMP算法

纯属抄书的QAQ

#include<iostream>
#include<Windows.h>
#include<vector>
#include<string.h>
using namespace std;
vector<int> failF(string a) {
	vector<int> fail(a.size(), -1);//初始化失败函数
	int j = 0;
	for (unsigned int i = 1; i < a.size() - 1; i++) {
		j = fail[i - 1];
		while (a[i] != a[i + 1] && j >= 0) {
			j = fail[j];
		}//找到相同的位置
		if (a[i] == a[i + 1])
			fail[i] = j + 1;
		else fail[i] = -1;
	}
	return fail;
}

int main() {
	int i = 0, j = 0;
	string P, S;
	cout << "输入要搜索的字符串";
	cin >> P;
	cout << "输入被搜索的字符串";
	cin >> S;
	vector<int>F = failF(P);//计算失败函数
	while (j < S.size()) {
		if (P[i] == S[j]) {
			i++; j++;
			if (i + 1 == P.size() && P[i] == S[j]) {
				cout << "在" << j - P.size() + 1 << "处\n";
				i = 0;
				j++;
			}//找到一个后归零重找
		}//如果匹配则继续
		else if (i == 0) {
			j++;
		}//如果不匹配,则下一个
		else i = F[i - 1] + 1;//满足头尾不同则直接跳转
	}
}
首页      本地磁盘(C:)      数据结构第一次上机实验

INSPI

文章作者

保持学者的沉默与谦恭

发表评论

textsms
account_circle
email

Arect和他的……

数据结构第一次上机实验
单链表的操作 创建单链表单链表排序打印并统计单链表(遍历)转化为双链表 #include<iostream> #include<Windows.h> #include<vector> #include<string.h> using names…
扫描二维码继续阅读
2019-12-01