链表

单链表

单链表是由若干结点构成

单链表的结点只有一个指针域（单链表包含一个指针域和一个数据域）

链表的结构

头指针：指向第一个结点的地址

尾标志：终端结点的指针域为空

 

申请一个结点

1
2
3
4
5
6
typedef struct node
{
	DataType data;     //数据域
	struct node *next;   //指针域
}Node,*Link;   
//用typedef去声明结构体时，Node和*Link两个位置就被定义成了类型
1
Node st;    //struct node st;
1
Link p;     //struct node *p;  //p是一个指向结构体的指针

申请结点

1
p=(Link)malloc(sizeof(Node));
1
2
3
sizeof(node);     //计算出node结点的大小
malloc(sizeof(Node));   //用malloc分配给Link这么大的空间  malloc返回函数时viod*

分配地址以后，其把首地址分配给了指针p，在使用这块空间的时候，需要对这块地址进行强制转换。转换成指针p希望看到的类型。

指针p是一个Link类型，所以把malloc也定义成Link类型

 

如何引用数据元素？

1
2
(*p).data;
p->data;

如何引用指针域？

1
p->next;

 

链表的实现

单链表的遍历操作

操作接口：void displayNode(Link head);

1
2
3
4
5
6
7
8
9
void displayNode(Link head)
{
	p= head->next;
	while(p!=NULL)
	{
	cout<<p->next<<endl;
	p = p->next;
	}
}

求单链表的元素个数

操作接口：int length(Link head);

1
2
3
4
5
6
7
8
9
10
int length(Link head){
	p = head->next;    //p指向头指针的next域
	count = 0;         //count的数值为零
	while(p！=NULL)
	{
		p = p->next;    //如果p不为空，则p指向下一个结点的                           // next域
		count++;
 	}
 	return count;      //注意count和初始化返回值之间的关系
}

 

单链表的查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int queryNode(Link head,DaraType x){
	p = head->next;
    count = 0;
    while(p!=NULL)
    {
        if(p—>data==x)
        {
            cout<<data<<endl;    //找到则调用输出函数，并提                                  //前返回true
            return true;
        }
        p = p->next;
	}
    //如果链表结束，说明没有找到
    return false;
}

单链表的插入操作

操作接口：void insertNode(Link head,int i,DataType x);

1
2
3
4
node = (Link)malloc(sizeof(Node)); //申请一个结点node
node->data = x;                    //结点的数据域是x
node -> next = p->next;            //p的next域赋给node的                                    //next域
p->next = node;          //将node的数据域赋值给p的next域

RgcuI.png

  1. 工作指针p初始化

  2. 查找第i-1个结点并使用、工作指针p指向该结点

  3. 若查找不成功，则返回false

    3.1生成一个元素值为x的新结点；

    3.2将新结点s插入到结点p之后；

    3.3返回true；

     

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool insertNode(Link head,int i,DataType x)
{
    p = head;          //工作指针p指向头结点
    count = 0;
    while (p!=NULL&&count<i-1) //查找第i-1个结点
    {
        p=p->next;
        count++;
    }
    if(p==NULL)
    	return false;  //没有找到第i-1个结点
    else{
        node = (Link)malloc(sizeof(Node));//申请一个结点                                             //node
        node->data=x;
        node->next=p->next; //结点node插入结点p之后
        p->next=node;
        return ture;
    }
}

 

创建一个单链表—-头插法

操作接口：Link newList(DataType a[],int n)

头插法：将待插入结点插在头结点的后面。

初始化头结点

1
2
head = (Link)malloc(sizeof(Node));
head->next=NULL;

RgQaM.png

插入第一个元素

1
2
3
4
node = (Link)malloc(sizeof(Node));
node->data=a[0];
node->next=head->next;
head->next=node;

image-20221005111133614.png-20221005111133614.png" />

1
2
3
4
node = (Link)malloc(sizeof(Node));
node->data=a[1];
node->next=head->next;
head->next=node;

RgSNG.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class DataType>
Link newList(DataType a[],int n)
{
    head=(Link)malloc(sizeof(Node));
    head->next=NULL;
    //创建后续结点
    for(i = 0; i < n;i++)
    {
        node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        node->next = head->next;
		head->next = node;    
    }
    return head;
}

 

创建一个单链表—-尾插法

操作接口：Link newList(DataType a[],int n)

