小蜜蜂

小蜜蜂

关注
发信
关注(|-)粉丝(-|)

数据结构自学笔记（未完成）

1、时间复杂度

2、空间复杂度

/*
问题：
在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。
设计一个算法，找出出现次数最多的数字。
*/

#include

using namespace std;

void search(int a[], int len) // O(n)
{
int sp[1000] = {0};
int max = 0;

for(int i=0; i<len; i++)
{
    sp[a[i] - 1]++;
}

for(int i=0; i<1000; i++)
{
    if( max < sp[i] )
    {
        max = sp[i];
    }
}

for(int i=0; i<1000; i++)
{
    if( max == sp[i] )
    {
        cout << i + 1 << endl;
    }
}

}

int main(int argc, char* argv[])
{
int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3};

search(a, sizeof(a)/sizeof(*a));

return 0;

}
3、泛型编程
// template
// 函数模板可以自动推导具体类型，也可以指定具体类型
// 类模板只能指定具体类型
#include

using namespace std;

template // 函数模板
void Swap(T& a, T& b)
{
T t = a;
a = b;
b = t;
}

template // 类模板
class Op
{
public:
T process(T& v)
{
return v * v;
}
};

int main()
{
int a = 2;
int b = 1;

Swap(a, b); 		// 不指定数据类型

cout << "a = " << a << " " << "b = " << b << endl;
/////////////////////////////////////////////////////////////////////
double c = 0.01;
double d = 0.02;

Swap<double>(d, c); // 指定数据类型

cout << "c = " << c << " " << "d = " << d << endl;
////////////////////////////////////////////////////////////////////////
Op<int> opInt;			// 建立类对象
Op<double> opDouble;

cout << "5 * 5 = " << opInt.process(5) << endl;
cout << "0.3 * 0.3 = " << opDouble.process(0.3) << endl;

return 0;

}

4、智能指针
//

、顶层父类的设计

、线性表（List）
// 线性表是具有相同类型的有n个数据元素的有限序列

、单链表

// 解决数组大小不能动态扩展的问题
// 链表的内存要求比较灵活，不能用栈

#include
#include

using namespace std;

//////////////////////StuInfo.cpp//////////////////////////////
class StuInfo
{
public:
int id; // 学号
string name; // 姓名

public:
StuInfo();
~StuInfo();

};

StuInfo::StuInfo()
{
name = “”;
id = 0;
}

StuInfo::~StuInfo()
{
}

///////////////////////LinkedList///////////////////////////
template
struct Node
{
T info;// 数据
Node *next;// 指向下一个节 点的指针

Node<T>(){}
Node<T>(T x){ info = x; next = NULL; }

};

template
class LinkedList //: public StuInfo
{
protected: // 只允许子类直接访问
Node *header;
int length;

public:
LinkedList();
~LinkedList();
void insert(int pos, T& info);
void set(int id, T& info);
void remove(int id);
int find(int id);
T getInfo(int id);
int getLength();
void clear();
void print();
};

template
LinkedList::LinkedList()
{
header = new Node();// 建立头节点
header->next = NULL;
length = 0;
}

template
LinkedList::~LinkedList()
{
clear();
}

template
void LinkedList::insert(int pos, T& info)
{
bool ret = (pos>=0) && (pos<=length);

if (ret)
{
	Node<T> *current = header;
	Node<T> *node = new Node<T>(info);

	for (int index=0; index<pos; index++)
	{
		current = current->next;
	}

	node->next = current->next;
	current->next = node;

	length++;
}
else
{
	cout << "positi is ERROR！" << endl;
}

return;

}

template
void LinkedList::set(int id, T& info) //根据学生学号进行信息修改
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++)
{
	current = current->next;
}
current->next->info = info;

return;

}

template
void LinkedList::remove(int id) //根据学生学号进行删除
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++) // 删除的是pos节点的下一个节点
{
	current = current->next;
}

Node<T> *toDel = current->next;
current->next = toDel->next;

delete toDel;

length--;

return;

}

template
int LinkedList::find(int id) //根据学号进行查找，返回节点位置
{
Node *current = header;

for (int index=0; index<=length; index++)
{
	if ( (current->next != NULL) && (current->next->info.id == id) )
	{
		return index;
	}
	current = current->next;
}

return -1;

}

template
T LinkedList::getInfo(int id)
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++)
{
	current = current->next;
}
T info = current->next->info;

return info;

}

template
int LinkedList::getLength() //获得链表长度
{
return length;
}

