STL之list篇

╰半夏微凉° 2021-10-29 14:22 501阅读 0赞

（文章最后附上单链表C语言实现）

#### list ####

特性：

*  链表：由一系列节点组成，包含数据域和指针域
 *  内存非连续，增删改效率高，时间复杂度都是常数项
 *  在需要的时候才分配内存
 *  需要额外的空间保存节点关系，前驱后继
 *  不支持随机访问

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUzMzk1Ng_size_16_color_FFFFFF_t_70]

##### list常用API #####

###### 构造函数 ######

list<T> lstT;	//list采用模板类实现，list对象的默认构造形式
    list(beg, end);	//构造函数将[beg, end)区间的元素拷贝给自身
    list(n, elem);	//构造函数将n个elem拷贝给自身
    list(const list &lst);	//拷贝构造函数

###### 插入删除操作 ######

push_back(elem);	//在容器尾部插入一个元素
    pop_back();		//删除容器最后一个元素
    push_front(elem);	//从容器开头插入一个元素
    pop_front();		//从容器头部删除第一个元素
    insert(pos, elem);	//在pos位置插入elem元素的拷贝，返回新元素的位置
    insert(pos, n, elem);	//在pos位置插入n个elem数据，无返回值
    insert(pos, beg, end);	//在pos位置插入[beg, end)区间的数据，无返回值
    clear();	//移除容器的所有数据
    erase(beg, end);	//删除[beg, end)区间的数据，返回下一数据的位置
    erase(pos);		//删除pos位置的数据，返回下一数据的位置
    remove(elem);	//删除容器中所有的elem

###### 大小操作 ######

size();		//返回容器中元素个数
    empty();	//判断容器是否为空
    resize(num);	//重新指定容器的长度为num，若容器变长，则以默认值填充新位置，如果容器变短，则末尾超出容器长度的元素被删除
    resize(num, elem);	//重新指定容器的长度为num，若容器变长，则以elem值填充新位置，如果容器变短，则末尾超出容器长度的元素被删除

###### 赋值操作 ######

assign(beg, end);	//将[beg, end)区间的数据拷贝赋值给本身
    assign(n, elem);	//将n个elem拷贝赋值给自身
    list& operator=(const list &lst);	//重载等号操作符
    swap(lst);	//将list与本身元素互换

###### 存取操作 ######

front();	//返回第一个元素
    back();		//返回最后一个元素

###### 反转排序 ######

reverse();	//反转链表	1,3,5  ->  5,3,1
    sort();		//list排序，默认从小到大，加入规则可以改变sort(规则)

###### sort() ######

*  算法的sort()只可以用于可以随机访问的容器，可以提高排序效率
 *  list的sort()与算法的sort()不同

--------------------

##### C语言实现 #####

#include<iostream>
    #include<stack>
    using namespace std;
    
    typedef struct LNode {
        
    	int data;
    	struct LNode* next;
    }LNode, *LinkList;
    
    LinkList CreateList1(LinkList& L) {
        	//头插法建立单链表
    	L = (LinkList)malloc(sizeof(LinkList));
    	LNode* s;
    	int x;
    	L->next = NULL;
    	cin >> x;
    	while (!EOF) {
        
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = L->next;
    		L->next = s;
    		cin >> x;
    	}
    	return L;
    }
    
    LinkList CreateList2(LinkList& L) {
        	//尾插法建立单链表
    	L = (LinkList)malloc(sizeof(LinkList));
    	LNode* s, * r;	//r为表尾指针
    	r = L;
    	int x;
    	cin >> x;
    	while (!EOF) {
        
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		r->next = s;
    		r = s;
    		cin >> x;
    	}
    	return L;
    }
    
    LNode* GetElem(LinkList L, int i) {
        	//按照序号查找节点
    	int j = 1;
    	LNode* p = L->next;
    	if (i == 0) {
        
    		return L;
    	}
    	if (i < 1) {
        
    		return NULL;
    	}
    	while (p && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;
    }
    
    LNode* LocalElem(LinkList L, int e) {
        	//按值查找节点
    	LNode* p = L->next;
    	while (p && p->data!=e) {
        
    		p = p->next;
    	}
    	return p;
    }
    
    LNode* InsertList(LinkList L, int i, int e) {
        	//插入节点：前插法
    	LNode* p = L->next;
    	LNode* s;	//待插入节点
    	s->data = e;
    	p = GetElem(L, i - 1);	//找到插入位置的前驱结点
    	s->next = p->next;
    	p->next = s;
    }
    
    void test() {
        
    	LinkList L;
    	//CreateList1(L);	//头插法建立单链表
    	CreateList2(L);	//尾插法建立单链表
    	GetElem(L, 5);	//按照序号查找节点
    	LocalElem(L, 666);	//按值查找节点
    	InsertList(L, 5, 777);	//插入节点：前插法
    }
    
    int main() {
        
    
    	test();
    	return 0;
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTUzMzk1Ng_size_16_color_FFFFFF_t_70]: /images/20211029/27ddf1aa74894128ac418d2237f6d169.png