对一个链表的操作

对一个链表的操作： 创建一个链表，遍历输出链表的每个元素，对链表的增，删，排序

//创建一个链表，然后遍历输出

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

typedef struct Node
{
  int data;
  struct Node * next;
}NODE, *PNODE;

PNODE create_list();
void traverse_list(PNODE pHead);

int main()
{
    PNODE pHead = NULL;
    pHead = create_list();
    traverse_list(pHead);
}
PNODE create_list()
{
    int len, i, val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); //创建头结点分配地址
    if(pHead==NULL)
    {
        printf("内存分配失败，程序终止！
");
        exit(-1);
    }
    PNODE pTail = pHead; //定义一个表尾指针

    printf("请输入您需要生成的链表的结点的个数： len = ");
    scanf("%d", &len);

    for(i=0;i<len;i++)
    {
        printf("请输入第%d个结点的值： ",i+1);
        scanf("%d",&val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(pNew==NULL)
        {
            printf("内存分配失败，程序终止！
");
            exit(-1);
        }
        pNew->data = val;
        pTail->next = pNew;
        pNew->next = NULL;
        pTail = pNew;
    }
      pTail->next = NULL;
      return pHead;
}
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->next; //建立一个遍历指针 p
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("
");
    return;
}

// 自己写的一遍
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node * next;
}NODE, *PNODE;

PNODE create_list();
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE);
bool insert_list(PNODE, int, int);
bool delete_list(PNODE, int , int *);
void sort_list(PNODE);