template
void LinkedList::clear() // 清空节点 （不需要移动节点，挨个删除就可以）
{
for (int index = 0; index < length; index++)
{
Node *toDel = header->next;
header->next = toDel->next;

	delete toDel;
}

length =0;

return;

}

template
void LinkedList::print() //打印链表信息
{
Node *current = header;

for (int index=0; index<length; index++)
{
	cout << current->next->info.id << "," << current->next->info.name << endl;
	current = current->next;
}
cout << endl;

return;

}

int main(void)
{
LinkedList Lists;
StuInfo info1, info2, info3, info4, info5;
info1.id = 1001, info1.name = “李一”,
info2.id = 1002, info2.name = “王二”,
info3.id = 1003, info3.name = “张三”,
info4.id = 1004, info4.name = “莉丝”,
info5.id = 1005, info5.name = “黑武”;

Lists.insert(0, info1);
Lists.print();
Lists.insert(1, info2);
Lists.print();
Lists.insert(2, info3);
Lists.print();
Lists.insert(3, info4);
Lists.print();
Lists.insert(4, info5);
Lists.print();

cout << “链表长度为：” << Lists.getLength() << endl;

cout << Lists.getInfo(1001).id << "," <<Lists.getInfo(1001).name << endl;
cout << endl;

Lists.set(1003, info5);
Lists.print();
cout << "链表长度为：" << Lists.getLength() << endl;

Lists.remove(1002);
Lists.print();
cout << "链表长度为：" << Lists.getLength() << endl;

Lists.clear();
Lists.print();

return 0;

}

、链表反转

#include
#include

using namespace std;

//////////////////////StuInfo.cpp//////////////////////////////
class StuInfo
{
public:
int id; // 学号
string name; // 姓名

public:
StuInfo();
~StuInfo();

};

StuInfo::StuInfo()
{
name = “”;
id = 0;
}

StuInfo::~StuInfo()
{
}

///////////////////////LinkedList///////////////////////////
template
struct Node
{
T info;// 数据
Node *next;// 指向下一个节 点的指针

Node<T>(){next = NULL;}
Node<T>(T x){ info = x; next = NULL; }

};

template
class LinkedList //: public StuInfo
{
public: // 只允许子类直接访问
Node *header;
int length;

public:
LinkedList();
~LinkedList();
void insert(int pos, T& info);
void set(int id, T& info);
void remove(int id);
int find(int id);
T getInfo(int id);
int getLength();
Node* reverseList(Node* node);
void clear();
void print(Node* node);
};

template
LinkedList::LinkedList()
{
header = new Node();// 建立头节点
header->next = NULL;
length = 0;
}

template
LinkedList::~LinkedList()
{
clear();
}

template
void LinkedList::insert(int pos, T& info)
{
bool ret = (pos>=0) && (pos<=length);

if (ret)
{
	Node<T> *current = header;
	Node<T> *node = new Node<T>(info);

	for (int index=0; index<pos; index++)
	{
		current = current->next;
	}

	node->next = current->next;
	current->next = node;

	length++;
}
else
{
	cout << "positi is ERROR！" << endl;
}

return;

}

template
void LinkedList::set(int id, T& info) //根据学生学号进行信息修改
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++)
{
	current = current->next;
}
current->next->info = info;

return;

}

template
void LinkedList::remove(int id) //根据学生学号进行删除
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++) // 删除的是pos节点的下一个节点
{
	current = current->next;
}

Node<T> *toDel = current->next;
current->next = toDel->next;

delete toDel;

length--;

return;

}

template
int LinkedList::find(int id) //根据学号进行查找，返回节点位置
{
Node *current = header;

for (int index=0; index<=length; index++)
{
	if ( (current->next != NULL) && (current->next->info.id == id) )
	{
		return index;
	}
	current = current->next;
}

return -1;

}

template
T LinkedList::getInfo(int id)
{
int pos = find(id);

Node<T> *current = header;

for (int index=0; index<pos; index++)
{
	current = current->next;
}
T info = current->next->info;

return info;

}

template
int LinkedList::getLength() //获得链表长度
{
return length;
}

template
Node* reverseList(Node* head)// 反转链表
{
Node* prev = head;
Node* current = prev->next;
Node* next = NULL;

while (current != NULL) 		// 两个节点
{
	next = current->next;

	if (current == head->next)	// 第一个节点插入时 尾部连接
		current->next = NULL;
	else						// 后来的节点插入时 尾部连接
		current->next = prev->next;

	prev->next = current;		// 头部连接
	current = next;			// 移位
}
return head;

}

