C++数据结构与算法（单向链表）

谁借莪１个温暖的怀抱￠ 2022-01-12 11:41 287阅读 0赞

**目录**

1创建链表

1.1创建链表的顺序结构写法

1.2利用循环语句创建链表（正向创建）

1.3利用循环语句创建链表（逆向创建）

1.4改进写法

2删除节点

3增加节点

4查找节点

4.1链表查找元素的节点数或者按照节点查找数据域

4.2查找链表中的最值

5修改节点

6链表逆置

7删除链表中的最值

8链表排序

9链表合并

9.1将两个不同排序的链表进行升序排列

9.2将两个相同排序的链表进行升序排列

10测量一个链表的长度

--------------------

链表的引出：

数组是程序设计语言所提供的一种非常有用的数据结构，但是，数组有两个局限：1）编译期就要知道大小；2）数组中的数据在计算机内存中以等间隔分开，这就意味着如果向其中插入一个元素，那么需要移动该数组中的其他元素。链表就不存在这些问题。**链表是节点的集合。节点中存储着数据并且会链接到其他节点。**

**链表包含两个部分：数据域和链接域。**

**单向链表**

如果一个节点将指向另一个节点的指针作为数据成员，那么多个这样的节点就可以链接起来，只用一个变量能够访问整个节点序列。这样的节点序列就是最常用的链表实现方法。**链表是一种节点组成的数据结构，每个节点都包含某些信息以及指向链表另一个节点的指针。如果序列中的节点只包含指向后继节点的链接，该链表称为单向链表**。

## 1创建链表 ##

### 1.1创建链表的**顺序结构**写法 ###

#include<iostream>
    using namespace std;
    
    class Node  //节点
    {
    	friend class List; //声明为友元类，以使得List的成员函数可以使用Node的私有属性
    private:
    	int data;   //节点中的数据
    	Node* next; //指针指向下一个节点的指针
    };
    
    class List  //链表
    {
    public:
    	void test();
    	void show();
    private:
    	Node* first;  //指向第一个节点的指针
    };
    void List::show()
    {
    	cout << first->data << endl
    		<< first->next->data << endl
    		<< first->next->next->data << endl;
    }
    
    void List::test()
    {
    	Node *f = new Node();
    	f->data = 44;
    	f->next = NULL;
    
    	first = f;
    
    	f = new Node();
    	f->data = 72;
    	f->next = NULL;
    
    	first->next = f;
    
    	f = new Node();
    	f->data = 210;
    	f->next = NULL;
    
    	first->next->next = f;
    }
    
    int main()
    {
    	List a;
    	a.test();  //创建3个节点
    	a.show();   //输出节点的数据域
    	cout << "OK" << endl;
    	system("pause");
    	return 0;
    }

### 1.2利用**循环语句**创建链表（正向创建） ###

算法思想：从一个空表开始，每次读入数据，生成新节点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //创建链表函数 
    ElemSN *CreatLink(int a[], int n)
    {
    	ElemSN *h, *p, *t;  //h表示头指针，t表示尾指针，p是中间指针 
    	int i;
    	h = t = (ElemSN *)malloc(sizeof(ElemSN));
    	h->data = a[0];
    	h->next = NULL;
    	for (i = 1; i<n; i++)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = NULL;
    		t->next = p;
    		t = p;
    	}
    	return h;
    }
    
    //输出函数 
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data << endl;
    }
    
    //主函数 
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreatLink(a, 8);
    	PrintLink(head);
    	system("pause");
    	return 0;
    }

### 1.3利用**循环语句**创建链表（**逆向创建**） ###

该方法将新节点插到当前单链表的表尾上，相对于头插法的优势在于少声明一个中间指针变量，建议使用尾插法：

//利用结构体（尾插法）创建链表
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //创建链表函数（尾插法） 
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    //输出函数 
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data << endl;
    }
    
    //主函数 
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreateLink(a, 8);
    	PrintLink(head);
    	system("pause");
    	return 0;
    }

### 1.4改进写法 ###

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreatLink(int a[], int n)
    {
    	ElemSN *h = NULL, *p, *t = NULL;
    	int i;
    	for (i = 0; i<n; i++)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = NULL;
    		if (!h)  h = t = p;
    		else
    			t = t->next = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data;
    }
    
    int main()
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreatLink(a, 8);
    	PrintLink(head);
    	cout << endl;
    	system("pause");
    	return 0;
    }

