考研报名等待之时闲来无事，写了一个简单的单链表。
简单实现了以下功能：
- 头插法建立单链表
- 按序遍历链表
- 单链表原地排序（不使用额外的空间）
- 单链表按序删除
- 单链表原地倒置
附上代码如下：
节点结构体定义
typedef int ElemType;
typedef struct Lnode{
ElemType data;
struct Lnode * next;
}Lnode, *Linklist;
头插法建立单链表
// 初始化单链表
Linklist initLinkList()
{
int n;
cout << "how many nodes do you want to creat?" << endl;
cout << "input : ";
cin >> n;
// 创建头节点
Lnode * L;
L = (Linklist)malloc(sizeof(Lnode));
L -> next = NULL;
Lnode * rear = L;
while(n--)
{
Lnode * p;
p = (Linklist)malloc(sizeof(Lnode));
ElemType data;
cout << "input data: ";
cin >> data;
p -> data = data;
// 使用尾插法
p -> next = rear -> next;
rear -> next = p;
rear = p;
}
return L;
}
按序遍历链表
// 遍历单链表
void Traversal(Linklist L)
{
Lnode * p = L-> next;
while(p)
{
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
cout << endl;
}
单链表原地排序
void sort(Linklist &L)
{
// 使用头插法，顺序插入
Lnode *p = L -> next, *s, *pre;
L -> next = NULL;
// 按照顺序依次插入
while(p)
{
// 保存p节点的下一个节点
s = p -> next;
// 将p节点插入链表中,即找到插入p节点的前一个节点pre，将p插入到pre之后
pre = L;
while(pre -> next && pre -> next -> data < p->data)
pre = pre -> next;
p -> next = pre -> next;
pre -> next = p;
// 将p还原
p = s;
}
}
空间复杂度为O（1），时间复杂度为O（n^2）
该算法的实现也可以采用以空间换时间的方法，将单链表存储到数组中，使用时间复杂度为O（nlogn）的算法，但是相应的空间复杂度会上升为O（n）
按序删除单链表
// 删除单链表
void ruin(Linklist L)
{
Lnode * p = L-> next, *s;
// 遍历删除每一个节点
while(p)
{
s = p;
p = p->next;
cout << "Node which data is " << s->data << " has been deleted!" << endl;
free(s);
}
cout << "head node delete!" << endl;
free(L);
}
原地倒置
// 单链表倒置
void reverse(Linklist &L)
{
// 基本思想为，从第一个结点开始，使用头插法依次插入到头节点之后
Lnode *p = L -> next, *s;
L -> next = NULL;
while(p)
{
s = p -> next;
p -> next = L -> next;
L -> next = p;
p = s;
}
}
空间复杂度为O（1）， 时间复杂度为O（n）
代码整体如下（包括一部分测试）
# include<iostream>
using namespace std;
// 数据类型定义
typedef int ElemType;
// 节点结构定义
typedef struct Lnode{
ElemType data;
struct Lnode * next;
}Lnode, *Linklist;
// 初始化单链表
Linklist initLinkList()
{
int n;
cout << "how many nodes do you want to creat?" << endl;
cout << "input : ";
cin >> n;
// 创建头节点
Lnode * L;
L = (Linklist)malloc(sizeof(Lnode));
L -> next = NULL;
Lnode * rear = L;
// 尾插法依次插入节点
while(n--)
{
Lnode * p;
p = (Linklist)malloc(sizeof(Lnode));
ElemType data;
cout << "input data: ";
cin >> data;
p -> data = data;
// 使用尾插法
p -> next = rear -> next;
rear -> next = p;
rear = p;
}
return L;
}
// 遍历单链表
void Traversal(Linklist L)
{
Lnode * p = L-> next;
while(p)
{
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
cout << endl;
}
// 删除单链表
void ruin(Linklist L)
{
Lnode * p = L-> next, *s;
// 遍历删除每一个节点
while(p)
{
s = p;
p = p->next;
// cout << "Node which data is " << s->data << " has been deleted!" << endl;
free(s);
}
// cout << "head node delete!" << endl;
free(L);
cout << "delete success!" << endl;
}
// 单链表排序
void sort(Linklist &L)
{
// 使用头插法，顺序插入
Lnode *p = L -> next, *s, *pre;
L -> next = NULL;
// 按照顺序依次插入
while(p)
{
// 保存p节点的下一个节点
s = p -> next;
// 将p节点插入链表中,即找到插入p节点的前一个节点pre，将p插入到pre之后
pre = L;
while(pre -> next && pre -> next -> data < p->data)
pre = pre -> next;
p -> next = pre -> next;
pre -> next = p;
// 将p还原
p = s;
}
}
// 单链表倒置
void reverse(Linklist &L)
{
// 基本思想为，从第一个结点开始，使用头插法依次插入到头节点之后
Lnode *p = L -> next, *s;
L -> next = NULL;
while(p)
{
s = p -> next;
p -> next = L -> next;
L -> next = p;
p = s;
}
}
int main()
{
// 初始化
Linklist L = initLinkList();
// 遍历
cout << "start traversal! " << endl;
Traversal(L);
// 排序
cout << "after sort, link list is :" << endl;
sort(L);
Traversal(L);
// 倒置
cout << "after reverse, link list is: " << endl;
reverse(L);
Traversal(L);
// 删除
cout << "delete linklist" << endl;
ruin(L);
return 0;
}
就这样！感谢阅读!
