实现单链表的按顺序插入运算

假设单链表的节点结构体如下：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

按顺序插入就是要保证每个节点的值都是有序的，可以从头节点开始遍历，找到第一个大于等于插入值的节点，然后在该节点前插入新节点。

ListNode* insert(ListNode* head, int val) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    ListNode* curr = head;
    while (curr && curr->val < val) {
        prev = curr;
        curr = curr->next;
    }
    ListNode* newNode = new ListNode(val);
    prev->next = newNode;
    newNode->next = curr;
    return dummy.next;
}

其中，dummy节点是为了方便处理头节点而添加的虚拟节点，prev指向上一个节点，curr指向当前节点，循环中找到第一个大于等于插入值的节点之后，就在该节点前插入新节点。返回值是新的头节点，如果原来的头节点发生了改变，就返回虚拟节点的下一个节点。

相关问题

实现顺序表和单链表的基本运算,多项式的加法运算。

顺序表和单链表的基本运算：

1. 初始化操作：顺序表需要先定义一个数组来存储数据，然后利用数组创建一个顺序表，单链表需要先定义一个头结点，然后将头结点的指针域置为空。

2. 插入操作：顺序表需要先判断是否已经满了，如果没有满，则在指定位置插入元素，否则提示“表已满”。单链表需要先找到要插入的位置的前一个结点，然后将新结点插入到其后面。

3. 删除操作：顺序表需要先判断是否为空，如果不为空，则在指定位置删除元素，并将后面的元素向前移动，否则提示“表为空”。单链表需要先找到要删除的结点的前一个结点，然后将其指针域指向要删除结点的下一个结点，最后释放要删除结点的内存空间。

4. 查找操作：顺序表需要遍历整个表来查找指定元素，单链表同样需要遍历整个表，但是由于没有随机访问的能力，所以查找效率不如顺序表。

多项式的加法运算：

1. 定义多项式的结构体，包括系数和指数两个成员变量。

2. 创建两个多项式，并将它们以降幂顺序排列。

3. 定义一个新的多项式，用于保存两个多项式的和。

4. 分别将两个多项式的系数相加，指数相同的项合并，不同的项直接插入到新的多项式中。

5. 输出新的多项式。

(12)释放顺序表上。 实验题2/实现单链表的各种基本运算的算法 目的：领会单链表的存储结构和掌握单链表中各种基本运算算法的设计。内容：编写一个程序linklist.cpp，实现单链表的各种基本运算和整体建表算法(假设单链表的元素类型ElemType为char)，并在此基础上设计一个程序exp2-2.cpp完成以下功能。 (1)初始化单链表h。 (2)依次采用尾插法插入a、b、c、d、e元素。 (3)输出单链表h。 (4)输出单链表h的长度。 (5)判断单链表h是否为空。 (6)输出单链表h的第3个元素。 (7)输出元素a的位置。(8)在第4个元素的位置上插入f元素。 (9)输出单链表h。 (10)删除单链表h的第3个元素。(11)输出单链表h。 (12)释放单链表h。

以下是对于算法的实现：

#include <iostream>
using namespace std;

typedef struct node {
char data; // 假设单链表的元素类型ElemType为char
struct node * next;
}LNode, *LinkList;

void InitList(LinkList &L)
{
L = new LNode;
L->next = NULL;
}

void CreateList(LinkList &L)
{
InitList(L);
char ch = 'a';
LinkList p = L;
while(ch <= 'e')
{
LinkList tmp = new LNode;
tmp->data = ch++;
tmp->next = NULL;
p->next = tmp;
p = tmp;
}
}

int ListLength(LinkList L)
{
int cnt = 0;
LinkList p = L->next;
while(p)
{
cnt++;
p = p->next;
}
return cnt;
}

bool ListEmpty(LinkList L)
{
if(L->next == NULL)
return true;
return false;
}

char ListGetElement(LinkList L, int pos)
{
int cnt = 1;
LinkList p = L->next;
while(p && cnt < pos)
{
p = p->next;
cnt++;
}
return p->data;
}

int ListLocateElem(LinkList L, char e)
{
int cnt = 1;
LinkList p = L->next;
while(p)
{
if(p->data == e)
return cnt;
cnt++;
p = p->next;
}
return 0;
}

void ListInsert(LinkList &L, int pos, char e)
{
int cnt = 1;
LinkList p = L;
while(p && cnt < pos)
{
cnt++;
p = p->next;
}
LinkList tmp = new LNode;
tmp->data = e;
tmp->next = p->next;
p->next = tmp;
}

void ListDelete(LinkList &L, int pos)
{
int cnt = 1;
LinkList p = L;
while(p && cnt < pos)
{
cnt++;
p = p->next;
}
LinkList tmp = p->next;
p->next = tmp->next;
delete tmp;
}

void ListPrint(LinkList L)
{
LinkList p = L->next;
while(p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}

void DestroyList(LinkList &L)
{
LinkList p = L, q;
while(p)
{
q = p;
p = p->next;
delete q;
}
L = NULL;
}

int main()
{
LinkList L;
CreateList(L);
ListPrint(L);
cout << "List length: " << ListLength(L) << endl;
cout << "List empty: " << ListEmpty(L) << endl;
cout << "List 3rd element: " << ListGetElement(L, 3) << endl;
cout << "Element a index: " << ListLocateElem(L, 'a') << endl;
ListInsert(L, 4, 'f');
ListPrint(L);
ListDelete(L, 3);
ListPrint(L);
DestroyList(L);
return 0;
}