数据结构实践教程-线性表

博主：酱油瓶
发布时间：2021 年 10 月 10 日
1787 次浏览
暂无评论
2658字数
分类：学习软件工程

本文为本人按照书本要求所写作业，算法并非最优，仅供参考
</div>

# 试验2.2 有序表合并

姓名：郁闷的酱油瓶

班级：软工

学号：47

试验时间：2021.10.9

## 1.问题描述

把两个有序表并为一个有序表

## 2.数据结构设计

### (1)结构设计

考虑到无序输入，使用有头结点的单链表

```c++
//LinkList.h
template<class T>
struct Node
{
	T data;					//数据域
	Node* next;				//指针域
};
```

### (2)函数设计

所需要函数为 构造函数，创建链表，输出链表元素，合并链表

```c++
//LinkList.h
template<class T>
class LinkList
{
private:
	Node<T>* Head;						//链表头节点
public:
	LinkList();						//构造函数，创建空链表
	void CreatList(int n);					//创建具有n个元素的线性链表
	void ListDisplay();					//输出元素表
	void MergeList(LinkList<T> La, LinkList<T> Lb);		//合并
};
```

## 3.算法设计

### (1)输入集合

从键盘输入，先输入个数，再输入数据

```c++
	//LinkList.h
	//构造空链表
	LinkList<int>La;
	LinkList<int>Lb;
	LinkList<int>Lc;

//创建表
	int n;
	cout << "请输入顺序表SA元素个数:";
	cin >> n;
	cout << endl;
	try
	{
		La.CreatList(n);
	}
	catch (char* err)
	{
		cout << err << endl;
	}
	cout << "请输入顺序表SB元素个数:";
	cin >> n;
	cout << endl;
	try
	{
		Lb.CreatList(n);
	}
	catch (char* err)
	{
		cout << err << endl;
	}
```

### (2)合并算法

### Step 1: 初始化

```c++
//LinkList.h
template<class T>
void LinkList<T>::MergeList(LinkList<T> LA, LinkList<T> LB)
```

#### 1.1 设置工作指针pa、pb，分别指向两个有序表LA、LB。

```c++
Node<T>* pa, * pb;
pa = LA.Head->next;
pb = LB.Head->next;
```

#### 1.2 生成新表LC的头结点，链到LC表尾，pc指向它。

```c++
Node<T>* pc;
pc = Head;
```

### Step 2: 只要pa和pb有所指，循环执行下列操作

```c++
while (pa && pb)
```

#### 2.1 生成一个新结点，链到LC表尾，pc指向它

```c++
Node<T>* p=new Node<T>;
p->next = NULL;
pc->next = p;
pc = p;
```

#### 2.2 如果pa->data<=pb->data 执行pa->data=pa->data;pa后移

```c++
if (pa->data <= pb->data)
	{
		pc->data = pa->data;
		pa = pa->next;
	}
```

#### 2.3 否则：pc->data=pb->data; pb后移

```c++
else
		{
			pc->data = pb->data;
			pb = pb->next;
		}
```

### Step 3: 如果pa空，把pb开始的结点一次复制到pc后

```c++
if (pa == NULL)
	{
		while (pb)
		{
			Node<T>* p2=new Node<T>;
			p2->next = NULL;
			pc->next = p2;
			pc = p2;
			pc -> data = pb->data;
			pb = pb->next;
		}
	}
```

### Step 4: 如果pb空，把pa开始的结点一次复制到pc后

```c++
else if (pb == NULL)
	{
		while (pa)
		{
			Node<T>* p3=new Node<T>;
			p3->next = NULL;
			pc->next = p3;
			pc = p3;
			pc -> data = pa->data;
			pa = pa->next;
		}
	}
```

### (3)调用并输出

```c++
//main.cpp
Lc.MergeList(La, Lb);
cout<<"SC:"<<endl;
Lc.ListDisplay();
```

## 4.运行和测试

1. 测试1：

(1)运行程序

