C++实现线性表的链式存储（单链表）

蔚落 2023-07-09 04:24 32阅读 0赞

![线性表的分类及其表现形式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]  
**链式存储（单链表）：由多个节点串联而成，每一个节点不仅有数据信息，最重要的还存储了后继节点的地址，所以只要知道某一个节点的位置，就能遍历后续节点**，结构如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]  
注意：若不带头结点的链表，增加了程序的复杂性和出现bug的机会，因此，通常在单链表的开始结点之前附设一个头结点。

**节点的组成：存储数据元素信息的域称为数据域；存储后继位置的域称为指针域**，代码如下

struct Node
    {
        
    int data;//数据域
    Node *next;//指针域
    };
    Node n1;//创建了节点n1

实际上，节点在内存中的位置与该节点的数据域位置相同

链表的常见操作：  
①void Creat\_List(int n) 创建一个链表,长度为n  
②bool Is\_Empty() 判断链表是否为空  
③int Get\_Length() 返回链表长度  
④Node \*Find(Data\_type data) 返回某节点位置，返回的是Node型指针  
⑤Show() 遍历链表  
⑥void Insert(int n,Data\_type data) 在指定位置后插入新节点,如在第三个位置插入新节点，那么第三个节点就是新节点  
⑦void Delete(int n) 删除指定位置的节点，n的含义：头节点位序为0，第一个节点位序为1

创建一个List类

typedef int DataType;
    class List
    {
        
    private:
         struct Node
         {
        
         DataType data;//数据域
         Node *next;//指针域
         };
         Node *head;//指向头节点的指针
    public:
         List();
    	~List();
    	void Creat_List(int n);
    	bool Is_Empty();
    	int Get_Length();
    	Node * Find(DataType data);
        void Show();
    	void Insert(int n,DataType data);
    	void Delete(int n);

下面为具体的方法：  
构造函数

List::List()
    {
        
    	head = new Node;//创建了头节点，并初始化
    	head->data = 0;
    	head->next = 0;
    }

析构函数

List::~List()//删除整个链表（包括头节点），释放开辟的空间
    {
        
    	Node* p = head->next;
    	while (p!= 0)
    	{
        
    		Node *temp = p;//temp作为中间量，存储要删除的位置
    		head->next = p->next;
    		p=p->next;//令p指向下一个节点
    		delete temp;
    	}
    	delete head;//删除头节点
    	head = 0;
    }

①void Creat\_List(int n) 创建一个链表,长度为n

void List::Creat_List(int n)
    {
        
    	if (n < 0)
    		cout << "输入的节点数量有误" << endl;
    	else
    	{
        
    		Node *p = head;//p是用来指向当前的节点
    		for (int a = 0; a < n; a++)
    		{
        
    			Node *new_node = new Node;
    			cout << "请输入数据"<<endl;
    			cin >> new_node->data;
    			new_node->next = 0;
    			p->next = new_node;//令当前节点的next指向新节点
    			p = new_node;//p指向新节点
    			//最后两句的顺序不能调换
    		}
    	}
    }

②bool Is\_Empty() 判断链表是否为空

bool List::Is_Empty()
    {
        
    	if (head->next == 0)
    	{
        
    		cout << "链表为空";
    			return true;
    	}
    	else
    		return false;
    }

③int Get\_Length() 返回链表长度

int List::Get_Length()
    {
        
    	int n=0;
    	Node *p = head->next;
    	while (p != 0)
    	{
         
    		n++;
    		p = p->next;
    	}
    		return n;
    }

④Node \*Find(Data\_type data) 返回某节点位置，返回的是Node型指针

List::Node * List::Find(DataType n)
    {
        
    	Node *p = head->next;
    	while (p != 0)
    	{
        
    		if (p->data == n)
    			return p;
    		else
    		    p = p->next;
    	}
    	return 0;
    
    }

⑤Show() 遍历链表

void List::Show()
    {
        
    	Node *p = head->next;
    	while (p != 0)
    	{
        
    		cout << p->data << endl;
    		p = p->next;
    	}
    }

⑥void Insert(int n,Data\_type data) 在指定位置后插入新节点

void List::Insert(int n,DataType data)
    {
        
    	if (n<0 || n>Get_Length())
    		cout << "插入位置有误"<<endl;
    	else
    	{
        
    		Node *new_node = new Node;
    		new_node->data = data;
    		new_node->next = 0;
    		if (n == 1)//位序0，表示在头结点后插入
    		{
        
    			new_node->next = head->next;//首先要将原先的第一个节点位置保存在新节点的next中
    			head->next = new_node;//再将头节点的next指向新插入的节点
    		}
    		else
    		{
        
    			Node *p = head->next;
    			for (int a = 1; a < n-1; a++)
    				p = p->next;//经过n-2次循环，p已经指向位序为n的节点
    			new_node->next = p->next;//首先将位序n节点的next存储在新节点中
    			p->next = new_node;//再将位序n节点的next指向新节点
    		}
    	}
    }

⑦void Delete(int n) 删除指定位置的节点，

void List::Delete(int n)
    {
        
    	if (Is_Empty() || n <= 0 || n>Get_Length())
    		cout << "删除位置有误";
    	else
    	{
        
    		Node *p = head->next;
    		Node *temp;
    		if (n == 1)//删除头节点后的第一个节点
    		{
        
    			head->next = p->next;//将头节点的next指向头节点后的原第二个节点
    			temp = p;
    			delete temp;
    			temp = 0;
    		}
    		else
    		{
        
    			for (int a = 1; a < n-1 ; a++)
    				p = p->next;//遍历到要删除节点的上一个节点
    			temp = p->next;//p是被删除节点的上一个节点，那么p->next就是被删除节点
    			p->next = p->next->next;//将被删除节点的上一个节点的next指向被删除节点的下一个节点
    			delete temp;
    			temp = 0;
    		}
    	}
    }

总结：  
①Node\*p非常重要：**一、用于遍历，随着循环，p的指向会一直变化（体现在函数③④⑤）；二、是连接新旧节点的桥梁（体现在函数⑥⑦）**  
②在进行插入和删除操作时，首先要判断位置的合法性，而且在遇到**头节点后插入**和**删除第一个节点**，两种情况时**应该分类讨论，因为他们和头节点息息相关**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227203647376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227210902271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg==,size_16,color_FFFFFF,t_70