单非循环链表

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

#define NAMELEN 32
#define    ADDRLEN 128

/*单链表的虚拟实现*/
typedef struct lnode
{
    char name[NAMELEN];
    char addr[ADDRLEN];
    char sex;
    float score;
    int id;
    struct lnode * next;
}NODE;

typedef NODE * NodePtr;

int Initlist(NodePtr * headptr);
int CreatNode(NodePtr * nodeptr, char * name, char * addr, char sex, float score, int id);
int Lenlist(NodePtr headptr);
int GetNode(NodePtr headptr, int num, NodePtr * nodeptr);
int AddNode(NodePtr headptr, NodePtr nodeptr);
int PrintAllNode(NodePtr headptr);
int InsertNode(NodePtr headptr, int num, NodePtr nodeptr);
int DeleteNode(NodePtr headptr, int num);
int UnionList(NodePtr headptr1, NodePtr headptr2);
int SortNode(NodePtr headptr);
int SortNode2(NodePtr headptr);

int main(int argc, char ** argv)
{
    printf("*********单向非循环链表的操作********\n");

    NodePtr headptr = NULL;
    Initlist(&headptr); /*需传指针的地址，才能改变指针变量的值*/

    NodePtr nodeptr = NULL;
    CreatNode(&nodeptr, "wxc", "hb", 'm', 100.00, 1);
    AddNode(headptr, nodeptr);
    CreatNode(&nodeptr, "zqp", "hb", 'w', 100.00, 2);
    AddNode(headptr, nodeptr);
    CreatNode(&nodeptr, "程序员", "上海", 'm', 100.00, 3);
    AddNode(headptr, nodeptr);
    CreatNode(&nodeptr, "wolp", "上海", 'w', 100.00, 4);
    AddNode(headptr, nodeptr);
    CreatNode(&nodeptr, "wxc", "上海", 'm', 99.00, 6);
    AddNode(headptr, nodeptr);
    PrintAllNode(headptr);

    NodePtr getnodeptr = NULL;
    int num = 3;
    GetNode(headptr, num, &getnodeptr);
    printf("*************取得第[%d]个元素如下：************\n", num);
    printf(" id   =[%d]\n name =[%s]\n addr =[%s]\n sex  =[%c]\n score=[%.2f]\n", getnodeptr->id, getnodeptr->name, getnodeptr->addr, getnodeptr->sex, getnodeptr->score);

    CreatNode(&nodeptr, "wo", "上海", 'm', 98.00, 5);
    num = 6;
    InsertNode(headptr, num, nodeptr);
    /*
    num = 4;
    DeleteNode(headptr, num);
    */
    PrintAllNode(headptr);

    NodePtr headptr2 = NULL;
    Initlist(&headptr2); /*需传指针的地址，才能改变指针变量的值*/

    NodePtr nodeptr2 = NULL;
    CreatNode(&nodeptr2, "wxc", "hb", 'm', 98.00, 13);
    AddNode(headptr2, nodeptr2);
    CreatNode(&nodeptr2, "zqp", "hb", 'w', 99.00, 12);
    AddNode(headptr2, nodeptr2);
    CreatNode(&nodeptr2, "程序员", "上海", 'm', 100.00, 11);
    AddNode(headptr2, nodeptr2);

    UnionList(headptr, headptr2);
    PrintAllNode(headptr);

    SortNode(headptr);
    PrintAllNode(headptr);

    SortNode2(headptr);
    PrintAllNode(headptr);
    printf("链表长度=[%d]\n", Lenlist(headptr));

    return 0;
}

/*
单链表面试题：
写一个函数将一个链表逆序.
单链表,不知道长度,写一个函数快速找到中间节点的位置.
写一个函数找出一个单向链表的倒数第n个节点的指针
*/

