单向链表创建过程

链表的创建过程要特判链表的首部位置，对这个位置的操作要做一些特别的处理。

1. 创建链表head节点

struct node *head = (struct node*)malloc(sizeof(struct node));
int x;
cin >> x;
head->data = x;
head->next = NULL;

主要完成对head节点的创建以及初始化 2. 创建后续节点

while(i < n){
	p = (struct node*)malloc(sizeof(struct node));
	cin >> x;
	p->data = x;
	p->next = NULL;
	if(head->next == NULL){
		head->next = p;
	}else{
		tail->next = p;	
	}
	tail = p;
	i++;
}

首先申请一片内存，操作这个内存里的node节点，初始化各个数据之后将节点插入到链表的尾部，这里需要判断是不是插入在head节点的后面，因为这个时候并没有更新tail节点为链表的尾部，所以要特判处理。最后更新tail节点为链表的尾部，计数变量自增，即可完成尾部节点的插入。 3. 返回创建的链表head节点的指针

return head;

操作

查找等基本操作相当简单，这里不再提。

插入

list insert(element x,int i,list PtrL){
	list p,s;
	if(i == 1){//特判表头情况
		申请内存
		s->data = x.data;
		s->next = Ptrl;
		return s;
	}
	p = 插入位点
	if(p = NULL) return NULL;
	else{
		分配内存
		s->data = x.data;
		s->next = p->next;
		p->next = s;
	}
}

删除

1. 找到删除节点的前一个节点，指针p指向这个节点
2. 将指针s指向需要被删除的节点
3. 将p->next修改为s->next
4. 释放s的空间 如果删除的是头节点，如果链表为空，返回一个空指针，否则返回头节点的下一个节点。

广义表

为了表示二元多项式，可以在一元多项式的基础上将data指向另外一个存储一元多项式的链表： 广义表是线性表的推广。

构建

#include <stdio.h>
typedef struct GNode *GList;
struct GNode{
	int tag;
	union{
		ElementType Data;
		GList Sublist;
	} URegion;
	GList Next;
};

多重链表

如果一个矩阵 中0元素非常多的话，称之为稀疏矩阵，如果用二维数组存的话会造成空间浪费。(反之，稠密的，例如这个稠密图[[2023.12.22-2023.12.29#^eae0c0]]) 这时候可以采取十字链表存储，每一个元素由其行列坐标及数值构成。

$$A=\left[\begin{array}{ccccc}18& 0& 0& 2& 0\\ 0& 27& 0& 0& 0\\ 0& 0& 0& -4& 0\\ 23& -1& 0& 0& 12\end{array}\right]$$

十字链表可以理解成为一个$n\times m$个链表的组合。 左上角的Term节点是这个十字链表的入口，存储多重链表的行列数以及非零节点数。 每个Term节点有两个指针，一个指向行，一个指向列，每个非0元素在其 行列上都被构造成循环链表。 将b，c图示结构利用union合并可以统一为a的形式存储。