链表的实用操作函数
单向链表的操作
/*链表节点声明*/
typedef struct listnode *listpointer;
struct listnode {
int date;
// element else
listpointer link;
}listnode;
1/ 反转 invert
listpointer invert ( listpointer lead)
{ /* invert the list pointed to by Lead * /
listPointer middle, trail;
middle = NULL;
white (Iead) {
trail = middle;
middle = lead;
Iead = lead->link;
middle->link = trail;
}
return middle;
}
2/连接 concatenate
/* produce a new list that contains the list ptr1 followed by the
Iist ptr2. The list pointed to by ptr1 was changed permanently */
listpointer concatenate(listpointer ptr1, listpointer ptr2)
{
Iistpointer temp ;
/* check for empty lists */
if ( !ptr1) return ptr2 ;
if (!ptr2) return ptr1 ;
/* neither list is empty, find end of first list */
for (temp=ptr1; temp->Iink; temp=lemp->Iink) ;
/* link end of first list to start of second */
temp->link = ptr2;
}
循环链表的操作
1/ 循环链表表头插入
last指向表尾,而不指向表头。这样设置链表指针可以方便地在表头、表尾插入结点。如杲设置指向表头的指针,那么在表头前插入结点效率极低,我们必须从头遍历整个链表,直 到指针移到表尾,然 后才能在表头前插入。
下面的代码在循环链表表头插入结点。
/* insert node at the front of the circular list whose last node is
last * /
void insertFront (listPointer *last, listPointer node)
{
/* list is empty, change Last to point to new entry */
if (!(*Iast)) {
*last = node;
node->Iink = node;
}
else {
/* list is not empty, add new entry at front */
node->Iink = (*last) ->link;
(*last) ->link = node;
}
}
2/ 循环链表表尾插入
/* insert node at the end of the circular list whose last node is
last * /
void insertend (listPointer *last, listPointer node)
{
/* list is empty, change Last to point to new entry */
if (!(*Iast)) {
*last = node;
node->Iink = node;
}
else {
/* list is not empty, add new entry at end */
node->Iink = (*last) ->link;
(*last) ->link = node;
(*last) = node;
}
}
3/ 循环链表的长度
int length (listpointer last )
{ /* find the length of the circular list last */
listpointer temp;
int count = 0;
if (last) {
temp = Iast;
do{
count++;
temp = temp->link;
}while (temp!=last);
}
return count;
}
双向链表的操作
双向链表的结点至少有三个域,数据域 data,左链域 llink,右链域 rlink,结点声明 如下:
typedef struct node *nodepointer;
struct node {
element data;
nodepointer llink;
nodepointer rlink;
};
注: 双向链表也可以设成循环表，包括一个空表头。
1. 插入
函数 dinsert完成插入操作,node足 表中纣i点,可 以足头结点,也可以楚内点,newnode是待插入结点。
void dinsert (nodepointer node, nodepointer newnode)
{ /* insert newnode to the right of node */
newnode->Ilink = node;
newnode ->rIink = node ->rlink ;
node->rlink->llink = newnode;
node->rlink = newnode;
}
2.删除
void ddelete (nodePointer head, nodePointer deleted)
{ /*delete the node of 'deleted' with the first null_node of head*/
if (node==deleted)
printf ("Delete the only node of head is not permites");
else {
deleted->llink->rIink = deleted->rIink;
deleted->rIink->llink = deleted->IIink;
free (deleted) ;
}
}
