数据结构与算法——单链表的实现及原理

1. 单链表的原理

　　链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。如图所示：

　　从图中可以看出,每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是结点类型链表的核心要素：? 每个节点由数据域和指针域组成 ? 指针域指向下一个节点的内存地址。

　　1.1 结构体定义

1  Typedef struct LinkNode 
2  {
3      ElemType data;             //节点中存放数据的类型
4      struct LinkNode* next;     //节点中存放下一节点的指针
5  }LinkList, LinkNode;

2. 单链表初始化

链表的节点均单向指向下一个节点，形成一条单向访问的数据链

 1  //单链表的初始化
 2     typedef struct _LinkNode
 3     {
 4         int data;                      //结点的数据域
 5         struct _LinkNode* next;        //结点的指针域 
 6     }LinkNode, LinkList;               //链表节点、链表
 7 
 8     bool InitList(LinkList*& L)    　　//构造一个空的单链表 L
 9     {
10         L = new LinkNode;          　　//生成新结点作为头结点，用头指针 L 指向头结点 
11         if(!L)return false;        　　//生成结点失败 
12         L->next=NULL;              　　//头结点的指针域置空
13         return true;
14     }

3. 单链表增加元素 - 单链表前插法

插入节点的要素就是要找到要插入位置的前一个节点，将这个节点的Next赋值给新节点，然后将新节点的地址赋值给前一个节点的Next便可，任意位置插入和前插法均是如此。

1  //前插法
2 bool ListInsert_front(LinkList * &L, LinkNode * node)           //参数1 链表指针  参数2 要插入的节点元素
3 {
4     if (!L || !node) return false;          //如果列表或节点为空返回 false
5     node->next = L->next;                   //将头节点指向节点1的地址 赋值给要插入节点的指针域，使要插入的节点先与后部相连
6     L->next = node;                         //将插入节点的地址赋值给头结点的指针域，使要插入节点与头结点相连
7 
8     return true;
9 }

4. 单链表增加元素 - 单链表尾插法

 1  //尾插法
 2  bool ListInsert_back(LinkList*& L, LinkNode* node) 
 3  {
 4      LinkNode* last = NULL;                         //创建空指针，
 5      if (!L || !node) return false;                 //如果列表或节点为空返回 false                        
 6      
 7      last = L;
 8      while (last->next) last = last->next;          //使用 last 找到最后一个节点
 9      
10      node->next = NULL;                             //要插入节点由于在尾部，指针域置为 NULL
11      last->next = node;                             //将要插入节点的地址赋值给之前的尾部节点的指针域，将要插入节点放置到尾部
12      return true;
13  }

5. 单链表增加元素 - 单链表任意位置插入

插入节点的要素就是要找到要插入位置的前一个节点，将这个节点的Next赋值给新节点，然后将新节点的地址赋值给前一个节点的Next便可，任意位置插入和前插法均是如此。

 1  //任意位置插法
 2  bool LinkInsert(LinkList*& L, int i, int& e)       //参数1 链表指针  参数2 要插入的位置  参数3 要插入的节点元素
 3  {
 4      LinkList* p = L, * s;
 5      int j = 0;
 6 
 7      while (p && j < i - 1)                         //查找第i-1个结点(要插入位置的前一个节点)，p指向该结点
 8      {
 9          p = p->next;
10          j++;
11      }
12 
13      if (!p || j > i - 1)                           //验证数据有效性
14      {
15          return false;
16      }
17 
18      s = new LinkNode;                              //生成新结点 
19      s->data = e;                                   //将新结点的数据域置为 e
20      s->next = p->next;                             //将新结点的指针域指向结点 ai，使要插入的节点先与后部相连
21      p->next = s;                                   //将结点 p 的指针域指向要插入的结点，使要插入节点与头结点相连
22 
23      return true;
24  }

6. 单链表遍历

 1  void LinkPrint(LinkList*& L)                   //单链表的输出
 2  {
 3      LinkNode* p; 
 4      p = L->next;
 5 
 6      while (p)                                  //一直循环打印，直到 p->next == NULL 退出循环
 7      {
 8          cout << p->data << "\t";
 9          p = p->next;
10      }
11      cout << endl;
12  }

7. 单链表获取元素

 1  //单链表的取值
 2  //在带头结点的单链表 L 中查找第 i 个元素，用 e 记录 L 中第 i 个数据元素的值
 3 bool Link_GetElem(LinkList*& L, int i, int& e)     //参数1 要查找的链表指针  参数2 要查找的元素位置    参数3 要记录存放元素的值
 4 {
 5     int j; 
 6     LinkList* p;
 7     p = L->next;                           //p指向第一个结点
 8     j=1;                                   //j为计数器
 9 
10     while (j < i && p)                     //顺链域向后扫描，直到p指向第i个元素或p为空
11     {
12         p = p->next;                       //p指向下一个结点
13         j++;                               //计数器j相应加1
14     }
15 
16     if (!p || j > i) 
17     {
18         return false;                      //i 值不合法 i＞n 或 i<=0
19     }
20 
21     e = p->data;                           //取第i个结点的数据域
22     return true;
23 }

