单链表的基本操作--c++

  1 #include <iostream>     //实现单链表的建立，测长和打印
  2 #include <string>
  3 using namespace std;
  4 struct node            // 定义节点类型，包含一个数据域和一个指针域
  5 {
  6     int data;
  7     node *next;
  8 };
  9 node * creat()
 10 {
 11     node *head,*p,*s;   // p指针为当前的指针，s为新建结点的指针
 12     int temp,cycle = 1;
 13     //head = (node*)malloc(sizeof(node));
 14     head = new node;
 15     p = head;
 16     while(cycle)
 17     {
 18         cout << "请输入int型数据" << endl;
 19         cin >> temp;
 20         if (temp != 0)             // 当temp不为零时，创建新的
 21         {
 22             //s = (node*)malloc(sizeof(node));
 23             s = new node;         //创建新的结点
 24             s -> data = temp;
 25             cout << "新节点为" << s -> data;
 26             p -> next = s;  // 使头结点的指针指向新生成的结点
 27             p = s;          //  使p指向当前新的结点
 28         }
 29         else
 30         {
 31             cout << "输入完成" <<endl;
 32             cycle = 0;
 33         }
 34     }
 35     head = head -> next;      //头指针
 36     p -> next = nullptr;     //置最后一个结点的指针为空
 37     return head;
 38 }
 39 // 单链表测长
 40 int length(node *head)
 41 {
 42     int  n = 0;
 43     node *p = head;
 44     while (p != nullptr )
 45     {
 46         p = p -> next;
 47         n++;
 48     }
 49     return n;
 50 }
 51 // 单链表打印
 52 void printlinklist(node * head)
 53 {
 54     node *p = head;
 55     while( p != nullptr)
 56     {
 57         cout << "data is" << p -> data << endl;
 58         p = p -> next;
 59     }
 60 }
 61 // 单链表插入
 62 node *insert(node * head, int num)
 63 {
 64     node *p0,*p1,*p2;
 65     p1 = head;
 66     p2 = new node;
 67     p0 = new node;// 插入结点
 68     p0 -> data = num;  // 插入数据
 69     // 若插入结点的数据大于原结点的数据，并且原结点的存在下一个元素
 70     while(p0 -> data > p1 -> data && p1 -> next != nullptr)
 71     {
 72         p2 = p1;
 73         p1 = p1 -> next;  // 这时  p2->p1->p0  ??
 74     }
 75     if (p0 -> data <= p1 -> data)
 76     {
 77         if ( p1 == head)
 78         {  //  头部前插入    p0和p1的位置是 P0->P1->
 79             head = p0;
 80             p0 -> next =p1;
 81         }
 82         else
 83         {  // 插入中间节点，   p2->p0->p1
 84             p2 -> next = p0;
 85             p0 -> next = p1;
 86         }
 87     }
 88     else
 89     {// 尾部插入结点，  p2->p1->p0->null
 90         p1 -> next = p0;
 91         p0 -> next = nullptr;
 92     }
 93     return head;
 94 }
 95 //删除单链表
 96 node *del(node *head, int num)
 97 {
 98     node *p1,*p2;
 99     p2 = new node;
100     p1 = head;
101     while(num != p1 -> data && p1 -> next != nullptr)
102     {
103         p2 = p1;
104         p1 = p1 -> next;   //  p2->p1
105     }
106     if (num == p1->data)
107     {
108         if (p1 == head)  // 删除头结点
109         {
110             head =p1 -> next;
111             delete p1;
112         }
113         else
114         {
115             p2 -> next = p1 -> next;
116             delete p1;
117         }
118     }
119     else
120     {
121         cout << "could not been found in current single linklist"<< endl;
122     }
123     return head;
124 }
125 int main()
126 {
127 
128     cout << "创建单链表" << endl;
129     node *head = creat();
130     cout << endl;
131 
132     cout << "计算链表的长度" << endl;
133     int n = length(head);
134     cout << "the length of the linklist is " << n << endl;
135     cout << endl;
136 
137     cout << "print the linklist" << endl;
138     printlinklist(head);
139     cout << endl;
140 
141     cout << "insert the node" << endl;
142     cout << "please insert the data";
143     int indata;
144     cin >> indata;
145     head = insert(head,indata);
146     printlinklist(head);
147     cout << endl;
148 
149     cout << "delete the node" << endl;
150     cout << "input the data for deleting ";
151     int deldata;
152     cin >> deldata;
153     head = del(head,deldata);
154     printlinklist(head);
155     cout <<endl;
156     return 0;
157 }