实现链表

小咪咪 2023-08-17 15:49 100阅读 0赞

自己实现的链表，包括对链表的基本实现，其中有的函数实现了，没有用到，因为这个是一个简单的程序，没有实现了，其中有的问题需要注意一下：

\#include <iostream>  
using namespace std;

\#define true 1  
\#define false 0

class List;             //注意List的前置声明，其实也可以将ListNode放到List类中去实现，但是这样的实现的灵活性不是很好  
class ListNode  
\{  
 friend class List;               //声明List为友元类  
private:  
 int data;  
 ListNode \*link;  
\};

class List  
\{  
public:  
 List();  
 void Insert(int,int);           //链表中插入，在一个位置插入一个值  
 void Remove(int);           //删除操作，删除一个位置的一个值  
 bool IsEmpty();                 //判断链表是否为空  
 int GetElement(int);       //取链表中一个位置的一个元素值  
 int Find(int);                   //遍历链表查找元素  
 void Show();          //列出链表  
private:  
 ListNode \*head;          //指向链表表头的指针  
 int size;                     //定义指针的长度  
\};

List::List()  
\{  
 ListNode \*first,\*s;  
 size = 0;  
 first = new ListNode;  
 head = first;  
 cout<<"Input the Elements:";  
 cin>>first->data;  
 while((first->data) != -1 )  
 \{  
  s = first;  
  first = new ListNode;  
  s->link = first;  
  size++;  
  cin>>first->data;  
 \}  
 delete first;  
 s->link = NULL;  
\}

void List::Show()  
\{  
 cout<<"Now show the List:";  
 while(head)  
 \{  
  cout<<head->data<<" ";  
  head = head->link;  
 \}  
 cout<<endl;  
\}

void List::Insert(int Element,int Location)  
\{  
 int i = 0;  
 ListNode \*newNode,\*p,\*s;  
 s = head;  
 while(i != Location)  
 \{  
  s = s->link;  
  i++;  
 \}  
 p = s->link;  
 newNode = new ListNode;  
 newNode->data = Element;  
 s->link = newNode;  
 newNode->link = p;  
 size =size + 1;  
\}

void List::Remove(int Location)  
\{  
 int i = 0;  
 ListNode \*s,\*p;  
 s = head;  
 while(i != Location)  
 \{  
  s = s->link;  
  i++;  
 \}  
 p = s->link->link;  
 delete s->link;                             //删除了一个节点，但是不能忘了，把这个节点的位置的指针删除了，对于一个小程序来说

//没什么，但是要是对于一个大程序来说，这个是致命的地方，可能有内存泄露。  
 s->link = p;  
\}

bool List::IsEmpty()  
\{  
 if(size == 0)  
  return true;  
 else  
  return false;  
\}

int List::GetElement(int Location)  
\{  
 int i = 0;  
 ListNode \*t;  
 t = head;  
 while(i != Location)  
 \{  
  t = t->link;  
  i++;  
 \}  
 return (t->data);  
\}

void main()                              //main函数实现的比较粗糙了，就是输入几个整形数了。没有定义很多的变量来实现输入操作  
\{  
 int Element;  
 List list;  
 list.Insert(3,2);  
 list.Remove(6);  
 Element = list.GetElement(5);  
 cout<<Element<<endl;  
 list.Show();                      //将这个函数放在最后，你可能不懂，但是它必须放在最后面，如果不想，要多定义一个指针了。因            //head  是List的私有变量  
\}

转载于:https://www.cnblogs.com/JPAORM/archive/2010/04/20/2509927.html