数据结构mooc课小结（2.1）

这节课讲的是线性表。

两种实现方法：数组、链表。

针对主要的操作：查找指定元素值，获取指定位置的元素，删除，插入，获得长度。

以表示多项式为例，需要保存系数和指数。

用数组下标表示指数，合并同类项的时候，找同类项就比较方便，去下标就好了。

但是空间浪费的问题严重，如果指数的跨度比较大，那么大部分元素都是0。

而且灵活性不足，不能表示负指数。

链表则相反，灵活性有了，但是查找同类项的时候，需要遍历。空间浪费也是有的，毕竟指针也需要空间，但能面对指数跨度大的情况。

数组的插入删除需要移动大量元素。获取指定位置的元素特别快。

链表优势在于插入删除只需要调整指针就好了。

查找指定元素值都差不多，需要遍历才能找到。当然数组的遍历会快一点，毕竟不需要通过指针的间接访问。

接下来介绍了链表的一些变种实现，用于不同需求。

例如带头节点的单链表（简化链表操作的代码），双向链表， 十字链表（表示稀疏矩阵），广义表(表示多元多项式)，链表的数组（哈希表处理冲突）。

个人感觉这些都是不错的编程练习。

用十字链表实现稀疏矩阵的乘法，加法。

单链表实现一元多项式的乘法加法。

广义表实现多元多项式的四则运算，按某元的降幂输出

struct node
{
	int i;
	node* next;
	node( int d=0): i(d), next(NULL){
	}
};

struct list
{
	node* head, **tail;
	list():head(NULL), tail(&head){};
	
	void push( int i)
	{
		node * tmp = new node(i);
		*tail = tmp;
		tail = &(tmp->next);
	}
	void push( node* p)
	{
		if (p == NULL) return;
		*tail = p;
		//p->next = NULL;
		tail = &(p->next);
	}
	node* pop()
	{
		node *ret = head;
		head = head->next;
		if ( head == NULL) //最后一个也被弹走，空了 
		{
			tail = &head; 
		}
		return ret;	
	}
	
	list merge( list &b)
	{
		list ret;
		node* tmp;
		while (head != NULL && b.head!=NULL)
		{
			if ( head->i < b.head->i)
				tmp = pop();
			else
				tmp = b.pop();
			tmp->next = NULL;
			ret.push( tmp );
		}
		if ( head == NULL)
		{
			ret.push(b.head);
		}
		else
		{
			ret.push(head);
		}
		return ret;
	}
};