尾插法：将待插入结点插在终端结点的后面

1
2
3
head = (Link)malloc(sizeof(Node));  //创建一个头
head->next = NULL;           
rear = head;               //将head赋给rear

RgEdr.png

插入第一个元素结点

1
2
3
4
node = (Link)malloc(sizeof(Node)); //创建结点node
node->data = a[0];         //结点第一个数据域
rear->next = node;         //rear的next域是node
rear = node;               //将node名为rear

RgsFD.png

依次插入每一个结点

1
2
3
4
node = (Link)malloc(sizeof(Node))
node->dat = a[1];
rear->next = node;
rear = node;

RgVRF.png

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Link newList(DataType a[],int n)
{
  	head = (Link)malloc(sizeof(Node));
  	head->next = NULL;
  	rear = head;         //尾指针初始化
  	for(i = 0; i<n;i++)
  	{
  	 	node=(Link)malloc(sizeof(Node));//创建结点
  	 	node->data = a[i];
  	 	rear->next = node;
  	 	rear = ndoe;
  	}
  	rear->next = NULL;
  	return head;
}

 

单链表结点的删除

操作接口：bool deleteNode(Link head, Datatype x);

1
2
q->next = p->next;
free(p);

将q的next域指向p的next域，将被删除的p空间释放。

查找结点

在查找过程中，如果发现p所指向的结点data值不是要找的x，则p，q同时后移；一旦找到则执行删除操作

 

查找到p结点并将其删除

1.如何找到p结点。

2.如何保证p，q指针一前一后。

 

初始化
1
2
p = head->next;
q = head;
指针移动一次
1
2
q = p;
p = p->next;
删除中的特殊情况

在查找过程中，如果一直没有找到data域为x的结点，或者发现待删除的表是空表，则提前返回false

1
2
3
if(head==NULL||head->next==NULL){
	return false;
}

单链表的删除

1.判断是否是空表，如果是空表返回false；

2.工作指针p，q初始化

3.若p指针不为空，则继续下列循环：

​ 3.1如果找到data域等于x的结点，则：

​ 3.1.1摘链，将结点p的从链表上摘下来

​ 3.1.2释放别删除的结点

​ 3.1.3提前返回true，代表删除成功

4.循环结束了，说明没有找到和x相等的结点，则返回false

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool deleteNode(Link head,DataType x){
	if(head==NULL||head->next==NULL){
	return false;
	}
	p=head->next;
	q=head;
	while(p!=NULL){
		if(p->data==x){
		q->next=p->next;
		free(p);    //单链表的释放
		return true;
		}
		else{
			q = p;
			p = p->next;
		}
	}
	//如果循环结束了，说明没有找到和x相关的结点
	return false;
}

 

循环列表的实现

将单链表的首位相接，将终端结点的指针由空指针改为指向头结点，构成单循环链表，简称循环链表

RgY96.png

 

循环链表的插入

1
2
3
4
node = (Link)malloc(sizeof(Node));
node->data = x;
node->next = p->next;
p->next = node;

 

1
2
p! = NULL;     //p != head
p->next != NULL;    //p->next != head

 

双向链表

在单链表的每一个结点中再设置一个指向其前驱结点的指针域。

RglUP.png

data：数据域，储存数据元素

prior：指针域，储存该结点的前驱结点地址

next：指针域，储存该结点的后继结点地址

 

一元多项式的相加

题目描述：

实现两个一元n次多项式的加法。例如P(A)=x+3x2-5x5+7，P(B)=2x2+6x3+x5-4x6，求P(A)+P(B)。

首先弄清楚一元多项式的加法原理，然后明确多项式的存储方法。链表节点存储系数和指数，只存系数非0的项。

输入二项式数据的函数

给用户合适的提示，读入用户输入的系数和指数。
调用函数insert，将用户输入的二项式的一项插入到链表中去。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void inputPoly(Link head)
{
    int coefficient, exp;//系数和指数

    cout << "请输入系数和指数（如：\"2 3\"表示2x^3）:" << endl;
    cin >> coefficient>>exp;



    while (coefficient != 0 || exp != 0)//连续输入多个系数和指数
    {
        insert(head, coefficient, exp);//调函数输入多项式

        cout << "请输入系数和指数" << endl;
        cin >> coefficient>>exp;
    }
}

 

向多项式链表中插入元素的函数

