数据结构（八）链表基本算法实现

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
typedef struct Node {
      int data;     //数据域
      struct Node * pNext; //指针域
}NODE, *PNODE;
PNODE create_list(void); //创建链表
void traverse_list(PNODE pHead);  //遍历链表
bool is_empty(PNODE pHead);     //判空
int length_list(PNODE pHead);  //长度
bool insert_list(PNODE pHead, int pos, int val); //插入
bool delete_list(PNODE pHead, int pos, int *pVal); //删除
void sort_list(PNODE pHead);  //排序

int main(void) {
    PNODE pHead = NULL;
    int val;
    pHead = create_list();    //创建非循环单链表，并将该链表头结点地址传给pHead
    //insert_list(pHead, 4, 33);
    sort_list(pHead);
    
    if (delete_list(pHead, 4, &val)) {
        printf("succes! your delete is %d\n", val);
    }
    traverse_list(pHead);   //输出链表所有元素
      int len = length_list(pHead);
       printf("len = %d", len);
      return 0;
}

PNODE create_list(void) {
      int len; //有效节点个数
      int i;
      int val; //临时存放用户输入节点的值
      PNODE pHead = (PNODE)malloc(sizeof(NODE));
      if (NULL == pHead) {
          printf("分配失败");
          exit(-1);
      }
      PNODE pTail = pHead;
      pTail->pNext = NULL;
      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 (NULL == pNew) {
              printf("分配失败");
              exit(-1);
          }
          pNew->data = val;
          pTail->pNext = pNew;
          pNew->pNext = NULL;
          pTail = pNew;
      }
      return pHead;
}

void traverse_list(PNODE pHead) {
      PNODE p = pHead->pNext;
      while (NULL != p) {
      printf("%d ", p->data);
      p = p->pNext;
      }
      printf("\n");
      return;
}

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

int length_list(PNODE pHead) {
    PNODE p = pHead->pNext;
      int len = 0;
    while (NULL != p) {
        ++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) {
        for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext) {
            if (p->data > q->data) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
    return;
}

bool insert_list(PNODE pHead, int pos, int val) {
    int i = 0;
    PNODE p = pHead;
    while (NULL != p && i < pos-1) {
        p = p->pNext;
        ++i;
    }
    if (i>pos-1  NULL==p) {
        return false;
    }
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew) {
        printf("error of memary!");
        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 (NULL != p->pNext && i < pos-1) {
        p = p->pNext;
        ++i;
    }
    if (i > pos-1  NULL == p->pNext) {
        return false;
    }
    PNODE q = p->pNext;
    *pVal = q->data;
    
    //删除p节点后面的节点
    p->pNext = p->pNext->pNext;
    free(q);
    q = NULL;
    return true;
}