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