数据结构学习笔记（4）——链表的插入和删除

说明（2018-3-19 15:32:59）：

1. 按照自己的理解写的，循环遍历的部分不太一样，大于小于什么的细节也不一样，可能视频里的方法比较健壮吧，只是这个不是重点地方。

2. 链表的插入和删除思想基本是一样的，插入就是把一侧指针断开，加入新节点，再把指针连起来。删除就是把两侧指针断开，前一个指针跟后一个指针连接。

3. 补充一点，删除元素的时候，要把被删除的元素先保存起来，pNODE q = p->pNext，然后free(q)，q=NULL，不然这块内存就找不到了，也不会释放。注意free后面要紧跟=NULL。

指针free之后，free函数只是把指针指向的内存空间释放了，即内存中存储的值，但是并没有将指针的值赋为NULL，指针仍然指向这块内存。而程序判断一个指针是否合法，通常都是使用if语句测试该指针是否为NULL来判断，导致指针成为所谓的“野指针”，诱导误操作。

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 #pragma warning(disable:4996)
  5 #include<stdbool.h>
  6 
  7 typedef struct Node
  8 {
  9     int data;
 10     struct Node * pNext;
 11 
 12 }NODE, *pNODE;
 13 pNODE CreatList();
 14 void ShowList(pNODE pHead);
 15 int LengthList(pNODE pHead);
 16 bool InsertList(pNODE pHead, int pos, int val);
 17 bool DeleteList(pNODE pHead, int pos, int*val);
 18 
 19 void main()
 20 {
 21     pNODE pHead = CreatList();
 22     ShowList(pHead);
 23     //int len = LengthList(pHead);
 24     //printf("链表长度为%d
", len);
 25     //InsertList(pHead, 2, 100);
 26     int val;
 27     if (DeleteList(pHead, 4, &val))
 28     {
 29         printf("删除成功！");
 30     }
 31     else
 32     {
 33         printf("删除失败！");
 34     }
 35 
 36     printf("删除的值是：%d
", val);
 37     printf("
");
 38     ShowList(pHead);
 39     system("pause");
 40 }
 41 
 42 pNODE CreatList()
 43 {
 44     pNODE pHead = (pNODE)malloc(sizeof(NODE));
 45     pNODE pTail = pHead;
 46     if (pHead == NULL)
 47     {
 48         printf("内存分配失败！");
 49         exit(-1);
 50     }
 51     printf("请输入链表的长度：");
 52     int len;
 53     scanf("%d", &len);
 54     for (int i = 0; i < len; i++)
 55     {
 56         pNODE pNew = (pNODE)malloc(sizeof(NODE));
 57         if (pNew == NULL)
 58         {
 59             printf("内存分配失败！");
 60             exit(-1);
 61         }
 62         int val;
 63         printf("请输入第%d个元素的数值：", i + 1);
 64         scanf("%d", &val);
 65         pNew->data = val;
 66         pTail->pNext = pNew;
 67         pTail = pNew;
 68         pNew->pNext = NULL;
 69     }
 70     return pHead;
 71 }
 72 
 73 void ShowList(pNODE pHead)
 74 {
 75     pNODE p = pHead->pNext;
 76     while (p != NULL)
 77     {
 78         printf("%d ", p->data);
 79         p = p->pNext;
 80     }
 81     return;
 82 }
 83 
 84 int LengthList(pNODE pHead)
 85 {
 86     int len = 0;
 87     pNODE p = pHead->pNext;
 88     while (p != NULL)
 89     {
 90         p = p->pNext;
 91         len++;
 92     }
 93     return len;
 94 
 95 }
 96 
 97 bool InsertList(pNODE pHead, int pos, int val)
 98 {
 99     pNODE pNew = (pNODE)malloc(sizeof(NODE));
100     if (pNew == NULL)
101     {
102         exit(-1);
103     }
104     int len = LengthList(pHead);
105     if (pos<1 || pos>len)
106     {
107         return false;
108     }
109     pNew->data = val;
110     pNODE p = pHead;
111     int n = 0;
112     while (p != NULL)
113     {
114         n++;
115         if (n == pos)
116         {
117             pNew->pNext = p->pNext;
118             p->pNext = pNew;
119             break;
120         }
121         p = p->pNext;
122     }
123     return true;
124 }
125 
126 bool DeleteList(pNODE pHead, int pos, int*pVal)
127 {
128     int n = 0;
129     pNODE p = pHead;
130     if (p == NULL || pos < 1)
131     {
132         return false;
133     }
134     while (p != NULL&&n < pos - 1)
135     {
136         p = p->pNext;
137         n++;
138     }
139     *pVal = p->pNext->data;
140     p->pNext = p->pNext->pNext;
141     return true;
142 }