线性表的链式存储结构——链表学习记录_struct listnode *head = (struct listnode*)malloc(s

链表总结

一.链表的创建

1.若使用形如函数struct ListNode* createListtail()，此函数中为头结点申请好了空间，在主函数中定义好类型即可使用。例如下面代码中L1的尾插法创建

struct ListNode*L1;

L1=createListtail();

2.若使用形如函数 struct ListNode* createListhead(struct ListNode* L),此函数为头结点后的结点申请空间，需要传入头结点。例如下面代码中L2的头插法创建

struct ListNode*L2=(struct ListNode*)malloc(sizeof(struct ListNode));

L2=createListhead(L2);使用较为麻烦不清晰，不推荐使用。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct ListNode{
	int val;
	struct ListNode* next;
}ListNode;

struct ListNode* createListtail(){/*尾插创建含头结点的链表，输入-1终止。 */
	int n;
	scanf("%d",&n);
	struct ListNode*head=(struct ListNode*)malloc(sizeof(struct ListNode)),*p=head;
	head->next=NULL; 
	while(n!=-1){
		p ->next = (struct ListNode*)malloc(sizeof(struct ListNode));
		p=p->next;
		p->val=n; 
		p->next=NULL; 
		scanf("%d",&n);
	}
	return head;
}

struct ListNode* createListhead(struct ListNode* L){/*头插创建含头结点的链表，输入-1终止。 */
	int n;
	L->next=NULL;
	scanf("%d",&n);
	struct ListNode*head=L,*p=head; 
	while(n!=-1){
		struct ListNode*p=(struct ListNode*)malloc(sizeof(struct ListNode));
		p->next=head->next;
		p->val=n; 
		head->next=p; 
		scanf("%d",&n);
	}
	return head;
}

void printList (struct ListNode* L)			/*输出链表结点值*/ 
{
	if(L == NULL)
	{
		printf("NULL\n");
		return ;
	}
	while (L)
	{
		printf("%d ", L->val);
		L = L->next;
	}
	printf("\n");
} 

struct ListNode* Addnode(struct ListNode* L,int index,int e){		/*在第index位插入值位e的结点*/	
	struct ListNode*p=L;
	while(index-1){
		p=p->next;
		index--;
	}
	struct ListNode*Next=p->next;
	p->next=(struct ListNode*)malloc(sizeof(struct ListNode));
	p=p->next;
	p->val=e;
	p->next=Next;
	return L;
}

int lenlist(struct ListNode* L){								/*返回链表长度（结点数）*/
	struct ListNode*p=L;
	int count=0;
	while(p){
		p=p->next;
		count++;
	}
	return count;
}

int Getelem(struct ListNode* L,int index,int e){			/*返回第index个结点的值*/	
	if(index>lenlist(L))  
		return -1;
	struct ListNode*p=L;
	while(index-1){
		p=p->next;
		index--;
	}
	return p->val;
}

void listreverse(struct ListNode*L	)						/*含头结点链表逆置*/
{										
	struct ListNode*p=L->next,*temp;						/*声明一个临时结点，将临时结点插入头结点之前*/ 
	L->next=NULL;
	while(p){
		temp=p;
		p=p->next;
		temp->next=L->next;
		L->next=temp;
	}
}

struct ListNode* removefromend(struct ListNode* L, int n){		/*删除链表倒数第n个结点*/
	int k=n;
	if(n>lenlist(L)) return NULL;
	struct ListNode*p=L,*p1=L;									/*p1快指针，p慢指针*/ 
	while(k+1){													/*p1多走一步p2就少走一步，最终p2可以到达删除结点的前一个结点*/ 
		p1=p1->next;
		k--;		
	}	
	while(p1){														
		p=p->next;												/*p1为NULL时p走到倒数第n+1个结点*/
		p1=p1->next;
	}
	p1=p->next;													/*p1位倒数第n个结点*/
	p->next=p1->next; 
	free(p1);
	return L;
}

int main(){
	struct ListNode*L1,*L2=(struct ListNode*)malloc(sizeof(struct ListNode));
	L2->next=NULL;
	
	printf("尾插法创建链表L1，输入-1终止\n");
	L1=createListtail();/*创建含头结点的链表 */ 
	printf("链表L1输出如下：\n");
	printList(L1->next);
	printf("L1链表长度为%d（不含头结点）\n",lenlist(L1));
	
	Addnode(L1,2,999);
	printf("尾插法在第二位插入999后输出如下\n");
	printList(L1->next);
	printf("此时L1链表长度为%d（不含头结点）\n",lenlist(L1)-1);
	
	printf("头插法创建链表L2，输入-1终止\n");
	L2=createListhead(L2);
	printf("链表L2输出如下：\n");
	printList(L2->next);
	printf("L2链表长度为%d（不含头结点）\n",lenlist(L2)-1);
	
	Addnode(L2,2,999);
	printf("在第二位插入999后输出如下\n");
	printList(L2->next);
	printf("此时L2链表长度为%d（不含头结点）\n",lenlist(L2)-1);
	
	printf("逆置（不含头结点）链表L2后输出\n");
	listreverse(L2);
	printList(L2->next);

	printf("删除链表的倒数第2个结点后输出\n");
	removefromend(L2,2);
	printList(L2->next);
	
	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
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

#include<stdio.h>

struct Listnode{
	int val;
	struct Listnode*next;
}Listnode; 

struct Listnode* addbytail(struct Listnode*L){
	int n=0;
	scanf("%d",&n);
	struct Listnode*head=L,*p=head;
	while(n!=-1)
	{
		p->next=(struct Listnode*)malloc(sizeof(struct Listnode));	
		p=p->next;
		p->val=n;
		p->next=NULL;
		scanf("%d",&n);
	}
	return head;
}

struct Listnode* addbyhead(struct Listnode*head){
	int n=0;
	scanf("%d",&n);
	head=(struct Listnode*)malloc(sizeof(struct Listnode));
	head->next=NULL;
	while(n!=-1)
	{
		struct Listnode*p=(struct Listnode*)malloc(sizeof(struct Listnode));	
		p->val=n;
		p->next=head->next;
		head->next=p;
		scanf("%d",&n);
	}
	return head;
}

void printlist(struct Listnode*L)
{
	struct Listnode*p=L->next;
	while(p)
	{
		printf("%d ",p->val);
		p=p->next;
	}
	printf("\n");
}

void denode(struct Listnode* head,int target)
{
	struct Listnode* p=head,*c=head->next;
	while(c)
	{
		if(c->val==target)
		{
			p->next=c->next;
			free(c);
			c=p->next;
		}else{
			c=c->next;
			p=p->next;
		}
	}	
}

struct Listnode* mergeandarrange(struct Listnode* L1,struct Listnode* L2){
	struct Listnode*head=(struct Listnode*)malloc(sizeof(struct Listnode)),*p=L1->next;
	head->next=NULL;
	while(p->next)
	{
		p=p->next;
	}
	p->next=L2->next;
	
	struct Listnode*q=NULL;
	for(p=L1->next;p;p=p->next){
		for(q=p->next;q;q=q->next){
			if(q->val>p->val)
			{
				int t=q->val;
				q->val=p->val;
				p->val=t;
			}
		}
	}
	
	head->next=L1->next;
	return head;
}

struct Listnode*fanzhuan(struct Listnode*L){
	struct Listnode*newhead=(struct Listnode*)malloc(sizeof(struct Listnode)),*c=L->next,*p=newhead;
	newhead->next=NULL;
	
	while(c){
		struct Listnode*NEXT=c->next;
		c->next=p->next;
		p->next=c;
		c=NEXT;		
	}
	return p;
}

void listreverse(struct Listnode*L	)						/*含头结点链表逆置*/
{										
	struct Listnode*p=L->next,*temp;						/*声明一个临时结点，将临时结点插入头结点之前*/ 
	L->next=NULL;
	while(p){
		temp=p;
		p=p->next;
		temp->next=L->next;
		L->next=temp;
	}
}

int main()
{
	struct Listnode*L1=(struct Listnode*)malloc(sizeof(struct Listnode)),*L2;
	L1=addbytail(L1);
	printlist(L1);
	L2=addbyhead(L2);
	printlist(L2);
	denode(L2,2);
	printlist(L2);
	struct Listnode*L3;
	L3 = mergeandarrange(L1,L2);
	printlist(L3);
	struct Listnode*L4=(struct Listnode*)malloc(sizeof(struct Listnode));
	L4=addbytail(L4);
	printlist(L4);
	listreverse(L4);
	printlist(L4);
	struct Listnode*L5=fanzhuan(L4);
	printlist(L5);
}
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