[应用方案] 单项链表基本操作

#include <stdio.h>

#include<stdlib.h>

typedef int type;

#define  LEN  sizeof(struct node)

typedef struct node

{

    type data;

    struct node *next;

}node;

/*------------------------------------------------------------------------------------------------------------

-------------------------------------初始化链表---------------------------------------------------------*/

void initList(node ** phead){

     *phead = NULL;

     printf("initList函数执行，初始化成功\n");

}

/*------------------------------------------------------------------------------------------------------------------

-------------------------------------创建链表，返回头指针-------------------------------------------------*/

node * creatList(node * head){

        node  *p, *pl;

        head=p=(node * )malloc(LEN);

        printf("creatList函数执行,请输入链表数据成员,以0结束\n");

        scanf("%d",&p->data);/*头结点的数据成员*/

        while(p->data!=0)   /*给出0结束条件,退出循环*/

        {  

                pl=p;

                p=(node * )malloc(LEN);

                scanf("%d",&p->data);/*中间结点数据成员*/

        if(p->data!=0){

            pl->next=p;/*中间结点的指针成员值*/

        }else{

        break;

        }

        }

        pl-> next=NULL;/*尾结点的指针成员值*/

        

         return head;

}

/*--------------------------------------------------------------------------------------------------------

-----------------------------------------------打印链表------------------------------------------------*/

void printList(node *head){

 if(NULL == head)   //链表为空

    {

        printf("printList函数执行，链表为空\n");

    }

    else

    {

        while(NULL != head)

        {

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

            head = head->next;

        }

        printf("\n");

    }

}

/*------------------------------------------------------------------------------------------------------------

-------------------------------------------------获取长度-------------------------------------------------*/

int getLength(node * head){

 int length = 0;

 if(NULL == head)   //链表为空

    {

        printf("链表为空\n");

    }

    else

    {

  while(NULL != head)

        {

   length ++ ;

            head = head->next;

        }

    }

 printf("length is : %d\n",length);

 return length;

}

/*------------------------------------------------------------------------------------------------------------

-------------------------------------------------清空链表-------------------------------------------------*/

void cleanList(node **phead)

{

    node *pNext;            //定义一个与phead相邻节点

 

    if(*phead == NULL)

    {

        printf("clearList函数执行，链表为空\n");

        return;

    }

    while(*phead != NULL)

    {

        pNext = (*phead)->next;//保存下一结点的指针

        free(*phead);

        *phead = pNext;      //表头下移

    }

    printf("clearList函数执行，链表已经清除\n");

}

/*------------------------------------------------------------------------------------------------------------

----------------------------------------获取第n个结点的data-----------------------------------------*/



type getdatabyN(node * head,int n){

 int i=0;

    if(n <= 0)

    {

        printf("getdatabyN函数执行，n值非法\n");

        return 0;

    }

    if(head == NULL)

    {

        printf("getdatabyN函数执行，链表为空\n");

        return 0;

        //exit(1);

    }

    while(head !=NULL)

    {

        ++i;

        if(i == n)

        {

            break;

        }

        head = head->next; //移到下一结点

    }

    if(i < n)                  //链表长度不足则退出

    {

        printf("getElement函数执行，pos值超出链表长度\n");

        return 0;

    }

 

    return head->data;

}

/*---------------------------------------------------------------------------------------------------------------

--向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回0 ---*/

int insertList(node **pNode, int pos, type elemInserted)

{

 int i = 0;

 node *pInserted,*pTemp, *pLast;

    if(NULL == *pNode)

    {

        printf("insertList函数执行，链表为空\n");

        return 0;

    }

    if(elemInserted < 1)

    {

        printf("insertList函数执行，elemInserted值非法\n");

        return 0;

    }

    if(pos < 1)

    {

        printf("insertList函数执行，pos值非法\n");

        return 0;

    }

  

    pTemp = *pNode;   //把*pNode先赋值给pTemp，后面的操作（例如循环链表到最后一个节点）主要是对pTemp进行操作，否则返回*pNode的时候，将返回链表*pNode在当前指针后面的部分，而不是整个链表。

    //因为pTemp与*pNode指向同一个链表，所以对pTemp进行节点改动即是对*pNode作改动

    pInserted = (node *)malloc(sizeof(node));

    pInserted->data = elemInserted;

    pInserted->next = NULL;  //先赋值为null

    //循环链表至pos节点

  

    while(pTemp != NULL)

    {

        i++;

        if(i == pos)

        {

            pLast->next = pInserted;  //让上一个节点的next指向插入节点

            pInserted->next = pTemp;  //让插入节点的next指向下一节点

            break;

        }

        pLast = pTemp;  //记住上一个节点的位置

        pTemp = pTemp->next;

    }

 printf("在%d插入%d得到",pos,elemInserted);

    return 1;

/*------------------------------------------------------------------------------------------------------------

--------------------------------------------排序单链表,降序--------------------------------------------*/



int sortList(node **pnode)

{

 int p,k,i,Listsize;

    node *pTemp;

 node *pCurr, *pLast;

    if(NULL == *pnode)

    {

        printf("sortList函数执行，链表为空\n");

        return 0;

    }

    pTemp = *pnode;

 Listsize = getLength(*pnode);

    //循环: 用for循环来取代指针循环，因为指针循环一次后，下次起始的指针将自动转到下一节点，而我们还想从第一个元素开始

    for( i=0; i < Listsize; i++)

    {

 

      

        pCurr = pLast = pTemp;

        for(k=0; k < Listsize-i; k++)

        {

             p = 0;

         

            if(pLast->data < pCurr->data)

            {

                p = pLast->data;

                pLast->data = pCurr->data;

                pCurr->data = p;

            }

            pLast = pCurr;

            pCurr = pCurr->next;

        }

    }

 printf("sortList函数执行,排序成功");

}



/*--------------------------------------*/

/*-----------------主函数：测试---------------*/

int main()

{   

 node * head;

 initList(&head);               //初始化

 head = creatList(head);        //建表

 printList(head);               //印表

 getLength(head);               //多长

 insertList(&head,3,15);        //插数

 printList(head);               //印表

 sortList(&head);               //排序

 printList(head);               //印表

 cleanList(&head);              //清空

 printList(head);               //印表

}