8. 单链表查找元素

 1 //按值查找
 2 bool Link_FindElem(LinkList* L, int e)  //在带头结点的单链表L中查找值为e的元素
 3 {
 4     LinkList* p; 
 5     p = L->next;
 6     while (p && p->data != e)           //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
 7     {
 8         p = p->next;                    //p指向下一个结点
 9     }
10     if (!p)return false;                //查找失败p为NULL
11 
12     return true;
13 }

9. 单链表删除

 1 //单链表的节点删除
 2 bool LinkDelete(LinkList*& L, int i)                    //在带头结点的单链表L中，删除第i个位置
 3 {
 4     LinkList* p = L, * q;
 5     int j = 0;
 6 
 7     while (p->next && j < i - 1)                        //查找第i-1个结点，p指向该结点
 8     {
 9         p = p->next; 
10         j++;
11     }
12 
13     if (!(p->next) || j > i - 1)  return false;         //当 i > n 或 i < 1 时，删除位置不合理 
14         
15     q = p->next;            //临时保存被删结点的地址以备释放空间,(删除的是 P 的下一个节点)
16     p->next = q->next;      //将要删除的节点的下一个节点地址覆盖要删除节点的地址（就是把要删除节点的下一个节点地址，赋值给被删除节点的前一个节点的next）
17     delete q;               //释放被删除结点的空间
18 
19     return true;
20 }

