链表

数据结构课上机实验报告

编写一个程序 Linklist.cpp ，实现链表的各种基本运算和整体建表算法（假设链表的元素类型 ElemType 为 int ），并在此基础上设计一个主程序，完成如下功能：

• 构建基于动态分配内存的链表L，并初始化链表。
• 依次将 1Mints.txt 文件中的数据输入到链表中。
• 输出链表L长度。
• 判断链表L是否为空。
• 分别输出顺序表L的第 30、300、3000、30000、300000 个元素值，记录相应时间。
• 输出值为 -12345 的元素的位置。
• 依次在第 4、40、400、4000、40000、400000 个元素位置上插入整数 -10086 ，记录相应的时间。
• 依次删除在第 4、40、400、4000、40000、400000 个元素位置上的元素，记录相应的时间。
• 输出链表L的前 10 个元素。
• 释放链表L。

// LinkList.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<fstream>
#include<ctime>
#include <windows.h>
using namespace std;
typedef int ElemType;
const int N = 5e6 + 5;
ElemType a[N];
LARGE_INTEGER nFreq;

LARGE_INTEGER t1;

LARGE_INTEGER t2;

double dt;
typedef struct node{
	ElemType val;
	struct node *next;
	//node(int _val=0,node * _next=NULL):val(_val),next(_next){}
}Node;
void CreateHead(Node *&head){
	head = (Node *)malloc(sizeof(Node));
	if (head == NULL) {
		cout << "头节点内存分配失败" << endl;
		exit(1);
	}
	head->val = 0;
	head->next = NULL;
}
void InitLinkList(Node *&head,int n){
	Node *temp = head;
	for (int i = 0; i < n; i++)
	{
		Node * pnode = (Node *)malloc(sizeof(Node));
		if (pnode == NULL){
			cout << "节点内存分配失败" << endl;
			exit(1);
		}
		pnode->val = a[i];
		pnode->next = NULL;
		temp->next = pnode;
		temp = temp->next;
	}
	cout << "输入成功!" << endl<<endl;
	head->val = n;
}
int ListLength(Node *L) {
	return (L->val);
}
bool ListEmpty(Node *L) {
	return (L->val == 0);
}
void DestroyList(Node *&head){
	Node *temp = head;
	while (head != NULL)
	{
		head = head->next;
		free(temp);
		temp = head;
	}
}
bool DispList(Node *head,int n) {
	int length = ListLength(head);
	if (length < n) return false;
	Node *cur = head;
	for (int i = 0; i < n; i++) {
		cur = cur->next;
		printf("%d ", cur->val);
	}
	printf("\n\n");
	return true;
}
bool GetElem(Node *head, int i, ElemType &e) {
	int length = ListLength(head);
	if (length <= 0) return false;
	if (i<1 || i>length) return false;
	Node *temp = head;
	for (int j = 0; j < i; j++)
	{
		temp = temp->next;
	}
	e = temp->val;
	return true;
}
int LocateElem(Node *head, ElemType e) {
	int i = 1;
	int length = ListLength(head);
	if (length <= 0) return -1;
	Node *temp = head->next;
	while (i <= length&&temp->val != e) {
		i++;
		temp = temp->next;
	}
if (i > length) return -1;
	else return i;
}
bool ListInsert(Node *&head, int i, ElemType e) {
	int length = ListLength(head);
	if (i<1 || i>length + 1) return false;
	Node *pre = head;
	for (int j = 1; j < i&&pre!=NULL; j++)
	{
		pre = pre->next;
	}
	if (pre == NULL){
		return false;
	}
	else{
		Node *cur = (Node *)malloc(sizeof(Node));
		if (cur == NULL) return false;
		cur->val = e;
		cur->next = pre->next;
		pre->next = cur;
		head->val++;
		return true;
	}
}
bool ListDelete(Node *&head, int i, ElemType &e) {
	int length = ListLength(head);
	if (length == 0) return false;
	if (i<1 || i>length) return false;
	Node *cur = head, *pre = head;
	for (int j = 1; j <= i; j++)
	{
		if (cur == NULL || pre == NULL) return false;
		pre = cur;
		cur = cur->next;
	}
	if (cur == NULL || pre == NULL) return false;
	else{
		e = cur->val;
		pre->next = cur->next;
		free(cur);
		head->val--;
		return true;
	}
}
void GetElemTime(Node *&head)
{
	ElemType e;
	for (int i = 30; i <= 300000; i *= 10)
	{
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&t1);
		GetElem(head, i, e);
		QueryPerformanceCounter(&t2);
		dt = (t2.QuadPart - t1.QuadPart) / (double)nFreq.QuadPart;
		cout << "链表第" << i << "个元素的值为：" << e << "        所花时间为：" << dt*1000000 << "μs" << endl;
	}
	cout << endl;
}
void ListInsertTime(Node *&head)
{
	ElemType e = -10086;
	for (int i = 4; i <= 400000; i *= 10)
	{
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&t1);
		ListInsert(head, i, e);
		QueryPerformanceCounter(&t2);
		dt = (t2.QuadPart - t1.QuadPart) / (double)nFreq.QuadPart;
		cout << "链表第" << i << "个位置插入" << e << "         所花时间为：" << dt*1000000 << "μs" << endl;;
	}
	cout << endl;
}
void ListDeleteTime(Node *&head)
{
	ElemType e;
	for (int i = 4; i <= 400000; i *= 10)
	{
		QueryPerformanceFrequency(&nFreq);
		QueryPerformanceCounter(&t1);
		ListDelete(head, i, e);
		QueryPerformanceCounter(&t2);
		dt = (t2.QuadPart - t1.QuadPart) / (double)nFreq.QuadPart;
		cout << "链表删除第" << i << "个位置的元素" << e << "        所花时间为：" << dt*1000000 << "μs" << endl;;
	}
	cout << endl;
int main()
{
	cout << "链表的基本运算如下：" << endl << endl;
	cout << "(1)初始化链表" << endl << endl;
	Node *head;
	CreateHead(head);
	string filename = "C:\\Users\\c1515\\Desktop\\Experiment_code\\1Mints.txt";
	ifstream fn(filename.c_str());
	if (!fn.is_open()){
		cout << "Cannot open file:" << filename << endl;
		exit(1);
	}
	string s;
	int cnt = 0;
	while (!fn.eof())
	{
		getline(fn,s);
		if (s.empty()) continue;
		a[cnt++] = atoi(s.c_str());
	}
	fn.close();
	cout << "(2)依次将1Mints.txt文件中的数据输入到链表中" << endl;
	InitLinkList(head, cnt);
	cout << "(3)链表L的长度：" << ListLength(head) << endl << endl;
	cout << "(4)链表L为" << (ListEmpty(head) ? "空" : "非空") << endl << endl;
	cout << "(5)输出链表L的第30、300、3000、30000、300000个元素值" << endl;
	GetElemTime(head);
	cout << "(6)元素-12345的位置：" << LocateElem(head, -12345) << endl << endl;
	cout << "(7)依次在第4、40、400、4000、40000、400000个元素位置上插入整数-10086" << endl;
	ListInsertTime(head);
	cout << "(8)依次删除在第4、40、400、4000、40000、400000个元素位置上的元素" << endl;
	ListDeleteTime(head);
	cout << "(9)输出前10个元素 " << endl;
	DispList(head,10);
	cout << "(10)释放链表" << endl;
	DestroyList(head);
	return 0;
}