单向链表的操作

/*链表节点声明*/

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) ;

  }

}