声明：仅供留档查阅，仅用作起到提示引导性作用，仅用作学习交流，切勿直接照搬

作业Ch2-1:

总结单链表中引入头节点的原因？

为了使操作方便，加了头结点之后，无论单链表是否为空，头指针始终指向头节点，因此空表和非空表的处理也统一了

作业Ch2-2:

编程题目，逆置一个单链表为一个新表，编制源代码并运行。

没用ai跑，自己写的，实际上原理就是头插法和尾插法，两个方法的顺序是相反的

重做了，原来的做法不符题意，虽然功能是一样的，新做法的思路↓

nizhi函数的原理是通过改变链表中节点的链接顺序来实现链表的反转。

具体步骤如下：

  1. 初始化：创建一个新的空链表（只有头节点，头节点的next指针为nullptr）。
  2. 遍历原链表：从原链表的第一个节点开始，每次处理一个节点。
  3. 插入新链表：将当前处理的节点插入到新链表的头节点之后。具体操作是先将当前节点的next指针指向新链表的第一个节点，然后再将头节点的next指针指向当前节点。
  4. 移动到下一个节点：保存下一个要处理的节点的位置，然后将当前节点从原链表中断开（也就是将当前节点的next指针置为nullptr），最后移动到下一个要处理的节点。
  5. 重复步骤3和4，直到原链表中所有的节点都被处理完毕。

这样，原链表中的节点就被逐个移动到了新链表中，并且在新链表中的顺序与在原链表中的顺序相反，从而实现了链表的反转。这个过程中，我们没有创建任何新的节点，只是改变了已有节点之间的链接关系。因此，这个函数的时间复杂度为O(n)，空间复杂度为O(1)。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
using namespace std;

template<typename DataType>
struct Node
{
    DataType data;
    Node<DataType>* next;
};

template<typename DataType>
class linklist
{
public:
    linklist();
    linklist(DataType a[], int n);
    ~linklist();
    void nizhi();
    void display();
private:
    Node<DataType>* first;//头结点
};

template<typename DataType>
linklist<DataType>::linklist()
{
    first = new Node<DataType>;
    first->next = nullptr;//头结点指针置空
}

template <typename DataType>
linklist<DataType>::linklist(DataType a[], int n)
{
    first = new Node<DataType>;              // 生成头结点
    Node<DataType>* r = first, * s = nullptr; // 尾指针初始化
    for (int i = 0; i < n; i++)
    {
        s = new Node<DataType>;
        s->data = a[i];
        r->next = s;
        r = s; // 将结点s插入到终端结点之后
    }
    r->next = nullptr; // 单链表建立完毕，将终端结点的指针域置空
}

template<typename DataType>
void linklist<DataType>::nizhi()
{
    Node<DataType>* p = first->next;
    Node<DataType>* q;
    first->next = nullptr;
    while (p != nullptr)
    {
        q = p->next; // 保存下一个节点的位置
        p->next = first->next; // 将当前节点插入到头节点之后
        first->next = p;
        p = q; // 移动到下一个节点
    }
}

template<typename DataType>
void linklist<DataType>::display()
{
    Node<DataType>* p = first->next;
    while (p != nullptr)
    {
        cout << p->data << "\t";
        p = p->next;
    }
}

template <class DataType>
linklist<DataType>::~linklist()
{
    Node<DataType>* q = NULL;
    while (first != NULL) // 释放单链表的每一个结点的存储空间
    {
        q = first;           // 暂存被释放结点
        first = first->next; // first指向被释放结点的下一个结点
        delete q;
    }
}
    /*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
            .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    佛祖保佑       永不宕机     永无BUG
*/

int main()
{
    int maxsize;
    cout << "请输入你要创建数组的大小" << endl;
    cin >> maxsize;
    int* a = new int[maxsize];
    for (int i = 0; i < maxsize; i++)
    {
        a[i] = i + 1;
    }
    cout << "已创建一个最大长度" << maxsize << "的链表" << endl;
    linklist<int> L{ a, maxsize };
    cout << "执行遍历链表" << endl;
    L.display();
    cout << endl;
    cout << "下面逆置最大长度为" << maxsize << "的链表" << endl;
    L.nizhi();
    L.display();
    return 0;
}

作业Ch2-3:

教材P66, 2(1)题：请说明顺序表和单链表有何优缺点？并分析不同情况下采用何种存储结构更合适？

顺序表的优点:① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间;② 可以快速地存取表中任一位置的元素(即随机存取)。

顺序表的缺点:① 插入和删除操作需移动大量元素;② 表的容量难以确定;③ 造成存储空间的“碎片”。

