功能:
- ListNode* buildList(vector<int> &array) :用数组建链表
- ListNode* reverse(ListNode* head) :翻转链表
数据结构
构造链表
- 约定数组用array
- 链表用p
- 有序表内容是 1、2、3、4、5、6、7
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {}
};
vector<int> array = {1,2,3,4,5,6,7};
ListNode* buildList(vector<int> &array) {
ListNode * head = new ListNode(array[0]);
ListNode * p = head;
for(int i=1;i<array.size();i++) {
p->next = new ListNode(array[i]);
p = p->next;
}
return head;
}
int main() {
ListNode * p = buildList(array);
for(int i=0;i<array.size();i++){
cout<<p->val<<" ";
p = p->next;
}
return 0;
}
vector 结构体排序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Man{
string name;
int age;
bool operator <(const Man &M) const{
return age<M.age;
};
Man(string s,int x) :
name(s), age(x){}
};
Man* man1 = new Man("aa",23);
Man* man2 = new Man("bb",21);
Man* man3 = new Man("cc",22);
vector<Man> manVec = {*man1,*man2,*man3};
int main(int argc, char *argv[]) {
sort(manVec.begin(),manVec.end());
for(auto it=manVec.begin();it!=manVec.end();++it){
cout<<it->name<<endl;
}
return 0;
}
二维矩阵
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> matrix =
{{1,2,3,4}
,{5,6,7,8}
,{9,10,11,12}
,{13,14,15,16}
};
int main(int argc, char *argv[]) {
for(auto i=matrix.begin();i!=matrix.end();++i){
for(auto j=i->begin();j!=i->end();++j){
cout<<(*j)<<"\t";
}
cout<<endl;
}
return 0;
}
创建二叉树
/* 先序创建一棵任意二叉树 */
/* 注意:输入数据的顺序很有特点,本题输入的顺序要求为,先是根节点,再是左子树,再是右子树 */
#include <iostream>
#include <malloc.h>
using namespace std;
typedef int ElementType; //给int起别名为ElementType, typedef是起别名的意思
typedef struct bitnode //定义二叉树节点数据类型
{
ElementType data;
struct bitnode *left, *right;
} bitnode, *bitree; //bitree为指向bitnode这种结构的指针
bitree PerCreateTree(bitree T); //先序创建一棵二叉树
void PerOrder(bitree T); //先序输出一棵二叉树
bitree FreeTree(bitree T); //释放空间
//先序创建一棵二叉树
bitree PerCreateTree()
{
bitree T;
ElementType item;
cin >> item;
if( item == 0 ) //叶节点数据标志:其后根两个0
T = NULL; //若某一节点为叶子结点,则其左右子树均为NULL,0表示建空树
else
{
T = (bitree)malloc(sizeof(bitnode));
T->data = item;
T->left = PerCreateTree(); //递归创建其左子树
T->right = PerCreateTree(); //递归创建其右子树
}
return T; //返回根节点
}
//先序递归周游二叉树
void PerOrder(bitree T)
{
if( T ) // T != NULL
{
cout << T->data << " ";
PerOrder(T->left); //递归先序周游其左子树
PerOrder(T->right); //递归先序周游其右子树
}
}
//释放空间
bitree FreeTree(bitree T)
{
if( T )
{
FreeTree(T->left); //递归释放其左子树
FreeTree(T->right); //递归释放其右子树
free(T); //释放根节点
T = NULL; //释放指向根节点的指针
}
return T; //返回释放后的根节点NULL
}
int main()
{
bitree root;
cout << "请输入数据先序创建一棵二叉树:";
root = PerCreateTree(); //先序创建一棵二叉树
cout << "先序周游的结果:";
PerOrder(root); //先序周游
cout << endl;
return 0;
}
数据透视工具
横向打印一颗树
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> ret;
if(root==NULL)
return ret;
queue <TreeNode*> q;
q.push(root);
while(!q.empty()){
int cnt = q.size(); // 每一层有多少个节点
while(cnt--){
TreeNode* node = q.front();
ret.push_back(node->val);
cout<<node->val<<"\t";
if(node->left!=NULL){
q.push(node->left);
}
if(node->right!=NULL){
q.push(node->right);
}
q.pop();
}
cout<<endl;
}
return ret;
}
数组变化监视程序
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class monitor{
private:
vector<string> vec;
vector<vector<int> > vecs;
public:
string loadstr(string s){
vec.push_back(s);
return s;
}
vector<int> loadvec(vector<int> v){
vecs.push_back(v);
return v;
}
vector<int> loadarray(int *ary,int len){
vector <int> v(ary,ary+len);
vecs.push_back(v);
return v;
}
void show(){
for(int i=0;i<vec.size();i++){
cout<<vec[i]<<endl;
}
vector<int> old_v(vecs[0].begin(),vecs[0].end());
for(int i=0;i<vecs.size();i++){
for(int j=0;j<vecs[i].size();j++){
if(j>=1 && vecs[i][j]!=old_v[j]){
cout<<vecs[i][j]<<"<-"<<old_v[j]<<"\t";
}else cout<<vecs[i][j]<<"\t";
}
old_v.assign(vecs[i].begin(),vecs[i].end());
cout<<endl;
}
}
}M;
int* BubbleSort(int* ary, int length)
{
int i, j, tmp;
for(i=0; i<length-1; i++)
{
tmp = ary[i];
for(j=length-1; j>i; j--)
{
//找到数组中最小的数,并交换
if(tmp > ary[j])
{
ary[i] = ary[j];
ary[j] = tmp;
tmp = ary[i];
M.loadarray(ary,length);
}
}
}
return ary;
}
int main(){
int ary [10] ={4,3,21,5,2,10,5,6,7,2};
BubbleSort(ary,10);
M.show();
}
算法
逆序输出链表
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {}
};
vector<int> array = {1,2,3,4,5,6,7};
ListNode* buildList(vector<int> &array) {
ListNode * head = new ListNode(array[0]);
ListNode * p = head;
for(int i=1;i<array.size();i++) {
p->next = new ListNode(array[i]);
p = p->next;
}
return head;
}
ListNode* reverse(ListNode* head){
if(head==NULL || head->next ==NULL)
return head;
ListNode* newhead = reverse(head->next);
head->next->next = head;
head->next = NULL;
return newhead;
}
int main() {
ListNode * p = buildList(array);
ListNode * p_print = p;
while(p_print!=NULL){
cout<<p_print->val<<" ";
p_print = p_print->next;
}
cout<<endl;
ListNode * q = reverse(p);
while(q!=NULL){
cout<<q->val<<" ";
q = q->next;
}
return 0;
}
数组翻转
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string s="hello";
reverse(s.begin(),s.end());
char c[]="hello";
reverse(c,c+strlen(c));
char x[6]={'h','e','l','l','o'};
reverse(x,x+strlen(x));
char str[11];
for(int i=0;i<5;i++)cin>>str[i];
reverse(str,str+5);
cout<<s<<endl;
cout<<c<<endl;
cout<<x<<endl;
for(int i=0;i<5;i++)cout<<str[i];
return 0;
}