链表类
【问题描述】
(1)链表元素的空间是动态申请的。(2) 在链表类的构造函数中初始化链表，在链表类的析构函数中释放链表所有元素的空间。
#include <iostream> using namespace std; class node{ int data; node *next; public :friend class LinkList; node() { } node(int m) { data=m; next=NULL; } }; class LinkList { protected: int count; //链表中元素的个数 node * dataLinkHead, * dataLinkTail; //表头、表尾指针 public: LinkList(void); //构造函数 ~LinkList(void); //析构函数 void putTail (int newData); //在表尾加入一个新元素 void putHead (int newData); //在表头插入一个新元素 int getHead (void); //从表头取出一个元素,并释放该结点 int peekHead(void); //查看表头元素的值，假定链表至少有一个元素 bool empty ( ); //检查链表是否空 int getElemCount() ; //取链表元素个数 }; void LinkList::putTail (int newData) { //建立一个新的结点 node *pNew = new node; if (pNew == NULL) { //判断是否申请到空间 cout << "Memory Insufficient!"; return; } pNew->data = newData; //为新节点填充内容 pNew->next = NULL; //将新节点插入到链表中 if (dataLinkTail == NULL) //链表为空, 新结点成为第一个结点 dataLinkHead = dataLinkTail = pNew; else { //链表不空 dataLinkTail->next = pNew; dataLinkTail = pNew; } count++; } int LinkList::getHead (void) { int n; if(count==0) cout<<"error"<<endl; else { n=dataLinkHead->data; node *temp=dataLinkHead; dataLinkHead=dataLinkHead->next; delete temp; } count--; return n; } int LinkList::getElemCount() { return this->count; } LinkList::~LinkList() { node *ptemp; while(this->dataLinkHead!=NULL) { ptemp=dataLinkHead->next; delete dataLinkHead; dataLinkHead=ptemp; } } LinkList::LinkList() { this->count=0; this->dataLinkHead=NULL; this->dataLinkTail=NULL; } void LinkList::putHead(int newData) { node *pnew; pnew=new node(newData); count++; if ((*this).empty()) { dataLinkHead=pnew; } else { pnew->next=dataLinkHead; dataLinkHead=pnew; } } int LinkList::peekHead() { return this->dataLinkHead->data; } bool LinkList::empty() { return (dataLinkHead==NULL); } int main() { LinkList l; int i; //测试链表是否为空 cout << " linklist empty:"; if (l.empty()) cout << "Yes" << endl; else cout << "No" << endl; //往链表中依次放入四个数 cout << endl << "4 elements enter linklist " << endl; for(i = 0; i < 4; i++) l.putTail (i); //输出链表是否为空 cout << " linklist empty:"; if (l.empty()) cout << "Yes" << endl; else cout << "No" << endl; //取出两个数 cout << endl << "2 elements leave linklist:"; cout << l.getHead () << " "; cout << l.getHead () << " "; //再放入两个数 cout << endl << "2 elements enter linklist " << endl; l.putTail (4); l.putTail (5); //按顺序输出剩下的成员 cout << "Elements left:" ; int num = l.getElemCount(); for(i = 0; i < num; i++) cout << l.getHead () << " "; cout << endl; return 0; }
编写链表实现插入和删除等操作
【问题描述】编写链表实现插入和删除等操作【输入形式】
【输出形式】
【样例输入输出】
请输入学生姓名：
zhang
wang
li
zhao
sun
qian
学生信息为：
2018001 li
2018002 wang
2018003 zhang
2018004 zhao
2018005 sun
2018006 qian
请输入要删除的学生学号：
2018004
学生信息为：
2018001 li
2018002 wang
2018003 zhang
2018005 sun
2018006 qian
请输入要插入的学生学号和姓名：
2018004 han
学生信息为：
2018001 li
2018002 wang
2018003 zhang
2018004 han
2018005 sun
2018006 qian
【样例说明】
【评分标准】
#include <iostream> #include <string> using namespace std; class Node { public: Node(int id, string name); //定义编号和姓名 void showMessage(); //输出数据 friend class LinkList; //把Linklist作为自己的友元类 protected: int mId; //编号 string mName; //姓名 Node *next; //指针指向下一个 }; Node::Node(int id, string name) //接受编号和姓名 { this->mId = id; this->mName = name; this->next = NULL; } void Node::showMessage() //输出数据 { cout << this->mId << " " << this->mName << endl; } class LinkList { public: void addNodeAtHead(int i, string name); void addNodeAtTail(int i, string name); void print(); void deleteNode(int ID); void insertNode(int ID, string name); ~LinkList() { Node *p; while(head!=NULL) { p=head->next; delete head; head=p; } } LinkList() { this->head=NULL; } protected: Node *head; //指针指向头 }; void LinkList::addNodeAtHead(int i, string name) { Node* p; p = new Node (i, name); if (this->head == NULL) this->head = p; else { p->next = head; head = p; } } void LinkList::addNodeAtTail(int i, string name) { Node* p,*q; p = new Node (i, name); if (head==NULL) head=p; else { q = head; while (q->next!= NULL) q = q->next; q->next = p; } } void LinkList::print() { Node* p; p = head; while (p!= NULL) { p->showMessage(); p = p->next; } } void LinkList::deleteNode(int ID) { Node* p, * q; if (head != NULL) { p = this->head; q = p; while ((p != NULL) && (p->mId != ID)) { q = p; p = p->next; } if (p != NULL) { if (p == this->head) this->head = this->head->next; else q->next = p->next; delete p; } } } void LinkList::insertNode(int ID, string name) { Node* p = new Node(ID, name),*q,*pre; if (this->head == NULL) head = p; else { q = this->head; pre = q; while ((q!=NULL)&&(q->mId < ID)) { pre=q; q = q->next; } if (pre == this->head) { p->next = head; head = p; } else { p->next = pre->next; pre->next = p; } } } int main() { int ID; LinkList list1; string name; cout << "请输入学生姓名：" << endl; for (int i = 2018003; i >= 2018001; i--) //依次输入名字 { cin >> name; list1.addNodeAtHead(i,name); } for (int i = 2018004; i <= 2018006; i++) //依次输入名字 { cin >> name; list1.addNodeAtTail(i,name); } cout <<"学生信息为："<< endl; list1.print(); cout << "请输入要删除的学生学号："<<endl; cin >> ID; cout << "学生信息为：" << endl; list1.deleteNode(ID); list1.print(); cout << "请输入要插入的学生学号和姓名："<<endl; cin >> ID >>name; cout << "学生信息为：" << endl; list1.insertNode(ID, name); list1.print(); return 0; }