## 2删除节点 ##

**链表删除节点（三种写法）**

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *q;
    	for (q = h; q; q = q->next)
    		cout << setw(5) << q->data;
    }
    
    ElemSN *DelkeyNode(ElemSN *h, int key)   //删除节点
    {
    	ElemSN *p, *q = NULL;
    	p = h;
    	while (p)  //从头指针开始遍历
    	{
    		if (p->data != key) //不是待删节点
    		{
    			q = p;
    			p = p->next;
    		}
    		else if (p == h)  //是待删节点，且待删节点是第一个节点
    		{
    			h = h->next;  //头结点后移
    			free(p);      //删除头节点
    			p = h;        //p指向新的头节点
    		}
    		else             //是待删节点，但不是第一个节点
    		{
    			q->next = p->next;
    			free(p);
    			p = q->next;
    		}
    	}
    	return h;
    }
    
    int main()
    {
    	int a[8] = { 10, 20, 30, 20, 20, 60, 7, 20 };
    	int key;
    	ElemSN *head;
    	//创建链表
    	head = CreateLink(a, 8);
    	//输出链表
    	PrintLink(head);
    	cout << endl;
    	cout << "请输入key值: ";
    	cin >> key;
    	//删除数据域为key的值
    	head = DelkeyNode(head, key);
    	PrintLink(head);
    	cout << endl;
    	system("pause");
    	return 0;
    }

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *q;
    	for (q = h; q; q = q->next)
    		cout << setw(5) << q->data;
    }
    
    ElemSN *DelkeyNode(ElemSN *h, int key)  //删除节点
    {
    	ElemSN *p, *q;
    	for (p = h; p&&p->data == key; p = p->next);
    	h = p;
    	if (h->next)
    	{
    		for (q = h, p = h->next; p; p = p->next)
    		{
    			if (p->data != key)
    			{
    				q->next = p;
    				q = p;
    			}
    			else if (!p->next)
    			{
    				q->next = NULL;
    			}
    		}
    	}
    	return h;
    }
    
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 20, 60, 7, 20 };
    	int key;
    	ElemSN *head;
    	//创建链表
    	head = CreateLink(a, 8);
    	//输出链表
    	PrintLink(head);
    	cout << endl;
    	cout<<"请输入key值: ";
    	cin >> key;
    	//删除数据域为key的值
    	head = DelkeyNode(head, key);
    	PrintLink(head);
    	cout << endl;
    	system("pause");
    	return 0;
    }

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *q;
    	for (q = h; q; q = q->next)
    		cout << setw(5) << q->data;
    }
    
    ElemSN *DelkeyNode(ElemSN *h, int key)   //删除节点
    {
    	ElemSN *p, *t, *h1;
    	h1 = NULL;
    	t = NULL;
    	while (h)
    	{
    		p = h;  //p指向头指针
    		h = h->next; //头指针后移
    		if (p->data == key) //是待删节点
    			free(p);       //删除
    		else               //不是待删节点
    		{
    			p->next = NULL;
    			if (!h1)
    				h1 = t = p;
    			else               
    				t = t->next = p;
    		}
    	}
    	return h1;
    }
    
    
    int main()
    {
    	int a[8] = { 10, 20, 30, 20, 20, 60, 7, 20 };
    	int key;
    	ElemSN *head;
    	//创建链表
    	head = CreateLink(a, 8);
    	//输出链表
    	PrintLink(head);
    	cout << endl;
    	cout << "请输入key值: ";
    	cin >> key;
    	//删除数据域为key的值
    	head = DelkeyNode(head, key);
    	PrintLink(head);
    	cout << endl;
    	system("pause");
    	return 0;
    }

## 3增加节点 ##

**向链表中添加节点（头插、尾插和任意插）**

