链表基本操作复习

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//定义结点
typedef struct NODE
{
int key;
struct NODE * next;
} node,*List;
List init_list();//初始化链表
List list_insert(List list,int key);//向链表插入节点，尾插法
List list_insertBypos(List list,int pos,int key);//向链表指定位置插入结点
void print_list(List list);//打印链表
int cal_list_length(List list);//计算链表长度
node *find_node(List list,int pos);//寻找指定位置结点
List dele_node(List list,int pos);//删除指定位置结点
List sort_list(List list);//对链表排序
List init_list()
{
List list=(List)malloc(sizeof(node));
list->next=NULL;
return list;
}
List list_insert(List list,int key)
{
node *temp;
temp=list;
node *tail=(node *)malloc(sizeof(node));
while(temp->next)
{
temp=temp->next;
}
tail=temp;
node *p=(node *)malloc(sizeof(node));
p->key=key;
p->next=NULL;
tail->next=p;
tail=p;
return list;
}
int cal_list_length(List list)
{
node *p=list->next;
int length=0;
while(p)
{
p=p->next;
length++;
}
return length;
}
void print_list(List list)
{
node *p=list->next;
while(p)
{
printf("%d
",p->key);
p=p->next;
}
}
List list_insertBypos(List list,int pos,int key)
{
int i=0,list_length=0;
node * p,* temp;//p指向要插入位置之前，temp指向要插入位置之后的链表
p=list->next;
list_length=cal_list_length(list);
if(pos<0||pos>list_length)
{
printf("插入位置不合法");
return list;
}
while(i<pos-1)
{
p=p->next;//将p指向要插入位置之前
i++;
}
node *q=(node *)malloc(sizeof(node));
q->key=key;
temp=p->next;
p->next=q;
q->next=temp;
return list;
}
node *find_node(List list,int pos)
{
int count=0;
node *temp;
temp=list->next;
while(count<pos)
{
temp=temp->next;
count++;
}
return temp;
}
List dele_node(List list,int pos)
{
List l=list;
node *pre=find_node(l,pos-1);//找到待删除结点的前驱
node* temp;
temp=pre->next;
pre->next=pre->next->next;
free(temp);
return list;
}
List sort_list(List list)//采用最简答的排序，即将当前结点逐个和后面的结点比较大小
{
int i=0,j=0;
node* link=list->next;
node* temp,* pointer;
int length=cal_list_length(list);
for( i=0;i<length;i++,link=link->next)
{
for( j=i+1,pointer=link->next;j<length;j++,pointer=pointer->next)
{
if(link->key>pointer->key)
{
temp->key=link->key;
link->key=pointer->key;
pointer->key=temp->key;
}
}
}
return list;
}
int main()
{
List list=init_list();
list=list_insert(list,1);
list=list_insert(list,12);
list=list_insert(list,6);
list=list_insert(list,8);
list=list_insert(list,4);
list=list_insertBypos(list,2,10);
//node *f_node=find_node(list,2);
//printf("找到2号位置的结点值为：%dn",f_node->key);
int length=cal_list_length(list);
printf("链表长度为：%dn",length);
print_list(list);
printf("n");
printf("删除2号位置结点n");
list=dele_node(list,2);
length=cal_list_length(list);
printf("链表长度为：%dn",length);
print_list(list);
printf("n");
printf("排序后链表为");
list=sort_list(list);
print_list(list);
}