算法导论chapter10链表的简单实现

绝地灬酷狼 2022-04-01 15:21 75阅读 0赞

基本原理仍然easy，直接上代码：

#include<iostream>
    using namespace std;
    struct my_list
    {
    	my_list *pre,*next;
    	int key;
    };
    my_list* Init_list()
    {
    	my_list *list = new my_list();
    	if(list == NULL)
    		cout << "申请内存空间失败\n";
    	list->pre = list->next = NULL;
    	return list;
    }
    my_list* Create_list()
    {
    	my_list *list1 = new my_list();
    	int value = 0;
    	my_list *list = list1;
    	cout << "请输入各元素值：\n";
    	while(cin >> value)
    	{
    		my_list *temp = new my_list();
    		temp->key = value;
    		temp->next = NULL;
    		list->next = temp;
    		temp->pre = list;
    		list = temp;
    	}
    	return list1;
    }
    
    void list_insert(my_list *list, int i, int value)
    {
       my_list *temp = list->next;
       while(--i)
    	   temp = temp->next;
       if(temp == NULL)
       {
    	   cerr << "删除错误\n";
    	   exit(1);
       }
       my_list *p = new my_list();
       p->key = value;
       p->next = temp->next;
       temp->next->pre = p;
       temp->next = p;
       p->pre = temp;
    }
    
    void list_delete(my_list *list, int i)
    {
       my_list *temp = list->next;
       while(i--)
    	   temp = temp->next;
       my_list *temp1 = temp;
       temp1->pre->next = temp1->next;
       temp->next->pre = temp1->pre;
       free(temp1);
    }
    
    int list_search(my_list *list,int key)
    {
    	my_list *temp = list->next;
    	int i = 0;
    	while(temp != NULL)
    	{
    		if(temp ->key == key)
    			return i;
    		temp = temp->next;
    		++i;
    	}
    	return -1;
    }
    void print(my_list *list)
    {
    	my_list *temp = list->next;
    	cout << "链表的元素是：\n";
    	while(temp != NULL)
    	{
    		cout << temp->key << " ";
    		temp = temp->next;
    	}
    	cout << endl;
    }
    int main()
    {
    	my_list *list = Init_list();
    	list = Create_list();
    	print(list);
    	list_insert(list,2,10);
    	print(list);
    	list_delete(list,3);
    	print(list);
    	cout << list_search(list, 1) << endl;
    }

运行结果：

![2010111716134131.png][]

[2010111716134131.png]: /images/20220401/7214c2fc7f6a440c98cfc2d8ecb06ade.png