ch2-线性表-链表的插入，删除，查找及更新操作

发表于 | 分类于 | 阅读次数： 
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
#include <stdio.h>
#include <stdlib.h>
typedef struct Link{
    int  elem;
    struct Link *next;
}link;
link * initLink();
//链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置
link * insertElem(link * p,int elem,int add);
//删除结点的函数，p代表操作链表，add代表删除节点的位置
link * delElem(link * p,int add);
//查找结点的函数，elem为目标结点的数据域的值
int selectElem(link * p,int elem);
//更新结点的函数，newElem为新的数据域的值
link *amendElem(link * p,int add,int newElem);
void display(link *p);
int main() {
    //初始化链表（1，2，3，4）
    printf("初始化链表为：\n");
    link *p=initLink();
    display(p);
  
    printf("在第4的位置插入元素5：\n");
    p=insertElem(p, 5, 4);
    display(p);
  
    printf("删除元素3:\n");
    p=delElem(p, 3);
    display(p);
  
    printf("查找元素2的位置为：\n");
    int address=selectElem(p, 2);
    if (address==-1) {
        printf("没有该元素");
    }else{
        printf("元素2的位置为：%d\n",address);
    }
    printf("更改第3的位置上的数据为7:\n");
    p=amendElem(p, 3, 7);
    display(p);
  
    return 0;
}
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
//插入元素函数，p为链表，elem为待插入的元素值，add为要插入的位置（从1开始）
link * insertElem(link * p,int elem,int add){
	//上来二话不说先搞个工作指针出来,并初始指向头结点
	link *temp=p;
	//首先得来到待插入位置的前一个元素的位置
	for(int i=1;i<add;++i){
		if(temp==NULL){
			printf("插入失败\n");
			return p;
		}
		//temp不是NULL时，工作指针temp就开始向前推进了
		//并且根据for循环设定的次数，temp最终会来到待插入位置的前一个位置
		temp=temp->next;
	}//关于这个for循环更详细的解释：当i=1时，temp可以到达头结点后面的第一个结点位置；
	//当i=2时，temp可以到达第二个结点位置
	//一直下去...
	//当i=add-1时，temp到达第add-1个结点位置，这正是我们的目标位置！
	//当i=add时，就退出循环了，不执行
	//***************//
	
	//现在，应该准备造一个结点出来了
	link *c=(link*)malloc(sizeof(link));
	c->elem=elem;
	//造好了结点，接下来就把它插入到add位置处
	//此时我们的工作指针已经在add-1处等候多时了
	c->next=temp->next;
	temp->next=c;
	//temp=c;//不必了，这又不是建立链表
	return p;
}

//删除链表中add（从1开始计数）处的结点
link * delElem(link * p,int add){
	//同样也先搞个工作指针出来并且初始指向头结点
	link *temp=p;
	//然后同理，让工作指针temp来到待删除结点的前一个结点所在位置处
	for(int i=1;i<add;++i){
		temp=temp->next;
	}//理解和前面一样：当i=1时，temp可以到达头结点后面的第一个结点位置；
	//当i=2时，temp可以到达第二个结点位置
	//一直下去...
	//当i=add-1时，temp到达第add-1个结点位置，这正是我们的目标位置！
	//当i=add时，就退出循环了，不执行
	//***************//
	//现在可以进行删除操作了
	link *q=temp->next;//q保存了待删除的结点,以便于回收内存；因为下面的操作仅仅是断开了q结点与链表p的链接关系，q结点索然已无用，但仍然存在于内存，所以最后要释放掉
	//开始删除啦
	temp->next=temp->next->next;//temp->next=q->next;
	////手动释放该结点，防止内存泄漏
	free(q);
	return p;
}

//查找某一指定元素elem在链表中的位置
int selectElem(link * p,int elem){
	//还是先搞个工作指针出来并初始指向头结点
	link *temp=p;
	//开始遍历链表进行查找
	int i=1;//i用来计数，即标明第几个位置
	while(temp->next!=NULL){
		temp=temp->next;//i=1时，temp到达头结点之后的第一个结点；i=2，temp到达第二个结点；i=p->length时，temp来到第p->length个结点（最后一个结点）
		if(temp->elem==elem) return i;	//找到则返回其位置
		i++;//每当运行至此，说明当前结点的元素值不等于elem，那么位置计数器i就自增1，开启下一次循环（if循环条件仍然满足的话）
	}
	return -1;//程序运行到这里说明查找失败
}

//更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
    link * temp=p;
    temp=temp->next;//tamp指向首元结点
    ////遍历到被删除结点,temp指向被删除结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->elem=newElem;//替换元素值
    return p;
}
void display(link *p){
    link* temp=p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp->next) {
        temp=temp->next;
        printf("%d ",temp->elem);
    }
    printf("\n");
}
凡希 wechat
喜欢所以热爱，坚持干货分享，欢迎订阅我的微信公众号
呐，请我吃辣条