数据结构-单链表(C语言)_形如下面的整型单链表类型: struct linknode { int data; linknode

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、单链表的定义

单链表是一种链式存取的数据结构 ，用一组地址任意的存储单元 ，来存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：数据域 + 指针域，数据域就是存储数据的存储单元，指针域存放的就是连接每个结点的地址数据。

二、单链表的操作

1.定义节点

对于每个链表结点，除了存放元素自身的信息的数据域外，还需要一个存放指向其后继的指针域。

typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}LNode,*Linklist,*NodePtr;
1
2
3
4

2.初始化

通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。如下图所示：

头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的第一个结点，而头结点是带头结点的单链表中的第一个结点，结点内通常不存储信息。

Linklist initLinklist(){
	NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));
	tempHeader->data='\0';
	tempHeader->next=NULL;
	return tempHeader;
} 
1
2
3
4
5
6

3.打印链表

声明一个指针p，从头结点指向的第一个结点开始，如果p不为空，那么就输出当前结点的值，并将p指向下一个结点，直到遍历到最后一个结点为止。

void printlist(NodePtr pheader){
	NodePtr p=pheader->next;
	while(p){
		printf("%c",p->data);
		p=p->next;
	}
	printf("\r\n");
	
}
1
2
3
4
5
6
7
8
9

4、尾插法

首先声明两个指针变量p,q,创建一个新的节点赋值给q,然后从头节点指向的第一个节点开始，直到找到最后一个节点，将q的地址存入最后一个节点的指针域，此时节点q变为最后一个节点。

void addElement(NodePtr pheader,char pchar){ //尾插法 
	NodePtr p,q;
	q=(NodePtr)malloc(sizeof(LNode));  //创建一个新的节点
	q->data=pchar;
	q->next=NULL;
	
	p=pheader;
	while(p->next!=NULL){
		p=p->next; 
	}   //找到最后一个位置 
	
	p->next=q; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5、指定位置插入

声明两个指针变量p,q.
1、判断指定位置是否合法，是否在链表范围内.
2、通过循环找到指定位置的前一个节点p.
3、创建新节点并赋值给q,q的数据域为要插入的元素，q指针域指向p节点的下一个节点.
4、修改p的指针域，p的指针域指向q.

void insertElement(NodePtr pheader,char pchar,int position){  //指定位置插入 
	NodePtr p,q;
	p=pheader;
	if(position<0){
		printf("指定位置非法.\n"); 
		return;
	}
	
	int i;
	for(i=0;i<position;i++){
		p=p->next;
		if(p==NULL){
			printf("The position is beyond the list.\n");
			return; 
		}
	} 
	
	q=(NodePtr)malloc(sizeof(LNode));
	q->data=pchar;
	q->next=p->next;
	p->next=q;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6、指定数据删除

1、循环遍历链表，找到存放指定数据的前一个节点p.
2、修改p的指针域：将p的指针域赋值为第（p+1）个节点的指针域，即p的指针域指向第（p+2)个节点.（删除实质：覆盖节点）
3、释放被覆盖节点.

void deleteElement(NodePtr pheader,char pchar){
	NodePtr p,q;
	p=pheader;
	while(p->next!=NULL && p->next->data!=pchar){
	p=p->next;		
	}
	
	if(p->next==NULL){
		printf("元素不在链表中，无法删除.\n");
		return;
	}
	
	q=p->next;
	p->next=p->next->next;
	free(q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7、指定数据修改

逻辑同上

void change(NodePtr pheader,char Achar,char pchar){
	NodePtr p;
	p=pheader;
	while(p->next!=NULL && p->next->data!=Achar){
		p=p->next;
	}
	if(p->next==NULL){
		printf("元素不在链表内.\n");
	}
	p->next->data=pchar;
}
1
2
3
4
5
6
7
8
9
10
11

三、完整代码

#include<stdio.h>
#include<malloc.h>

typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}LNode,*Linklist,*NodePtr;


Linklist initLinklist(){
	NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));
	tempHeader->data='\0';
	tempHeader->next=NULL;
	return tempHeader;
} 

void printlist(NodePtr pheader){
	NodePtr p=pheader->next;
	while(p){
		printf("%c",p->data);
		p=p->next;
	}
	printf("\r\n");
	
}

void addElement(NodePtr pheader,char pchar){ //尾插法 
	NodePtr p,q;
	q=(NodePtr)malloc(sizeof(LNode));  //创建一个新的节点
	q->data=pchar;
	q->next=NULL;
	
	p=pheader;
	while(p->next!=NULL){
		p=p->next; 
	}   //找到最后一个位置 
	
	p->next=q; 
}

void insertElement(NodePtr pheader,char pchar,int position){  //指定位置插入 
	NodePtr p,q;
	p=pheader;
	if(position<0){
		printf("指定位置非法.\n"); 
		return;
	}
	
	int i;
	for(i=0;i<position-1;i++){
		p=p->next;
		if(p==NULL){
			printf("The position is beyond the list.\n");
			return; 
		}
	} 
	
	q=(NodePtr)malloc(sizeof(LNode));
	q->data=pchar;
	q->next=p->next;
	p->next=q;
} 

void deleteElement(NodePtr pheader,char pchar){
	NodePtr p,q;
	p=pheader;
	while(p->next!=NULL && p->next->data!=pchar){
	p=p->next;		
	}
	
	if(p->next==NULL){
		printf("元素不在链表中，无法删除.\n");
		return;
	}
	
	q=p->next;
	p->next=p->next->next;
	free(q);
}

void add_insert_deleteText(){
	Linklist templist=initLinklist();
	printlist(templist);
	
	addElement(templist,'h');
	addElement(templist,'e');
	addElement(templist,'l');
	addElement(templist,'l');
	addElement(templist,'o');
	addElement(templist,'!');
	printlist(templist);
	
	deleteElement(templist,'e');
	deleteElement(templist,'a');
	deleteElement(templist,'o');
	printlist(templist);
	
	insertElement(templist,'G',1);
	printlist(templist);
	
}

void insertElement_Text(){
	Linklist templist=initLinklist();
	printlist(templist);
	
	addElement(templist,'h');
	addElement(templist,'e');
	addElement(templist,'l');
	addElement(templist,'l');
	addElement(templist,'o');
	addElement(templist,'!');
	printlist(templist);
	
	insertElement(templist,'H',-1);
	printlist(templist);
	insertElement(templist,'H',6);
	printlist(templist);
	insertElement(templist,'H',5);
	printlist(templist);
}
int main()
{
	add_insert_deleteText();
	insertElement_Text();
}
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

运行结果：

hello!
元素不在链表中，无法删除.
hll!
Ghll!

hello!
指定位置非法.
hello!
helloH!
hellHoH!

hello!
元素不在链表内.
hello!
h2llo!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15