int coefficient 一个多项式项的系数
int exp 一个多项式项的幂

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool insert(Link head, int coefficient, int exp)
{
    Link node;  //node指针指向新创建的节点
    Link q, p;   //q,p两个节点一前一后

    //创建一个新结点
    q = head;
    p = head->next;

    node = (Link)malloc(sizeof(Node));
    node->coefficient = coefficient;
    node->exp = exp;
    node->next = NULL;

    if (head->next == NULL)//空表,插第1个
    {
        head->next = node;
    }
    else
    {
        while (p != NULL) { 
            if (exp == p->exp) {
                p->coefficient += coefficient;
                return true;
            }
            //大于当前次数
            else if (exp > p->exp) {
                q->next = node;
                node->next = p;
                return true;
            }
            else {
                q = p;
                p = p->next;
            }
        }
        if (p == NULL) {
            q->next = node;
            node->next = NULL;
            return true;
        }
        //如果退出循环是当前指针p移动到链表结尾，则说明之前没有插入，那么当前node节点的指数值是最大值，此时插在链表的最后面
    }
    return true;
}

 

多项式的输出

数字转换为字符串函数itoa
标志是否为第一个节点的flag的设置
字符串连接函数strcat
字符串清空函数memset。memset(item,0,20);清空长20的字符串item

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
void Cout(Link head) {
    Link p; //指向链表要输出的结点
    cout << "多项式如下" << endl;
    p = head->next;

    if (p == NULL) {
        
        cout << "多项式为空" << endl;
        return;
    }
    // 不是空表
    char item[20] = ""; //要打印的当前多项式的一项
    char number[7] = ""; //暂时存放系数转换成的字符串
    bool isFirstItem = true;//标志是否为第一个节点的flag
    int flag = 0;
    //打印节点
    while (p != NULL) {
        memset(item, 0, 20); //清空字符串item
        _itoa_s(p->coefficient, number, 10);
        if (p->coefficient == 0) {//当为0时的判断非常容易出错
            if (flag == 0) {
                isFirstItem = true;	//如果第一项系数为0，移动指针，判断仍为true
                p = p->next;
                continue;
            }
            else if (flag == 1) {
                p = p->next;
                continue;
            }
        }
        else {
            if (isFirstItem != true && p->coefficient > 0) {
                strcat_s(item, "+");
            }
            if (p->coefficient == 1) {}
            else if (p->coefficient == -1) {
                strcat_s(item, "-");
            }
            else if (p->coefficient != 0) {
                strcat_s(item, number);
            }
            if (p->exp == 1) {
                strcat_s(item, "x");
            }
            else if (p->exp == 0) {
                if (p->coefficient == 1 || p->coefficient == -1)
                    strcat_s(item, "1");
            }
            else {
                strcat_s(item, "x^");
                _itoa_s(p->exp, number, 10);
                strcat_s(item, 20,number);
                //strcat_s(item, _itoa_s(p->exp, number, 10));
            }
            flag = 1;
        }
        
        cout << item ;//打印当前节点代表的项
        p = p->next;//指向下个结点
        isFirstItem = false; //flag标志不是第一项了
    }
 
    cout << endl;
    return;
}

 

链表合并

合并两个有序链表a，b到链表ab
heada.headb,headab分别为链表a,b,ab的头指针

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void combin2List(Link heada, Link headb, Link headab)
{
    Link pa, pb;//指向a，b链表和ab的指针
    pa = heada->next;
    pb = headb->next;
    while (pa != NULL && pb != NULL)//a,b链表都没有没有访问完毕
    {
        //如果指数a>指数b，a节点插入ab链表，a指针后移
        if (pa->exp > pb->exp) {
            insert(headab, pa->coefficient, pa->exp);
            pa = pa->next;
        }
        //如果指数a<指数b，b节点插入ab链表，b指针后移
        else if (pa->exp < pb->exp) {
            insert(headab, pb->coefficient, pb->exp);
            pb = pb->next;
        }
        //如果指数a==指数b，a、b系数相加，插入ab链表，a、b指针后移
        else if (pa->exp == pb->exp) {
            int coefficient;//系数
            coefficient = pa->coefficient + pb->coefficient;
            insert(headab, coefficient, pa->exp);
            pa = pa->next;
            pb = pb->next;
        }
        //如果a，b链表后还有尾巴，则加到链表后面   是否可以去掉
        while (pa != NULL) {
            insert(headab, pa->coefficient, pa->exp);
            pa = pa->next;
        }
        while (pb != NULL) {
            insert(headab, pb->coefficient, pb->exp);
            pb = pb->next;
        }
        return;
    }
    //如果a、b链表还有尾巴，将它加到ab链表后面
    while (pa != NULL)
    {
        insert(headab, pa->coefficient, pa->exp);
        pa = pa->next;
    }
    while (pb != NULL)
    {   
        insert(headab, pb->coefficient, pb->exp);
        pb = pb->next;
    }
    return;
}

 