//向链表中添加数据
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //创建链表函数（尾插法） 
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    //输出函数 
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data << endl;
    }
    
    //向头部添加数据
    ElemSN * add(int number, ElemSN *head)
    {
    	ElemSN * temp = (ElemSN *)malloc(sizeof(ElemSN));
    	temp->data = number;
    	temp->next = NULL;
    	ElemSN * p = head;
    	head = temp;
    	head->next = p;
    	return head;
    }
    
    //向尾部添加数据
    ElemSN * add2(int number, ElemSN *head)
    {
    	ElemSN * temp = (ElemSN *)malloc(sizeof(ElemSN));
    	ElemSN * q = (ElemSN *)malloc(sizeof(ElemSN));
    	temp->data = number;
    	temp->next = NULL;
    	ElemSN * p;
    	for (p = head,q->next = p; p; p = p->next,q=q->next);
    	q->next = temp;
    	return head;
    }
    
    //返回链表长度
    int GetLength(ElemSN *head)
    {
    	int length = 0;
    	ElemSN *p = head;
    	while (p != NULL)
    	{
    		++length;
    		p = p->next;
    	}
    	return length;
    }
    
    //从指定位置后面插入元素
    ElemSN * IndexInsertNode(ElemSN *head, int num, int pos)
    {
    	ElemSN *p = head;
    	int count = 0;
    	int length = GetLength(head);
    	cout << "---------------" << endl;
    	cout << length << endl;
    	if (pos < 0 || pos > length)
    		cout << "插入位置不正确!" << endl;
    	if (!pos)
    	{
    		node *temp = new node;
    		temp->data = num;
    		temp->next = NULL;
    		head = temp;
    		head->next = p;
    		return head;
    	}
    	while (p != NULL)
    	{
    		count++;
    		if (count == pos)
    		{
    			node *p1 = new node;
    			p1->data = num;
    			p1->next = p->next;
    			p->next = p1;
    		}
    		p = p->next;
    	}
    	return head;
    }
    
    
    //主函数 
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreateLink(a, 8);
    	cout << "原链表：" << endl;
    	PrintLink(head);
    	int number;
    	cout << "请输入要插入的数据：" << endl;
    	cin >> number;
    	//向链表头部添加数据 head = add(number, head);
    	//向链表尾部添加数据 head = add2(number, head);
    	//指定位置插入数据
    	int pos;
    	cout << "请输入要插入的位置：" << endl;
    	cin >> pos;
    	head = IndexInsertNode(head, number, pos);
    	cout << "插入数据后的链表：" << endl;
    	PrintLink(head);
    
    	system("pause");
    	return 0;
    }

## 4查找节点 ##

### **4.1链表查找元素的节点数或者按照节点查找数据域** ###

//在链表中查找数据
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //创建链表函数（尾插法） 
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    //输出函数 
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data << endl;
    }
    
    int Search_Elem(int num, ElemSN *head)
    {
    	node *p = new node;
    	p = head;
    	int index = 1;
    	while (p)
    	{
    		if (num == p->data)
    			return index;
    		else
    		{
    			p = p->next;
    			++index;
    		}
    	}
    	return -1;
    }
    
    int Search_index(int index, ElemSN *head)
    {
    	node *p = new node;
    	int i = 1;
    	for (i = 1, p = head; p&&i < index; p = p->next,i++);
    	return p->data;
    }
    
    
    //主函数 
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreateLink(a, 8);
    	cout << "原链表：" << endl;
    	PrintLink(head);
    	//int number;
    	//cout << "请输入要查找的数据：" << endl;
    	//cin >> number;
    	//int index = Search_Elem(number, head);
    	//if (index < 0)
    	//	cout << "没找到" << number << endl;
    	//else
    	//	cout << "找到了" << number << ",它是第" << index << "个节点" << endl;
    
    	int index;
    	cout << "查找第几个节点？" << endl;
    	cin >> index;
    	int data = Search_index(index, head);
    	cout << "第" << index << "个节点的数据是：" << data << endl;
    
    	system("pause");
    	return 0;
    }

### 4.2查找链表中的最值 ###

