＜数据结构＞创建一个单链表_如何建立一个单链表

单链表基本操作的实现

内容：构建线性表的链式存储结构，采用动态分配方式实现单链表的初始化，数据的插入，删除，输出单链表内中各元素，求单链表的长度，实现单链表中数据结点的按值排序，实现单链表的逆置，合并两个有序的单链表（有序的a表和有序的b表合并之后的结果保存在a表中）等操作。
同时：
（1）要有能根据用户的输入来选择不同运算的菜单界面。
（2）单链表中数据元素的类型统一抽象表示为ElemType类型，具体类型不限，可以是整型、实型、字符型、或者是自己构造的一种结构体类型。

代码如下：

#include <iostream>
#define ElemType int
using namespace std;

//带头结点的单链表类，头结点存放单链表长度 
class Single_List {
   
private:
    ElemType data;
    Single_List* next;
public:

    Single_List() {
   };

    //单链表的创建函数，尾插法 
    Single_List* Create(int len) {
   
        Single_List* prev, * head, * tail;
        head = new Single_List;
        head->data = len;
        head->next = NULL;
        prev = head;
        if (len == 0) {
   
            goto end;
        }
        cout << "请输入各个结点的数值：" << endl;
        while (len--) {
   
            int data;
            tail = new Single_List;
            cin >> data;
            this->attach(prev, tail, data);
            prev = tail;
        }
    end:    return head;
    }

    void attach(Single_List* prev, Single_List* tail, int data) {
   
        tail->next = NULL;
        tail->data = data;
        prev->next = tail;
    }

    int getLength(Single_List* list) {
   
        return list->data;
    }

    //判断单链表是否为空的函数 
    bool Isempty(Single_List* list) {
   
        return list->data == 0;
    }

    //单链表的打印函数
    void Print(Single_List* list) {
   
        if (list->Isempty(list)) {
   
            cout << "单链表为空" << endl;
            return;
        }
        int len = list->data;
        Single_List* ptrl = list->next;
        for (int i = 0; i < len; i++) {
   
            cout << ptrl->data << " ";
            ptrl = ptrl->next;
        }
    }

    //在第index个结点后面插入数值为data的结点的函数 
    Single_List* Insert(Single_List* list, int index, int data) {
   
        Single_List* prev = list;
        Single_List* insert;
        insert = new Single_List;
        int len = list->getLength(list);
        //链表为空时,无论index为多少，只能插在第一个位置 
        if (this->Isempty(list)) {
   
            this->attach(prev, insert, data);
            list->data++;
            return list;
        }
        //如果插入的位置大于等于链表长度直接插到末尾， 
        index = (list->data <= index) ? list->data : index;
        for (int i = 0; i < index; i++) {
   
            prev = prev->next;
        }
        insert->data = data;
        insert->next = prev->next;
        prev->next = insert;
        list->data++;
        return list;
    }

    //寻找第k个结点的函数,只适用链表不为空的情况 
    Single_List* Findkth(Single_List* list, int k
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