链表写不出来咋整啊
链表已经学了三四天，它不是那种学不会，他就是那种很特别的，你懂吧，单链表：这不还是挺简单的吗，双链表：哦吼有点难度了啊，循环链表：，马嘞个…马马虎虎啊。跳跃链表：…。自组织链表：啥玩意啊？？？稀疏表：老子不学了还不行吗，标准模板库中的链表：对不起大爷，俺错了，饶了俺吧.所以知识不牢固；链表分分钟教你做人
嘛毕竟不能一口吞个坦克，不过想想的确链表挺揪心的。俺们组的大佬人家说了，深刻的理解和令人胆寒的代码量必然带来的不仅仅是质的变化。道理谁都懂但但做到很难！！！！今天打算好好梳理一下。
单链表
这个我之前就已经吧搜索，插入，删除，以及一些常见的概念说的很清楚了大概【？】 ，我看实现单链表的详细清单有3页这就已经很扯淡了，所以这里的只说一些简单的实现。
单链表结构
我们设计一个简单的单链表结构，如下：
1
2
3
4
| struct ListNode {
int value;
struct ListNode *next;
};typedef struct ListNode * list;
|
phead为单链表的头指针，它指向表中的第一个节点，头结点的数据可以不存储然后信息，也可以设计成存储线性表长度等附加信息。
打印单链表
首先，我们可以利用链表打印数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| struct ListNode {
int data;
struct ListNode *next;
};
typedef struct ListNode * list;
ListNode *creat(int n)
{
int i;
ListNode *phead, *p1, *p2;
int a;
phead = NULL;
p2 = NULL;
for (i = 1; i <= n; i++)
{
p1 = (ListNode *)malloc(sizeof(ListNode));
printf("请输入链表中的第%d个数：", i);
cin>>a;
p1->data = a;
if (phead == NULL)
{
phead = p1;
p2 = p1;
}
else
{
p2->next = p1;
p2 = p1;
}
p2->next = NULL;
}
return phead;
}
int main()
{
int n;
ListNode *q;
printf("请输入链表的长度：\n");
cin>>n;
q = creat(n);
printf("链表中的数据：\n");
while (q)
{
printf("%d ", q->data);
q = q->next;
}
system("pause");
return 0;
}
|
注释很很很很很清楚了，就不解释了
我这边还有我第一次写的一个demo，和这个意思也是一样的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
Node*creat(int n){
struct Node* head, *p1,*p2;
head=(struct Node*)malloc(sizeof(struct Node));
p1=head;
for(int i=0;i<n;i++){
p2=(struct Node*)malloc(sizeof(struct Node));
p2->data=i+1;
p1->next=p2;
p1=p2;
}
p2->next=nullptr;
return head->next;
}
int main(){
int n;
Node *q;
printf("请输入链表的长度：\n");
cin>>n;
q = creat(n);
printf("链表中的数据：\n");
while (q)
{
printf("%d ", q->data);
q = q->next;
}
system("pause");
return 0;
}
|
单链表排序
下面实现稍微复杂的一些的链表操作，比如单链表的排序，单独排序功能实现常见的就有插入排序，冒泡排序，简单排序，快速排序，这里我们简单实现一些插入排序好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| void sort(list linklist)
{
if((linklist -> next == NULL) || (linklist -> next -> next == NULL))
{
return;
}
ListNode * phead, * p1, * prep1, * p2, * prep2, * temp;
phead = linklist;
prep1 = phead -> next;
p1 = prep1 -> next;
bool flag;
while(p1 != NULL)
{
flag = true;
temp = p1;
for(prep2 = head, p2 = prep2 -> next; p2 != p1; prep2 = prep2 -> next, p2 = p2 -> next)
{
if(p2 -> data > p1 -> data)
{
p1 = p1 -> next;
prep1 -> next = p1;
prep2 -> next = temp;
temp -> next = p2;
flag = false;
break;
}
}
if(flag)
{
prep1 = prep1 -> next;
p1 = p1 -> next;
}
}
}
|
以上的操作都不是很难那我们再试试反转
单链表翻转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ListNode reverse(list linklist)
{ ListNode *phead；
phead = linklist;
if(phead == NULL || phead->next == NULL)
return phead;
ListNode pre = NULL;
ListNode next = NULL;
while(phead != NULL){
next = phead->next;
phead->next = pre;
pre = phead;
phead = next;
}
return pre;
}
|
emmmmm至于剩下的插入，删除，还有封装等我会了在填坑吧！！！就酱
我回来填坑啦
大概算是首次填坑？？？？？
大概重新写了一遍又有了新的感悟吧，这算不算填坑啊【苦恼】，有时间废话还不如直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#include < stdio.h>
#include < stdlib.h>
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkedList;
LinkedList LinkedListInit()
{
Node *L;
L = new Node;
if(L == nullptr)
printf("申请内存空间失败/n");
L->next = nullptr;
}
LinkedList LinkedListCreatH()
{
Node *L;
L = new Node;
L->next = nullptr;
ElemType x;
while(scanf("%d",&x) != EOF)
{
Node *p;
p = new Node;
p->data = x;
p->next = L->next;
L->next = p;
}
return L;
}
LinkedList LinkedListCreatT()
{
Node *L;
L = new Node;
L->next = nullptr;
Node *r;
r = L;
ElemType x;
while(scanf("%d",&x) != EOF)
{
Node *p;
p = new Node;
p->data = x;
r->next = p;
r = p;
}
r->next = nullptr;
return L;
}
LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)
{
Node *pre;
pre = L;
int tempi = 0;
for (tempi = 1; tempi < i; tempi++)
pre = pre->next;
Node *p;
p = new Node;
p->data = x;
p->next = pre->next;
pre->next = p;
return L;
}
LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
Node *p,*pre;
p = L->next;
while(p->data != x)
{
pre = p;
p = p->next;
}
pre->next = p->next;
free(p);
return L;
}
int main()
{
LinkedList list,start;
printf("请输入单链表的数据：");
list = LinkedListCreatH();
for(start = list->next; start != nullptr; start = start->next)
printf("%d ",start->data);
printf("/n");
printf("请输入单链表的数据：");
list = LinkedListCreatT();
for(start = list->next; start != nullptr; start = start->next)
printf("%d ",start->data);
printf("/n");
int i;
ElemType x;
printf("请输入插入数据的位置：");
scanf("%d",&i);
printf("请输入插入数据的值：");
scanf("%d",&x);
LinkedListInsert(list,i,x);
for(start = list->next; start != nullptr; start = start->next)
printf("%d ",start->data);
printf("/n");
printf("请输入要删除的元素的值：");
scanf("%d",&x);
LinkedListDelete(list,x);
for(start = list->next; start != nullptr; start = start->next)
printf("%d ",start->data);
printf("/n");
return 0;
}
|
话说与时代落后的老爷爷终于用上了nullptr【雾】
