單連結清單的基本操作(C++連結清單實作)

[問題描述]

實作帶頭結點的單連結清單的建立、求長度，取元素、修改元素、插入、删除等單連結清單的基本操作。

[基本要求]

（1）依次從鍵盤讀入資料，建立帶頭結點的單連結清單；

   (2）輸出單連結清單中的資料元素

（3）求單連結清單的長度；

（4）根據指定條件能夠取元素和修改元素；

（5）實作在指定位置插入和删除元素的功能

1、初始化連結清單輸入0停止輸入：

void init(LinkList &L)
{
	LinkList p = new LNode;
	L = new LNode;
	L->next = NULL;
	p = L;
	int x;
	cout << "輸入0時結束對連結清單進行指派" << endl;
	while (1)
	{
		cin >> x;
		if (x == 0)
			break;
		LinkList q = new LNode;
		q->data = x;
		q->next = NULL;
		p->next = q;
		p = q;
	}
}
           

2、擷取連結清單長度

int  getlength(LinkList &L)
{
	LinkList t = new LNode;
	t = L->next;
	int sum = 0;
	while (t)
	{
		sum++;
		t = t->next;
	}
	return sum;
}
           

3、取出想要修改連結清單元素的位置并修改其值為9

void getelem(LinkList &L)
{
	int x;
	cout << "請輸入想要擷取的連結清單下标并将其修改為9" << endl;
		cin >> x;
	int ans = 0;
	LinkList t = new LNode;
	t = L->next;
	if (getlength(L) < x)
	{
		cout << "輸入坐标不在合法範圍内,請重新輸入" << endl;
		getelem(L);
	}
	for (int i = 0; i < x; i++)
	{
		t = t->next;
	}
	t->data = 9;
}
           

4、在指定位置插入元素

void insert(LinkList &L)
{
	int x;
	cout << "請輸入你想在某個位置插入元素的坐标" << endl;
		cin >> x;
	LinkList p = new LNode;
	p = L;
	if (getlength(L)+1 < x)
	{
		cout << "插入的位置不合法,請重新輸入" << endl;
		insert(L);
		return;
	}
	cout << "請輸入想要插入的值" << endl;
	int m;
	cin >> m;
	for (int i = 0; i < x-1;i++)
	{
		p = p->next;
	}
	LinkList q = new LNode;
	q->data = m;
	q->next = p->next;
	p->next = q;
	p = q;
}
           

5、删除指定位置的元素

void del(LinkList &L)
{
	int x;
	cout << "請輸入想要删除的元素的下标" << endl;
		cin >> x;
	if (x > getlength(L))
	{
		cout << "你輸入的資料不合法，超過了連結清單長度,請重新輸入" << endl;
		del(L);
		return;
	}
	LinkList q = new LNode;
	q = L;
	x--;
	while (x>=0)
	{
		q = q->next;
		x--;
	}
	LinkList t = new LNode;
	t->data = q->next->data;
	t = q->next;
	t->next = q->next->next;
	q->next = t->next;
	q = t;
	delete t;
}
           

6、列印連結清單

void print(LinkList &L)
{
	LinkList t = new LNode;
	t = L->next;
	while (t)
	{
		cout << t->data << ' ';
		t = t->next;
	}
	cout << endl;
}
           

7、完整代碼如下：

#include<iostream>
using namespace std;

typedef struct LNode
{
	int data;
	struct LNode *next;
}*LinkList;

void init(LinkList &L)
{
	LinkList p = new LNode;
	L = new LNode;
	L->next = NULL;
	p = L;
	int x;
	cout << "輸入0時結束對連結清單進行指派" << endl;
	while (1)
	{
		cin >> x;
		if (x == 0)
			break;
		LinkList q = new LNode;
		q->data = x;
		q->next = NULL;
		p->next = q;
		p = q;
	}
}

int  getlength(LinkList &L)
{
	LinkList t = new LNode;
	t = L->next;
	int sum = 0;
	while (t)
	{
		sum++;
		t = t->next;
	}
	return sum;
}

void print(LinkList &L)
{
	LinkList t = new LNode;
	t = L->next;
	while (t)
	{
		cout << t->data << ' ';
		t = t->next;
	}
	cout << endl;
}

void getelem(LinkList &L)
{
	int x;
	cout << "請輸入想要擷取的連結清單下标并将其修改為9" << endl;
		cin >> x;
	int ans = 0;
	LinkList t = new LNode;
	t = L->next;
	if (getlength(L) < x)
	{
		cout << "輸入坐标不在合法範圍内,請重新輸入" << endl;
		getelem(L);
	}
	for (int i = 0; i < x; i++)
	{
		t = t->next;
	}
	t->data = 9;
}

void insert(LinkList &L)
{
	int x;
	cout << "請輸入你想在某個位置插入元素的坐标" << endl;
		cin >> x;
	LinkList p = new LNode;
	p = L;
	if (getlength(L)+1 < x)
	{
		cout << "插入的位置不合法,請重新輸入" << endl;
		insert(L);
		return;
	}
	cout << "請輸入想要插入的值" << endl;
	int m;
	cin >> m;
	for (int i = 0; i < x-1;i++)
	{
		p = p->next;
	}
	LinkList q = new LNode;
	q->data = m;
	q->next = p->next;
	p->next = q;
	p = q;
}

void del(LinkList &L)
{
	int x;
	cout << "請輸入想要删除的元素的下标" << endl;
		cin >> x;
	if (x > getlength(L))
	{
		cout << "你輸入的資料不合法，超過了連結清單長度,請重新輸入" << endl;
		del(L);
		return;
	}
	LinkList q = new LNode;
	q = L;
	x--;
	while (x>=0)
	{
		q = q->next;
		x--;
	}
	LinkList t = new LNode;
	t->data = q->next->data;
	t = q->next;
	t->next = q->next->next;
	q->next = t->next;
	q = t;
	delete t;
}

int main()
{
	LinkList L;
	init(L);

	cout << "連結清單的元素為" << endl;
	print(L);

	int len = getlength(L);
	cout << "連結清單的長度為" << len << endl;

	getelem(L);
	cout << "修改後的連結清單為" << endl;
	print(L);
	
	
	insert(L);
	cout << "插入元素後的連結清單為" << endl;
	print(L);

	del(L);
	cout << "删除後的連結清單為" << endl;
	print(L);
	return 0;
}