/*查找链表中的最值*/
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p, *t;
    	int i;
    	h = t = (ElemSN *)malloc(sizeof(ElemSN));
    	h->next = NULL;
    	for (i = 0; i<n; i++)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = NULL;
    		t = t->next = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p->next; p = p->next)
    		cout << setw(5) << p->next->data;
    	cout << endl;
    }
    
    int SearchNode_MAX(ElemSN *h)
    {
    	ElemSN *p;
    	int max;
    	p = h->next;
    	max = h->next->data;
    	for (p; p->next; p = p->next)
    	{
    		if (p->next->data>max)
    		{
    			max = p->next->data;
    			p = p->next;
    		}
    	}
    	return max;
    }
    
    int SearchNode_MIN(ElemSN *h)
    {
    	ElemSN *p;
    	int min;
    	p = h->next;
    	min = h->next->data;
    	for (p; p->next; p = p->next)
    	{
    		if (p->next->data<min)
    		{
    			min = p->next->data;
    			p = p->next;
    		}
    	}
    	return min;
    }
    
    
    int main(void)
    {
    	int a[8] = { 60, 20, 10, 40, 10, 60, 60, 10 };
    	int max, min;
    	ElemSN *head;
    	//创建带表头结点的单向链表
    	head = CreateLink(a, 8);
    	//输出单向链表
    	PrintLink(head);
    	//找最大值结点
    	max = SearchNode_MAX(head);
    	cout << "最大值结点的数据域值为: " << max << endl;
    	//找最小值结点
    	min = SearchNode_MIN(head);
    	cout << "最小值结点的数据域值为: " << min << endl;
    	system("pause");
    	return 0;
    }

## 5修改节点 ##

**修改链表中节点的数据域数据**

//在链表中修改第index个节点的数据域数据
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //创建链表函数（尾插法） 
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    //输出函数 
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout << setw(5) << p->data;
    	cout << endl;
    }
    
    ElemSN * Modify_index(int index, int num, ElemSN *head)
    {
    	node *p = new node;
    	int i = 1;
    	for (i = 1, p = head; p&&i < index; p = p->next, i++);
    	p->data = num;
    	return head;
    }
    
    
    //主函数 
    int main(void)
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	head = CreateLink(a, 8);
    	cout << "原链表：" << endl;
    	PrintLink(head);
    
    	int index;
    	cout << "修改第几个节点？" << endl;
    	cin >> index;
    	int num;
    	cout << "请输入要修改的值：" << endl;
    	cin >> num;
    	head = Modify_index(index, num, head);
    	cout << "修改后的链表是："<< endl;
    	PrintLink(head);
    
    	system("pause");
    	return 0;
    }

## 6链表逆置 ##

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    //头插法 
    ElemSN *CreateLink1(int a[], int n)
    {
    	ElemSN *h, *p, *t;
    	int i;
    	h = t = new node;
    	h->next = NULL;
    	for (i = 0; i<n; i++)
    	{
    		p = new node;
    		p->data = a[i];
    		p->next = NULL;
    		t = t->next = p;
    	}
    	return h;
    }
    
    //尾插法
    ElemSN *CreateLink2(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = new node;
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p->next; p = p->next)
    		cout << setw(5) << p->next->data << " ";
    }
    
    void NiZhiLink(ElemSN *h)
    {
    	ElemSN *p, *s;
    	p = h->next;
    	h->next = NULL;
    	while (p)
    	{
    		s = p->next;
    		p->next = h->next;
    		h->next = p;
    		p = s;
    	}
    }
    
    
    
    int main()
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	int key;
    	ElemSN *head;
    	//创建带表头结点的单向链表
    	head = CreateLink1(a, 8);
    	//输出单向链表
    	cout << "原链表：" << endl;
    	PrintLink(head);
    	cout << endl;
    	NiZhiLink(head);
    	cout << "逆置后：" << endl;
    	PrintLink(head);
    	cout << endl;
    	system("pause");
    	return 0;
    }

## 7删除链表中的最值 ##

