离散存储结构—链表

离散存储【链表】

                优点：

                     空间没有限制

                     插入删除元素很快

               缺点：

                     存取速度很慢

定义：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点同时每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

专业术语

• 首节点：存放第一个有效数据的节点

• 尾节点：存放最后一个有效数据的节点

• 头结点：位于首节点之前的一个节点，头结点并不存放有效的数据，加头结点的目的主要是为了方便对链表的操作

• 头指针：指向头结点的指针变量

• 尾指针：指向尾节点的指针变量

确定一个链表需要几个参数：只需要一个头指针参数，因为我们通过头指针可以推算出链表的其他所有信息

分类

• 单链表：每一个节点只有一个指针域

• 双链表：每一个节点有两个指针域

• 循环链表：能通过任何一个节点找到其他所有的节点

• 非循环链表：不能通过任何一个节点找到其他所有的节点

 

# include <stdio.h>
# include <malloc.h>
# 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);
//在指定节点处插入某个元素
bool insert_list(PNODE,int,int);
//删除指定位置的元素
bool delete_list(PNODE,int,int *);
//对链表排序
void sort_list(PNODE pHead);
​
int main(void)
{
    PNODE pHead = NULL;//定义头结点指针
    pHead = create_list();
    return 0;
}
​
PNODE create_list(void)
{
    int len;//链表成员个数，由用户输入
    int i;
    int val;//链表成员值，由用户输入
​
    PNODE pHead = (PNODE)malloc(sizeof(NODE));//定义头结点指针
    if (NULL == pHead)
    {
      printf("分配内存失败，程序结束");
      exit(-1);
    }
​
    printf("请输入链表长度,len=");
    scanf("%d",&len);
​
    PNODE pTail = pHead;
    pTail->pNext = NULL;
​
    for(i=0; i < len; i++)
    {
      PNODE pNew = (PNODE)malloc(sizeof(NODE));
      if (NULL == pNew)
      {
        printf("分配内存失败，程序结束");
        exit(-1);
      }
      printf("请输入要插入链表的值,val=");
      scanf("%d",&val);
  
      pNew->data = val;
      pTail->pNext = pNew;
      pNew->pNext = NULL;
      pTail = pNew;
    }
    return pHead;
}
​
void traverse_list(PNODE pHead)
{
     PNODE p = pHead->pNext;
     if (NULL != p)
     {
         printf("%d\t",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)
{
     int len = 0;
     PNODE p = pHead->pNext;
     while(NULL != p)
     {
        ++len;
        p = p->pNext;
     }
     return len;
}
​
bool insert_list(PNODE pHead,int pos,int val)
{
     int i;
     PNODE p = pHead;
     //循环到p指向pos-1的位置
     while( NULL != p && i<pos-1)
     {
         p = p->pNext;
         ++i;
     }

     if (NULL == p || i > pos -1)
     {
         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;
     return ture;
} 
​
bool delete_list(PNODE pHead,int pos,int *pVal)
{
     int i;
     PNODE p = pHead;

     //循环到p指向pos-1的位置
     while( NULL != p->pNext && i<pos-1)
     {
         p = p->pNext;
         ++i;
     }

    if (NULL == p->pNext || i > pos -1)
    {
        return false;
    }

     PNODE q = p->pNext;
    *pVal = p->data;
    p->pNext=q->pNext;
    free(q);
    q=NULL;
    return true;
}
​
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;
}