#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;
}
- 2 回答
- 0 关注
- 1717 浏览
添加回答
举报
0/150
提交
取消