10. 单链表销毁

 1 //单链表的销毁
 2 void LinkDestroy(LinkList*& L)
 3 {
 4     //定义临时节点p指向头节点
 5     LinkList* p = L;
 6     cout << "销毁链表!" << endl;
 7 
 8     while (p)                                               //遍历整个链表，逐个释放直到 L->next == NULL
 9     {
10         L = L->next;                                        //L指向下一个节点
11         cout << "删除元素: " << p->data << endl; 
12         delete p;                                           //删除当前节点
13         p = L;                                              //p 移向下一个节点
14     }
15 }

 11. 完整实现

  1 #include
  2 #include<string>
  3 #include
  4 
  5 using namespace std;
  6 
  7 typedef struct _LinkNode 
  8 {
  9     int data;                //结点的数据域
 10     struct _LinkNode* next; //结点的指针域
 11 }LinkNode, LinkList;        //LinkList 为指向结构体LNode 的指针类型
 12 
 13 bool InitList(LinkList*& L) 
 14 {
 15     L = new LinkNode;
 16     if (!L) return false;    //生成节点失败
 17     L->next = NULL;
 18     L->data = -1;
 19     return true; 8979438401111
 20 }
 21 
 22 //前插法
 23 bool ListInsert_front(LinkList*& L, LinkNode* node) 
 24 {
 25     if (!L || !node) return false;
 26     node->next = L->next;
 27     L->next = node;
 28     return true;
 29 }
 30 
 31 //尾插法
 32 bool ListInsert_back(LinkList*& L, LinkNode* node) 
 33 {
 34     LinkNode* last = NULL;
 35     if (!L || !node) return false;
 36     last = L;
 37     while (last->next) last = last->next;
 38     node->next = NULL;
 39     last->next = node;
 40     return true;
 41 }
 42 
 43 //指定位置插入
 44 bool LinkInsert(LinkList*& L, int i, int& e) 
 45 {
 46     if (!L) return false;
 47     int j = 0;
 48     LinkList* p, * s;
 49     p = L;
 50     while (p && j < i - 1)                //查找位置为i-1 的结点，p 指向该结点
 51     {
 52         p = p->next;
 53         j++;
 54     }
 55     if (!p || j > i - 1) 
 56     {
 57         return false;
 58     }
 59     s = new LinkNode;                    //生成新节点
 60     s->data = e;
 61     s->next = p->next;
 62     p->next = s;
 63     return true;
 64 }
 65 
 66 //遍历
 67 void LinkPrint(LinkList*& L) 
 68 {
 69     LinkNode* p = NULL;
 70     if (!L) {
 71         cout << "链表为空." << endl;
 72         return;
 73     }
 74     p = L->next;
 75     while (p) {
 76         cout << p->data << "\t";
 77         p = p->next;
 78     }
 79     cout << endl;
 80 }
 81 
 82 //单链表的取值
 83 bool Link_GetElem(LinkList*& L, int i, int& e)            
 84 {
 85     //在带头结点的单链表L 中查找第i 个元素
 86     //用e 记录L 中第i 个数据元素的值
 87     int index;
 88     LinkList* p;
 89     if (!L || !L->next) return false;
 90     p = L->next;
 91     index = 1;
 92     while (p && index < i)                                //顺链表向后扫描，直到p 指向第i 个元素或p 为空
 93     {
 94         p = p->next;                                    //p 指向下一个结点
 95         index++;                                        //计数器index 相应加1
 96     }
 97     if (!p || index > i) {
 98         return false;                                    //i 值不合法,i＞n 或i<=0
 99     }
100     e = p->data;
101     return true;
102 }
103 
104 //按值查找
105 bool Link_FindElem(LinkList* L, int e, int& index)
106 {
107     //在带头结点的单链表L 中查找值为e 的元素
108     LinkList* p;
109     p = L->next;
110     index = 1;
111     if (!L || !L->next) 
112     {
113         index = 0;
114         return false;
115     }
116     while (p && p->data != e) 
117     {
118         p = p->next;
119         index++;
120     }
121     if (!p) 
122     {
123         index = 0;
124         return false;                                    //查无此值
125     }
126     return true;
127 }
128 
129 //单链表的删除
130 bool LinkDelete(LinkList*& L, int i)
131 {
132     LinkList* p, * q;
133     int index = 0;
134     p = L;
135     if (!L || !L->next) 
136     {
137         return false;
138     }
139 
140     while ((p->next) && (index < i - 1)) 
141     {
142         p = p->next;
143         index++;
144     }
145 
146     if (!p->next || (index > i - 1))                    //当 i>n 或 i<1 时，删89除7位94置38不40合1理111
147     { 
148         return false;
149     }
150     q = p->next;                                        //临时保存被删结点的地址以备释放空间
151     p->next = q->next;                                    //改变删除结点前驱结点的指针域
152     delete q;                                            //释放被删除结点的空间
153     return true;
154 }
155 
156 //单链表的销毁
157 void LinkDestroy(LinkList*& L)
158 {
159     //定义临时节点p 指向头节点
160     LinkList* p = L;
161     cout << "销毁链表!" << endl;
162     while (p) {
163         L = L->next;                                    //L 指向下一个节点
164         cout << "删除元素: " << p->data << endl;
165         delete p;                                        //删除当前节点
166         p = L;                                            //p 移向下一个节点
167     }
168 }
169 
170 int main(void) 
171 {
172     LinkList* L = NULL;
173     LinkNode* s = NULL;
174 
175     //1. 初始化一个空的链表
176     InitList(L);
177 
178     //2. 使用前插法插入数据
179     /*int n;
180     cout<<"前插法创建单链表"<181     std::cout<<"请输入元素个数n：";
182     cin>>n;
183     cout<<"\n 请依次输入n 个元素：" <184     while(n>0){
185     s = new LinkNode; //生成新节点s
186     cin>>s->data;
187     ListInsert_front(L, s);
188     n--;
189     }*/
190 
191     //3. 使用尾插法插入数据
192     /*int n;
193     cout<<"尾插法创建单链表"<194     std::cout<<"请输入元素个数n：";
195     cin>>n;
196     cout<<"\n 请依次输入n 个元素：" <197     while(n>0){
198     s = new LinkNode; //生成新节点s
199     cin>>s->data;
200     ListInsert_back(L, s);
201     n--;
202     }*/
203 
204     //4. 单链表的输出
205     /*
206     LinkPrint(L);
207     */
208 
209     //5. 任意位置插入元素
210     for (int j = 0; j < 3; j++) {
211         int i, x;
212         cout << "请输入插入的位置和元素（用空格隔开）:";
213         cin >> i;
214         cin >> x;
215         if (LinkInsert(L, i, x)) {
216             cout << "插入成功.\n\n";
217         }
218         else {
219             cout << "插入失败!\n\n";
220         }
221         LinkPrint(L);
222     }
223 
224     //6. 单链表根据位置获取元素
225     int element = 0;
226     if (Link_GetElem(L, 2, element)) {
227         cout << "获取第二个元素成功, 值：" << element << endl;
228     }
229     else {
230         cout << "获取第二个元素失败!" << endl;
231     }
232 
233     //7. 单链表根据值查询元素所在的位置
234     int index = 0;
235     if (Link_FindElem(L, 10, index)) {
236         cout << "查找元素10 存在,所在位置: " << index << endl;
237     }
238     else {
239         cout << "不存在元素10." << endl;
240     }
241 
242     //8. 单链表删除元素
243     if (LinkDelete(L, 2)) {
244         cout << "删除第2 个元素成功!" << endl;
245         LinkPrint(L);
246     }
247     else {
248         cout << "删除第2 个元素失败!" << endl;
249     }
250 
251     //9. 销毁单链表
252     LinkDestroy(L);
253     system("pause");
254     return 0;
255 }

======================================================================================================================