数据结构学习笔记(二)

链表(linked list)分为很多种。有单链表和多链表等。结点(Node)的组成：线性表中的数据元素及元素之间的逻辑关系可有结点来表示。结点由两部分组成：一部分是用来存储数据元素的值的数据域，另一部分是用来存储元素之间逻辑关系的指针域，指针域存放的是该结点的直接后继结点的地址。结点的结构如图所示：

定义：用链式存储结构表示的线性表称为链表，即用一组任意(可以连续也可以不连续)的存储单元来存放线性表的结点；把每个结点只有一个指针域的链表称为单链表。

开始结点、尾结点、头结点、和头指针：

在链表中存储第一个数据元素的结点称为开始结点；存储最后一个数据元素的结点称为尾结点。在开始结点之前附加一个结点称为头结点；指向链表中第一个结点的指针称为头指针。

typedef struct Node {
    int data;
    struct Node * pNext;
}NODE, * PNODE; //NODE等价于struct Node，PNODE等价于struct Node *

用结构体表示结点的指针域和数据域。通过typedef定义NODE和* PNODE。这里的NODE等价于struct Node，PNODE等价于struct Node * 

PNODE createList() {
    int len;
    int i;
    int val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); // 等价于 struct Node * pHead = (struct Node *) mallc(sizeof(struct Node));
    PNODE pTail = pHead; //等价于 struct Node * 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(NULL == pNew) {
            printf("分配失败，程序终止!n");
            exit(-1);
        }
        pNew->data = val; // 新结点得到值
        pTail->pNext = pNew; // 尾指针指向新结点，这样就将每个结点连起来了
       pNew->pNext = NULL; 
        pTail = pNew; // 尾结点指向最后的有效结点
    }
    return pHead;
}

void traverseList(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);

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

typedef struct Node {
    int data;
    struct Node * pNext;
}NODE, * PNODE; //NODE等价于struct Node，PNODE等价于struct Node *


// 函数定义
PNODE createList();
void traverseList(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() {
  int deleted_val;
    PNODE pHead = NULL; //将头结点设为空 
    pHead = createList(); // 创建链表
    traverseList(pHead);
  int len = length_list(pHead);
  printf("链表的长度为%dn", len);

  if(delete_list(pHead,2,&deleted_val)) {
    printf("删除成功，您删除的是%dn",deleted_val);
  
  }else {
    printf("删除失败!n");
  }
  traverseList(pHead);
  
  return 0;
}

// 创建链表
PNODE createList() {
    int len;
    int i;
    int val;
    PNODE pHead = (PNODE)malloc(sizeof(NODE)); // 等价于 struct Node * pHead = (struct Node *) mallc(sizeof(struct Node));
    PNODE pTail = pHead; //等价于 struct Node * 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(NULL == pNew) {
            printf("分配失败，程序终止!n");
            exit(-1);
        }
        pNew->data = val; // 新结点得到值
        pTail->pNext = pNew; // 尾指针指向新结点，这样就将每个结点连起来了
    pNew->pNext = NULL; 
        pTail = pNew; // 尾结点指向最后的有效结点
    }
    return pHead;
}

// 遍历链表
void traverseList(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;

  PNODE p,q;

  int len = length_list(pHead); 
  
  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("动态内存分配失败!n");
    exit(-1);
  }
  pNew->data = val;
  PNODE q = p->pNext;
  p->pNext = pNew;
  pNew->pNext = q;
}
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) {
    return false;
  }
  
  PNODE q = p->pNext;
  *pVal = q->data;

  //删除p节点后面的节点
  p->pNext = p->pNext->pNext;
  free(q);
  q = NULL;

  return true;
}