//
//  MyList.h
//  List
//  editor:DRAGON
//  Created by 5016 on 13-11-25.
//  Copyright (c) 2013年 dradon. All rights reserved.
//

#ifndef List_MyList_h
#define List_MyList_h

//声明结构体
typedef struct Node{
    char data;//数据域
    struct Node *next;//指针域
}*List;

/***********函数声明*************/
//创建头结点
List creatHead();
//在链表后插入结点
int insertNodeInBack(List head,char data);
//在链表任意位置插入结点
int insertNode(List head,char data,int position);
//删除任意位置上的某个数据的结点
int deleteNode(List head,char data);
//修改某个结点上的数据
int alterValue(List head,char newdata,char olddata);
//查询某个结点的值,返回结点
int queryData(List head,char data);
//倒置链表
void daozhi(List head);
//打印链表
void displayList(List head);


#endif

//
//  MyList.c
//  List
//  editor:DRAGON
//  Created by 5016 on 13-11-25.
//  Copyright (c) 2013年 dradon. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include "MyList.h"


/*
 *函数名:creatHead
 *返回值:head ----- List 头结点
 *参数:无
 *功能:创建头结点
 */
List creatHead()
{
    List head = (List)malloc(sizeof(List));
    head->data = '\0';
    head->next = NULL;
    
    return head;
}

/*
 *函数名:insertNodeInBack
 *返回值:0 ----- int 成功
 *      1 ----- int 失败
 *参数:q ----- List 头结点
 *    data -----char 数据
 *功能:在链表后插入结点
 */
int insertNodeInBack(List q,char data)
{
    List p;
    while (data != '!') {
        //1.开辟p结点
        p = (List)malloc(sizeof(List));
        p->data = data;
        p->next = NULL;
        //2.连接p结点
        q->next = p;
        q = p;
        //继续输入
        scanf("%c",&data);
        getchar();
    }
    return 0;
}

/*
 *函数名:insertNode
 *返回值:0 ----- int 成功
 *      1 ----- int 失败
 *参数:head ----- List 头结点
 *    data ----- char 数据
 *    position --- int 位置
 *功能:在链表任意位置插入结点
 */
int insertNode(List head,char data,int position)
{
    List q,p;
    int n = 0;
    
    q = head;
    n = 1;
    
    //1.先找到插入数据所在的位置
    while (n != position && q->next != NULL) {
        q = q->next;//移动指针
        n++;//移动位置
    }
    
    //2.健壮性判断
    if(n < position){//超出长度
        printf("找不到插入的位置");
        return 1;
    }else{//n=position,不肯能出现n>position,while控制了
        //开辟新结点空间,并赋值
        p = (List)malloc(sizeof(List));
        p->data = data;
        //连接新结点
        p->next = q->next;
        q->next = p;
    }
    
    return 0;
}

/*
 *函数名:deleteNode
 *返回值:0 ----- int 成功
 *      1 ----- int 失败
 *参数:head ----- List 头结点
 *    data ----- char 删除的数据
 *功能:删除任意位置上的某个数据的结点
 */
int deleteNode(List head,char data)
{
    List q,p;
    
    //q指向首结点,p指向头结点
    q = head->next;
    p = head;
    
    //先遍历不要删除的数据
    while (q != NULL && q->data != data) {
        p = q;
        q = q->next; //p 和 q交替移动
    }
    
    if(q == NULL){
        printf("找不到删除的数据");
        return 1;
    }else{
        p->next = q->next;//删除数据
        //省略释放结点内存
        return 0;
    }
}

/*
 *函数名:alterValue
 *返回值:0 ----- int 成功
 *      1 ----- int 失败
 *参数:head ----- List 头结点
 *  newdata ----- char 新数据
 *    olddata ----- char 位置
 *功能:修改某个结点上的数据
 */
int alterValue(List head,char newdata,char olddata)
{
    List q,p;
    
    //q指向首结点,p指向头结点
    q = head->next;
    p = head;
    
    //先遍找到修改的数据
    while (q != NULL && q->data != olddata) {
        p = q;
        q = q->next; //p 和 q交替移动
    }
    
    if(q == NULL){
        printf("找不到修改的数据");
        return 1;
    }else{
        //修改数据
        p->next->data = newdata;
        return 0;
    }
}

/*
 *函数名:queryData
 *返回值:position ----- int 位置
 *参数:head ----- List 头结点
 *     data ----- char 查询的数据
 *功能:查询某个结点的值,返回位置
 */
int queryData(List head,char data)
{
    int position = 0;
    int n = 0;
    
    List q = head->next;//指向首结点
    n = 1;//从首结点开始计算
    
    while (q->next != NULL) {
        if (q->data == data) {
            position = n;//查询到数据
        }
        q = q->next;//移动指针
        n++;//计算位置
    }
    
    if (position == 0) {
        printf("找不到改数据");
        return 0;
    }
    
    return position;
}

//倒置链表
/*
 *函数名:queryData
 *返回值:void
 *参数:head ----- List 头结点
 *功能:倒置链表
 */
void daozhi(List head)
{
    List p,q,r;
    
	q=head->next; // 0|null->e|next->e|next->e|next->e|next->e|next->e|next->e|next->null
    p=q->next;	  
    r=p->next;    
    q->next=NULL;
    
    while(r!=NULL)
    {
        p->next=q;
        q=p;
        p=r;
        if(r->next!=NULL)    
            r=r->next;
        else
            break;
    }
    r->next=q;
    head->next=r;        
}

/*
 *函数名:displayList
 *返回值:void
 *参数:head ----- List 头结点
 *功能:打印链表
 */
void displayList(List head)
{
    List q;
    q = head;
    
    printf("null(head)--->");
    while (q->next != NULL) {
        printf("%c--->",q->next->data);
        q = q->next;
    }
    printf("null(last)");
	printf("\n");
}

//
//  main.c
//  List
//  editor:DRAGON
//  Created by 5016 on 13-11-25.
//  Copyright (c) 2013年 dradon. All rights reserved.
//

#include <stdio.h>
#include "MyList.h"

//主函数
int main(int argc, const char * argv[])
{
    char data;
    List head;
    //新建头结点
    head = creatHead();
    
    printf("请输入一个字符:\n");
    scanf("%c",&data);
    getchar();
    
    insertNodeInBack(head, data);//从链表后插入
    displayList(head);//打印链表
    
    int pos = queryData(head,'f');//查询数据所在位置
    printf("数据所在的位置是:%d\n",pos);
    
    insertNode(head,'g',3);//任意位置插入
    displayList(head);//打印链表

    deleteNode(head,'f');
    displayList(head);//打印链表
    
    alterValue(head,'z','g');//修改数据
    displayList(head);//打印链表
    
    daozhi(head);//倒置链表
    displayList(head);//打印链表
    return 0;
}