/*功能：初始化单链表:（带头结点的）初始时链表为空*/
int Initlist(NodePtr * headptr)
{
    printf("初始化链表......\n");
    *headptr = (NodePtr)malloc(sizeof(NODE)); /*头结点*/
    (*headptr)->next = NULL;
    return 0;
}

/*创建一个节点*/
int CreatNode(NodePtr * nodeptr, char * name, char * addr, char sex, float score, int id)
{
    *nodeptr = (NodePtr)malloc(sizeof(NODE));
    memset((*nodeptr)->name, 0, sizeof(char)*NAMELEN);
    strcpy((*nodeptr)->name, name);
    memset((*nodeptr)->addr, 0, sizeof(char)*ADDRLEN);
    strcpy((*nodeptr)->addr, addr);
    (*nodeptr)->sex = sex;
    (*nodeptr)->score = score;
    (*nodeptr)->id = id;
    (*nodeptr)->next = NULL;
    return 0;
}

/*功能：求单链表的长度,参数node：头结点指针*/
int Lenlist(NodePtr headptr)
{
    int len = 0;
    NodePtr p = NULL;
    p = headptr->next;
    while(p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

/*功能：求单链表中的第num个元素的节点指针*/
int GetNode(NodePtr headptr, int num, NodePtr * nodeptr)
{
    NodePtr p = NULL;
    int count = 1;
    if(num < 0)
    {
        printf("num值不可小于0！\n");
        return -1;
    }
    if(num == 0)
    {
        *nodeptr = headptr;
        return 0;
    }
    p = headptr->next;
    while((p != NULL)&&(count < num))
    {
        p = p->next;
        count++;
    }
    if((p == NULL)||(count < num)) /*第num个元素不存在*/
    {
        printf("count = [%d]\n", count);
        printf("第[%d]个元素不存在！\n", num);
        return -1;
    }
    else if((p != NULL)&&(count == num)) /*第num个元素存在*/
        {
            *nodeptr = p;
            return 0;
        }
}

/*功能：在单链表尾插入一个元素*/
int AddNode(NodePtr headptr, NodePtr nodeptr)
{
    printf("在链尾增加一个元素！\n");
    NodePtr p = NULL;

    p = headptr;
    while(p->next != NULL) /*p指向最后一个节点元素了*/
    {
        p = p->next;
    }
    p->next = nodeptr;
    return 0;
}

/*功能：打印出单链表中所有节点元素的信息*/
int PrintAllNode(NodePtr headptr)
{
    NodePtr p = NULL;
    p = headptr->next;
    printf("链表长度=[%d]\n", Lenlist(headptr));
    printf("显示链表的所有内容如下：\n");
    printf("*************************************************************************\n");
    printf("id        name        addr        sex        score\n");
    while(p != NULL)
    {
        printf("[%d]        [%s]    [%s]        [%c]        [%.2f]\n", p->id, p->name, p->addr, p->sex, p->score);
        p = p->next;
    }
    return 0;
}

/*功能：在单链表的第num个元素之前插入一个元素（先找到第num-1个元素）*/
int InsertNode(NodePtr headptr, int num, NodePtr nodeptr)
{
    int count = 1;
    NodePtr p = NULL;
    p = headptr->next;
    while((p != NULL)&&(count < num-1)) /*p会指向第num-1个元素*/
    {
        count++;
        p = p->next;
    }
    if((p != NULL)&&(num-1 == 0))/*在第1个元素之前插入新的元素*/
    {
        nodeptr->next = headptr->next;
        headptr->next = nodeptr;
        return 0;
    }
    else if((p == NULL)||(count > num-1)) /*第num-1个元素不存在*/
    {
        printf("第[%d]个元素不存在！\n", num-1);
        return -1;
    }
    else if((p != NULL)&&(count == num-1)) /*p指向第num-1个元素*/
    {
        nodeptr->next = p->next;
        p->next = nodeptr;
        return 0;
    }

    return 0;
}

/*功能：删除单链表中的第num个元素*/
int DeleteNode(NodePtr headptr, int num)
{
    NodePtr p = NULL;
    NodePtr q = NULL;
    int count = 1;

    p=headptr->next;
    while((p != NULL)&&(count < num-1)) /*p会指向第num-1个元素*/
    {
        count++;
        p = p->next;
    }
    if((p != NULL)&&(num-1 == 0))/*要删除的是第1个元素*/
    {
        q = headptr->next;
        headptr->next = headptr->next->next;
        free(q); /*删除的节点要释放*/
        return 0;
    }
    else if((p == NULL)||(count > num-1)) /*第num-1个元素不存在*/
    {
        printf("第[%d]个元素不存在！\n", num-1);
        return -1;
    }
    else if((p != NULL)&&(count == num-1)) /*p指向第num-1个元素*/
    {
        q = p->next;
        p->next = q->next;
        free(q); /*删除的节点要释放*/
        return 0;
    }

    return 0;
}

/*功能：按照数据域中某个数据成员的值(id)对单链表的元素进行递增排序*/
int SortNode(NodePtr headptr)
{
    int i, j, len;
    NodePtr P0 = NULL;
    NodePtr P1 = NULL;
    NodePtr P2 = NULL;

    printf("对单链表排序如下：\n");
    len = Lenlist(headptr);
    /*用冒泡法排序：相邻两数比较，对链表来说，交换相邻两数要相对容易的多*/
    for(i=0; i<len-1; i++)
    {
        for(j=0; j<len-1-i; j++)
        {
            GetNode(headptr, j, &P0); /*j=0，则P0是头指针*/
            P1 = P0->next;
            P2 = P0->next->next;
            /*P1，P2是要交换的2个节点的指针，P0是这2个节点之前的节点指针*/
            /*3个节点的指针都已经保存，所以就不需要另外定义临时节点指针了*/
            if(P1->id > P2->id)
            {
                P1->next = P2->next;
                P2->next = P1;
                P0->next = P2;
            }
        }
    }

    return 0;
}

/*功能：按照数据域中某个数据成员的值(id)对单链表的元素进行递减排序*/
int SortNode2(NodePtr headptr)
{
    int i, j, len;
    NodePtr p0 = NULL;
    NodePtr p1 = NULL;
    NodePtr p2 = NULL;

    printf("对单链表排序如下：\n");
    len = Lenlist(headptr);
    /*用冒泡法排序：相邻两数比较，对链表来说，交换相邻两数要相对容易的多*/
    for(i=0; i<len-1; i++)
    {
        p0 = headptr; /*p0指向头节点*/
        for(j=0; j<len-1-i; j++)
        {
            p1 = p0->next;
            p2 = p0->next->next;
            /*p1，p2是要交换的2个节点的指针，p0是这2个节点之前的节点指针*/
            /*3个节点的指针都已经保存，p2->next的链不要断了，
            也可以定义4个节点的指针，就绝对不会断链了*/
            if(p1->id < p2->id)
            {
                p1->next = p2->next;
                p2->next = p1;
                p0->next = p2;
            }
            p0 = p0->next; /*第一个最小的已经排好，所以p0可以指向下一个节点了*/
        }
    }

    return 0;
}

/*功能：合并2条单链表为1条链表(不排序)(还可以做让2条已经有序的链表归并为1条有序的链表？？？)*/
int UnionList(NodePtr headptr1, NodePtr headptr2)
{
    NodePtr p1 = NULL;

    p1 = headptr1;
    while(p1->next != NULL)/*p指向最后一个节点元素了*/
    {
        p1 = p1->next;
    }
    p1->next = headptr2->next; /*首尾连接2条链表*/
    free(headptr2); /*第2条链表的头节点要释放*/
    return 0;
}

/***********************************************************
把链表节点倒过来不是排序 英文试卷  我不认识那个递归的单词  第一遍是用非递归搞的
后来面试的时候当面写个递归的
************************************************************/