int main()
{
    PNODE pHead = NULL;
    int val;
    pHead = create_list();
    traverse_list(pHead);
    insert_list(pHead, 3, 44);
    printf("插入后的元素内容为：
");
    traverse_list(pHead);
    if(delete_list(pHead,  4, &val))
        printf("删除成功，您删除的元素是： %d
", val);
    else
        printf("删除失败，您删除的元素不存在！
");
    traverse_list(pHead);
    sort_list(pHead);
    printf("冒泡排序后的结果为：
");
    traverse_list(pHead);



}
PNODE create_list()
{
    int len, i, val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); //创建头结点分配地址
    if(pHead==NULL)
    {
        printf("内存分配失败，程序终止！
");
        exit(-1);
    }
    PNODE pTail = pHead; //定义一个表尾指针

    printf("请输入您需要生成的链表的结点的个数： len = ");
    scanf("%d", &len);

    for(i=0;i<len;i++)
    {
        printf("请输入第%d个结点的值： ",i+1);
        scanf("%d",&val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(pNew==NULL)
        {
            printf("内存分配失败，程序终止！
");
            exit(-1);
        }
        pNew->data = val;
        pTail->next = pNew;
        pNew->next = NULL;
        pTail = pNew;
    }
      pTail->next = NULL;
      return pHead;
}
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->next; //建立一个遍历指针 p
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("
");
    return;
}
int length_list(PNODE pHead)
{
    int len = 0;
    PNODE p = pHead->next; //建立一个遍历指针 p
    while(p!=NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}
bool is_empty(PNODE pHead)
{
    if(pHead=NULL)
        return true;
    else
        return false;
}
bool insert_list(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;
    while(p!=NULL&&i<pos-1)
    {
        p = p->next;
        i++;
    }
    if(i>pos-1||p==NULL)
        return false;
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew==NULL)
    {
        printf("内存分配失败，程序终止！
");
        exit(-1);
    }
    pNew->data = val;
    PNODE q = p->next;
    p->next = pNew;
    pNew->next = q;
    return true;
}
bool delete_list(PNODE pHead, int pos , int * val)
{
    int i = 0;
    PNODE p = pHead;
    while(p->next!=NULL&&i<pos-1)
    {
        p = p->next;
        i++;
    }
    if(i>pos-1||p->next==NULL)
        return false;

    PNODE q = p->next;
    *val = q->data;
    p->next = q->next;
    free(q);
    q = NULL;
    return true;
}
void sort_list(PNODE pHead)
{
    int i,j,t,len=0;
    PNODE p;
    PNODE q;
    len = length_list(pHead);
    for(i=0,p=pHead->next;i<len-1;i++,p=p->next)
    {
        for(j=i+1,q=p->next;j<len;j++,q=q->next)
        {
            if(p->data>q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
    return;
}

//带有注释的
#include <stdio.h>
#include <malloc.h> //它包含了malloc函数
#include <stdlib.h> //包含了exit函数
#include <stdbool.h>

typedef struct Node
{
    int data; //数据域
    struct Node * pNext; //指针域
}NODE, *PNODE; // NODE 等价于 struct Node  *PNODE等价于 struct Node *

PNODE create_list(void);
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE);
//在PHead所指向链表的第pos个节点前面插入一个新节点，该节点的值是val，并且pos的值是从1开始
bool insert_list(PNODE, int, int);
bool delete_list(PNODE, int, int * );
void sort_list(PNODE);


int main()
{
    PNODE pHead = NULL;
    int val;
    pHead = create_list(); //创建一个非循环单链表，并将该链表的头结点的地址赋给pHead
    //insert_list(pHead, 4, 33);
    if(delete_list(pHead, 4, &val))
        printf("删除成功，您删除的元素是： %d
", val);
    else
        printf("删除失败，您删除的元素不存在！
");
    traverse_list(pHead);  //遍历输出链表
    //int len = length_list(pHead);
    //printf("链表的长度是%d
", len);

   // sort_list(pHead);
    //traverse_list(pHead);

    /*if(is_empty(pHead))
        printf("链表为空！
");
    else
        printf("链表不空
");*/

    return 0;
}

PNODE create_list(void)
{
    int len; //有效结点的个数
    int i;
    int val; //用来临时存放用户输入结点的值

    //分配一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); //生成一个临时结点pHead
    if(pHead==NULL)
    {
        printf("分配失败，程序终止！
");
        exit(-1); //终止整个程序
    }
    PNODE pTail = pHead; //创建一个表尾指针，让其指向pHead

    printf("请输入您需要生成的链表结点的个数： len = ");
    scanf("%d", &len);

    for(i=0;i<len;i++)
    {
        printf("请输入第%d个结点的值： ", i+1);  //输入结点的值
        scanf("%d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
         if(pNew==NULL)
         {
            printf("分配失败，程序终止！
");
            exit(-1); //终止程序
         }
         pNew->data = val; //尾插法，把pNew结点插入
         pTail->pNext = pNew;
         pNew->pNext = NULL;
         pTail = pNew; //pTai指向新的表尾结点
    }
    pTail->pNext = NULL; //尾指针置空
    return pHead;
}
void traverse_list(PNODE pHead) //遍历输出函数
{
    PNODE p = pHead->pNext; //定义一个遍历指针p

    while(p!=NULL) //如果p不为空，则输出p所指地址的变量
    {
        printf("%d ", p->data);
        p = p->pNext; //继续往后遍历
    }
    printf("
");
    return;
}

bool is_empty(PNODE pHead)
{
    if(pHead->pNext==NULL)
        return true;
    else
        return false;
}

int length_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;

    while(p!=NULL)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}

void sort_list(PNODE pHead)
{
    int i,j,t;
    int len = length_list(pHead);
    PNODE p,q;

    for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)//用冒泡排序，n个数比较n-1次
    {
        for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
        {
            if(p->data>q->data)  //类似于数组中的： a[i]>a[j]
            {
                t = p->data;  //类似于数组中的： t=a[i];
                p->data = q->data;  //类似于数组中的： a[i]=a[j];
                q->data = t;  //类似于数组中的： a[j]=t;
            }
        }
    }
    return;
}

//在PHead所指向链表的第pos个节点前面插入一个新节点，该节点的值是val，并且pos的值是从1开始
bool insert_list(PNODE pHead, int pos , int val)
{
   int i = 0;
   PNODE p = pHead;
   while(p!=NULL&&i<pos-1)
   {
       p = p->pNext;
       i++;
   }
   if(i>pos-1|| p==NULL)
    return false;

   PNODE pNew = (PNODE)malloc(sizeof(NODE));
   if(pNew==NULL)
   {
       printf("动态内存分配失败！
");
       exit(-1);
   }
   pNew->data = val;
   PNODE q = p->pNext;
   p->pNext = pNew;
   pNew->pNext = q;

 return true;
}

bool delete_list(PNODE pHead, int pos , int * pVal)
{

   int i = 0;
   PNODE p = pHead;
   while(p->pNext!=NULL&&i<pos-1)
   {
       p = p->pNext;
       i++;
   }
   if(i>pos-1|| p->pNext==NULL)
    return false;

   PNODE q = p->pNext;
   *pVal = q->data;  //用于存放被删除节点的值
   //删除p节点后面的结点
   p->pNext = q->pNext;
   free(q);
   q = NULL;
 return true;
}

typedef struct Node
{
  int data;
  struct Node * next;  
}NODE , * PNODE;

删除一个结点：
q = p->next;
p->next = q->next;
free(q);

插入一个结点：
s->data = val;
s->next = p->next;
p->next = s;


头插法插入一个结点：
s->data = val;
s->next = L->next;
L->next = s;

尾插法插入一个结点：
PNODE r = (PNODE)malloc(sizeof(NODE));
PNODE s = (PNODE)malloc(sizeof(NODE));
s->data = val;
r->next = s;
r = s;
r->next = NULL;