2.3线性表的链式存储结构

链表

增加O(1)

删除O(1)

线性查找O(n)

修改O(1)

插入O(1)

1 head

2 头结点

3 开始结点

4 终端结点

5 尾指针

1 head

指向头结点的指针变量

2 头结点

开始结点，即是第一个有效结点之前的那个结点

头结点并不存储有效数据

加头结点的目的主要是为了方便对链表的操作

3 开始结点

第一个有效结点

4 终端结点

最后一个有效结点

5 尾指针

指向终端结点的指针变量

分类：

单链表

双向链表：每一个结点有两个指针域

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

非循环链表

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <stdbool.h>
  4 
  5 struct node//说明一个结构体
  6 {
  7     int data;
  8     struct node * next;
  9 };
 10 
 11 typedef struct node LinkNode;//简写
 12 
 13 LinkNode * create();//创建一个非循环单链表，并将该链表的头结点地址赋给head
 14 void add(LinkNode * head, int data);//尾部插入
 15 void print1(LinkNode * head);//遍历，递归
 16 void print2(LinkNode * head);//遍历，非递归
 17 bool is_empty(LinkNode * head);//判断链表是否为空，1为空，0为非空
 18 int length_list(LinkNode * head);//返回链表结点数量
 19 bool InsertList(LinkNode * head, int pos, int val);//在第pos个结点的前面插入一个新的结点，pos从1开始计算，该结点的值为val
 20 bool DeleteList(LinkNode * head, int pos, int *val);//删除第pos个结点
 21 void sort_list(LinkNode * head);//排序
 22 
 23 void main()
 24 {
 25     LinkNode * head = NULL;//头指针
 26     int val = 0;//保存删除的元素
 27 
 28     head = create();//创建一个非循环单链表，并将该链表的头结点地址赋给head
 29 
 30     printf("判断链表是否为空%d
", is_empty(head));//判断链表是否为空，1为空，0为非空
 31 
 32     add(head, 4);//尾部插入
 33     add(head, 3);
 34     add(head, 2);
 35     add(head, 1);
 36 
 37     print1(head);//遍历，递归
 38     printf("
");
 39 
 40     printf("判断链表是否为空%d
", is_empty(head));//判断链表是否为空，1为空，0为非空
 41     printf("返回链表结点数量%d
", length_list(head));//返回链表结点数量
 42 
 43     //sort_list(head);//链表排序
 44     //traverse_list1(head);//遍历，递归
 45 
 46     if (InsertList(head, 4, 33))//在第pos个结点的前面插入一个新的结点，pos从1开始计算，该结点的值为val
 47     {
 48         printf("插入成功
");
 49         print1(head);//遍历，递归
 50         printf("
");
 51     }
 52     else
 53     {
 54         printf("插入失败
");
 55     }
 56 
 57     if (DeleteList(head, 4, &val))//删除第pos个结点
 58     {
 59         printf("删除成功，删除的元素是:%d
", val);
 60         print1(head);//遍历，递归
 61         printf("
");
 62     }
 63     else
 64     {
 65         printf("删除失败
");
 66     }
 67 
 68     system("pause");
 69 }
 70 
 71 LinkNode * create()//创建一个非循环单链表，并将该链表的头结点地址赋给head
 72 {
 73     LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode));
 74     if (head == NULL)
 75     {
 76         printf("创建链表失败，内存分配失败
");
 77         return NULL;
 78     }
 79     else
 80     {
 81         head->next = NULL;
 82         return head;
 83     }
 84 }
 85 
 86 void add(LinkNode * head, int data)//尾部插入
 87 {
 88     LinkNode * new = (LinkNode *)malloc(sizeof(LinkNode));//第1步，创建指针new，用于存储新数据
 89     if (new == NULL)
 90     {
 91         printf("尾部插入失败，内存分配失败
");
 92         return;
 93     }
 94     else
 95     {
 96         new->data = data;
 97         new->next = NULL;
 98     }
 99 
100     LinkNode * p = head;//第2步，创建指针p，用于移动
101     if (p == NULL)
102     {
103         printf("头指针为空
");
104         return;
105     }
106     else
107     {
108         while (p->next != NULL)//遍历
109         {
110             p = p->next;
111         }
112         p->next = new;//第3步，指针p指向指针new
113     }
114 }
115 
116 void print1(LinkNode * head)//遍历，递归
117 {
118     if (head->next == NULL)
119     {
120         return;
121     }
122     else
123     {
124         printf("%d ", head->next->data);
125         print1(head->next);
126     }
127 }
128 
129 void print2(LinkNode * head)//遍历，非递归
130 {
131     LinkNode * p = head;
132     while (p->next)
133     {
134         printf("%d ", p->next->data);
135         p = p->next;
136     }
137     printf("
");
138 }
139 
140 bool is_empty(LinkNode * head)//判断链表是否为空，1为空，0为非空
141 {
142     if (head->next)
143     {
144         return false;
145     }
146     else
147     {
148         return true;
149     }
150 }
151 
152 int length_list(LinkNode * head)//返回链表结点数量
153 {
154     LinkNode * p = head;
155     int count = 0;//保存结点数量
156     while (p->next)
157     {
158         count++;
159         p = p->next;
160     }
161     return count;
162 }
163 
164 bool InsertList(LinkNode * head, int pos, int val)//在第pos个结点的前面插入一个新的结点，pos从1开始计算，该结点的值为val
165 {
166     int i = 0;
167     LinkNode * p = head;
168 
169     while (p != NULL && i < pos - 1)//且
170     {
171         p = p->next;
172         i++;
173     }
174 
175     if (i > pos - 1 || p == NULL)//或
176     {
177         printf("插入结点失败
");
178         return false;
179     }
180 
181     LinkNode * new = (LinkNode *)malloc(sizeof(LinkNode));
182 
183     if (new == NULL)
184     {
185         printf("插入结点失败，内存分配失败
");
186         return false;
187     }
188 
189     new->data = val;
190     new->next = NULL;
191 
192     LinkNode * q = p->next;//创建新结点q指向p的下一个
193     p->next = new;
194     new->next = q;
195 
196     return true;
197 }
198 
199 bool DeleteList(LinkNode * head, int pos, int * val)//删除第pos个结点
200 {
201     int i = 0;
202     LinkNode * p = head;
203 
204     while (p != NULL && i < pos - 1)//且
205     {
206         p = p->next;
207         i++;
208     }
209 
210     if (i > pos - 1 || p == NULL)//或
211     {
212         printf("插入结点失败
");
213         return false;
214     }
215 
216     LinkNode * q = p->next;//保存即将要删除的结点
217     *val = q->data;//保存即将要删除的结点的值
218 
219     p->next = p->next->next;//跳过即将要删除的结点
220     free(q);
221     q = NULL;
222 
223     return true;
224 }
225 
226 void sort_list(LinkNode * head)//链表排序
227 {
228     int i, j;
229     int temp;
230     LinkNode * p, *q;
231     int length = length_list(head);//返回链表结点数量
232 
233     for (i = 0, p = head->next; i < length - 1; i++, p = p->next)//冒泡
234     {
235         for (j = i + 1, q = p->next; j < length; j++, q = q->next)
236         {
237             if (p->data > q->data)
238             {
239                 temp = p->data;
240                 p->data = q->data;
241                 q->data = temp;
242             }
243         }
244     }
245 }

C++实现链表，无头结点

重点掌握

void sort();//排序，冒泡

void deletesame();//删除相同的元素

void rev();//链表逆转

头文件

 1 #pragma once
 2 #include "Node.h"
 3 
 4 template <class T>
 5 class List
 6 {
 7 public:
 8     Node<T> *pHead;
 9 public:
10     List();
11     void add(T t);//尾部插入
12     void show();//打印
13     Node<T> *find(T t);//查找
14     void change(Node<T> *p, T t);//修改
15     int getnum();//获取个数
16     bool delete1(T t);//删除元素
17 
18     void sort();//排序，冒泡
19     void deletesame();//删除相同的元素
20     void rev();//链表逆转
21 
22     void insert(T oldt, T newt);//前插
23     bool clear();//清空
24     void merge(List & list);//归并
25     ~List();
26 };

源文件

  1 #include "List.h"
  2 
  3 template <class T>
  4 List<T>::List()//构造函数
  5 {
  6     this->pHead = nullptr;
  7     std::cout << "链表创建" << std::endl;
  8 }
  9 
 10 template <class T>
 11 void List<T>::add(T t)//尾部插入
 12 {
 13     Node<T> *pnew = new Node<T>;//分配结点
 14     pnew->t = t;
 15     pnew->pNext = nullptr;
 16 
 17     if (pHead == NULL)
 18     {
 19 
 20         this->pHead = pnew;//头结点
 21     }
 22     else
 23     {
 24         Node<T> *p = pHead;//获取开始结点位置
 25         while (p->pNext != nullptr)//循环到尾部
 26         {
 27             p = p->pNext;
 28         }
 29         p->pNext = pnew;
 30     }
 31 }
 32 
 33 template <class T>
 34 void List<T>::show()//打印
 35 {
 36     Node<T> *p = pHead;//获取开始结点位置
 37     while (p != nullptr)//循环到尾部
 38     {
 39         std::cout << p->t << " ";
 40         p = p->pNext;
 41     }
 42     std::cout << "
";
 43 }
 44 
 45 template <class T>
 46 Node <T> *List<T>::find(T t)//查找
 47 {
 48     Node<T> *p = pHead;//获取开始结点位置
 49     while (p != nullptr)//循环到尾部
 50     {
 51         if (t == p->t)
 52         {
 53             return p;
 54         }
 55         p = p->pNext;
 56     }
 57     return nullptr;
 58 }
 59 
 60 template <class T>
 61 void List<T>::change(Node<T> *p, T newt)//修改
 62 {
 63     if (nullptr == p)
 64     {
 65         return;
 66     }
 67     else
 68     {
 69         p->t = newt;
 70     }
 71 }
 72 
 73 template <class T>
 74 int List<T>::getnum()//获取结点数量
 75 {
 76     int i;
 77     Node<T> *p = pHead;//获取开始结点位置
 78     while (p != nullptr)//循环到尾部
 79     {
 80         i++;
 81         p = p->pNext;
 82     }
 83     return i;
 84 }
 85 
 86 template <class T>
 87 bool List<T>::delete1(T t)//删除元素
 88 {
 89     Node<T> *p = this->find(t);
 90     if (nullptr == p)
 91     {
 92         return false;
 93     }
 94     else
 95     {
 96         if (pHead == p)//开始结点
 97         {
 98             pHead = p->pNext;
 99             delete p;
100         }
101         else
102         {
103             Node<T> *p1, *p2;//p1在前，p2在后
104             p1 = pHead;
105             p2 = p1->pNext;
106 
107             while (p2 != p)
108             {
109                 p1 = p2;
110                 p2 = p2->pNext;
111             }
112 
113             p1->pNext = p2->pNext;//跳过p2
114             delete p2;
115         }
116         return true;
117     }
118 }
119 
120 template <class T>
121 void List<T>::sort()//排序，冒泡
122 {
123     for (Node<T>*p1 = pHead; p1 != nullptr; p1 = p1->pNext)
124     {
125         for (Node<T>*p2 = pHead; p2 != nullptr; p2 = p2->pNext)
126         {
127             if (p1->t < p2->t)
128             {
129                 T temp = p1->t;
130                 p1->t = p2->t;
131                 p2->t = temp;
132             }
133         }
134     }
135 }
136 
137 template <class T>
138 void List<T>::deletesame()//删除链表相同的元素
139 {
140     Node<int>*p1, *p2;
141     p1 = pHead;//p1在前
142     p2 = pHead->pNext;//p2在后
143 
144     while (p2)
145     {
146         if (p1->t == p2->t)//如果p1的关键字和p2的关键字相同
147         {
148             p1->pNext = p2->pNext;//跳过p2
149             delete p2;//删除p2
150             p2 = p1->pNext;//p2仍然是p1后面
151         }
152         else
153         {
154             p1 = p2;//p1继续向后
155             p2 = p2->pNext;//p2继续向后
156         }
157     }
158 }
159 
160 template <class T>
161 void List<T>::rev()//链表逆转
162 {
163     if (pHead == nullptr || pHead->pNext == nullptr)//如果开始结点为空，或者只有一个结点，没有必要逆转
164     {
165         return;
166     }
167     else
168     {
169         Node<T>*p1, *p2, *p3;//p1前p2中p3后
170         p1 = pHead;
171         p2 = p1->pNext;
172         while (p2)
173         {
174             p3 = p2->pNext;//p3在p2后
175             p2->pNext = p1;//p2往前指向p1
176             p1 = p2;//p1向前
177             p2 = p3;//p2向前
178         }
179         pHead->pNext = nullptr;
180         pHead = p1;
181     }
182 }
183 
184 template <class T>
185 void List<T>::insert(T oldt, T newt)//在某个元素前插
186 {
187     Node<T>*p = find(oldt);
188     if (p)
189     {
190         Node<T>*p1, *p2;
191         p1 = pHead;
192         p2 = p1->pNext;
193         while (p2 != p)
194         {
195             p1 = p2;
196             p2 = p2->pNext;
197         }
198         Node<T>*pnew = new Node<T>;
199         pnew->t = newt;
200         pnew->pNext = p2;
201         p1->pNext = pnew;
202     }
203 }
204 
205 template <class T>
206 bool List<T>::clear()//清空
207 {
208     if (!pHead)
209     {
210         return false;
211     }
212     else
213     {
214         Node<int>*p1, *p2;//p1在前，p2在后
215         p1 = pHead->pNext;
216 
217         while (p1)
218         {
219             p2 = p1->pNext;
220             delete p1;
221             p1 = p2;
222         }
223 
224         delete pHead;
225         pHead = nullptr;
226 
227         return true;
228     }
229 }
230 
231 template <class T>
232 void List<T>::merge(List & list)//归并
233 {
234     Node<T>*p = pHead;//获取开始结点
235     while (p->pNext)//循环到尾部
236     {
237         p = p->pNext;
238     }
239     p->pNext = list.pHead;
240 }
241 
242 template <class T>
243 List<T>::~List()//析构函数
244 {
245     std::cout << "链表销毁" << std::endl;
246 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/denggelin/p/5683289.html