数据结构第一次上鸡

因为代码搓得太烂了，所以也记录一下遇到的问题吧。。大佬绕过

上鸡要求：搓个链表，然后实现增删改查、冒泡排序、约瑟夫问题、一元多项式计算

代码大杂烩。。

增删改查

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
#include<stdio.h>
#include<malloc.h>
struct Node{
	int data;
	struct Node *next=NULL;
};

void Init(struct Node *&L,int x[],int len){
	struct Node* p=((struct Node*)(malloc(sizeof(struct Node))));
	int i=0;
	L=p;
	for(i = 0;i<len;i++){
		p->data=x[i];
		p->next=((struct Node*)(malloc(sizeof(struct Node))));
		p=p->next;
}
	p->next=NULL;
	printf("初始化成功！\n");
	return;
}

void Insert(struct Node *&L,int num,int d){
	int i=0;
	struct Node *a=((struct Node*)(malloc(sizeof(struct Node))));
	struct Node *p=L;
	
	while(i<num-1){
		p=p->next;
		i++;				
	}
	a->next=p->next;
	p->next=a;
	a->data=d;
	printf("插入成功！\n");
	return;
}

void Delete(struct Node *&L,int num){
	int i=0;
	Node *p=L;
	if(num==0){
		L=L->next;
		return;
	}
	while(i<num-1){
		p=p->next;
		i++;
	}
	p->next=(p->next)->next;
	printf("删除成功！\n");
	return;
}

void Print(struct Node *L){
	struct Node* trans=L;
	if(trans->next==NULL){
		printf("empty list!\n");
		return;
	}
	while(trans!=NULL){
		printf("%d\n",trans->data);
		trans=trans->next;
		if(trans->next==NULL)
			break;
	}

	printf("显示完毕\n"); 
	return;
}

int main(){
	struct Node *L;
	int num=5,data=12;
	int x[]={1,2,3,4,5,0}; 
	printf("初始化：\n");
	Init(L,x,5);
	Print(L);
	printf("向下标为2处插入元素12：\n");
	Insert(L,2,data);
	Print(L);
	printf("依次删除元素：\n");
	for(int i=-1;i<8;i++){
		Delete(L,0);
		Print(L);
	}	
}

约瑟夫问题(损版)

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include<stdio.h>
#include<malloc.h>
struct Node{
	int data;
	struct Node *next=NULL;
};
void Init(struct Node *&L,int x[],int len){
	struct Node*p=((struct Node*)(malloc(sizeof(struct Node))));
	int i=0;
	L=p;
	for(i = 0;i<len;i++){
		p->data=x[i];
		p->next=((struct Node*)(malloc(sizeof(struct Node))));
		p=p->next;
}
	p->next=NULL; 
	printf("Fini5h3d\n");
	return;
}

int Length(Node *L){
	int i=0;
	
	while(L->next!=NULL){
		i++;
		L=L->next;
	}
	return i;
}

void Insert(struct Node *&L,int num,int d){
	int i=0;
	struct Node *a=((struct Node*)(malloc(sizeof(struct Node))));
	struct Node *p=L;
	while(i<num-1){
		p=p->next;
		i++;		
	}
	a->next=p->next;
	p->next=a;
	a->data=d;
	printf("1n53rt 5ucc355!\n");
	return;
}
void Delete(struct Node *&L,int num){
	int i=0;
	Node *p=L;
	shit3:	if(num<0){
		num=num+Length(*&L);
		goto shit3;
	}
	if(num>=Length(*&L)){
			num=num%Length(*&L);
	}
	if(num==0){
		L=L->next;
		return;
	}
	while(i<num-1){
		p=p->next;
		i++;
	}
	p->next=(p->next)->next;
	//printf("D3l3t3 5ucc3553d!\n");
	return;
}
void Print(struct Node *L){
	struct Node* trans=L;
	if(trans->next==NULL){
		printf("empty list!\n");
		return;
	}
	while(trans->next!=NULL){
		printf("%d\n",trans->data);
		trans=trans->next;
	}
	printf("Pr1nt f1n15h3d\n");
	return;
}
void ChangeSpace(Node *&L,int a1,int a2){
	Node *p=L;
	Node *q=L;
	int i; 	
	for(i=0;i<a1;i++){
		p=p->next;   //此时p到了下标a处	
	}
	for(i=0;i<a2;i++){
		q=q->next; 
	}
	i=p->data;
	p->data=q->data;
	q->data=i;	
	return;
}


void Sorted(Node *&L){
	int i,j,k,t;
	Node *p=L;
	int len=Length(*&L);
	for(i=0;i<len-1;i++){
		p=L;
		for(j=0;j<len-1;j++){
			if(p->data<p->next->data){
				t=p->data;
				p->data=p->next->data;
				p->next->data=t;				 
			}
			
			p=p->next;
		}
	}
	printf("fini5h3d\n");						
	return;	
}

int GetItem(Node *L,int x){
	int i;
	//printf("Get:Length=%d,x=%d\n",Length(*&L),x);
shit1:	if(x<0){
		x=x+Length(*&L);
		goto shit1;
	}
	if(x>=Length(*&L)){
			x=x%Length(*&L);
	}
	if(x==0){
		return L->data;
	}
	for(i=0;i<x;i++){
		L=L->next;
	}
	//printf("G3t 5ucc3553d,return=%d\n",L->data);
	return L->data;
}

