带头节点的链表

链表的基本操作

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef int type;
typedef struct Node
{
    type info;
    struct  Node *next;
}node;
//建立一个头节点并将其指针返回
node *node_init()
{
    node *head=(node*)malloc(sizeof(node));
    head->next=NULL;
    return head;
}
//打印一个链表
void node_display(node*head)
{
    node*p=head->next;
    if(!p){
        printf("EMPTY
");
    }
    else{
        while(p){
            printf("%5d",p->info);
            p=p->next;
        }
        printf("
");
    }
}
//找到第n个节点并返回其指针，若n==0则返回头节点指针
node* node_find(node*head,int n)
{
    int i=0;
    node *p=head;
    if(n<0){
        printf("not
");
        return NULL;
    }
    else if(n==0){//第零个位置的节点：头节点
        return head;
    }
    while(p&&i<n){//找到第i个节点的地址
        p=p->next;
        i++;
    }
    if(!p)printf("not
");
    return p;
}
//在pos个节点的位置插入一个值为num的节点
void node_insert(node*head,int pos,type num)
{
    node*pre=node_find(head,pos-1),*q;//找到前驱节点
    if(!pre){
        printf("not
");
    }
    else{
        q=(node*)malloc(sizeof(node));
        q->info=num;
        q->next=pre->next;
        pre->next=q;
    }
}
//删除第pos个节点
void node_dele(node*head,int pos)
{
    node*pre=node_find(head,pos-1),*q;
    if(!pre){
        printf("not
");
    }
    else{
        q=pre->next;
        pre->next=q->next;
        free(q);
    }
}
//删除整个链表并释放内存
void node_destory(node*head)
{
    node*p=head,*q;
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
}

课后习题部分

//返回第i个节点的值
type node_get(node*head,int i)
{
    node*p=node_find(head,i);
    if(!p){
        printf("not
");
        exit(1);
    }
    return p->info;
}
//返回值为x的节点的位置是第几个节点
int node_Get(node*head,type x)
{
    int i=1;
    node*pre=head,*p=head->next;
    while(pre&&p&&p->info!=x){
        pre=p;
        p=p->next;
        i++;
    }
    if(p)return i;
    else return -1;
}
//返回值为x的节点的指针
node*node_Find(node*head,type x)
{
    node*pre=head,*p=head->next;
    while(pre&&p&&p->info!=x){
        pre=p;
        p=p->next;
    }
    if(p){
        return p;
    }
    else{
        printf("not
");
        return NULL;
    }
}
//把p2链表连接的p1后面
void node_cat(node*p1,node*p2)
{
    node*p=p1;
    while(p->next){
        p=p->next;
    }
    p->next=p2->next;
    free(p2);
}
//把p2链表插入到p1节点的第n个节点的位置
void node_Insert(node*p1,int n,node*p2)
{
    node*pre=node_find(p1,n-1),*p=p2;
    if(!pre){
        printf("node_Insert error
");
    }
    else{
        while(p->next){
            p=p->next;
        }
        p->next=pre->next;
        pre->next=p2->next;
        free(p2);
    }
}
//删除p1，节点的从begin开始的n个节点
void node_Del(node*p1,int begin,int n)
{
    int i;
    for(i=1;i<=n;i++)
        node_dele(p1,begin);
}
//返回节点的和
int node_sum(node*head)
{
    node*p=head->next;
    int sum=0;
    while(p){
        sum+=p->info;
        p=p->next;
    }
    return sum;
}
//创建链表，当输入的值为负数结束
void node_create(node*head)
{
    node*p=head,*pre;
    while(1){
        pre=(node*)malloc(sizeof(node));
        pre->next=NULL;
        scanf("%d",&pre->info);
        if(pre->info<0){
            free(pre);
            break;
        }
        else{
            p->next=pre;
            p=pre;
        }
    }
}
//计算链表节点数
int node_count(node*head)
{
    int i=0;
    node*p=head->next;
    while(p){
        p=p->next;
        i++;
    }
    return i;
}
//在值为y的节点前面插入x
void node_insert_xy(node *head,type x,type y)
{
    node*p=head,*pre=p->next,*q;
    while(pre&&pre->info!=y){
        p=pre;
        pre=pre->next;
    }
    if(pre&&pre->info==y){
        q=(node*)malloc(sizeof(node));
        q->next=NULL;
        q->info=x;
        q->next=pre;
        p->next=q;
    }
    else printf("error
");
}
//倒置链表
void node_reverse(node*head)
{
    node*pre=NULL,*mid=head->next,*next;
    while(mid){
        next=mid->next;
        mid->next=pre;
        pre=mid;
        mid=next;
    }
    head->next=pre;
}
//将链表的偶数部分保留，奇数部分赋给另外一个链表，并返回其头指针
node *node_divide(node*head1)
{
    node*head2=(node*)malloc(sizeof(node));
    node *p2=head2,*p=head1,*pre=p->next;
    while(pre){
        if(pre->info%2!=0){
            p->next=pre->next;
            p2->next=pre;
            p2=pre;
        }
        else
        p=pre;
        pre=pre->next;
    }
    p2->next=NULL;
    p->next=NULL;
    return head2;
}
//删除链表中大约x不大于y的节点
void node_dele_XtoY(node*head,int x,int y)
{
    node*p=head,*pre=p->next,*pmid;
    while(pre){
        pmid=pre->next;
        if(pre->info>x&&pre->info<=y){
            p->next=pre->next;
            free(pre);
        }
        else p=p->next;
        pre=pmid;
    }
}