不带头结点单链表题

1.编写函数linklist dex(linklist head, datatype x),删除不带头结点单链表head中的第一个值为x的结点。

思路：对链表head进行循环遍历，若找到含有x的结点，直接删除。

linklist dex(linklist head, datatype x){
        linklist p = head;
        linklist pre = NULL;
        while(p && p->info!=x){  //查找第一个x的位置
            pre=p;
            p=p->next;
        }
        if(p){    //找到位置，进行删除
            if(pre==NULL){ //如果是第一个单独处理
                head=p->next;
            }else{
            	pre->next=p->next;
        	}
            free(p);
        } 	
        return head;
}

2.假设线性表(a1,a2,a3,...,an)采用不带头结点的单链表存储，请设计算法函数linklist reverse1(linklist head), 和void reverse2(linklist *head)将不带头结点的单链表head倒置，是变成(an,an-1,...,1)。

思路：将链表的值放在一个顺序表里，在顺序表里进行逆置，然后在依次赋值到链表中。

思路2：直接利用头插法，在建立新的链表的基础上，将原链表的值赋值到上面。

答案思路：利用头插法，将原有的链表赋值到新的链表上，然后在原来的head上使用头插法。

//带头结点
linklist reverse1(linklist head){
    linklist p=head->next;
    linklist nhead = (linklist)malloc(sizeof(node)); //新链表的头结点
    nhead->next=NULL;
    while(p){   //采用头插法建立逆置链表
        linklist s= (linklist)malloc(sizeof(node));
        s->next=nhead->next;
        s->info=p->info;
        nhead->next=s;
        p=p->next;
    }
    return nhead;
}

//不带头结点
void reverse2(linklist *head){
    linklist p = head;
    linklist nhead = *head; //对第一个节点单独处理
    nhead->next=NULL;
    p=p->next;
    while(p){ //从第二个节点开始处理
        linklist s= (linklist)malloc(sizeof(node));
        s->next=nhead;
        s->info=p->info;
        nhead=s;
        p=p->next;
    }
    *head=nhead; //将以逆置的值赋给原来的head
}

参考答案代码：

linklist reverse1(linklist head){
    linklist s,p=head;
    head=NULL;
    while(p){   //采用头插法建立逆置链表
        s=p;
        s->next=head;
        head=s;
        p=p->next;
    }
    return head;
}


void reverse2(linklist *head){
    linklist s,p = *head;
    *head=NULL;
    while(p){ 
        s=p;
        s->next=*head;
        *head=s;
        p=p->next;
    }
}

3.假设不带头结点的单链表head是升序排列的，设计算法函数算法函数linklist insert(linklist head, datatype x)，将值为x的节点插入到链表head中，并保持链表的有序性。分别构造插入的表头，表中，表尾3中情况。

思路：先遍历找到x的位置，即大于x的地方，然后再进行插入。

linklist insert(linklist head,datatype x){
    linklist pre,p=head;
    while(p && p->info < x){
        pre=p;
        p=p->next;
    }
    linklist s = (linklist)malloc(sizeof(node));
    s->info=x;
    if(pre==NULL){ //头插入
        s->next=head;
        head=s;
    }else{  //中间和尾插入
        s->next=p; //这里要从p的前面插入，因为x小于p
        pre->next=s;
    }
    return head;
}

4.编写算法函数linklist delallx(linklist head, int x)，删除不带头节点单链表head中所有值为x的结点。

思路：遍历链表，若发现结点信息是x，则直接让其前驱结点指向下下个节点。

linklist delallx(linklist head, int x){
    linklist p=head;
    if(p->info==x){
        head=head->next;
        free(p);
    }else{
        while(p &&　p->info != x){
            if(p->info=x){
                pre=p->next;
                free(p);
                p=pre->next;
            }else{
                pre=p;
            	p=p->next;
            }
        }
    }
    return head;
}

参考书代码：

linklist delallx(linklist head, int x){
    linklist p,pre;
    p=head;
    pre=NULL;
    while(p){
        while(p && p->info != x){
            pre=p;
            p=p->next;
        }
       if(p){ //如果p不为空。空表示表中无x
            if(pre==NULL){ //头位置是x
            	head=p->next;
            	free(p);
            	p=head;
        	}else{ //其他位置是x
            	pre->next=p->next;
            	free(p);
            	p=pre->nxet;
        	}
       }
    } 
    return head;
}