int IfEmpty(Node *L){
	if(L->next==NULL)
		return 1;
	else
		return 0;
}

void Josephus(int n, int k,int a[]){
	Node *head, *p, *q;
	head = NULL;
	for(int i = 1; i <= n; ++ i){
		p = (Node*)malloc(sizeof(Node));
		p->data = a[i];
		p->next = NULL;
		if(head==NULL){
			head = p;
		}else{
			q->next = p;
		}
		q = p;
	}
	p->next = head;  //形成循环链表
	p = head;
	while(p->next!=p){ // 条件不成立时循环链表中只有一个结点
		for(int i = 1; i < k; ++ i){
			q = p;
			p = p->next;
		}
		q->next = p->next;  
		printf("%d ", p->data);
		free(p); 	  
		p = q->next;  // 新一轮计数的起点  
	}
	printf("%d", p->data);
	return;
}




int main(){
	struct Node *L;
	int i,num,a[30],m,x;
shit:	printf("请输入初始报数上限数：\n");
	scanf("%d",&num);
	if(num>30){
		printf("err0r!!\n");
		goto shit;
	}
	printf("请输入数组：\n");
	for(i=0;i<num;i++){
		scanf("%d",&x);
		a[i]=x;
	}
	Init(*&L,a,num);
	Print(*&L);
	printf("请输入随机数m：\n");
	scanf("%d",&m);
	Josephus(num,m,a);
}

列表排序

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
#include<stdio.h>
#include<malloc.h>
struct Node{
	int data;
	struct Node *next=NULL;
};
void Init(struct Node *&L,int x[],int len){
	struct Node*p=((struct Node*)(malloc(sizeof(struct Node))));
	int i=0;
	L=p;
	for(i = 0;i<len;i++){
		p->data=x[i];
		p->next=((struct Node*)(malloc(sizeof(struct Node))));
		p=p->next;
}
	p->next=NULL; 
	printf("Fini5h3d\n");
	return;
}
void Insert(struct Node *&L,int num,int d){
	int i=0;
	struct Node *a=((struct Node*)(malloc(sizeof(struct Node))));
	struct Node *p=L;
	while(i<num-1){
		p=p->next;
		i++;				
	}
	a->next=p->next;
	p->next=a;
	a->data=d;
	printf("插入成功！\n");
	return;
}
void Delete(struct Node *&L,int num){
	int i=0;
	Node *p=L;
	if(num==0){
		L=L->next;
		return;
	}
	while(i<num-1){
		p=p->next;
		i++;
	}
	p->next=(p->next)->next;
	printf("删除成功！\n");
	return;
}
void Print(struct Node *L){
	struct Node* trans=L;
	if(trans->next==NULL){
		printf("empty list!\n");
		return;
	}
	while(trans->next!=NULL){
		printf("%d\n",trans->data);
		trans=trans->next;
	}
	printf("显示完毕\n");
	return;
}
void ChangeSpace(Node *&L,int a1,int a2){
	Node *p=L;
	Node *q=L;
	int i; 	
	for(i=0;i<a1;i++){
		p=p->next;   //此时p到了下标a处	
	}
	for(i=0;i<a2;i++){
		q=q->next; 
	}
	i=p->data;
	p->data=q->data;
	q->data=i;	
	return;
}

int Length(Node *L){
	int i=0;
	
	while(L->next!=NULL){
		i++;
		L=L->next;
	}
	return i;
}



void Sorted(Node *&L){
	int i,j,k,t;
	Node *p=L;
	int len=Length(*&L);
	for(i=0;i<len-1;i++){
		p=L;
		for(j=0;j<len-1;j++){
			if(p->data<p->next->data){
				t=p->data;
				p->data=p->next->data;
				p->next->data=t;
				 
			}
			
			p=p->next;
		}
	}
	printf("fini5h3d!!\n");						
	return;	
}

int main(){
	struct Node *L;
	int num=5,data=12,x[]={3,7,6,1,5,9,10},len=sizeof(x)/sizeof(num); 
	printf("初始化：\n");
	Init(L,x,len);
	Print(L);
	printf("排序\n");
	Sorted(*&L);
	Print(L);
}

关于L和&L的区别

我定义了个链表结构体Node，并声明了一个结构体指针L，然后定义1个初始化函数Init()，将L作为参数传进去，结果函数运行结束后发现，L的next和data地址的值并未改变，即函数里对L的修改出了函数就没卵用了

经查阅资料发现，原理是：将结构体指针传入函数时，函数内会做一个copy，但此时函数内的L和函数外的L指向的地址8一样，所以导致里面变化而外面不变

解决方法：传参时，将结构体指针的引用传过去，当传入函数的参数规定为*&L时，将改变传入实参的值，为*L时，8会改变值

参考
csdn

&，引用

地址是在电脑内存中的地址（变量的值在内存中的储存位置），指针是存地址的变量，所以指针可以“指向”内存地址。概念上讲，引用变量本质上是指针的另一个名字（但是并不能被编译器实例化）。。。wtf???这玩意你他妈不是学过吗?

就把引用当成变量的另一个名字就好

寄科 > 编程
#寄科
数据结构第一次上鸡
https://bl4zygao.github.io/2021/09/26/数据结构-链表的上鸡报告/
Author
bl4zy
Posted on
September 26, 2021
Licensed under