单链表的优点:① 不必事先知道线性表的长度;② 插入和删除元素时只需修改指针,不用移动元素。

单链表的缺点:① 指针的结构性开销;② 存取表中任意元素不方便,只能进行顺序存取。

⑴ 应选用顺序存储结构。因为顺序表是随机存取结构,单链表是顺序存取结构。本题很少进行插入和删除操作,所以空间变化不大,且需要快速存取,所以应选用顺序存储结构。

⑵ 应选用链接存储结构。链表容易实现表容量的扩充,适合表的长度动态发生变化。⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多,需要经常修改、扩充和删除各种信息, 才能适应不断发展的需要。而顺序表的插入、删除的效率低,故不合适。

作业Ch2-4:

算法设计：在顺序表中删除所有元素值为x的元素，要求空间复杂度为O(1)，给出算法伪代码和源代码。

ai加自己写的，有两个方法，第一个方法比较好一些

伪代码

法一

1
2
3
4
5
6
7
输入：顺序表data，元素x
输出：删除所有值为x的元素后的顺序表

1. 初始化一个新的索引j为0
2. 对于顺序表data中的每个元素，执行以下操作：
   1. 如果当前元素不等于x，则将当前元素复制到j位置，并将j增加1
3. 将顺序表data的长度设置为j

法二

1
2
3
4
5
6
7
8
输入：顺序表data，元素x
输出：删除所有值为x的元素后的顺序表

1. 对于顺序表data中的每个元素，执行以下操作：
   1. 如果当前元素等于x，则执行以下操作：
      1. 对于从当前元素到倒数第二个元素的每个元素，将下一个元素复制到当前位置
      2. 将顺序表data的长度减1
      3. 将当前索引减1（因为删除了元素）

源代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <random>
#include <chrono>

using namespace std;

const int MaxSize = 100;            //100只是示例性的数据，根据实际问题具体定义

template <class DataType>          //定义模板类SeqList
class SeqList
{
public:
    SeqList();                     //无参构造函数，建立空的顺序表
    SeqList(DataType a[], int n);      //有参构造函数，建立长度为n的顺序表
    ~SeqList();                    //析构函数
    DataType Delete(int i);            //删除操作，删除第i个元素
    void PrintList();                 //遍历操作，按序号依次输出各元素
private:
    DataType data[MaxSize];          //存放数据元素的数组
    int length;                       //线性表的长度
};

template <class DataType>
DataType SeqList<DataType> ::Delete(int x)
{   /*这段代码遍历顺序表，每次遇到值不等于x的元素时，就将其复制到新的位置。最后，它将顺序表的长度设置为新的长度。这个算法的空间复杂度是O(1)，因为它只使用了固定数量的额外空间。*/
    int j = 0;
    for (int i = 0; i < length; i++)
    {
        if (data[i] != x)
        {
            data[j] = data[i];
            j++;
        }
        
    }
    length = j;
    return x;
    /*
    这个有两种做法，还有一种是直接删除。每次遇到值为x的元素时，就将其删除。但是，这种方法的时间复杂度是O(n^2)，因为每次删除操作都需要O(n)的时间。
    for (int i = 0; i < length; i++)
    {
        if (data[i] == x)
        {
            for (int j = i; j < length - 1; j++)
            {
                data[j] = data[j + 1];
            }
            length--;
            i--;  // 因为删除了元素，所以需要将索引减1
        }
    }*/
}

template<class DataType>
SeqList<DataType> :: ~SeqList()
{

}

template <class DataType>
SeqList<DataType> ::SeqList()
{
    length = 0;
}

template <class DataType>
SeqList<DataType> ::SeqList(DataType a[], int n)
{
    if (n > MaxSize)
        throw "参数非法";
    for (int i = 0; i < n; i++)
        data[i] = a[i];
    length = n;
}

template <class DataType>
void SeqList<DataType> ::PrintList()
{
    for (int i = 0; i < length; i++)
        cout << data[i]<<" ";                   //依次输出线性表的元素值
}
    /*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
            .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    佛祖保佑       永不宕机     永无BUG
*/
int main()
{
    // 使用当前时间作为随机数生成器的种子
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    // 创建一个随机数生成器
    default_random_engine generator(seed);
    // 创建一个均匀分布的随机数生成器，范围从1到100
    uniform_int_distribution<int> distribution(1, 10);
    int maxsize;
    cout << "请输入你要创建表的大小" << endl;
    cin >> maxsize;
    int* a = new int[maxsize];
    for (int i = 0; i < maxsize; i++)
    {
        a[i] = distribution(generator);//赋值
    }
    cout << "已创建一个最大长度" << maxsize << "的顺序表" << endl;
    SeqList<int> L{ a, maxsize };
    cout << "*******执行遍历链表******" << endl;
    L.PrintList();
    cout << endl;
    cout << "**************************" << endl;
    cout << "请输入你要删除的数据" << endl;
    int del;
    cin >> del;
    cout << "删除的数据是" << L.Delete(del) << endl;
    cout << "*******执行遍历链表******" << endl;
    L.PrintList();
    cout << endl;
    cout << "**************************" << endl;
    return 0;
}

