[牛人杂谈] 单链表

/* 1.C语言单向链表  

 * 2.链表的(增,删,查,遍历)  

 * Author: Mr.Long  



 */ 





#include "stdafx.h"

#include<stdlib.h> 





/* 结构定义 */  

struct node {  

    int data;  

    node *next;  

};  





/* 函数定义 */  

void printNode(struct node *head);  

struct node* appendNode(struct node *head,int);  

struct node* addFirstNode(struct node *head,int);  

struct node* findNode(struct node *head,int);  

int deletNode(struct node *head,int);





int main(int argc, char* argv[])

{

  /* 定义一个head指针,作为链表的头节点*/  

    struct node *head = NULL;  

    //申请内存空间   

    head = (struct node *)malloc(sizeof(struct node));  

    //初始化头结点数据   

    head->data = 0;  

    head->next = NULL;  

  

    printf("*****************添加节点******************\r\n");  

    /* 在链表尾部追加节点 */  

    head = appendNode(head,5);  

    head = appendNode(head,8);  

    head = appendNode(head,4);  

    head = appendNode(head,34);  

    head = appendNode(head,6);  

    head = appendNode(head,9);  

  

    /* 添加为头节点 */  

    head = addFirstNode(head,12);  

    head = addFirstNode(head,61);  

  

    printf("添加成功... \n");  

      

    printf("*****************查找节点******************\r\n");  

    /* 查找指定节点 */  

    struct node *a;  

    a = findNode(head,34);  

    if(a != NULL) {  

        printf("查找成功... \n");  

        printf("data:%d \n",a->data);  

        printf("next:0x%X \n",a->next);  

    } else {  

        printf("没找到该节点 \n");  

    }  

    printf("*****************删除节点******************\r\n");  

    /* 删除指定节点 成功返回1 失败返回0 */  

    int dest = 0;  

    bool state = deletNode(head,dest);  

    if(state)  

        printf("删除[%d]成功... \n",dest);  

    else  

        printf("删除[%d]失败... \n",dest);  

  

    printf("*****************所有节点******************\r\n");  

      

    /* 遍历节点并输出 */  

    printNode(head);  

  

    return 0;  

}





int deletNode(struct node *head,int dest) {  

    struct node *p = head;  

    struct node *lp;  

    while(p->next) {  

        if(p->data == dest) {  

            // 删除操作:将上一个节点的next指向被删除节点的next   

            lp->next = p->next;  

            //释放被删除节点的内存空间  

            free(p);  

            return true;  

        }  

        //记录上一个节点  

        lp = p;  

        //移动指针  

        p = p->next;  

    }  

    return false;  

}  

struct node* findNode(struct node *head,int dest) {  

    struct node *p = head;  

    struct node *pc = NULL;//临时变量  

       

    while(p) { //当p不为NULL时   

      

        if(p->data == dest) {//找到了指定节点   

            pc = p;  

            break;  

        }  

        p = p->next; //移动指针   

    }  

    return pc;  

}  

struct node* appendNode(struct node *head,int data) {  

    if(data == NULL) return head;  

    if(head == NULL) { //若头结点为空,则创建一个节点作为头结点   

        printf("head is NULL \n");  

        head = (struct node *)malloc(sizeof(struct node));  

        head->data = data;  

        head->next = NULL;  

        return head;  

    }  

    /*易错点 

     *  这里千万注意循环条件是p->next而不是p 

     *  因为当执行到链表尾节点时p已经为NULL 

     *  而当p为NULL时56行的空指针操作会导致程序崩溃 

     */  

    struct node *p = head;  

    while(p->next) {  

        p = p->next;  

    }  

    struct node *pNew;  

    pNew = (struct node *)malloc(sizeof(struct node));  

    pNew->data = data;  

    pNew->next = NULL;  

  

    p->next = pNew;  

    /*易错点: 

     *  如果这里返回 p 则链表只保留了最后两项数据 

     *  原因在于47行的while循环移动了p的指针 

     */  

    return head;  

}  

struct node* addFirstNode(struct node *head,int data) {  

    struct node *p;  

    p = (struct node *)malloc(sizeof(struct node));  

    p->data = data;  

    p->next = head;  

    return p;  

}  

void printNode(struct node *head) {  

    struct node *p = head;  

    while(p) { /* 当p不为NUll时 */  

        printf("self=0x%X  |  data=%2d  |  next=0x%X\n",p,p->data,p->next);  

        p = p->next;  

    }