线性表之单链表
线性表的链式存储结构
下面讨论线性表的链式存储结构，即链表。
单链表的结构：
将线性表L=（a0,a1,a2…,an-1）中各元素分布在不同存储器的不同存储块，称为结点，通过地址或指针 建立它们之间的联系，所得到的存储结构为链表结构。其中，节点的data域存放数据元素，而next域是一个指针，指向ai的直接后继ai+1所在的结点。于是结点和线性表的结构如下图：
单链表的基本运算
1.结点的描述：
代码实现：
typedef int datatype;
typedef struct node
{
datatype data;
struct node* next;
}listnode,*linklist;
2.头结点的创建
代码实现：
linklist Firstnode_create()
{
linklist H = NULL;
H = (linklist)malloc(sizeof(listnode));
if(H == NULL)
{
printf("malloc faild.");
return NULL;
}
H->data = 0;
H->next = NULL;
return H;
}
3.单链表的创建*
算法思路：依次读入结点中每一个元素ai(假设为int型)，若ai != 结束符（-1），则创建一个结点，然后插入表尾，最后返回链表的 头结点指针H。
代码实现：
linklist list_create()
{
linklist H=NULL;
linklist r=NULL;
int value;
H = (linklist)malloc(sizeof(listnode));
if(H == NULL)
{
printf("malloc faild.");
return NULL;
}
H->data = value;
H->next =NULL;
r = H;
linklist P=NULL;
while(1)
{
printf("input a number(-1 exit):");
scanf("%d",&value);
if(value == -1)
{
break;
}
P = (linklist)malloc(sizeof(listnode));
if(NULL == P)
{
printf("malloc failed.\n");
return H;
}
P->data = value;
P->next = NULL;
r->next = P;
r = P;
}
return H;
}
4.链表的遍历
算法思路：当遍历查找结点的指针域为NULL时结束遍历。
代码实现：
void list_show(linklist H)
{
while(H->next)
{
printf("%d\n",H->next->data);
H = H->next;
}
printf("\n");
}
5.链表的按序号查找
算法思路：从链表的a0起，判断是否为第pos结点，若是则返回该节点的指针，否则查找下一结点，以此类推。
代码实现：
linklist list_get(linklist H,int pos)
{
linklist P = H;
int i = -1;
if(pos < 0) //判断输入的位置是否合理
{
printf("position is invalid:<0\n");
return NULL;
}
while(P->next && i < pos)
{
P = P->next;
i++;
}
if(i==pos)
{
return P;
}
else
{
printf("position is invalid:>length\n");
return NULL;
}
}
6.链表的按值查找
算法思路：从链表的a0起，判断某结点是否等于value，若是则返回该节点的指针，否则查找下一结点，以此类推。
实现代码：
linklist list_get_value(linklist H,datatype value)
{
linklist P = H->next;
while(P && P->data!= value)
{
P = P->next;
}
return P;
}
7.链表的头插入算法
算法思路：
实现代码：
int list_head_insert(linklist H,datatype value)
{
linklist P = NULL;
P = (linklist)malloc(sizeof(listnode));
if(P == NULL)
{
printf("malloc failed\n");
return -1;
}
P->data = value;
P->next = H->next;
H->next = P;
return 0;
}
8.上面第三点链表的创建就是链表的尾插入，这里就不在累赘。
9.链表的按位置插入
算法思路：调用算法list_get(linklist H,int pos)，获取结点要插入的位置的ai的前驱a (i-1),然后申请一个结点，存入x,并将其插入P指向的结点之后。
代码实现：
int list_local_insert(linklist H,int pos,datatype value)
{
linklist p,q;
if(pos == 0)
{
p = H;
}
else
{
p = list_get(H,pos-1);
}
if(p == NULL)
{
printf("para is invalid\n");
return -1;
}
else
{
q = (linklist)malloc(sizeof(listnode));
if(q == NULL)
{
printf("malloc failed\n");
return -1;
}
q->data = value;
q->next = p->next;
p->next = q;
return 0;
}
}
10.链表的有序插入
算法思路：类似按位置插入算法，只是通过比较传入的value选择插入的位置。
代码实现：
int list_order_insert(linklist H,datatype value)
{
linklist p,q;
p = (linklist)malloc(sizeof(listnode));
if(p == NULL)
{
printf("malloc failed\n");
return -1;
}
p->data = value;
q = H;
while(q->next &&q->next->data < value)
{
q = q->next;
}
p->next = q->next;
q->next = p;
return 0;
}
11.链表结点的删除
算法思路：同插入法，先调用函数list_get(H,pos-1);获取ai的前驱ai-1，然后定义一个指针变量q指向要删除的ai结点，指针变量P指向那个ai的前驱，然后将ai结点删除即可。
代码实现：
int list_delete(linklist H,int pos)
{
linklist p,q;
if(pos == 0)
{
p = H;
}
else
{
p = list_get(H,pos-1);
}
if(p == NULL)
{
printf("para is failed\n");
return -1;
}
else
{
q = p->next;
p->next = q->next;
free(q);
q = NULL;
return 0;
}
}
12.单链表的倒置
算法思路：先把链表一分为二，依次为头结点和剩下的结点（剩下的结点用指针P指向），依次取P指向的链表中的各个结点，并将其作为新链表首结点插入H结点之后。
代码实现：
void list_reverse(linklist H)
{
linklist p,q;
p = H->next; //将头结点根剩下的结点一分为二
H->next = NULL;
while(p)
{
q = p; //把P赋值给q来操作
p = p->next; //依次往下取各个结点
q->next = H->next; //头插入法插入头结点
H->next = q;
}
}
13.链表的排序
算法思路：
代码实现：
void list_sort(linklist H)
{
linklist p,q,r;
p = H->next;
H->next = NULL;
while(p)
{
q = p;
p = p->next;
r = H;
while(r->next && r->next->data < q->data)
{
r = r->next;
}
q->next = r->next;
r->next = q;
}
}
上一篇： 一个找最接近值有关问题，请高手给个思路
下一篇： 单链表的增删改查