(2)输入SA元素个数![](https://snz04pap001files.storage.live.com/y4mbplrNEP_hZpO9Hqxk8Y8ZtCw2XvT6D-qdV5sN_s6ahIIIEMwwnaSRUiE2EmuZj1ECTa3v2Y9AH0qxiEHR2o39R6DxH5kJiIDesFI0_eGMJgK5BbHZvMnfn9RiYCBgRdJklikNRCeLpv5L0z1NVOfED0Cz3tgklIfeSMm-IBwsMLEfaLagHGCuCwr0mgP9am0?width=1470&height=768&cropmode=none)

(3)输入SA元素

![](https://snz04pap001files.storage.live.com/y4mCJpXRpZ58n35qd_Xmqoc8icS5Dsok_Yv-K3f5TLeUHvCc3zGUOmGIAGf1zmMoh__e6FHZxbTngFPk9uNKLCauFRIxTHKLSwC6zY_RX9bg46Kn3l-tayCTpdfafqaNs4lppzzuCySrWo_Cebm-8Nfuq3Lc4MEy5_YlcPigWyP9L54Pp1WzPFMXDtd8FWgyWsB?width=1470&height=766&cropmode=none)

(4)输入SB元素个数

![](https://snz04pap001files.storage.live.com/y4mI3Y8ZW8aJDEzH7o2ecqXLAPvAMYYuqBIUgKnKoIYKpXXMJJBeewxty8KeEgfw8HTRwBJ373iMrlwPwOZJMME9HQMPX7e5KOnGVMQpC8YsySmkxxJ1YLcicyVAG_IypUr6lEcQdQZaauzFkbO4lpqsxqP2IJxBLt-0RIjYFjYKsrZFepKalo6pemodduRBwtp?width=1470&height=766&cropmode=none)

(5)输入SB元素

![](https://snz04pap001files.storage.live.com/y4mXTboDxbXlSEsWaHXz1jtCxV9Iwm6obVBFfVJT8k7M4UgKa_lr-unKTrI6MAOwSfnw3MqRUWvcPnD-S3VM4_U6LmoYWGXjB1qRbL92BziHxdeeQgakfmE5rGKbB634TVxCUvd6fJlVbDzSx7Ji4WeY0Dt1udWp5NCqHeYLPy1nSOqS__jr973DCUfVa0U6C_W?width=1470&height=766&cropmode=none)

(6) 输出SC

![](https://snz04pap001files.storage.live.com/y4muvrZD5tbdwPK1KWoFE27yWFOnQ7sltuhq2MXn3siV3tElcgwFn_et85K0IvMfj5wbaFZmtPiL6ySh9V0hRy_3_OnXiwF9LBkHRDxoGjIKsqZSp9jRkJPBqUka-VYOMpxBwsCjw1DcfoeL7AaGb_b2tbeDncyDeLW49qzjYqnbbpyww2OmpKpFpO1eAn9UmxM?width=1470&height=766&cropmode=none)

2. 测试2：![](https://snz04pap001files.storage.live.com/y4m69KmH8Cytiy0FxuxmNXhCm_FB6DrgGVcCuo5p-Oxn4sUY_7AOMn0cMB8nA9CTz0VNsL5YUPx13-CPv_bwX_D_60-kMzTuZK9yXFUSXAhAUoCMbyZNrE-HHh8t-S3Dvr2LAAg9mdxMhWoQ-Y_Jr0ctsPWMOgeqJlZ0eyDKl70EifgA-S0IeNij5rxtBqvUh-c?width=1470&height=768&cropmode=none)
3. 测试3：![](https://snz04pap001files.storage.live.com/y4mSqhjdZqY8IpuW8-u3n480RbVKFPa18Jft1NFSfUShMw_qYh0TYyvazNjYUHVVJn4F5gY_S6QR2XSW9Z5npubxb2DF4dTY2d70l6-wr_sA8ASgsZg_Jjd-DDqTFApA4fqHhJXC-m3FUmNNv5bTTrfVPcLLlHG9E2b2g-CIs5VInboCQMbFgNpbMWV8NOniXwr?width=1470&height=766&cropmode=none)
4. 测试4：![](https://snz04pap001files.storage.live.com/y4mPm49Adw_bJoytWjaOu2w0-Peqcr6QNgctakxuD9mERa-Rb-6ekblVrwcVPIATBWnVXTxZP4jGiPW62t2j_ZwOetzEWtabauNiVe23W4N29Wv3qQfY0O3OtGZDJ3DSRs-12T0B9jVGtwOinCDvrUFWI2OJfE0q0BE7_qtPq0IG15BtHYt5NzP1-1FGzu30JXP?width=1470&height=766&cropmode=none)
5. 测试5：![](https://snz04pap001files.storage.live.com/y4mbtQXg8qOAILUYWzggTjx0tSRoOpmLCnzBHkonS8QJYGSRXME0AgD_NoDpxNdHn2ki6engwQwrsCbbldFPK1uWo63MptHyvhoC-dnIiRn7NeVjB-hm_OOB2p85XrZAJ-DF6CJ_QPh_71Q_22FSYQi7mCbzzmVcLndX69mexVaHOriae2ogg2pPKvJAqJ-_iFt?width=1470&height=766&cropmode=none)
6. 测试6：![](https://snz04pap001files.storage.live.com/y4mA0rKH7KpqRiiXyApTzqsZ58YIlIreirhnjwo7EeeE6gLoEOpYVjK03x5qMa8fSJKpgm5zt5KM0ZESpWoZsU1rxVo4zrRNA1xvoQ0GQllA9PKVkpza24Vcymh-GMvx-9T9OK9cbVkAISQSF4mshD1_g1x6x_8geiTgcKXKEQoKHUlGlS9toS_IoXPDpi14Y12?width=1470&height=766&cropmode=none)
7. 测试7：![](https://snz04pap001files.storage.live.com/y4m3ucGvRTifGolWLRqfQ8v5IMGBpwwl1LEup93EvTV7icslo6t1mu3bL_Xe13djUVcPyYAbdpEUwB_1opshQIsDFup9IJ7OoWotMN-ei43fmvAL8dBnwIDAgzANKX0bVZkIdmSCwpn7NKSP0YiUvzjR7Fz3PxW4P9TmvylpbFVBw8xZyTotVwXlVOdN6n0UKDJ?width=1470&height=768&cropmode=none)

## 5.调试记录及收获

附1：源程序清单

```c++
//LinkList.h
#pragma once
#include<iostream>
using namespace std;

template<class T>
struct Node
{
	T data;							//数据域
	Node* next;						//指针域
};

template<class T>
class LinkList
{
private:
	Node<T>* Head;						//链表头节点
public:
	LinkList();						//构造函数，创建空链表
	void CreatList(int n);					//创建具有n个元素的线性链表
	void ListDisplay();					//输出元素表
	void MergeList(LinkList<T> La, LinkList<T> Lb);		//合并
};

//构造函数，创建空链表
template<class T>
LinkList<T>::LinkList()
{
	Head = new Node<T>;
	Head->next = NULL;
}

//创建具有n个元素的线性链表
template<class T>
void LinkList<T>::CreatList(int n)
{
	Node<T>* p, * s;
	p = Head;
	cout << "请依次输入" << n << "个元素值：" << endl;
	for (int i = 1; i <= n; i++)
	{
		s = new Node<T>;
		cin >> s->data;
		s->next = p->next;
		p->next = s;
		p = s;
	}
}

//输出元素表
template<class T>
void LinkList<T>::ListDisplay()
{
	Node<T>* p;
	p = Head->next;
	int i = 1;
	while (p)
	{
		cout << i << "\t";
		cout << p->data << endl;
		p = p->next;
		i++;
	}
}

template<class T>
void LinkList<T>::MergeList(LinkList<T> LA, LinkList<T> LB)
{
	Node<T>* pa, * pb;
	pa = LA.Head->next;
	pb = LB.Head->next;
	Node<T>* pc;
	pc = Head;
	while (pa && pb)
	{
		Node<T>* p=new Node<T>;
		p->next = NULL;
		pc->next = p;
		pc = p;
		if (pa->data <= pb->data)
		{
			pc->data = pa->data;
			pa = pa->next;
		}
		else
		{
			pc->data = pb->data;
			pb = pb->next;
		}
	}
	if (pa == NULL)
	{
		while (pb)
		{
			Node<T>* p2=new Node<T>;
			p2->next = NULL;
			pc->next = p2;
			pc = p2;
			pc -> data = pb->data;
			pb = pb->next;
		}
	}
	else if (pb == NULL)
	{
		while (pa)
		{
			Node<T>* p3=new Node<T>;
			p3->next = NULL;
			pc->next = p3;
			pc = p3;
			pc -> data = pa->data;
			pa = pa->next;
		}
	}
}
```

```c++
//main.cpp
#include<iostream>
#include"LinkList.h"
using namespace std;
typedef int T;

//有序表合并
int main()
{
	//构造空链表
	LinkList<int>La;
	LinkList<int>Lb;
	LinkList<int>Lc;

```

# 试验2.3 集合交运算问题

姓名：郁闷的酱油瓶

班级：软工

学号：47

试验时间：2021.10.9

## 1.问题描述

用线性表表示两个集合，求两个集合的交集。

## 2.数据结构设计

### (1)结构设计

考虑到集合的插入和删除，使用有头节点的单链表

```c++
//LinkList.h
template<class T>
struct Node
{
	T data;						//数据域
	Node* next;					//指针域
};

```

### (2)函数设计

需要用到构造函数，析构函数，创建单链表，删除元素，查找元素，获取元素，测表长，输出元素表

```c++
//LinkList.h
template<class T>
class LinkList
{
private:
	Node<T>* Head;				//链表头节点
public:
	LinkList();				//构造函数，创建空链表
	~LinkList();				//析构函数，删除表空间
	void CreatList(int n);			//创建具有n个元素的线性链表
	T Delete(int i);			//删除表中的第i个元素
	T GetElem(int i);			//获取第i个元素的值
	int Locate(T e);			//在链表种查找值为e的元素
	int Length();				//测表长
	void SetDisplay();			//以集合形式输出元素表
};
```

## 3.算法设计

### (1)数据输入

从键盘输入La与Lb的元素

```c++
//main.cpp
	//构造空链表
	LinkList<char>La;
	LinkList<char>Lb;

//创建表
	int n;
	cout << "请输入顺序表La元素个数:";
	cin >> n;
	cout << endl;
	try 
	{
		La.CreatList(n);
	}
	catch (char* err) 
	{
		cout << err << endl;
	}
	cout << "请输入顺序表Lb元素个数:";
	cin >> n;
	cout << endl;
	try 
	{
		Lb.CreatList(n);
	}
	catch (char* err) 
	{
		cout << err << endl;
	}
```

### (2)交集算法

#### step 1:

扫描A

```c++
for (int i = 1; i <= La.Length(); i++)	//扫描La中的元素
```

#### step 2:

在B中查找元素，若B中有，则保留，否则删除该节点

```c++
if (!Lb.Locate(La.GetElem(i)))			//若扫描到的元素在Lb中不存在，则删除
		{
			La.Delete(i);		//删除元素
			i--;			//定位-1
		}
```

#### step 3:

释放B所占用的空间

```c++
Lb.~LinkList();
```

#### step 4:

显示A∩B

```c++
cout << "A∩B=";
La.SetDisplay();
```

## 4.运行和测试

#### 测试1：

(1)运行程序

![](https://snz04pap001files.storage.live.com/y4muHL0dDH692_A7wQIKEzOoA9A4hdow-WhR68Fq3edjaNNwwHQMce_N9FCmtUlmwfqKQFprmJ2-bE_bMx42KD_ivbPI6bi1QJ37J6jjVLePM0Ub7I-r96opp0WBcQcv3L11rE6Ts8fJBlvBEwE6EUmk7h93mahMSVndZAiSVgyAZ8AyEbv2NeE2wA_B6sXvLoO?width=1470&height=768&cropmode=none)

(2)输入集合A的元素个数

![](https://snz04pap001files.storage.live.com/y4mNTkmvdhFlGuAiIi6XVFYAKFJBC2jJrOT8GxrZGjckiZnaEz-dIX4orzolL5x7kvXhfNBwD555ckfAlDy4yKXdjF3HA7VdL2UoihV6KxLySuXyECW3re_j7Y3FCiEy1ZV2UclB_s4nhRQlmqeawjWJZmiPpqxBU3RAQuB-E6U4TdutqYxI8-CQ0osE-hd7HR2?width=1470&height=768&cropmode=none)

(3)输入集合A的元素

![](https://snz04pap001files.storage.live.com/y4mT75bKQmEzkR2QoHDzhokb8DnQ7p0W1ADfYra97BNZ8IPjeW9iM8r5WAu8ZdYx7C62Uc9h3hpv_64-IvtKLrrh0nRs1j8RplSPfCI107L1Mb7NisEhOkFLTbTB-LcHfvgm_fROQhdHHDA4RJ8CarUmEby94jSF7q86kMqxpkuHJO94Va6KeO3jwXvu03xfa2g?width=1470&height=766&cropmode=none)

(4)输入集合B的元素个数

![](https://snz04pap001files.storage.live.com/y4mlPwzvCp6vCm76Om0Ib-MbEuFGavZ2xlEwXr_AMcaaWO9G0-LUarowP51RD_CyNQJrU-xAUGMEszLVk__ikBioz7_AtdFN-Uhhs3Q-FoIYqMCxKzqnkk3bz4N1Ei-FijC_7jzUW65FFjR_-TShaClgqMtPhY0Own97HPh6KB5kfkOHD4QBhtZVBScmcDYvYTb?width=1470&height=766&cropmode=none)

(5)输入集合B的元素

![](https://snz04pap001files.storage.live.com/y4mRGJxrODPVqjqr5qtoq95T-0BRPlTtpa3SyJ9xpbBZkEw9lkyIGSVEUE2sJnzAPjUDj1Tv_la5zVv8eoHiFMgUPjoADrJ-DZZlguvjCFgiwK4SdndUngWNrUoociB6-zDTolnyv1m2lQQuBtOj-ir3rWEgzyVP_vxSzKX_lPsddlVUnKg9kkKKgRpWCFCsxdV?width=1470&height=766&cropmode=none)

(6)得到A∩B

![测试1](https://snz04pap001files.storage.live.com/y4m35Vgzxrh5XG1RibppiQop4TExMXAdMOCi83RI-PTtWU97CSxc6snw-q5ZMwcLfzV2V4T2O8bcim2qItCCLeIZv8H4AG38bamQKPSgdXp_DXW6pza9YQwDQ_JuuMGo9xkggfoIBqWcDHTqeiP5FIj_x7clFRuZFVHI7mY2RQibgwN-DqU7JicnQT6pM0o1vms?width=1470&height=747&cropmode=none)

#### 测试2：![测试2](https://snz04pap001files.storage.live.com/y4mm5tSs7-Mw6sp6gbnlAuu5Tgz44w3_Y6fblj4bQfRtzSl9shHRjoT592dC9R2oEngVy3rQ_ZGGCo2uTmI-zMx3957BhzVc9OFUBDqDXCUkjNIEL8bWC8RlJ0GetXI2ztktRe0sov-burCH2aNw88EV6t3nptx1JmMOKbenmdsVNhuw8vrJXnqlcl0T5NrEvJv?width=1470&height=766&cropmode=none)

#### 测试3：

![测试3](https://snz04pap001files.storage.live.com/y4mm5tSs7-Mw6sp6gbnlAuu5Tgz44w3_Y6fblj4bQfRtzSl9shHRjoT592dC9R2oEngVy3rQ_ZGGCo2uTmI-zMx3957BhzVc9OFUBDqDXCUkjNIEL8bWC8RlJ0GetXI2ztktRe0sov-burCH2aNw88EV6t3nptx1JmMOKbenmdsVNhuw8vrJXnqlcl0T5NrEvJv?width=1470&height=766&cropmode=none)

#### 测试4：

![测试4](https://snz04pap001files.storage.live.com/y4m97vflvgyavHVRwkz0p2U-rZ3sDQJAgB9MDJTMBXOAffmOjD_0zIelbfGrGJVWgn8tR9UG5VshH7-JUFOAlkY3duSc_1uRlV3EBdTIPBne1PMPKCDN1B9khkJ77R2gwAUISOr9odW5G6I5iUq_QbRp-zBFalSYyvbjNwTa4eE_pfC-Fzijtpl0ji9QNwp7FCU?width=1470&height=766&cropmode=none)

## 5.调试记录与收获

附1：源程序清单

```c++
//LinkList.h
#pragma once
#include<iostream>
using namespace std;

template<class T>
struct Node
{
	T data;						//数据域
	Node* next;					//指针域
};

template<class T>
class LinkList
{
private:
	Node<T>* Head;				//链表头节点
public:
	LinkList();				//构造函数，创建空链表
	~LinkList();				//析构函数，删除表空间
	void CreatList(int n);			//创建具有n个元素的线性链表
	T Delete(int i);			//删除表中的第i个元素
	T GetElem(int i);			//获取第i个元素的值
	int Locate(T e);			//在链表种查找值为e的元素
	int Length();				//测表长
	void SetDisplay();			//以集合形式输出元素表
};
//函数的实现
//构造函数，创建空链表
template<class T>
LinkList<T>::LinkList()
{
	Head = new Node<T>;
	Head->next = NULL;
}

//析构函数，删除表空间
template<class T>
LinkList<T>::~LinkList()
{
	Node<T>* p;
	while (Head)
	{
		p = Head;
		Head = Head->next;
		delete p;
	}
	Head = NULL;
}

//创建具有n个元素的线性链表
template<class T>
void LinkList<T>::CreatList(int n)
{
	Node<T>* p, * s;
	p = Head;
	cout << "请依次输入" << n << "个元素值：" << endl;
	for(int i=1;i<=n;i++)
	{
		s = new Node<T>;
		cin >> s->data;
		s->next = p->next;
		p->next = s;
		p = s;
	}
}

//删除表中的第i个元素
template<class T>
T LinkList<T>::Delete(int i)
{
	T x;
	Node<T>* p, * q;
	p = Head;
	int j = 0; while (p->next && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		throw"位置异常";
	else
	{
		q = p->next;
		p->next = q->next;
		x = q->data;
		delete q;
		return x;
	};
}

//获取第i个元素的值
template<class T>
T LinkList<T>::GetElem(int i)
{
	Node<T>* p;
	p = Head->next;
	int j = 1;
	while (p&&j<i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
		throw"位置";
	else 
		return p->data;
}

//在链表种查找值为e的元素
template<class T>
int LinkList<T>::Locate(T e)
{
	int j = 1;
	Node<T>* p;
	p = Head->next;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p == NULL) return 0;
	else return j;
}

//测表长
template<class T>
int LinkList<T>::Length()
{
	int len = 0;
	Node<T>* p;
	p = Head;
	while (p->next)
	{
		len++;
		p = p->next;
	}
	return len;
}

//以集合形式输出
template<class T>
void LinkList<T>::SetDisplay()
{
	Node<T>* p;
	p = Head->next;
	int i = 1;
	cout << "{";
	while (p)
	{
		cout << p->data << ", ";
		p = p->next;
		i++;
	}
	cout << "}";
}
```

```c++
//main.cpp
#include<iostream>
#include"LinkList.h"
using namespace std;
typedef char T;

//2.3集合交运算问题
int main()
{
	//构造空链表
	LinkList<char>La;
	LinkList<char>Lb;

for (int i = 1; i <= La.Length(); i++)		//扫描La中的元素
	{
		if (!Lb.Locate(La.GetElem(i)))		//若扫描到的元素在Lb中不存在，则删除
		{
			La.Delete(i);			//删除元素
			i--;				//定位-1
		}
	}

//释放表Lb
	Lb.~LinkList();
	//输出交集
	cout << "A∩B=";
	La.SetDisplay();
}
```

最后修改：2022 年 06 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构实践教程-线性表

酱油瓶 • 2021 年 10 月 10 日