#include <iostream> //实现单链表的建立，测长和打印
#include <string>
using namespace std;
struct node // 定义节点类型，包含一个数据域和一个指针域
{
int data;
node *next;
};
node * creat()
{
node *head,*p,*s; // p指针为当前的指针，s为新建结点的指针
int temp,cycle = ;
//head = (node*)malloc(sizeof(node));
head = new node;
p = head;
while(cycle)
{
cout << "请输入int型数据" << endl;
cin >> temp;
if (temp != ) // 当temp不为零时，创建新的
{
//s = (node*)malloc(sizeof(node));
s = new node; //创建新的结点
s -> data = temp;
cout << "新节点为" << s -> data;
p -> next = s; // 使头结点的指针指向新生成的结点
p = s; // 使p指向当前新的结点
}
else
{
cout << "输入完成" <<endl;
cycle = ;
}
}
head = head -> next; //头指针
p -> next = nullptr; //置最后一个结点的指针为空
return head;
}
// 单链表测长
int length(node *head)
{
int n = ;
node *p = head;
while (p != nullptr )
{
p = p -> next;
n++;
}
return n;
}
// 单链表打印
void printlinklist(node * head)
{
node *p = head;
while( p != nullptr)
{
cout << "data is" << p -> data << endl;
p = p -> next;
}
}
// 单链表插入
node *insert(node * head, int num)
{
node *p0,*p1,*p2;
p1 = head;
p2 = new node;
p0 = new node;// 插入结点
p0 -> data = num; // 插入数据
// 若插入结点的数据大于原结点的数据，并且原结点的存在下一个元素
while(p0 -> data > p1 -> data && p1 -> next != nullptr)
{
p2 = p1;
p1 = p1 -> next; // 这时 p2->p1->p0 ??
}
if (p0 -> data <= p1 -> data)
{
if ( p1 == head)
{ // 头部前插入 p0和p1的位置是 P0->P1->
head = p0;
p0 -> next =p1;
}
else
{ // 插入中间节点， p2->p0->p1
p2 -> next = p0;
p0 -> next = p1;
}
}
else
{// 尾部插入结点， p2->p1->p0->null
p1 -> next = p0;
p0 -> next = nullptr;
}
return head;
}
//删除单链表
node *del(node *head, int num)
{
node *p1,*p2;
p2 = new node;
p1 = head;
while(num != p1 -> data && p1 -> next != nullptr)
{
p2 = p1;
p1 = p1 -> next; // p2->p1
}
if (num == p1->data)
{
if (p1 == head) // 删除头结点
{
head =p1 -> next;
delete p1;
}
else
{
p2 -> next = p1 -> next;
delete p1;
}
}
else
{
cout << "could not been found in current single linklist"<< endl;
}
return head;
}
int main()
{
cout << "创建单链表" << endl;
node *head = creat();
cout << endl;
cout << "计算链表的长度" << endl;
int n = length(head);
cout << "the length of the linklist is " << n << endl;
cout << endl;
cout << "print the linklist" << endl;
printlinklist(head);
cout << endl;
cout << "insert the node" << endl;
cout << "please insert the data";
int indata;
cin >> indata;
head = insert(head,indata);
printlinklist(head);
cout << endl;
cout << "delete the node" << endl;
cout << "input the data for deleting ";
int deldata;
cin >> deldata;
head = del(head,deldata);
printlinklist(head);
cout <<endl;
return ;
}