template
void LinkedList::clear() // 清空节点 （不需要移动节点，挨个删除就可以）
{
for (int index = 0; index < length; index++)
{
Node *toDel = header->next;
header->next = toDel->next;

	delete toDel;
}

length =0;

return;

}

template
void LinkedList::print(Node* node) //打印链表信息
{
Node *current = node;

while(current->next != NULL)
{
	cout << current->next->info.id << "," << current->next->info.name << endl;
	current = current->next;
}
cout << endl;
return;

}

int main(void)
{
LinkedList Lists;
StuInfo info1, info2, info3, info4, info5;
info1.id = 1001, info1.name = “李一”,
info2.id = 1002, info2.name = “王二”,
info3.id = 1003, info3.name = “张三”,
info4.id = 1004, info4.name = “莉丝”,
info5.id = 1005, info5.name = “黑武”;

Lists.insert(0, info1);
Lists.insert(1, info2);
Lists.insert(2, info3);
Lists.insert(3, info4);
Lists.insert(4, info5);
Lists.print(Lists.header);
Node<StuInfo>* p = NULL;
p = reverseList(Lists.header);
Lists.print(p);

/*
cout << "链表长度为：" << Lists.getLength() << endl;

cout << Lists.getInfo(1001).id << "," <<Lists.getInfo(1001).name << endl;
cout << endl;

Lists.set(1003, info5);
Lists.print(Lists.header);
cout << "链表长度为：" << Lists.getLength() << endl;

Lists.remove(1002);
Lists.print(Lists.header);
cout << "链表长度为：" << Lists.getLength() << endl;

Lists.clear();
Lists.print(Lists.header);
*/
return 0;

}

、静态单链表
// 单链表中频繁增加和删除数据元素会产生内存碎片
// 顺序表 + 单链表 = 静态单链表

、双向链表

#include
#include

using namespace std;

/////////////////Info///////////////////
class StuInfo
{
public:
string name ;
int ID;

StuInfo();
~StuInfo();

};

StuInfo::StuInfo()
{
name = “”;
ID = 0;
};

StuInfo::~StuInfo()
{

};

////////////////DuaLinkList////////////////////
template
class Node
{
public:
T info;
Node* next;
Node* prev;

public:
Node()
{
next = NULL;
}

Node<T>(T& info)
{
	this->info = info;
	next = NULL;
	prev = NULL;
}

};

template
class DuaLinkList : public Node
{
public:
Node* head;
int m_length;

public:
DuaLinkList();
~DuaLinkList();

bool insert(int pos, T& info);
bool remove(int pos);
void print(Node<T>* current);
void clear();

};

template
DuaLinkList::DuaLinkList()
{
head = new Node();
head->next = NULL;
m_length = 0;
}

template
DuaLinkList::~DuaLinkList()
{
clear();
}

template
bool DuaLinkList::insert(int pos, T& info)
{
int ret = (pos>=0) && (pos<=m_length);

if (ret)
{
	Node<T>* current = head;
	Node<T>* node = new Node<T>(info);

	for (int i=0; i<pos; i++)
	{
		current = current->next;
	}

	node->next = current->next;		// 1
	current->next = node;			// 2

	if (current->next != NULL)
		current->next->prev = node;	// 3 不是尾节点

	if (current != head)			// 4 不是头节点
		node->prev = current;
	else
		node->prev = NULL;			// 4 是头节点

	m_length++;

	return true;
}
else
{
	cout << "insert error" << endl;

	return false;
}

}

template
bool DuaLinkList::remove(int pos)
{
int ret = (pos>=0) && (pos<=m_length);

if (ret)
{
	Node<T> *current = head;

	for (int index=0; index<pos; index++) // 删除的是pos节点的下一个节点
	{
		current = current->next;
	}

	Node<T>* toDel = current->next;
	current->next = toDel->next;

	if (toDel->next != NULL)
		toDel->next->prev = current;

	delete toDel;

	m_length--;
}
return true;

}

template
void DuaLinkList::print(Node* current)
{
current = head;

while (current != NULL)
{
	cout << current->info.ID << "::" << current->info.name << endl;
	current = current->next;
}

}

template
void DuaLinkList::clear()
{

}

int main()
{
DuaLinkList list;
StuInfo stu1, stu2, stu3;

stu1.ID = 101;
stu1.name = "aaa";
stu2.ID = 102;
stu2.name = "bbb";
stu3.ID = 103;
stu3.name = "ccc";

list.insert(0, stu1);
list.insert(1, stu2);
list.insert(2, stu3);
list.insert(3, stu2);

list.remove(2);

list.print(list.head);

}

10-07 15:35
Powered by LMLPHP ©2024 小蜜蜂 0.052501