精华内容
下载资源
问答
  • 输出十字矩阵

    2021-03-23 20:24:30
    输出十字矩阵 //----------------------------------------输出十字数组------------------------------------- //*输出3行3列的第二行和第二列其余用空格表示并打印*// #include<stdio.h> void main() { int...

    输出十字矩阵

    //----------------------------------------输出十字数组-------------------------------------
    //*输出3行3列的第二行和第二列其余用空格表示并打印*//
    #include<stdio.h>
    void main()
    {
    	int i,j;
    	int a[3][3]; 
    	for(i=0;i<=2;i++)
    	{
    		for(j=0;j<=2;j++)
    		{
    			printf("a[%d][%d]=",i,j);
    			scanf("%d",&a[i][j]);
    		}
    		
    	}
    	for(i=0;i<=2;i++)
    	{
    		for(j=0;j<=2;j++)
    		{
    			if(i==1||j==1)
    			{
    				printf("%-6d",a[i][j]);
    			}
    			else
    			{
    				printf("%-6c",' ');
    			}
    		}
    		printf("\n");
    		
    	}
    } 
    
    展开全文
  • 使用十字矩阵实现稀疏矩阵的运算,完全使用C++实现
  • // 十字矩阵模板类 template class Grid { private: // 矩阵的长宽和面积 int width, height, size; // 指向矩阵四角的四个指针 node<T> *upper_left, *upper_right, *lower_left, *lower_right; public: //...

    今天接到一个单,是纯手写实现一个比较复杂的模板类

    想也没想就接了下来,因为之前只是听说过模板类,但是自己也没有敲过,毕竟ACM的算法也不会涉及到那方面

    花十分钟先找了些实现模板类的博客看了一下,然后就跟着给的测试用例开始写

    真正开始写才发现,这东西是真tm难

    特别是迭代器部分,网上基本找不到有关的实现

    从晚上十点半写到现在凌晨五点也只写了200+行

    两个通宵4000字五百行写出的玩意儿

    完整版(+注释)

    grid.h

    #include <iostream>
    #include <iomanip> 
    using namespace std;
    
    // 十字链表节点,flag用于螺旋迭代器,为0表示当前节点未经过,为1表示当前节点已经走过
    template <class T>
    struct node {
    	int flag;
    	T val;
    	node *up, *down, *left, *right;
    	// 默认构造函数
    	node() :up(nullptr), down(nullptr), left(nullptr), right(nullptr), flag(0) {}
    	// 带参构造函数
    	node(T val) {
    		this->val = val;
    		up = down = left = right = nullptr;
    		flag = 0;
    	}
    };
    
    // 十字链矩阵模板类
    template <class T>
    class Grid {
    private:
    	// 矩阵的长宽和面积
    	int width, height, size;
    	// 指向矩阵四角的四个指针
    	node<T> *upper_left, *upper_right, *lower_left, *lower_right;
    public:
    	// 迭代器子类
    	class iterator {
    	public:
    		// dir 和 mode 是用于蛇形迭代器和螺旋迭代器的,mode 表示迭代器类型,dir 表示迭代器的当前方向
    		// 当 mode 值为 0 时是普通迭代器,当 mode 值为 1 时是蛇形迭代器, 当 mode 值为 2 时是螺旋迭代器
    		int dir, mode;
    		// itr 是迭代器的核心指针,pre 是一个辅助指针
    		node<T> *itr, *pre;
    		// 迭代器的 set 函数就是把当前指针的值修改
    		void set(T val) { itr->val = val; }
    
    		// 下面四个函数是迭代器的移动操作,返回值是当前迭代器的引用,便于连续操作
    		iterator& left() {
    			itr = itr->left;
    			return *this;
    		}
    		iterator& right() {
    			itr = itr->right;
    			return *this;
    		}
    		iterator& up() {
    			itr = itr->up;
    			return *this;
    		}
    		iterator& down() {
    			itr = itr->down;
    			return *this;
    		}
    
    		// 迭代器默认构造函数,默认构造一个普通迭代器
    		iterator() :itr(nullptr), pre(nullptr), mode(0) {}
    
    		// 重载迭代器的 = 操作
    		void operator=(node<T> *it) {
    			// 使用指针 = 的时候一般都是普通迭代器
    			mode = 0;
    			dir = 0;
    			// 当这个指针为空,就不用继续了
    			if (it == nullptr)
    				return;
    			// 当这个指针不为空的时候,找到当前指针的最左段,并把辅助指针复制为最左端的下面一个,方便之后 ++ 操作
    			node<T> *p = it;
    			while (p->left != nullptr)
    				p = p->left;
    			itr = it;
    			pre = p->down;
    		}
    		// 重载迭代器的 != 和 == 操作
    		bool operator!=(const iterator& it) { return this->itr != it.itr; }
    		bool operator==(const iterator& it) { return this->itr == it.itr; }
    		// 重载迭代器的 * 操作,返回一个模板类的引用,方便赋值、判断等操作
    		T& operator*() { return itr->val; }
    		// 重载迭代器的 ++ 操作
    		void operator++(int) {
    			// 普通迭代器,靠辅助指针,每次到了这一行最后可以直接跳到下一行的最左边
    			// 辅助指针只需要在 = 操作时,增加一些操作就可以让 ++ 操作简化到 O1 的复杂度
    			if (mode == 0) {
    				if (itr->right == nullptr) {
    					itr = pre;
    					// 如果到了最后一行,那么下一行得最左端肯定是个空指针
    					// 如果再执行这一步就会出现指针越界
    					if (pre)
    						pre = pre->down;
    				}
    				else
    					itr = itr->right;
    			}
    			// 蛇形迭代器,触底就变向,这个不用说太细
    			else if (mode == 1) {
    				if (dir == 0) {
    					if (itr->right == nullptr)
    						itr = itr->down, dir = 1;
    					else
    						itr = itr->right;
    				}
    				else {
    					if (itr->left == nullptr)
    						itr = itr->down, dir = 0;
    					else
    						itr = itr->left;
    				}
    			}
    			// 螺旋迭代器,靠着在创建节点时的辅助标记 (node 中的 flag), 让这个 ++ 操作变成了 O1 的复杂度
    			// 但是在 begin_spiral 中需要一次 O(W*H) 的复杂度对矩阵中所有节点的 flag 进行一次初始化
    			// 每次到一个节点经过之后赋值为 1,所以每当当前方向之前的节点的 flag 为 1 或是为空就变向就可以了
    			else if (mode == 2) {
    				// 空指针返回空
    				if (itr == nullptr)
    					itr = nullptr;
    				// 当周围四个方向都不能走时,说明已经走完了整个矩阵了,所以变成空指针就可以了
    				else if ((itr->right == nullptr || itr->right->flag == 1) && (itr->down == nullptr || itr->down->flag == 1) && (itr->left == nullptr || itr->left->flag == 1) && (itr->up == nullptr || itr->up->flag == 1))
    					itr = nullptr;
    				// 下面为 4 个方向的具体实现,撞墙就转向,不装就继续往前走,代码很好懂的
    				else if (dir == 0) {
    					itr->flag = 1;
    					if (itr->right == nullptr || itr->right->flag == 1)
    						itr = itr->down, dir = 1;
    					else
    						itr = itr->right;
    				}
    				else if (dir == 1) {
    					itr->flag = 1;
    					if (itr->down == nullptr || itr->down->flag == 1)
    						itr = itr->left, dir = 2;
    					else
    						itr = itr->down;
    				}
    				else if (dir == 2) {
    					itr->flag = 1;
    					if (itr->left == nullptr || itr->left->flag == 1)
    						itr = itr->up, dir = 3;
    					else
    						itr = itr->left;
    				}
    				else if (dir == 3) {
    					itr->flag = 1;
    					if (itr->up == nullptr || itr->up->flag == 1)
    						itr = itr->right, dir = 0;
    					else
    						itr = itr->up;
    				}
    			}
    		}
    	};
    
    	// 具体实现在下面
    	Grid();
    	Grid(int n, int m);
    	Grid(int n, int m, T val);
    	~Grid();
    	void print();
    	T get(int n, int m);
    	void set(int n, int m, T val);
    	void join(Grid<T>& oth);
    	void stack(Grid<T>& oth);
    	void reset(T val);
    	void lift(Grid<T>::iterator x, Grid<T>& oth);
    	void chop(Grid<T>::iterator x, Grid<T>& oth);
    	void clear();
    
    	// 获得宽高面积,直接返回一个相应值就行了,复杂度O1
    	int getWidth() { return this->width; }
    	int getHeight() { return this->height; }
    	int getSize() { return this->size; }
    
    	// 返回一个普通迭代器,指向左上的起点
    	iterator begin() {
    		iterator x;
    		x = upper_left;
    		return x;
    	}
    	// 返回一个普通迭代器,指针域为空
    	iterator end() {
    		iterator x;
    		return x;
    	}
    	// 返回一个蛇形迭代器,指向左上的起点
    	// 注意把迭代器的 mode 设置为蛇形迭代器模式,初始方向向右
    	iterator begin_snake() {
    		iterator x;
    		x = upper_left;
    		x.mode = 1;
    		x.dir = 0;
    		return x;
    	}
    	// 返回一个空指针域的迭代器
    	iterator end_snake() {
    		return end();
    	}
    	// 返回一个螺旋迭代器,指向左上起点
    	// 注意把迭代器的 mode 设置为螺旋迭代器模式,初始方向向右
    	iterator begin_spiral() {
    		iterator it = begin();
    		// 这就是上面说到把矩阵所有节点的 flag 初始化的地方 复杂度 O(W*H)
    		while (it != end())
    			it.itr->flag = 0, it++;
    		iterator x;
    		x = upper_left;
    		x.mode = 2;
    		x.dir = 0;
    		return x;
    	}
    	// 返回一个空指针域迭代器
    	iterator end_spiral() {
    		return end();
    	}
    
    	// 返回指向四角的迭代器
    	iterator begin_upper_left() {
    		iterator x;
    		x = upper_left;
    		return x;
    	}
    	iterator begin_upper_right() {
    		iterator x;
    		x = upper_right;
    		return x;
    	}
    	iterator begin_lower_left() {
    		iterator x;
    		x = lower_left;
    		return x;
    	}
    	iterator begin_lower_right() {
    		iterator x;
    		x = lower_right;
    		return x;
    	}
    };
    
    // 默认构造函数,四角默认为空指针,宽高面积为 0
    template <class T>
    Grid<T>::Grid() {
    	upper_left = nullptr; upper_right = nullptr;
    	lower_left = nullptr; lower_right = nullptr;
    	width = height = size = 0;
    }
    // 只有宽高的构造函数,默认填充的为 int 0
    template <class T>
    Grid<T>::Grid(int n, int m) {
    	width = n; height = m; size = n * m;
    	// 三个辅助指针,pre表示上一层相应位置节点,up为上一层最左端点,q为左边一个节点
    	// 用于将当前节点与前面和上面的节点链接起来
    	node<T> *pre = nullptr, *up = nullptr, *q = nullptr;
    	for (int a = 0; a < m; a++) {
    		// pre初始化为上一层最左端点
    		pre = up;
    		for (int b = 0; b < n; b++) {
    			node<T> *p = new node<T>(0);
    			// 把左上指针指向当前节点
    			if (a == 0 && b == 0)
    				upper_left = p;
    			// 把右上指针指向当前节点
    			if (a == 0 && b == n - 1)
    				upper_right = p;
    			// 把左下指针指向当前节点
    			if (a == m - 1 && b == 0)
    				lower_left = p;
    			// 把右下指针指向当前节点
    			if (a == m - 1 && b == n - 1)
    				lower_right = p;
    			// 第一竖排,前面没有节点可供链接
    			if (b == 0) {
    				// up每次赋值为最左端点,下一次循环 pre 赋值时就变成了上一层的最左端点
    				up = p, q = p;
    				// 第一横排之后才需要和上一层的节点链接
    				if (a != 0)
    					p->up = pre, pre->down = p, pre = pre->right;
    			}
    			else {
    				if (a != 0)
    					p->up = pre, pre->down = p, pre = pre->right;
    				p->left = q, q->right = p, q = q->right;
    			}
    		}
    	}
    }
    // 和上面的流程一样,只是带上了值,就不重复写了
    template <class T>
    Grid<T>::Grid(int n, int m, T val) {
    	width = n; height = m; size = n * m;
    	node<T> *pre = nullptr, *up = nullptr, *q = nullptr;
    	for (int a = 0; a < m; a++) {
    		pre = up;
    		for (int b = 0; b < n; b++) {
    			node<T> *p = new node<T>(val);
    			if (a == 0 && b == 0)
    				upper_left = p;
    			if (a == 0 && b == n - 1)
    				upper_right = p;
    			if (a == m - 1 && b == 0)
    				lower_left = p;
    			if (a == m - 1 && b == n - 1)
    				lower_right = p;
    			if (b == 0) {
    				up = p, q = p;
    				if (a != 0)
    					p->up = pre, pre->down = p, pre = pre->right;
    			}
    			else {
    				p->left = q, q->right = p, q = q->right;
    				if (a != 0)
    					p->up = pre, pre->down = p, pre = pre->right;
    			}
    		}
    	}
    }
    // 析构函数,不能边遍历边删除内存,因为删除之后,之前的节点就不存在了,用++就无法跳到下一个
    // 所以用一个指针数组,遍历一遍把所有指针存起来,然后再挨个删除,复杂度为 O(W*H)
    // clear()函数和这个析构函数一模一样下面就不重复了
    template <class T>
    Grid<T>::~Grid() {
    	iterator it = begin();
    	node<T>*ve[10000];
    	int len = 0;
    	// 遍历矩阵,把每个指针都存入指针数组
    	while (it != end())
    		ve[len++] = it.itr, it++;
    	// 挨个删除节点内存
    	for (int a = 0; a < len; a++)
    		delete ve[a];
    	// 初始化长宽面积和四角指针
    	width = height = size = 0;
    	upper_left = upper_right = nullptr;
    	lower_left = lower_right = nullptr;
    }
    // 打印函数,遍历打印就行了
    // setw(4)设置宽度为4,右对齐,空格补缺
    template <class T>
    void Grid<T>::print() {
    	iterator it = begin();
    	for (int a = 0; a < height; a++, cout << endl)
    		for (int b = 0; b < width; b++)
    			cout << setw(4) << *it, it++;
    }
    // get函数,获取某个位置的值
    // 返回右移 n 次,下移 m 次之后对应的值就行 复杂度 O(W*H)
    template <class T>
    T Grid<T>::get(int n, int m) {
    	iterator it = begin();
    	while (n--)
    		it.right();
    	while (m--)
    		it.down();
    	return *it;
    }
    // set函数,修改某个位置的值
    // 基本思路和 get 函数一样,找到位置通过迭代器的 set 函数赋值就行了
    template <class T>
    void Grid<T>::set(int n, int m, T val) {
    	iterator it = begin();
    	while (n--)
    		it.right();
    	while (m--)
    		it.down();
    	it.set(val);
    }
    // join函数,把另一个矩阵合并到当前矩阵右边
    // 因为合并之后需要把传入的矩阵清除,所以传参用引用
    template <class T>
    void Grid<T>::join(Grid<T>& oth) {
    	// 宽度变成合并之后的宽度
    	width += oth.getWidth();
    	// 修改面积
    	size = width * height;
    	iterator pre, back;
    	// 找到当前矩阵的右上角和 oth 矩阵的左上角
    	pre = begin_upper_right();
    	back = oth.begin_upper_left();
    	// 然后把这两个节点链接在一起,并一起向下移动,就想拉拉链一样把两个矩阵缝合起来
    	while (pre != end()) {
    		pre.itr->right = back.itr;
    		back.itr->left = pre.itr;
    		pre.down(); back.down();
    	}
    	// 重新设置当前矩阵的右上角和右下角的指向
    	upper_right = oth.upper_right;
    	lower_right = oth.lower_right;
    	// 清除 oth 矩阵的信息
    	oth.width = oth.height = oth.size = 0;
    	oth.upper_left = oth.upper_right = nullptr;
    	oth.lower_left = oth.lower_right = nullptr;
    }
    // stack函数,把两个矩阵上下合并
    // 思路和join函数相同,代码也差不多,结合着看就行
    template <class T>
    void Grid<T>::stack(Grid<T>& oth) {
    	height += oth.getHeight();
    	size = width * height;
    	iterator pre, back;
    	pre = begin_upper_left();
    	back = oth.begin_lower_left();
    	while (pre != end()) {
    		pre.itr->up = back.itr;
    		back.itr->down = pre.itr;
    		pre.right(); back.right();
    	}
    	upper_left = oth.upper_left;
    	upper_right = oth.upper_right;
    	oth.width = oth.height = oth.size = 0;
    	oth.upper_left = oth.upper_right = nullptr;
    	oth.lower_left = oth.lower_right = nullptr;
    }
    // clear函数,和析构函数一样,删除内存,并清除相应信息
    template <class T>
    void Grid<T>::clear() {
    	iterator it = begin();
    	node<T>*ve[10000];
    	int len = 0;
    	while (it != end())
    		ve[len++] = it.itr, it++;
    	for (int a = 0; a < len; a++)
    		delete ve[a];
    	width = height = size = 0;
    	upper_left = upper_right = nullptr;
    	lower_left = lower_right = nullptr;
    }
    // reset函数,用一个值覆盖矩阵
    // 遍历并赋值就行了
    template <class T>
    void Grid<T>::reset(T val) {
    	iterator it = begin();
    	while (end() != it) {
    		*it = val;
    		it++;
    	}
    }
    // lift上下切割函数
    // 因为要把切下来的矩阵给 oth,所以传参用引用
    template <class T>
    void Grid<T>::lift(Grid<T>::iterator x, Grid<T>& oth) {
    	// 把传入的矩阵清理掉,以免赋值后出现内存泄漏
    	oth.clear();
    	// 三个赋值指针
    	node<T> *lf = x.itr, *rt = x.itr, *p = x.itr;
    	int ind = 0;
    	// p的目的是找出要切割部分的高度
    	while (p->up != nullptr)
    		ind++, p = p->up;
    	// lf的目的是找到传入迭代器的最左端
    	while (lf->left != nullptr)
    		lf = lf->left;
    	// rt的目的是找到传入迭代器的最右端
    	while (rt->right != nullptr)
    		rt = rt->right;
    	// 更新切下矩阵的相关信息
    	oth.width = width;
    	oth.height = ind;
    	oth.size = oth.width*oth.height;
    	// 当切下的部分至少有一行才需要更新
    	if (ind != 0) {
    		// 更新 oth 矩阵的四角指针
    		oth.upper_left = upper_left; oth.upper_right = upper_right;
    		oth.lower_left = lf->up; oth.lower_right = rt->up;
    		// 因为上面被切了,所以当前矩阵的左上右上指针要下移到找到的左端点和右端点
    		upper_left = lf; upper_right = rt;
    		// 更新当前矩阵相关信息
    		height -= ind;
    		size = height * width;
    		// 因为矩阵切开了,所以要把上下两部分矩阵之前的连线断开
    		// 挨个断开,并不断右移
    		while (lf != nullptr)
    			lf->up->down = nullptr, lf->up = nullptr, lf = lf->right;
    	}
    }
    // chop左右切割函数
    // 大体思路和lift一样只是把横着的变成了竖着的,除此之外只有一个地方不同
    template <class T>
    void Grid<T>::chop(Grid<T>::iterator x, Grid<T>& oth) {
    	oth.clear();
    	node<T> *tp = x.itr, *dn = x.itr, *p = x.itr;
    	int ind = 1;
    	while (p->right != nullptr)
    		ind++, p = p->right;
    	while (tp->up != nullptr)
    		tp = tp->up;
    	while (dn->down != nullptr)
    		dn = dn->down;
    	oth.width = ind;
    	oth.height = height;
    	oth.size = oth.width*oth.height;
    	// 因为这个切割有可能把当前矩阵切得一点不剩,所以当这种情况发生的时候,之前把 oth 赋值为当前矩阵,并把当前矩阵的信息清除就行了
    	if (ind == width) {
    		oth.lower_left = lower_left; oth.lower_right = lower_right;
    		oth.upper_left = upper_left; oth.upper_right = upper_right;
    		lower_left = lower_right = nullptr;
    		upper_left = upper_right = nullptr;
    		height = width = size = 0;
    	}
    	else {
    		oth.upper_left = tp; oth.upper_right = upper_right;
    		oth.lower_left = dn; oth.lower_right = lower_right;
    		upper_right = tp->left; lower_right = dn->left;
    		width -= ind;
    		size = height * width;
    		while (tp != nullptr)
    			tp->left->right = nullptr, tp->left = nullptr, tp = tp->down;
    	}
    }

    main.cpp

    // =====================================================================
    // =====================================================================
    // NOTE: DO NOT EDIT THIS FILE EXCEPT WHERE INDICATED
    // =====================================================================
    // =====================================================================
    
    
    #include <iostream>
    #include <cassert>
    #include <cstdlib>
    #include <string>
    
    
    // You will write the grid.h file to implement the Grid class and
    // helper classes GridIterator and Node.
    #include "grid.h"
    
    
    // prototypes for helper testing functions
    void test_example();
    void test_iterators();
    void test_separation();
    void test_iterators_part_2();
    
    void additional_student_tests();
    
    
    // =====================================================================
    // =====================================================================
    
    int main(int argc, char* argv[]) {
      //_CrtSetBreakAlloc(361);
      // =======================================================================
      // NOTE: UNCOMMENT THESE FUNCTIONS AS YOU WORK THROUGH YOUR IMPLEMENTATION
      // =======================================================================
    
      test_example();
      test_iterators();
      test_separation();
      test_iterators_part_2();
    
      //additional_student_tests();
      _CrtDumpMemoryLeaks();
    }
    
    // =====================================================================
    // =====================================================================
    
    void test_example() {
      std::cout << "=====================================================================" << std::endl;
      std::cout << "test_example()" << std::endl;
    
    
      // ------------------------------
      // simple construction & printing
      std::cout << "\nA 5x1 horizontal row:" << std::endl;
      Grid<int> horizontal(5,1,42);
      horizontal.print();
    
      std::cout << "\nA 1x3 vertical column:" << std::endl;
      Grid<int> vertical(1,3,99);
      vertical.print();
      
      std::cout << "\nA 4x3 grid of zeros:" << std::endl;
      Grid<int> grid(4,3);
      assert (grid.getWidth() == 4);
      assert (grid.getHeight() == 3);
      assert (grid.getSize() == 12);
      grid.print();
    
      
      
      // --------------------------------------------
      // initializing and checking values by index
      // (rather inefficient for this data structure)
      std::cout << "\nNow let's initialize the grid values:" << std::endl;
      int tmp = 1;
      for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 4; i++) {
          grid.set(i,j,tmp);
          tmp++;
        }
      }
      grid.print();
      assert (grid.get(0,0) == 1);
      assert (grid.get(0,1) == 5);
      assert (grid.get(2,2) == 11);
    
      
      // ----------------------
      // create basic iterators
      Grid<int>::iterator itr;
      itr = grid.begin_upper_left();
      assert (*itr == 1);
      itr  = grid.begin_upper_right();
      assert (*itr == 4);
      itr = grid.begin_lower_left();
      assert (*itr == 9);
      itr  = grid.begin_lower_right();
      assert (*itr == 12);
      
      
      // -------------------------------
      // combining grids: join and stack
      std::cout << "\nLet's join the vertical column on the right: " << std::endl;
      grid.join(vertical);
      assert (grid.getWidth() == 5);
      assert (grid.getHeight() == 3);
      assert (vertical.getWidth() == 0);
      assert (vertical.getHeight() == 0);
      grid.print();
      std::cout << "\nAnd stack the horizontal row on the top: " << std::endl;
      grid.stack(horizontal);
      assert (grid.getWidth() == 5);
      assert (grid.getHeight() == 4);
      assert (horizontal.getWidth() == 0);
      assert (horizontal.getHeight() == 0);
      grid.print();
    
      std::cout << "\ndone with test_example()" << std::endl;
    }
    
    // =====================================================================
    // =====================================================================
    
    void test_iterators() {
    
      
      std::cout << "=====================================================================" << std::endl;
      std::cout << "test_iterators()" << std::endl;
      
      std::cout << "\nA 6x4 grid of dots:" << std::endl;
      Grid<char> grid(6,4,'.');
      assert (grid.getWidth() == 6);
      assert (grid.getHeight() == 4);
      grid.print();
    
      std::cout << "\nUse an iterator to walk along a specific path in the grid:" << std::endl;
      Grid<char>::iterator itr  = grid.begin_lower_right();
      assert (*itr == '.');
      *itr = '0';
      itr.left();  *itr = '1';
      itr.up();    *itr = '2';
      itr.up();    *itr = '3';
      itr.left();  *itr = '4';
      itr.left();  *itr = '5';
      itr.left();  *itr = '6';
      itr.down();  *itr = '7';
      itr.right(); *itr = '8';
      itr.down();  *itr = '9';
      grid.print();
    
      
      std::cout << "\nReset all values in the grid to a specific value" << std::endl;
      grid.reset('?');
      grid.print();
      
      std::cout << "\nLabel by snaking horizontally through the grid:" << std::endl;
      char tmp = 'a';
      itr = grid.begin_snake();
      while (itr != grid.end_snake()) {
        assert (*itr == '?');
        *itr = tmp;
        tmp++;
        itr++;
      }
      grid.print();
    
      grid.clear();
      assert (grid.getSize() == 0);
      assert (grid.getWidth() == 0);
      assert (grid.getHeight() == 0);
        
      std::cout << "\ndone with test_iterators()" << std::endl;
     
    }
    
    // =====================================================================
    // =====================================================================
    
    void test_separation() {
      
      std::cout << "=====================================================================" << std::endl;
      std::cout << "test_separation()" << std::endl;
    
      std::cout << "\nPrepare an interesting grid:" << std::endl;
      Grid<int> grid(7,5);
      int tmp = 1;
      Grid<int>::iterator itr = grid.begin_snake();
      while (itr != grid.end_snake()) {
        assert (*itr == 0);
        *itr = tmp;
        tmp++;
        itr++;
      }
      grid.print();
      itr = grid.begin_upper_left();
      itr.right().right().down().down();
      assert (*itr == 17);
    
      
      std::cout << "\nLifting off the top:" << std::endl;
      Grid<int> top;
      assert (top.getSize() == 0 && top.getWidth() == 0 && top.getHeight() == 0);
      grid.lift(itr,top);
      top.print();
    
      std::cout << "\nLeaving the rest:" << std::endl;
      grid.print();
      assert (*itr == 17);
    
      
      std::cout << "\nChopping off the right:" << std::endl;
      Grid<int> side;
      grid.chop(itr,side);
      side.print();
    
      std::cout << "\nLeaving the rest:" << std::endl;
      grid.print();
      assert (*itr == 17);
      itr.right().down();
      assert (*itr == 25);
    
      
      std::cout << "\nJoin it back together on the other side:" << std::endl;
      side.join(grid);
      side.print();
    
      std::cout << "\nAnd stack on the top:" << std::endl;
      top.stack(side);
      top.print();
      assert (top.getWidth() == 7);
      assert (top.getHeight() == 5);
      assert (top.getSize() == 35);
    
      assert (*top.begin_upper_left()  == 17);
      assert (*top.begin_upper_right() == 16);
      assert (*top.begin_lower_right() == 8);
      assert (*top.begin_lower_left()  == 14);
      
      std::cout << "\ndone with test_separation()" << std::endl;
      
    }
    
    // =====================================================================
    // =====================================================================
    
    void test_iterators_part_2() {
      
      std::cout << "=====================================================================" << std::endl;
      std::cout << "test_iterators_part_2()" << std::endl;
    
      std::cout << "\nA 6x4 grid of _'s:" << std::endl;
      Grid<char> grid(6,4,'_');  
      grid.print();
    
      std::cout << "\nLabel by spiraling into the grid:" << std::endl;
      char tmp = 'A';
      Grid<char>::iterator itr = grid.begin_spiral();
      while (itr != grid.end_spiral()) {
        assert (*itr == '_');
        *itr = tmp;
        tmp++;
        itr++;
      }
      grid.print();
    
    
      std::cout << "\nAnd a larger example:" << std::endl;
      Grid<int> bigger(8,10,0);
      Grid<int>::iterator itr2 = bigger.begin_spiral();
      int tmp2 = 1;
      while (itr2 != bigger.end_spiral()) {
        *itr2 = tmp2;
        tmp2++;
        itr2++;
      }
      bigger.print();
    
    
      // walking off the board should hit the end iterator
      itr2 = bigger.begin_lower_left();
      assert (*itr2 == 24);
      itr2.right().right();
      assert (*itr2 == 22);
      itr2.down();
      assert (itr2 == bigger.end()); 
    
      itr2 = bigger.begin_upper_right();
      assert (*itr2 == 8);
      itr2.down().down();
      assert (*itr2 == 10);
      itr2.right();
      assert (itr2 == bigger.end());
    
      
      std::cout << "\nA dereferenced iterator can be an l-value (and modify data):" << std::endl;
      itr2 = bigger.begin_lower_right();
      itr2.up().left().up().left();
      assert (*itr2 = 65);
      *itr2 = 0;
      assert (bigger.get(5,7) == 0);
    
      itr2 = bigger.begin_snake();
      for (int i = 0; i < 19; i++) { itr2++; }
      assert (*itr2 = 58);
      *itr2 = -1;
      assert (bigger.get(3,2) == -1);
      
      bigger.print();
      
      std::cout << "\ndone with test_iterators_part_2()" << std::endl;
      
    }  
    
    
    // =====================================================================
    // =====================================================================
    
    void additional_student_tests() {
    
      std::cout << "=====================================================================" << std::endl;
      std::cout << "additional_student_tests()" << std::endl;
    
    
    
      // =======================================================================
      // NOTE: WRITE YOUR OWN TEST CASES HERE!
      // =======================================================================
    
    
    
      std::cout << "done with additional_student_tests()" << std::endl;
    }
    
    // ======================================================================
    // ======================================================================
    

     

    展开全文
  • 稀疏矩阵十字链表

    2015-10-05 15:19:53
    稀疏矩阵十字链表
  • 数据结构课程设计 十字链表稀疏矩阵相加 本课程设计主要实现在十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行相加,操作,最后输出运算后的结果。稀疏矩阵采用十字链表表示,并在不同的存储结构下,求两个具有...
  • 十字链表,矩阵

    2013-01-07 18:03:54
    十字链表,矩阵
  • 三元组矩阵十字链表矩阵三元组矩阵十字链表矩阵 #define smax 30 //定义存储元素空间大小,可根据按照需求更改 typedef int datatype; 三元组矩阵 // 定义存储三元组的结构体 typedef struc...

    学习了数据结构这门课后,针对我所掌握的知识进行学习记录。
    源码链接: https://github.com/GetorPut/Data-Structure.

    三元组矩阵、十字链表矩阵

    #define smax 30 //定义存储元素空间大小,可根据按照需求更改 
    typedef int datatype;
    

    三元组矩阵

    实际的矩阵
    非零元素

    // 定义存储三元组的结构体
    typedef struct
    {
    	int i,j;		//(当前元素的)行,列
    	datatype v;		//非零元素
    }node;
    typedef struct
    {
    	int m,n,t;		//(总的)行,列,元素数
    	node data[smax];//存储非零元素的空间
    }spmatrix;//三元组存储
    
    //创建三元组矩阵
    spmatrix *creatseqmat(void)
    {
    	int i,j,n,m,t=0,v;
    	spmatrix *p;
    	printf("创建三元组矩阵:\n");
    	p=(spmatrix*)malloc(sizeof(spmatrix));//申请一块连续的空间用于存放输入的非零数
    	printf("Please input 总行m,总列n:\n");
    	scanf("%d,%d",&m,&n);
    	if(m*n>smax || m<=0 || n<=0)
    	{
    		printf("输入无效\n");
    		return NULL;
    	}
    	printf("Please input 行i,列j,元素v:\n");
    	scanf(" %d,%d,%d",&i,&j,&v);//注意最前方有一个空格
    	p->m=m;
    	p->n=n;
    	p->t=t;
    	p->data[t].i=i;
    	p->data[t].j=j;
    	p->data[t].v=v;	//防止刚开始输入 x,y,0 这类情况发生后导致死循环现象 
    	while(v!=0)
    	{
    		if(t>=smax)
    		{
    			printf("储存空间已满\n");
    			break; 
    		}
    		t+=1;
    		p->t=t;
    		p->data[t].i=i;
    		p->data[t].j=j;
    		p->data[t].v=v;
    		scanf(" %d,%d,%d",&i,&j,&v);
    	}
    	return p;
    }
    //打印三元组矩阵
    void printmat(spmatrix *a)
    {
    	int i,j,k,t;
    	printf("打印三元组矩阵:\n");
    	for(i=1;i<=a->m;i++)
    	{
    		for(j=1;j<=a->n;j++)
    		{
    			t=0;	
    			/*
    				在每一轮列的循环中查找匹配的非零元素
    			 	否则出现一些漏输的现象
    			 	(因为之前的行列查找已经找过后一个非零元素,
    				 但是与当前非零元素的行列不匹配) 
    			*/
    			for(k=1;k<=a->t;k++) 
    				if((a->data[k].i==i)&&(a->data[k].j==j))
    				{
    					printf("%d ",a->data[k].v);
    					t++;
    					break;
    				}
    				if(t==0)
    					printf("0 ");
    				
    		}
    		printf("\n");
    	}
    } 
    

    结果截图

    十字链表矩阵

    演示图

    //十字链表
    typedef struct Inode
    {
    	int i,j;					//行,列
    	struct Inode *rptr,*cptr;	//行列指针
    	union
    	{
    		struct Inode *next;		//存放下一个结构体的地址
    		datatype v;				//非零元素
    	}uval;
    }link;
    
    //建立十字链矩阵
    link *createlinkmat(void)
    {
    	link *p,*a,*b,*cp[smax];
    	int i,j,v,m,n,t=0,max,k;
    	printf("创建十字链矩阵:\n");
    	printf("Please input 总行m,总列n:\n");
    	scanf("%d,%d",&m,&n);
    	if(m*n>smax || m<=0 || n<=0)
    	{
    		printf("输入无效\n");
    		return NULL;
    	}
    	if(m>n)max=m;
    	else max=n;
    	p=(link*)malloc(sizeof(link));
    	p->i=m;
    	p->j=n;
    	cp[0]=p;	//总表头节点
    	for(k=1;k<=max;k++)
    	{
    		cp[k]=(link*)malloc(sizeof(link));
     		cp[k]->i=0;
    		cp[k]->j=0;
    		cp[k]->rptr=cp[k];
    		cp[k]->cptr=cp[k];
    		cp[k-1]->uval.next=cp[k]; 
    	}		//行列表头节点
    	cp[max]->uval.next=p; //形成循环链表
    	printf("Please input 行i,列j,元素v:(不要超界呦)\n");
    	scanf(" %d,%d,%d",&i,&j,&v);
    	while(v!=0)
    	{
    		if(t>=smax)
    		{
    			printf("储存空间已满\n");
    			break; 
    		}
    		t++;
    		a=(link*)malloc(sizeof(link));
    		a->i=i;
    		a->j=j;
    		b=cp[i];//同一行
    		while(b->rptr!=cp[i]&&b->rptr->j<j)//最后,之间(的元素为基准)
    			b=b->rptr;
    		a->rptr=b->rptr;	//当前 -> 后 
    		b->rptr=a;			//前 -> 当前 
    		b=cp[j];//同一列
    		while(b->cptr!=cp[j]&&b->cptr->i<i)
    			b=b->cptr;
    		a->cptr=b->cptr;
    		b->cptr=a;
    		a->uval.v=v; 
    		scanf(" %d,%d,%d",&i,&j,&v);
    	}
    	return p;
    }
    //输出十字矩阵
    void printlinkmat(link *h)
    {
    	int i=1,n,k;
    	link *p,*q,*a;
    	printf("打印十字矩阵:\n");
    	n=h->j;
    	
    	p=h->uval.next;
    	while(p!=h && i<=h->i)
    	{
    		a=p->rptr;//row 行
    		q=p;
    		while(a!=p)
    		{
    			//插入同一行两非零元素间的“0”和 第一个非零元素之前的零 
    			for(k=1;k<(a->j)-(q->j);k++)  
    				printf("0 ");
    			printf("%d ",a->uval.v);	
    			q=a; 		//记录当前元素,直至同行最后一个非零值 
    			a=a->rptr;	//a指向这一行的下一个元素
    		}
    		for(k=q->j;k<n;k++)   //插入同一行中最后一个非零元素后面的“0” 
    			printf("0 ");
    		printf("\n");
    		i++;
    		p=p->uval.next;
    	}
    }
    //把十字矩阵转换为三元组矩阵
    spmatrix *changemat(link *h)
    {
    	int m,n,t=1;
    	link *p,*q;
    	spmatrix *l;
    	printf("十字矩阵转换为三元组矩阵:\n");
    	m=h->i;
    	n=h->j;
    	l=(spmatrix*)malloc(sizeof(spmatrix));
    	l->m=m;
    	l->n=n;
    	p=h->uval.next;
    	while(p!=h)
    	{
    		q=p->rptr; //行   以下为同一行的查找、赋值 
    		while(q!=p)
    		{
    			l->data[t].i=q->i;
    			l->data[t].j=q->j;
    			l->data[t].v=q->uval.v;	
    			t++;
    			q=q->rptr;
    		}
    		p=p->uval.next;
    	}
    	l->t=t-1;
    	return l;
    }
    //转置三元组矩阵
    spmatrix *transmat(spmatrix *b)
    {
    	int k,i,j;
    	spmatrix *p;
    	p=(spmatrix*)malloc(sizeof(spmatrix));
    	p->m=b->n;
    	p->n=b->m;//行列互换
    	p->t=b->t; 
    	printf("转置三元组矩阵:\n");
    
    	for(k=1;k<=b->t;k++)
    	{
    		i=b->data[k].i;
    		j=b->data[k].j;
    		p->data[k].i=j;
    		p->data[k].j=i;
    		p->data[k].v=b->data[k].v;
    	}
    	return p;
    } 
    

    在这里插入图片描述

    展开全文
  • 矩阵十字计算

    2012-11-27 21:13:34
    矩阵的计算代码,十字链表的计算,加减乘。
  • 十字链表矩阵

    2015-04-16 14:31:00
    数据结构的十字链表矩阵要一开始的行列的表头要相互连接来表示邻接关系 这里用数组表示邻接也不浪费空间 写了Serach( i , j );函数可以寻找矩阵位置为i j数值 然后加,减,乘,也就方便了…… 至于算法复杂度嘛...

    数据结构的十字链表矩阵要一开始的行列的表头要相互连接来表示邻接关系

    这里用数组表示邻接也不浪费空间

    写了Serach( i , j );函数可以寻找矩阵位置为i j数值

    然后加,减,乘,也就方便了……

    至于算法复杂度嘛……因为懒所以直接用Search()了(所以矩阵运算比想象中复杂度高……)……23333333

    代码……

    #include <iostream>
    #include <cstdio>
    #include <iomanip>
    #include <cstdlib>
    
    using namespace std;
    
    struct Node{
        int row;
        int col;
        int val;
        Node * right;
        Node * down;
        Node(int r = 0,int c = 0,int v = 0):row(r),col(c),val(v){
            right = down = NULL;
        }
    };
    
    class SparseMatrix{
        Node * first;
        friend ostream & operator << (ostream &,SparseMatrix &);
    public:
        SparseMatrix(){
            first = NULL;
        }
        void Create(int r,int c){
            int m = max(r,c);
            first = new Node[m+1];
            first[0].row = r;
            first[0].col = c;
            first[0].val = 0;
        }
        void Create(){
            cout << "请输入矩阵的行列和数目" << endl;
            int r,c,num;
            cin >> r >> c >> num;
            int m = max(r,c);
            first = new Node[m+1];
            first[0].row = r;
            first[0].col = c;
            first[0].val = 0;
    
            while(num--){
                cout << "请输入元素" << endl;
                cin >> r >> c >> m;
                if(m == 0)
                    continue;
                Insert(r,c,m);
            }
        }
        void Insert(int r,int c,int v){
            Node * p = new Node(r,c,v);
            Node * rr = &first[r];
            Node * cc = &first[c];
            first[0].val++;
            while(rr->right != NULL && rr->right->col <= c){
                rr = rr->right;
            }
            p->right = rr->right;
            rr->right = p;
            while(cc->down != NULL && cc->down->row <= r){
                cc = cc->down;
            }
            p->down = cc->down;
            cc->down = p;
        }
        int Search(int r,int c){
            Node * rr = & first[r];
            while(rr->right != NULL && rr->right->col <= c){
                if(rr->right->col == c)
                    return rr->right->val;
                rr = rr->right;
            }
            return 0;
        }
        Node * getFirst(){
            return first;
        }
        SparseMatrix & operator + (SparseMatrix & x){
            Node * p = first;
            Node * q = x.getFirst();
            int r = p[0].row;
            int c = p[0].col;
            if(r != q[0].row || c != q[0].col){
                cout << "矩阵行列不相同,退出" << endl;
                exit(1);
            }
            SparseMatrix s;
            s.Create(r,c);
            for(int i = 1;i <= r;i++){
                for(int j = 1;j <= c;j++){
                    int tmp = Search(i,j)+x.Search(i,j);
                    if(tmp != 0){
                        s.Insert(i,j,tmp);
                    }
                }
            }
            return s;
        }
        SparseMatrix & operator * (SparseMatrix & x){
            Node * p = first;
            Node * q = x.getFirst();
            int r = p[0].row;
            int c = q[0].col;
            int m = p[0].col;
            if(m != q[0].row){
                cout << "矩阵不能相乘"<< endl;
            }
            SparseMatrix s;
            s.Create(r,c);
            for(int i = 1;i <= r;i++){
                for(int j = 1;j <= c;j++){
                    int ans = 0;
                    for(int k = 1;k <= m;k++){
                        ans += (Search(i,k)*x.Search(k,j));
                    }
                    if(ans != 0){
                        s.Insert(i,j,ans);
                    }
                }
            }
            return s;
        }
        SparseMatrix & Reserve(){
            Node * p = first;
            int r = p[0].row;
            int c = p[0].col;
            SparseMatrix s;
            s.Create(r,c);
            for(int i = r;i > 0;i--){
                for(int j = c;j > 0;j--){
                    int tmp = Search(i,j);
                    if(tmp != 0){
                        s.Insert(j,i,tmp);
                    }
                }
            }
            return s;
        }
    };
    ostream & operator << (ostream &out,SparseMatrix &x){
        Node * p = x.getFirst();
        int r = p->row;
        int c = p->col;
        cout << "矩阵为:" << endl;
        for(int i = 0;i <= r;i++){
            if(i)
                cout << setw(4) << i;
            for(int j = 1;j <= c;j++){
                if(!i){
                    if(j == 1)
                        out << setw(8)<< j;
                    else
                        out << setw(4)<< j;
                    continue;
                }
                cout << setw(4) << x.Search(i,j);
            }
            cout << endl;
        }
        return out;
    }
    int main(){
        //freopen("input.txt","r",stdin);
        SparseMatrix matrix1;
        SparseMatrix matrix2;
        matrix1.Create();
        matrix2.Create();
        SparseMatrix matrix3 = matrix1 + matrix2;
        SparseMatrix matrix4 = matrix1 * matrix2;
        SparseMatrix matrix5 = matrix1.Reserve();
        cout << "矩阵1 为" << matrix1 << endl;
        cout << "矩阵2 为" << matrix2 << endl;
        cout << "矩阵1,2相加 为" << matrix3 << endl;
        cout << "矩阵1,2相乘 为" << matrix4 << endl;
        cout << "矩阵1 转置 为" << matrix5 << endl;
        return 0;
    }

     

    转载于:https://www.cnblogs.com/hanbinggan/p/4432026.html

    展开全文
  • 稀疏矩阵十字链表表示方法:矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序
  • 数据结构第五次作业-数组运算 数据结构第五次作业-----数组的运算 实验目的 掌握稀疏矩阵的压缩存储方法及主要运算的实现 实验内容与要求 设计一个稀疏矩阵计算器要求能够 输入并建立稀疏矩阵 输出稀疏矩阵 执行两个...
  • #include &lt;stdio.h&gt; #include &lt;malloc.h&...// 稀疏矩阵十字链表存储表示 typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值 ...
  • 十字链表储存稀疏矩阵矩阵相乘

    千次阅读 2016-11-03 09:28:11
    在进行矩阵的加法、减法和乘法等运算时,用十字链表表示稀疏矩阵比用三元组表示更灵活,以下为结构图和代码
  • 十字链表实现矩阵

    2015-04-29 16:46:36
    十字链表实现矩阵的加减乘转置
  • 在学习《数据结构(C语言版)》中第五章稀疏矩阵时,课本提示使用十字链表实现矩阵相加,没能运行,于是自己调试实现了下,希望对大家有帮助
  • 记录十字链表打印矩阵## 标题 源码 #include<iostream> using namespace std; #define maxSize 4 //十字链表存储矩阵 //普通结点结构定义 typedef struct OLNode { int col,row;//列号,行号 struct ...
  • 十字链表表示稀疏矩阵 只是很简单的程序 应该能看懂
  • 类型定义 #include<stdio.h> #include<malloc.h> #include<... 稀疏矩阵十字链表表示: 非零元素节点与表头节点公用一种类型 */ typedef struct matrixnode { int row,col; struct ...
  • 稀疏矩阵十字链表表示法和基本运算 #include <stdio.h> #include <malloc.h> #define M 3 //矩阵行 #define N 3 //矩阵列 #define Max ((M)>(N)?(M):(N)) //矩阵行列较大者 typedef int ...
  • 结构 十字链表 矩阵 相加 定义结构都是书上的 就是个求和没有 自己写的
  • 采用十字链表表示稀疏矩阵,并实现矩阵的加法运算
  • [c]代码库typedef struct node{int row, col;struct node *down , *right;union v_next{datatype v;...MLink CreatMLink( ) /* 返回十字链表的头指针*/{MLink H;Mnode *p,*q,*hd[s+1];int i,j,m,n...
  • 产生背景 矩阵的非零元个数和位置在操作过程中变化较大,不再...2、每个非零元同时是某个行列表或者列链表的结点,把一个矩阵转化成了一个十字交叉的链表。 3、可用两个一维数组来表示,分别存储行链表的头指针和列链..
  • //稀疏矩阵十字链表存储表示4 typedef structOLNode5 {6 int i,j; //该非零元的行和列下标7 ElemType e; //非零元素值8 struct OLNode *right,*down; //该非零元所在行表和列表的后继链域9 }OL...
  • 十字链表的实现当稀疏矩阵的非零元数量和位置在操作过程中变化较大时(如矩阵相加),便不再适宜采用顺序存储,此时使用链式存储更为恰当。十字链表的实现typedef struct{int i,j;ElemType e;OLNode *right,*down;//...
  • 因为实现矩阵转置的前提是将矩阵存储起来,数据结构中提供了 3 种存储矩阵的结构,分别是三元组顺序表、行逻辑链接的顺序表和十字链表。如果采用前两种结构,矩阵的转置过程会涉及三元组表也跟着改变的问题,如图 2 ...
  • 用C++编写的稀疏矩阵乘法运算,稀疏矩阵采用十字链表存储及计算

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,142
精华内容 456
关键字:

十字矩阵