作业Ch2-5:算法设计：已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中大于mink且小于maxk的所有元素，并释放被删结点的存储空间，给出算法伪代码和源代码。

这个也是借助ai加自己写的，就加了一个条件判断，另外还需要加强一下头插法尾插法的算法，不熟练

伪代码

1
2
3
4
5
6
1. 定义一个模板函数Delete，接受两个参数mink和maxk。
2. 初始化两个指针p和q，其中p指向链表的第一个节点，q指向头节点。
3. 进入一个while循环，条件是p不为空。
   - 如果p指向的节点的数据在mink和maxk之间，则删除该节点，并将q的next指针指向p的next节点。然后更新p为q的next节点。
   - 如果p指向的节点的数据不在mink和maxk之间，则将q更新为p，然后将p更新为p的next节点。
4. 循环结束后，所有在mink和maxk之间的节点都被删除。

源代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>                  //引入输入输出流
#include <random>
#include <chrono>

using namespace std;

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

template <typename DataType>
class LinkList
{
public:
    LinkList();                      //无参构造函数，建立只有头结点的空链表
    LinkList(DataType a[], int n);       //有参构造函数，建立有n个元素的单链表
    ~LinkList();                     //析构函数
    void Delete(int mink, int maxk);
    void PrintList();                  //遍历操作，按序号依次输出各元素

private:
    Node<DataType>* first;           //单链表的头指针
}; 

template <typename DataType>
void LinkList<DataType> ::Delete(int mink,int maxk)
{
    DataType x;
    Node<DataType>* p = first->next, * q = first;        //工作指针p指向头结点
    while (p != nullptr)
    {
        if ((p->data<maxk) &&(p->data>mink) )
        {
            q->next = p->next;
            delete p;
            p = q->next;
        }
        else
        {
            q = p;
            p = p->next;
            
        }
    }
}

template <typename DataType>
LinkList<DataType> ::LinkList()
{
    first = new Node<DataType>;              //生成头结点
    first->next = nullptr;                      //头结点的指针域置空
}

template <class DataType>
LinkList<DataType> :: ~LinkList()
{
    Node<DataType>* q = NULL;
    while (first != NULL)        //释放单链表的每一个结点的存储空间
    {
        q = first;                 //暂存被释放结点
        first = first->next;         // first指向被释放结点的下一个结点
        delete q;
    }
}

template <typename DataType>
void LinkList<DataType> ::PrintList()
{
    Node<DataType>* p = first->next;                //工作指针p初始化
    while (p != nullptr)
    {
        cout << p->data << "\t";
        p = p->next;                 //工作指针p后移，注意不能写作p++
    }
}

//尾插法构造
template <typename DataType>
LinkList<DataType> ::LinkList(DataType a[], int n)
{
    first = new Node<DataType>;                    //生成头结点
    Node<DataType>* r = first, * s = nullptr;           //尾指针初始化
    for (int i = 0; i < n; i++)
    {
        s = new Node<DataType>; s->data = a[i];
        r->next = s; r = s;                 //将结点s插入到终端结点之后
    }
    r->next = nullptr;        //单链表建立完毕，将终端结点的指针域置空
}

int main()
{
    int maxsize;
    cout << "请输入你要创建表的大小" << endl;
    cin >> maxsize;
    int* a = new int[maxsize];
    for (int i = 0; i < maxsize; i++)
    {
        a[i] = i;
    }
    cout << "已创建一个最大长度" << maxsize << "的单链表" << endl;
    LinkList<int> L{ a, maxsize };
    cout << "*******执行遍历链表******" << endl;
    L.PrintList();
    cout << endl;
    cout << "**************************" << endl;
    cout << "请输入左右界定范围mink和maxk" << endl;
    int mink, maxk;
    cin >> mink >> maxk;
    cout << "**************************" << endl;
    L.Delete(mink, maxk);
    cout << "题解删除操作已执行完毕" << endl;
    cout << "*******执行遍历链表******" << endl;
    L.PrintList();
    cout << endl;
    cout << "**************************" << endl;
}