C++链表的增删改查等基本操作

C++ 有头节点链表的基本操作

#include <iostream> using namespace std; typedef struct node{ int num; node* next; }Node; class list{ Node* head; static int size; public: //先是定义了一个Node结构类head的指针，指向链表的第一个节点（头结点），其后为head分配内存，初始化类成员 list(){ cout<<"构造函数的调用..."<<endl; head = new Node; head->num = 0; head->next = NULL; } ~list(){ cout<<"析构函数的调用..."<<endl; delete head; } //创建一个链表 void createList(){ Node* p = head; for (int i = 1; i < 10; i++) { Node* pNew = new Node; pNew->num = i; // 将新节点的值赋值为i pNew->next = NULL; p->next = pNew; // 上一个节点指向这个新建立的节点 p = pNew; // p节点指向这个新的节点 size++; } } //在头部插入节点数据 void insertHeadNode(int n){ Node* p = head; Node* pnew = new Node; pnew->num = n; if(p == NULL){ p->next = pnew; pnew->next = NULL; } else{ pnew->next = p->next; p->next = pnew; size++; } } //在尾部插入节点数据 void inserEndtNode(int n){ Node* p = head; Node* pnew = new Node; pnew->num = n; pnew->next = NULL; //再将新插入节点作为最后一个节点 if(p == NULL){ p = pnew; } else{ while(p->next){ //遍历查找到最后一个节点 p = p->next; } p->next = pnew; //将找到的最后一个节点的Next指针指向插入节点 size++; } } //在指定位置插入节点数据，n是要插入的数据，add是要插入的位置 void insertNode(int n,int add){ Node* p = head; Node* pnew = new Node; pnew->num = n; if(p == NULL){ p = pnew; pnew->next = NULL; } else{ if(add<1 || add>size){ cout<<"插入的位置有误！"<<endl; } else{ // 1 <=add< size int i = 1; while(i < add){ //遍历查找插入的位置，第add个位置 p = p->next; i++; } pnew->next = p->next; p->next = pnew; size++; } } } //修改指定位置的节点数据 void modNode(int old,int xin){ Node* p = head; if(p == NULL){ cout<<"链表为空！！"<<endl; } else{ while(p->next){ p = p->next; if(p->num == old){ //遍历查找到指定节点数据，并将其改为新数据 p->num = xin; } } } } //查找指定节点的前一个节点位置 int findNode(int n){ Node* p = head; int add=0; while(p->num != n){ p = p->next; add++; } return add; } //删除指定位置的节点数据 void delNode(int n){ Node* p = head; if(p == NULL){ cout<<"链表为空！！"<<endl; } else{ cout<<"add= "<<findNode(n)<<endl; for(int i=1; i<findNode(n); i++){ p = p->next; } Node* del = p->next; p->next = p->next->next; delete del; del = NULL; size--; } } //删除头部的节点数据 void delHeadNode(){ Node* p = head; if(p == NULL){ cout<<"链表为空！！"<<endl; } else{ Node* del = p->next; p->next = p->next->next; delete del; size--; } } //删除尾部的节点数据 void delEndNode(){ Node* p = head; Node* temp = NULL; if(p == NULL){ cout<<"链表为空！！"<<endl; } else{ while(p->next){ temp = p; //temp记录保存最后一个节点 p = p->next; } delete p; //删除最后一个节点 p = NULL; //将指向最后一个节点的指针指向NULL，防止出现野指针 temp->next = NULL; //再将记录保存最后一个节点的next指针指向NULL size--; } } //计算链表的长度 void listlength(){ Node* p = head; int len=0; while(p->next){ p = p->next; len++; } cout<<"链表的长度是："<<len<<endl; } //给链表元素冒泡排序，下面提供三种方法，都可以测试 //方法1： void sortList(){ Node* p = head; if(p == NULL){ cout<<"链表为空！！无法排序"<<endl; } else{ cout<<"给链表元素排序"<<endl; int len=0; while(p){ len++; p = p->next; } for(int i=0; i<len-1; i++){ //ph1指向首元结点 Node* ph1 = p->next; //ph2指向首元结点的后继 Node* ph2 = ph1->next; //进入循环冒出最大的数 for(int j=0; j<len-i-1; j++){ if(ph1->num < ph2->num){ p->next = ph2; ph1->next = ph2->next; ph2->next = ph1; //结点交换后，ph1与ph2位置颠倒回来 Node* temp = ph1; ph1 = ph2; ph2 = temp; } //如果不需要交换,三指针移动 p = p->next; ph1 = ph1->next; ph2 = ph2->next; } } } } //方法2： void sortList(){ Node* p = head; //tail指针的作用是每次冒泡排序后指向最后一个数（找出的最大值）的前一个数，效果是下一次的冒泡排序次数减少一次，提高了代码效率 Node* tail = NULL; while(p->next!=tail) { Node* p1 = head; Node* p2 = head->next; while(p2->next!=tail) { if(p1->next->num < p2->next->num) { p1->next = p2->next; p2->next = p2->next->next; p1->next->next = p2; p1 = p1->next; } else { p1 = p1->next; p2 = p2->next; } } tail = p2;//前移一位 } } //方法3： void sortList() { Node* p = head; Node* tail = NULL; //存放遍历出来的最小的节点数据的前一个数据位置 while(p->next != tail){ Node* pre = head; Node* pne = head->next; pre = pre->next; while(pre->next != tail){ if(pre->num < pre->next->num){ int temp = pre->num; pre->num = pre->next->num; pre->next->num = temp; } pre = pre->next; pne = pne->next; } tail = pre; //每次遍历，tail前移一位 } } //删除链表所有节点数据,保留头结点(清空链表) void delAllNode(){ Node* p = head; Node* temp = NULL; if(p->next == NULL){ cout<<"只有头结点，无法删除头结点以外的所有节点！"<<endl; } else{ while(p->next){ temp = p->next; p->next = p->next->next; delete temp; temp = NULL; size--; } p->next = NULL; cout<<"链表已清空"<<endl; } } //销毁链表 void clearList(){ Node* p = head; Node* temp = NULL; if(p == NULL){ cout<<"链表为空，无法销毁！"<<endl; } else{ if(p->next == NULL){ delete p; p = NULL; } else{ while(p->next){ temp = p->next; p->next = p->next->next; delete temp; size--; } delete p; p = NULL; cout<<"链表已销毁"<<endl; } } } //打印链表 void pointList(){ Node* p = head; //头指针最初指向的是头结点位置 if(p == NULL){ cout<<"链表为空！！"<<endl; } else{ while(p->next){ //从头结点下一节点判断是否为空，也就是先判断首元节点是否为空，依次接着判断 p = p->next; //将头指针移到首元节点开始依次往后打印每个节点 cout<<p->num<<"\t"; } cout<<endl; cout<<"链表元素个数：size= "<<size<<endl; } } }; int list::size = 0; int main(){ list s1; s1.createList(); //创建一个链表 s1.pointList(); s1.insertHeadNode(10); //在头部插入节点数据 s1.pointList(); s1.inserEndtNode(90); //在尾部插入节点数据 s1.pointList(); s1.insertNode(30,5); //在指定位置插入节点数据 s1.pointList(); s1.modNode(90,100); //修改指定位置的节点数据 s1.pointList(); s1.delHeadNode(); //删除头部的节点数据 s1.pointList(); s1.delEndNode(); //删除尾部的节点数据 s1.pointList(); s1.delNode(30); //删除指定位置的节点数据 s1.pointList(); s1.listlength(); //计算链表的长度 s1.sortList(); //给链表元素冒泡排序 s1.pointList(); s1.delAllNode(); //删除链表所有节点数据,保留头结点(清空链表) s1.pointList(); s1.listDel(); //销毁链表 s1.pointList(); return 0; }

以上代码有错误的地方，欢迎留言指出，互相学习进步。