C++简单链表/STL

ciaos

浏览: 303466 次
性别:
来自: 深圳

最近访客更多访客>>

smoking_boy

yangyongjie

muyuan

dongguangming88

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

#include<iostream>
#include<string>

using namespace std;

//——————————————————————————————————————————————————————————————————————
namespace LinkList {
	struct LinkNode{
		string Item;
		struct LinkNode *Next;
	};

	LinkNode *CreateNode(string item){
		LinkNode *node = new LinkNode();
		if(node)
		{
			node->Item = item;
			node->Next = NULL;
		}
		return node;
	}

	bool PushNode(LinkNode *head,string item){
		LinkNode *node = CreateNode(item);
		if(node){
			node->Next = head->Next;
			head->Next = node;
			return true;
		} else {
			return false;
		}
	}

	LinkNode* PopNode(LinkNode *head){
		LinkNode *prev,*curr;
		if(head == NULL || head->Next == NULL){
			return NULL;
		}
		prev = head;
		curr = prev->Next;
		while(curr->Next){
			prev = curr;
			curr = curr->Next;
		}
		prev->Next = NULL;
		return curr;
	}

	bool AppendNode(LinkNode *head,string item){
		LinkNode *node = CreateNode(item);
		if(!node){
			return false;
		}
		LinkNode *tail = head;
		while(tail->Next != NULL){
			tail = tail->Next;
		}
		tail->Next = node;
		return true;
	}

	LinkNode* FindNode(LinkNode *head,string item){
		LinkNode *node = head->Next;
		while(node!=NULL){
			if(node->Item == item){
				return node;
			} else {
				node = node->Next;
			}
		}
		return NULL;
	}

	void DeleteNode(LinkNode *head,string item){
		LinkNode *tail = head, *node;
		while(tail->Next!=NULL){
			if(tail->Next->Item == item){
				node = tail->Next;
				tail->Next = node->Next;
				delete(node);
			} else{
				tail = tail->Next;
			}
		}
	}

	void DeleteAll(LinkNode *head){
		if(head){
			while(head->Next!=NULL){
				DeleteAll(head->Next);
				head->Next=NULL;
			}
			delete(head);
			head=NULL;
		}
	}

	void _insert_for_sort(LinkNode *head,LinkNode *node){
		LinkNode *prev = NULL,*curr;
		node->Next = NULL;

		if(head->Next == NULL){
			head->Next = node; // 插入第一个数据节点
		} else {
			curr = head->Next;
			prev = head;
			while(curr) {	//如果curr为空，则目标节点最大，插在末尾
				if(curr->Item > node->Item){ //找到一个节点数据比目标节点大，插在前面
					break;
				}
				prev = curr;
				curr = curr->Next;
			}
			node->Next = prev->Next;
			prev->Next = node;
		}
	}

	void SortNode(LinkNode *head){
		LinkNode *prev,*curr;

		if(NULL == head || NULL == head->Next){
			return;
		}

		curr = head->Next;
		head->Next = NULL;

		while(curr){
			prev = curr;
			curr = curr->Next;

			_insert_for_sort(head, prev);
		}
	}
	
}
//——————————————————————————————————————————————————————————————————————

int main(){

	LinkList::LinkNode *head = LinkList::CreateNode("");
	if(head){
		LinkList::AppendNode(head,"A");
		LinkList::AppendNode(head,"B");
		LinkList::AppendNode(head,"C");
		LinkList::PushNode(head,"D");
		LinkList::AppendNode(head,"E");
		LinkList::AppendNode(head,"F");
		LinkList::PushNode(head,"F");
		LinkList::AppendNode(head,"E");
		LinkList::PushNode(head,"G");

		LinkList::DeleteNode(head,"E");

		LinkList::LinkNode *find = LinkList::FindNode(head,"A");
		find->Item="O";
		LinkList::DeleteNode(head,"M");
	}

	if(head){
		LinkList::LinkNode *test = head->Next;
		while(test!=NULL){
			cout << test->Item << endl;
			test = test->Next;
		}
	}

	cout << endl;
	LinkList::SortNode(head);

	LinkList::LinkNode *tt = LinkList::PopNode(head);

	cout << tt->Item << endl;
	cout << endl;

	LinkList::DeleteAll(tt);
	
	if(head){
		LinkList::LinkNode *test = head->Next;
		while(test!=NULL){
			cout << test->Item << endl;
			test = test->Next;
		}
	}
	LinkList::DeleteAll(head);
	return 0;
}

用valgrind查看无内存泄漏

root # valgrind ./a.out
==5602== Memcheck, a memory error detector
==5602== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==5602== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==5602== Command: ./a.out
==5602==
G
D
O
B
C
F
==5602==
==5602== HEAP SUMMARY:
==5602==     in use at exit: 0 bytes in 0 blocks
==5602==   total heap usage: 20 allocs, 20 frees, 430 bytes allocated
==5602==
==5602== All heap blocks were freed -- no leaks are possible
==5602==
==5602== For counts of detected and suppressed errors, rerun with: -v
==5602== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Vector数组自定义排序

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

class People{
public:
	string name;
	int age;
public:
	People(string name,int age){
		this->name = name;
		this->age = age;
	}
	bool operator < (const People &p) const{
//		return name < p.name;
		return age < p.age;
	}
};

bool less_operator(const People &p1, const People &p2){
//	return p1.name < p2.name;
	return p1.age < p2.age;
}

int main(){

	vector<People> vp;
	vector<People>::iterator vpi;
	
	People p1("ciaos",26);
	People p2("stone",25);
	People p3("tiger",27);
	People p4("apple",21);
//	People *p5 = new People("marks",50);	//memory leak
	
	vp.push_back(p1);
	vp.push_back(p2);
	vp.push_back(p3);
	vp.push_back(p4);
//	vp.push_back(*p5);

	for(vpi = vp.begin();vpi != vp.end();vpi ++){
		cout << (*vpi).name << " " << (*vpi).age << endl;
	}
	
	sort(vp.begin(),vp.end());
//	sort(vp.begin(),vp.end(),less_operator);

	for(int i=0;i<vp.size();i++){
		cout << vp[i].name << " " << vp[i].age << endl;
	}

	return 0;
}

Map基本操作

#include<iostream>
#include<map>
#include<algorithm>
#include<string>

using namespace std;

bool match_second(pair<int,string> data, string target){
	return (data.second == target)?true:false;
}

int main(){

	map<int,string> co;
	map<int,string>::iterator coi;

	co.insert(pair<int,string>(10086,"mobile"));
	co.insert(pair<int,string>(10010,"union"));
	co.insert(pair<int,string>(12306,"train"));
	co.insert(pair<int,string>(10000,"telecom"));

	for(coi = co.begin();coi != co.end();coi ++){
		cout << (*coi).first << " " << (*coi).second << endl;
	}
	
	coi = co.find(10010);
	cout << (*coi).first << " " << (*coi).second << endl;
	co.erase(coi);
	cout << endl;

	coi = find_if(co.begin(),co.end(),bind2nd(ptr_fun(match_second),"train"));
	if(coi != co.end()) {
		cout << (*coi).first << " " << (*coi).second << endl; 
	}

	cout << endl;
	for(coi = co.begin();coi != co.end();coi ++){
		cout << (*coi).first << " " << (*coi).second << endl;
	}
//	sort(vp.begin(),vp.end());
//	sort(vp.begin(),vp.end(),less_operator);


	return 0;
}

分享到：