释放空间

在main函数中一定不能忘记释放空间

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
void clearLink(Link head) {
    Link p, q;
    if (head == NULL)
        return;
    q = head->next;
    free(head);
    while (q != NULL) {
        p = q;
        q = q->next;
        free(p);
    }
}

 

头文件

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<string.h>
#include<malloc.h>
#include <cstring>

#undef UNICODE
#undef _UNICODE

using namespace std;

 

定义结点

其中，数据域包含指数和系数，还有一个指向下一个结点的指针

代码实现

1
2
3
4
5
6
typedef struct PNode
{
    int coefficient;//系数
    int exp;//指数
    struct PNode* next;
}*Link, Node;

 

函数声明

1
2
3
4
5
void inputPoly(Link head);//用于从控制台读入链表的函数
void Cout(Link head);//打印链表用的函数
bool insert(Link head, int coefficient, int exp);//向链表插入一个元素的函数
void combin2List(Link heada, Link headb, Link headab);//合并两个链表
void clearLink(Link head);

 

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main()
{
    Link headA, headB;//两个多项式的头指针
    Link headAB;//合并后的多项式的头指针

    /*链表的初始化*/
    headA = (Link)malloc(sizeof(Node));
    headA->next = NULL;
    headB = (Link)malloc(sizeof(Node));
    headB->next = NULL;
    headAB = (Link)malloc(sizeof(Node));
    headAB->next = NULL; 

    cout << "请输入第一个多项式的系数和指数，以（0 0）结束" << endl;
    inputPoly(headA);
    cout << "第一个" ;
    Cout(headA);
    cout << "请输入第二个多项式的系数和指数，以（0 0）结束" << endl;
    inputPoly(headB);
    cout << "第二个" ;
    Cout(headB);

    combin2List(headA, headB, headAB);
    cout << "合并后" ;
    Cout(headAB);

    clearLink(headA);
    clearLink(headB);
    clearLink(headAB);
    return 0;
}

 

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
请输入第一个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如："2 3"表示2x^3)：1 1
请输入系数和指数：-1 1
请输入系数和指数：2 2
请输入系数和指数：0 0
第一个多项式如下：
2x^2
请输入第二个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如："2 3"表示2x^3)：-2 2
请输入系数和指数：2 3
请输入系数和指数：4 5
请输入系数和指数：0 0
第二个多项式如下：
4x^5+2x^3-2x^2
合并后多项式如下：
4x^5+2x^3

输入

RrkBG.png

 

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
请输入第一个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如：2 3表示2x^3)：4 2
请输入系数和指数：-3 3
请输入系数和指数：-1 1
请输入系数和指数：2 0
请输入系数和指数：0 0
第一个多项式如下：
-3x^3+4x^2-x+2
请输入第二个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如：2 3表示2x^3)：4 5
请输入系数和指数：3 3
请输入系数和指数：-3 1
请输入系数和指数：0 0
第二个多项式如下：
4x^5+3x^3-3x
合并后多项式如下：
4x^5+4x^2-4x+2

RrWlM.png

 

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
请输入第一个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如：2 3表示2x^3)：3 5
请输入系数和指数：3 4
请输入系数和指数：-3 0
请输入系数和指数：1 4
请输入系数和指数：0 0
第一个多项式如下：
3x^5+4x^4-3
请输入第二个多项式的系数和指数，以(0 0)结束：
请输入系数和指数(如：2 3表示2x^3)：-3 5
请输入系数和指数：7 1
请输入系数和指数：2 4
请输入系数和指数：3 0
请输入系数和指数：0 0
第二个多项式如下：
-3x^5+2x^4+7x+3
合并后多项式如下：
6x^4+7x

RrUJr.png