/*查找链表中的最值*/
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p, *t;
    	int i;
    	h = t = (ElemSN *)malloc(sizeof(ElemSN));
    	h->next = NULL;
    	for (i = 0; i<n; i++)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = NULL;
    		t = t->next = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p->next; p = p->next)
    		cout << setw(5) << p->next->data << " ";
    	cout << endl;
    }
    
    int SearchNode_MAX(ElemSN *h)
    {
    	ElemSN *p;
    	int max;
    	p = h->next;
    	max = h->next->data;
    	for (p; p->next; p = p->next)
    	{
    		if (p->next->data>max)
    		{
    			max = p->next->data;
    			p = p->next;
    		}
    	}
    	return max;
    }
    
    int SearchNode_MIN(ElemSN *h)
    {
    	ElemSN *p;
    	int min;
    	p = h->next;
    	min = h->next->data;
    	for (p; p->next; p = p->next)
    	{
    		if (p->next->data<min)
    		{
    			min = p->next->data;
    			p = p->next;
    		}
    	}
    	return min;
    }
    
    void DelNode(ElemSN *h, int key)
    {
    	ElemSN *p, *delp;
    	p = h;
    	while (p->next)
    	{
    		if (p->next->data - key)
    			p = p->next;
    		else
    		{
    			delp = p->next;
    			p->next = delp->next;
    			free(delp);
    		}
    	}
    }
    
    int main(void)
    {
    	int a[8] = { 60, 20, 10, 40, 10, 60, 60, 10 };
    	int max, min;
    	ElemSN *head;
    	//创建带表头结点的单向链表
    	head = CreateLink(a, 8);
    	//输出单向链表
    	PrintLink(head);
    
    	//找最大值结点
    	max = SearchNode_MAX(head);
    	cout << "最大值结点的数据域值为:" << max << endl;
    
    	//找最小值结点
    	min = SearchNode_MIN(head);
    	cout << "最小值结点的数据域值为:" << min << endl;
    
    	//删除最大值结点
    	DelNode(head, max);
    	cout << "删除最大值结果：";
    	PrintLink(head);
    	//删除最小值结点
    	DelNode(head, min);
    	cout << "删除最小值结果：";
    	PrintLink(head);
    
    	system("pause");
    	return 0;
    }

## 8链表排序 ##

/*冒泡排序和快速排序*/
    #include <iostream>
    #include <algorithm>
    #include "string.h"
    #include "stdio.h"
    #include <vector>
    #include <deque>
    #include<stack>
    using namespace std;
    
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) : val(x), next(NULL) {}
    };
    class List{
    public:
    	ListNode* CreatList(int* arr, int len)
    	{
    		int val;
    		ListNode* pHead = new ListNode(arr[0]);
    		ListNode* pCurrent = NULL;
    		ListNode* rear = pHead;
    		int count = 1;
    		while (count<len)
    		{
    			ListNode* pCurrent = new ListNode(arr[count]);
    			rear->next = pCurrent;
    			rear = pCurrent;
    			count++;
    		}
    		rear->next = NULL;
    		return pHead;
    	}
    	void ShowList(ListNode* pHead)
    	{
    		while (pHead)
    		{
    			cout << pHead->val << " ";
    			pHead = pHead->next;
    		}
    		cout << endl;
    	}
    	//得到链表中最后一个结点
    	ListNode* GetLastNode(ListNode* pHead)
    	{
    		ListNode* pNode = pHead;
    		while (pNode->next != NULL)
    		{
    			pNode = pNode->next;
    		}
    		return pNode;
    	}
    };
    class Sort{
    public:
    	//冒泡排序
    	ListNode* BubbleSortList(ListNode* pHead)
    	{
    		ListNode* pNode1 = pHead;
    		ListNode* pNode2 = pHead;
    		if (pHead == NULL)
    			return NULL;
    		for (; pNode1->next != NULL; pNode1 = pNode1->next)
    		{
    			for (pNode2 = pHead; pNode2->next != NULL; pNode2 = pNode2->next)
    			{
    				if (pNode2->val>pNode2->next->val)
    				{
    					int temp = pNode2->val;
    					pNode2->val = pNode2->next->val;
    					pNode2->next->val = temp;
    				}
    			}
    		}
    		return pHead;
    	}
    	//快速排序
    	void QuickSortList(ListNode* pHead, ListNode* pEnd)
    	{
    		if (pHead != pEnd)
    		{
    			ListNode* part = Partition(pHead, pEnd);
    			QuickSortList(pHead, part);
    			QuickSortList(part->next, pEnd);
    
    		}
    	}
    	ListNode* Partition(ListNode* pBegin, ListNode* pEnd)
    	{
    
    		int key = pBegin->val;
    		ListNode* pSlow = pBegin;
    		ListNode* pFast = pSlow->next;
    		ListNode* temp = pBegin;
    
    		while (pFast != NULL&&pFast != pEnd->next)
    		{
    			if (pFast->val <key)
    			{
    				temp = pSlow;
    				pSlow = pSlow->next;
    
    				swap(pSlow->val, pFast->val);
    			}
    
    			pFast = pFast->next;
    		}
    		swap(pSlow->val, pBegin->val);
    		return temp;//返回的结点为支点节点的前一个结点    
    	}
    };
    int main()
    {
    	int array[] = { 3, 4, 5, 1, 2, 8, 7 };
    	List list;
    	Sort sort;
    	ListNode* pHead1 = list.CreatList(array, sizeof(array) / sizeof(array[0]));
    	ListNode* pHead2 = list.CreatList(array, sizeof(array) / sizeof(array[0]));
    	list.ShowList(pHead1);
    	sort.BubbleSortList(pHead1);
    	list.ShowList(pHead1);
    	ListNode* pEnd = list.GetLastNode(pHead2);
    	//cout<<pEnd->val<<endl;
    	sort.QuickSortList(pHead2, pEnd);
    	list.ShowList(pHead2);
    	system("pause");
    	return 0;
    }

