#include<stdlib.h> #include<iostream> #include<string> using?namespace?std; class?Node { public: int?data;//數(shù)據(jù)域 Node?*next;//指向下一個結(jié)點的指針域 void?printNode();//打印數(shù)據(jù)域? }?; class?List? { public: List()?;?//構(gòu)造函數(shù)，創(chuàng)建線性表? ~List();//析構(gòu)函數(shù)，釋放線性表 void?ClearList();//清空線性表? bool?ListEmpty();//判斷線性表是否為空? int?ListLength();//獲取當(dāng)前線性表的長度? bool?GetElem(int?i,Node?*pNode);?//獲取指定元素的值?? ????int?LocateElem(Node?*pNode);?//找與給定結(jié)點相同數(shù)據(jù)域?的結(jié)點的位置? bool?PriorElem(Node?*pCurrentNode,Node?*pPreNode);//獲取指定元素的前驅(qū)? bool?NextElem(Node?*pCurrentNode,Node?*pNextNode);//獲取指定元素的后繼? ????void?ListTraverse();//遍歷線性表? bool?ListInsert(int?i,Node?*pNode); //在第i個結(jié)點插入元素? bool?ListDelete(int?i,Node?*pNode);//在刪除第i個位置的元素? bool?ListInsertHead(Node?*pNode);//從頭結(jié)點后插入 bool?ListInsertTail(Node?*pNode);//從尾結(jié)后插入 ? private: Node?*m_pList;//指向存儲線性表的內(nèi)存? int?m_iLength;//線性表的長度? //對于鏈表不需要size，因為其內(nèi)存空間可以臨時申請? ?}?; class?Person { public: string?name; string?phone; Person?&operator=(Person?&person); }; ?void?Node::printNode() { cout<<data<<endl; ?}? ? ?List::List() { m_pList=new?Node;//從堆中申請內(nèi)存? //m_pList->data=0;//第一個結(jié)點數(shù)據(jù)域賦值零? m_pList->next=NULL;?//指針域空 m_iLength=0;? } List::~List?()//清空所有結(jié)點? { ClearList(); delete?m_pList; m_pList=NULL; } void?List::ClearList()//清空除了頭結(jié)點外所有結(jié)點? { Node?*currentNode=m_pList->next; while(currentNode!=NULL) { Node?*temp=currentNode->next; delete?currentNode; currentNode=temp;? } m_pList->next=NULL; } bool?List::ListEmpty() { if(m_iLength==0) { return?true; } else { return?false; } //return?m_iLength==0?true:false; } int?List::ListLength() { return?m_iLength; } bool?List::GetElem(int?i,Node?*pNode) { if(i<0||i>=m_iLength) { return?false; } Node?*currentNode=m_pList;//臨時變量找到結(jié)點 Node?*currentNodeBefore=NULL;? ????for(int?k=0;k<=i;k++) ????{ ???? currentNodeBefore=currentNode; ???? currentNode=currentNode->next; } pNode->data=currentNode->data; return?true; } int?List::LocateElem(Node?*pNode)//找與pNode數(shù)據(jù)域相同的結(jié)點? { Node?*currentNode=m_pList; while(currentNode->next!=NULL) { int?count=0; currentNode=currentNode->next; if(currentNode->data==pNode->data)//數(shù)據(jù)域的對比? { return?count; } count++; } return?-1; } //注意頭結(jié)點數(shù)據(jù)域沒意義，不能算頭結(jié)點 ? bool?List::PriorElem(Node?*pCurrentNode,Node?*pPreNode) { Node?*currentNode=m_pList; Node?*tempNode=NULL; while(currentNode->next!=NULL) { tempNode=currentNode; currentNode=currentNode->next; if(currentNode->data==pCurrentNode->data)//數(shù)據(jù)域的對比? { if(tempNode==m_pList)//當(dāng)前結(jié)點是否是頭結(jié)點? { return?false;? } pPreNode->data=tempNode->data; return?true; } } return?false; } bool?List::NextElem(Node?*pCurrentNode,Node?*pNextNode) { Node?*currentNode=m_pList; while(currentNode->next!=NULL) { currentNode=currentNode->next; if(currentNode->data==pCurrentNode->data)//數(shù)據(jù)域的對比? { if(currentNode->next==NULL)//當(dāng)前結(jié)點是否是頭結(jié)點? { return?false;? } pNextNode->data=currentNode->data; return?true; } } return?false; } void?List::ListTraverse() { ???Node?*currentNode=m_pList; ???while(currentNode->next!=NULL) ???{ ??? currentNode=currentNode->next; ??? currentNode->printNode(); ???} } bool?List::ListInsert(int?i,Node?*pNode) { if(i<0||i>m_iLength) { return?false; } Node?*currentNode=m_pList;? for(int?k=0;k<i;k++) { ???currentNode=currentNode->next; } Node?*newNode=new?Node; if(newNode==NULL) { return?false;//內(nèi)存申請失敗?? } newNode->data=pNode->data; newNode->next=currentNode->next; currentNode->next=new?Node;? return?true;? } bool?List::ListDelete(int?i,Node?*pNode) { ????if(i<0||i>=m_iLength) { return?false; } ????Node?*currentNode=m_pList;//臨時變量找到結(jié)點 Node?*currentNodeBefore=NULL;? ????for(int?k=0;k<=i;k++) ????{ ???? currentNodeBefore=currentNode; ???? currentNode=currentNode->next; } currentNodeBefore->next=currentNode->next; pNode->data=currentNode->data; delete?currentNode; m_iLength--; return?true; }? bool?List::ListInsertHead(Node?*pNode) { Node?*temp=m_pList->next; Node?*newNode=new?Node;//從堆中申請內(nèi)存，不能從棧中申請內(nèi)存? if(newNode==NULL) { return?false;//內(nèi)存申請失敗? } newNode->data=pNode->data;? m_pList->next=newNode; newNode->next=temp;? return?true; } bool?List::ListInsertTail(Node?*pNode) { Node?*currentNode=m_pList; while(currentNode->next!=NULL) { currentNode=currentNode->next; } Node?*newNode=new?Node;? if(newNode==NULL) { return?false;//內(nèi)存申請失敗?? } newNode->data=pNode->data; newNode->next=NULL; currentNode->next=new?Node; return?true; } int?main(void)? { ????Node?node1; node1.data=3; Node?node2; node2.data=4; Node?node3; node3.data=5; Node?node4; node4.data=6; Node?node5; node5.data=7; List?*pList=new?List(); ????pList->ListInsertHead(&node1); ????pList->ListInsertHead(&node2); pList->ListInsertHead(&node3); pList->ListInsertHead(&node4); ????/*pList->ListInsertTail(&node1); ????pList->ListInsertTail(&node2); pList->ListInsertTail(&node3); pList->ListInsertTail(&node4);*/ pList->ListInsert(0,&node5); pList->ListTraverse(); delete?pList; pList=NULL; system("pause"); return?0; }