链表笔记

//链表的一些简单操作

#include <stdio.h>

#include <malloc.h>

struct List {

    int    data;    //数据

    struct List *next; //指向下一个结点

};

//建立n个结点的后进先出单向链表

struct List * createList(int n);

//链表的遍历

void showList(struct List * head);

//在链尾加一个结点

void insertList(struct List * head,int data);

//删除链的一个结点

int deleteList(struct List * head,int data);

//释放链表

void freeList(struct List * head);

int main(void)

{

    //建立链表

    struct List *head=createList(9);

    showList(head);           //遍历链表

    insertList(head,0);       //在链尾加一个结点

    deleteList(head,4);       //删除链的一个结点

    freeList(head);           //释放链表

    return 0;

}

//功    能：建立n个结点的后进先出单向链表

//入口参数：项数n

//返 回 值：指向链表哨兵结点的指针

struct List * createList(int n)

{

    struct List *head,*node;

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

    //头结点(哨兵)的数据域为空！

    head->next=NULL;

    for (int i=0;i<n;i++) {

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

        node->data=i+1;

        node->next=head->next;

        head->next=node;

    }

    return head;

}

//功    能：链表的遍历

//入口参数：head指向链表哨兵结点的指针

void showList(struct List * head)

{

    struct List *h;

    h=(struct List*)malloc(sizeof(struct List));

    h=head->next;

    while(h!=NULL){

        printf("%d ",h->data);

        h=h->next;    

    }

}

//功    能：在链尾加一个结点

//入口参数：head指向链表哨兵结点的指针

//          data待插入结点的数据值

void insertList(struct List * head,int data)

{

    struct List *p,*newNode;

    newNode=(struct List*)malloc(sizeof(struct List));

    newNode->data=data;

    for(p=head;p->next!=NULL;p=p->next);  // 链表遍历惯用    

        p->next=newNode;

    newNode->next=NULL; 

}

//功    能：删除链的一个结点

//入口参数：head指向链表哨兵结点的指针

//          data待删除结点的数据值

//返 回 值：1成功删除，0结点不存在

int deleteList(struct List * head,int data)

{

    struct List *pre,*p;

    for(p=head->next;p->data!=data&&p->next!=NULL;p=p->next)

        pre=p;

    if(p->data!=data)return 0;

    else{

        pre->next=p->next;

    }

    return 1;

}

//功    能：释放链表

//入口参数：head指向链表哨兵结点的指针

void freeList(struct List * head)

{

    struct List *temp;

    for(struct List *p=head;p!=NULL;p=temp){

        temp=p->next;

        free(p);

    }

}