## 9链表合并 ##

### 9.1将两个不同排序的链表进行升序排列 ###

算法思想：将不同排序的两个链表进行合并，如果要求合并的链表进行**降序（升序）**排列，那么需要将**升序（降序）**的链表进行逆置后再进行合并。

/*
    * 有两个链表，第一个升序，第二个降序，合并为一个升序链表
    */
    
    #include <iostream>
    
    #define NULL 0
    
    using namespace std;
    
    struct Node {
    	char data;
    	Node *next;
    };
    
    Node *create() {
    	Node *head = NULL;
    	Node *rear = head;
    	Node *p; // The pointer points to the new created node.
    	char tmp;
    
    	do {
    		cout << "Please input integer or char '#':";  //#是停止标志
    		cin >> tmp;
    		if (tmp != '#') {
    			p = new Node;
    			p->data = tmp;
    			p->next = NULL;
    
    			if (head == NULL) {
    				head = p;
    			}
    			else {
    				rear->next = p;
    			}
    			rear = p;
    		}
    	} while (tmp != '#');
    
    	return head;
    }
    
    void print(Node *head) {
    	Node *p = head;
    	if (head != NULL) {
    		do {
    			cout << p->data << ' ';
    			p = p->next;
    		} while (p != NULL);
    	}
    	cout << endl;
    }
    
    /**
    * Reverse list.
    * @param head The head pointer. Use & here since the function body changed the head pointer.
    * @return The reversed list header.
    */
    Node *reverse(Node *&head) {
    	if (head == NULL) {
    		return NULL;
    	}
    
    	Node *pre, *cur, *ne;
    	pre = head;
    	cur = head->next;
    	while (cur) {
    		ne = cur->next; // Store next pointer.
    		cur->next = pre; // Reverse the current code pointer.
    		pre = cur;
    		cur = ne;
    	}
    
    	head->next = NULL;
    	head = pre;
    	return head;
    }
    
    Node *merge(Node *l1, Node *l2) {
    	Node *l2Reverse = reverse(l2);
    	Node *p = new Node;
    	p->next = NULL;
    	Node *q = p;
    	while (l1 && l2Reverse) {
    		if (l1->data < l2Reverse->data) {
    			p->next = l1;
    			l1 = l1->next;
    		}
    		else {
    			p->next = l2Reverse;
    			l2Reverse = l2Reverse->next;
    		}
    		p = p->next;
    	}
    
    	if (l1) {
    		p->next = l1;
    	}
    	else if (l2Reverse) {
    		p->next = l2Reverse;
    	}
    
    	return q->next;
    }
    
    int main() {
    	Node *list1 = create();
    	cout << "The first list is:";
    	print(list1);
    
    	Node *list2 = create();
    	cout << "The second list is:";
    	print(list2);
    
    	cout << "The merged list is:";
    	Node *list = merge(list1, list2);
    	print(list);
    	system("pause");
    	return 0;
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

### 9.2将两个相同排序的链表进行升序排列 ###

/*将两个升序排序的链表合并成一个升序链*/
    
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    //定义结构体单元 
    typedef struct node{
    	int data;//结构体数据域 
    	struct node* next;//结构体指针域 
    }ElemSN;
    //逆向创建单向链表（头插法）
    ElemSN *PreCreatLink(int a[], int n)
    {
    	ElemSN *head = NULL, *p;
    	for (int i = n - 1; i>-1; i--)
    	{
    		p = (ElemSN*)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = head;
    		head = p;
    	}
    	return head;
    }
    
    
    ElemSN* Combine(ElemSN *head1, ElemSN *head2)
    {
    	ElemSN *head, *p, *tail = NULL;
    	head = NULL;
    	while (head1&&head2)
    	{
    		if (head1->data<head2->data)
    		{
    			p = head1;
    			head1 = head1->next;
    		}
    		else
    		{
    			p = head2;
    			head2 = head2->next;
    		}
    		p->next = NULL;
    		if (!head)
    			head = tail = p;
    		else
    		{
    			tail = tail->next = p;
    		}
    	}
    	if (head1)
    		p = head1;
    	else
    		p = head2;
    	tail->next = p;
    	return head;
    }
    
    //打印链表所有结点的值
    void PrintLink(ElemSN* head)
    {
    	ElemSN *p = head;
    	for (; p; p = p->next)
    		cout<<setw(5)<<p->data;
    	cout << endl;
    }
    
    
    int main()
    {
    	ElemSN *head1, *head2, *head;
    	int a[7] = { 2, 3, 5, 6, 7, 9, 11 };
    	int b[5] = { 2, 4, 5, 7, 9 };
    	
    	
    	head1 = PreCreatLink(a, 7);    //创建链表head1 
    	head2 = PreCreatLink(b, 5);    //创建链表head2 
    	cout << "链表A:" << endl;
    	PrintLink(head1);
    	cout << "链表B:" << endl;
    	PrintLink(head2);
    
    	head = Combine(head1, head2);  //将两个有序链表合并成一个有序链表 
    	cout << "合并的升序链表：" << endl;
    	PrintLink(head);       //输出链表 
    	system("pause");
    	return 0;
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

## 10测量一个链表的长度 ##

/*测量链表长度*/
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct node{
    	int data;
    	struct node *next;
    }ElemSN;
    
    ElemSN *CreateLink(int a[], int n)
    {
    	ElemSN *h, *p;
    	int i;
    	h = NULL;
    	for (i = n - 1; i >= 0; i--)
    	{
    		p = (ElemSN *)malloc(sizeof(ElemSN));
    		p->data = a[i];
    		p->next = h;
    		h = p;
    	}
    	return h;
    }
    
    void PrintLink(ElemSN *h)
    {
    	ElemSN *p;
    	for (p = h; p; p = p->next)
    		cout<<setw(5)<<p->data;
    	cout << endl;
    }
    
    ElemSN *DelHeadnode(ElemSN *h)
    {
    	ElemSN *delp;
    	delp = h;
    	h = h->next;
    	free(delp);
    	return h;
    }
    
    int ListLength(ElemSN *h)
    {
    	ElemSN *p;
    	int j;
    	p = h;
    	j = 0;       //用于存放单向链表的长度
    	while (p != NULL)
    	{
    		p = p->next;
    		j++;
    	}
    	return j;
    }
    
    int main()
    {
    	int a[8] = { 10, 20, 30, 40, 50, 60, 70, 80 };
    	ElemSN *head;
    	int length;
    	//创建链表
    	head = CreateLink(a, 8);
    	//输出链表
    	cout << "单向链表为：" << endl;
    	PrintLink(head);
    	//测量单向链表的长度
    	length = ListLength(head);
    	cout<<"该单向链表的长度为: "<<length;
    	cout << endl;
    	system("pause");
    	return 0;
    }

结果图：

![20190724221953812.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20220109/b77fad7bcbd145148798136391923bd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20220109/25d1f708f0f7452aa6c2c4082d6948d7.png
[20190724221953812.png]: /images/20220109/b2725d90c95b460ab4a43af012610d35.png