单向无哑元结点
构造，析构，插入，删除，遍历输出，冒泡排序，选择排序，反转，
其中，冒泡排序的指针交换值得再看一看
# include
using namespace std;
class Node{
public:
int data;//数据
Node * next;//下一节点地址
Node(const int &d)//构造函数
{
data = d;
next = 0;
}
};
class linklist{
public:
//构造函数(无参数)
linklist(){
first = new Node;//头赋为NULL
last = 0;//尾赋为NULL
size = 0;//链表的规模
}
//参数为数组及其长度
/*
linklist(int * a, int len){
size = 0;
if (len == 0)
{
first = 0;
last = 0;
}
else
{
for (int i=0; inext = p;
//执行完此步之后，last指向了现在的结点
last = p;
}
size++;
}
}
}
*/
//析构函数
~linklist()
{
while (!first)
{
Node * t = first->next;//暂存first->next指向的下一片空间，再释放
delete first;
first = t;
}
}
//判空函数
int IsEmpty()
{
if (first->next == 0)
{
return 0;
}
return 1;
}
//遍历函数
void display()
{
Node * current = first;
while (current != NULL)
{
cout << current->data << " "<< "[" << current << "]";
current = current->next;
}
cout << endl;
}
//插入函数
int push(int date)
{
Node * Newnode = new Node(date);
Newnode->next = first;
first = Newnode;
size++;
return date;
}
//删除函数
void Eraser(int d)
{
Node * current = first;
Node * prev = NULL;
if (current == NULL)
{
cout << "无法删除空链表" << endl;
return;
}
while (current->data != d)
{
prev = current;
current = current->next;
if(current == NULL)
{
cout << "删除的值不存在" << endl;
return;
}
}
if (prev == NULL)
{
first = first->next;
}
else
{
prev->next = current->next;
}
delete current;
size--;
}
//查找函数
Node * find(int d)
{
Node * current = first;
if (current == NULL)
{
return NULL;
}
while (current->data != d)
{
current = current->next;
if(current == NULL)
{
cout << "查找的值不存在" << endl;
return NULL;
}
}
return current;
}
//冒泡
void bbsort()
{
if (first == NULL || first->next == NULL)return;
Node * p1 = first;
Node * p2;
Node * p1pre = 0;
Node * tail = 0;//尾指针是最新排好的一位
while (p1 != NULL && first->next != tail)//第二个条件是判断是否只剩两个数了
{
p2 = p1->next;
while (p2 != tail)
{
if (p1->data > p2->data)
{
if (p1pre == NULL)
{
first = p2;
}
else
{
p1pre->next = p2;
}
p1->next = p2->next;
p2->next = p1;
p1pre = p2;
p2 = p1->next;
}
else
{
p1pre = p1;
p1 = p1->next;
p2 = p2->next;
}
}
tail = p1;
p1 = first;
p1pre = NULL;
}
}
//老师的
void RankByNode()//函数功能：对链表内的节点通过交换进行排序 排序方法：从小到大；
{
Node *p1, *p2; //p1为当前节点，p2为下一个节点 p2=p1->next
Node *p1pre = 0; //p1的前驱
Node *tail = 0; //用于保存已经排好序的节点位置
Node * pHead = first;
p1 = pHead;
while (p1 != NULL && tail != pHead->next)
{
p2 = p1->next;
while (p2 != tail)
{
if (p1->data > p2->data)
{
if (p1pre == NULL)
{
pHead = p2;
}
else
{
p1pre->next = p2;
}
p1->next = p2->next;
p2->next = p1;
p1pre = p2;
p2 = p1->next;
}
else
{
p1pre = p1;
p1 = p1->next;
p2 = p2->next;
}
// LookThrough();
}
// if (p1->next == p2)
tail = p1;
//else
// tail = p2;
// LookThrough();
p1 = pHead;
p1pre = NULL;
}
first = pHead;
};
//逆序
void reserve()
{
if (first == NULL || first->next == NULL)return;
Node * prev = first;
Node * cur = prev->next;
while (cur != NULL)
{
Node * temp = cur->next;
cur->next = prev;
prev = cur;
cur = temp;
}
first->next = NULL;
first = prev;
}
//选择排序（升序），指针域交换
void selectsort()
{
if (first == NULL || first->next == NULL)return;
int min = 1000000000;
Node * cur = first;
Node * p = NULL;//用于记录当前最小值的位置
Node * p2 = NULL;//用于记录当前最小值的前驱
int size = 0;
//先换头指针
Node * prev;//前趋
while (cur != NULL)
{
size++;
if (cur->data < min)
{
min = cur->data;//更新最小值
p = cur;//记录当前
p2 = prev;//记录当前的前驱
}
prev = cur;
cur = cur->next;
}
Node * prev1 = p;//已经排好序的位置的最后一个
Node * prev2 = NULL;//cur的前趋
p2->next = p->next;//最小值前驱的下一个是最小值的下一个
p->next = first;//最小值下一个是first
first = p;//头指针指向当前
//换其他的
for (int i=2; inext;//当前是 已经排好序的位置的最后一个 的下一个
prev2 = prev1;//当前的前驱是 已经排好序的位置的最后一个
min = 1000000000;//极大数
while (cur != NULL)
{
if (cur->data< min)
{
min = cur->data;
p = cur;
p2 = prev2;
}
prev2 = cur;
cur = cur->next;
}
p2->next = p->next;//把断掉的地方连起来
Node * temp = prev1->next;//用temp记录 已经排好序的位置的下一个
prev1->next = p;//已经排好序的位置的下一个变成最小值的结点
p->next = temp;//小值的结点链接到temp
prev1 = p;//排好序的后移一位
}
}
private:
Node * first;//or head
Node * last;//or end
int size;
};
int main()
{
linklist list;
list.display();
int f = list.IsEmpty();
if (!f)
{
cout << "链表非空" << endl;
}
else
{
cout << "空链表" << endl;
}
list.Eraser(2);
list.push(3);
list.display();
cout << list.find(4) << endl;
cout << list.find(3) << endl;
list.Eraser(3);
cout << list.find(3) << endl;
list.display();
list.push(5);
list.push(6);
list.display();
list.Eraser(3);
list.Eraser(6);
list.display();
cout << list.find(5) << endl;
list.push(7);
list.push(7);
list.push(9);
list.push(4);
list.push(3);
list.push(8);
list.display();
// list.selectsort();
// list.display();
// list.reserve();
// list.display();
// list.RankByNode();
// list.display();
// list.reserve();
// list.display();
list.bbsort();
list.display();
list.~linklist();
system("pause");
return 0;
}
/*
空链表
无法删除空链表
3
查找的值不存在
0
0xa414f0
0
6 5
删除的值不存在
5
0xa414f0
7 6 2 2 9 5
2 2 5 6 7 9
请按任意键继续. . .
*/
