数据结构：不带头结点的单链表相关操作_不带头结点的单链表求表长

作者：繁依Fanyi0 | 2024-04-30 22:29:41

踩

不带头结点的单链表求表长

顺序结构和链式结构的优缺点：
顺序结构：
1. 查找效率高
2. 插入删除效率低
3. 内存连续，碎片小空间多
链式结构：
1.查找效率低
2.插入删除效率高
3.内存不一定连续，空间利用率高

[1] 单链表（不带头结点）

尾插法创建单链表

/*
 * 函数原型：Node* create_linkList1();
 * 功能说明：尾插创建链表
 * 参数说明：无
 */
Node* create_linkList1(){
	Node *head =NULL;
	Node *p = NULL;
	Node *tail = NULL;
	int x;
	scanf("%d",&x);
	while(getchar()!='\n');
	while(x){
		p = (Node*)malloc(sizeof(Node));
		if(p == NULL){
			printf("Error:内存分配失败");
			exit(-1);
		}
		/*数据域赋值*/
		p->data = x;
		/*指针域先指向NULL*/
		p->next = NULL;
		/*判断链表是否为空*/
		if(head == NULL){
			head = p;
		}
		else{
			tail->next = p; 
		}
		/*尾指针指向新创建的节点*/
		tail = p;
		scanf("%d",&x);
		while(getchar()!='\n');
	}
	return head;
}
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

头插法创建单链表

/*
 * 函数原型：Node* create_linkList2();
 * 函数说明：头插创建链表
 * 参数说明：无
 */
Node* create_linkList2(){
	Node *head = NULL;
	Node *p = NULL;
	int x;
	scanf("%d",&x);
	while(getchar()!='\n');
	while(x){
		p = (Node*)malloc(sizeof(Node));
		if(p == NULL){
			printf("Error:内存分配失败");
			exit(-1);
		}
		/*数据域赋值*/
		p->data = x;
		/*指针域保存head的地址*/
		p->next = head;
		/*head保存新节点的地址*/
		head = p;
		scanf("%d",&x);
		while(getchar()!='\n');
	}
	return head;
}
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

计算链表表长

/* 
 * 函数原型：int linkList_length(Node* head)
 * 功能说明：计算链表长度
 * 参数说明：head：链表头指针
 */
int linkList_length(Node* head){
	int count = 0;
	while(head != NULL){
		count++;
		head = head->next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

按照节点序号查找链表元素

/* 
 * 函数原型：Node *linkList_search(Node* head,int index)
 * 功能说明：根据节点序号查找链表元素
 * 参数说明：head：链表头指针，index：要查找的节点序号
 * 其他：节点序号从1开始
 */
Node *linkList_search(Node* head,int index){
	/*入参检测*/
	if(head == NULL || index < 1 || index > linkList_length(head)){
		return NULL;
	}
    /*节点序号=1，返回head；若节点序号为n(n>1),head依次指向下一节点递归n-1次*/
	return index==1?head:linkList_search(head->next,index-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入新节点

头插会改变head头指针的地址，所以要指针变量的地址传参，也就是形参用二级指针接收head指针的地址或者数值传参用返回值返回头指针新地址。
中间插和尾插入不会改变头指针地址
三种插入都是先把新节点的后面连接上，再断开原节点，连接左边节点

/*
 * 函数原型：void linkList_insert(Node **head,int index,int data)
 * 功能说明：插入新节点
 * 参数说明：*head：链表头指针，index：插入的位置，data：插入的数据
 */
void linkList_insert(Node **head,int index,int data){
    /*入参检测*/
    index < 1 ? index = 1 : ' ';
    index > linkList_length(*head)+1 ? index = linkList_length(*head)+1: ' ';
    /*分配内存*/
    Node *p = create_node();
    p->data = data;
    /*头插*/
    if(index == 1){ 
        p->next = *head;
        *head = p;
    }   
    /*中间插、尾插*/
    else{
        Node *find = linkList_search(*head,index-1);
        p->next = find->next;
        find->next = p;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

删除节点

与插入类似，要考虑头删会改变头指针指向的问题，中间删和尾删可以一同操作。

/*
 * 函数原型：void linkList_delete(Node **head,int index) 
 * 功能说明：删除指定节点
 * 参数说明：*head：链表头指针，index：删除的位置
 */
void linkList_delete(Node **head,int index){
	/*入参检测*/
	if(index < 1 || index > linkList_length(*head)){
		puts("Error：没有该节点");
		return;
	}
	Node *delete = NULL;
	/*头删*/
	if(index == 1){
		delete = *head;
		*head = (*head)->next;
		free(delete);
	}
	/*中间删、尾删*/
	else{
		Node *find = linkList_search(*head,index-1);
		delete = find->next;
		find->next = delete->next;
		free(delete);
	}
}
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

链表反转操作

将原链表节点从头开始一个个拿出来，头插进新链表。

/*
 * 函数原型：void linkList_reverse(Node **head)
 * 功能说明：反转链表
 * 参数说明：*head：原链表头指针
 */
void linkList_reverse(Node **head){
    Node *newhead = NULL,*p = NULL;
    while(*head != NULL){
        p = *head;
        *head = (*head)->next;
        p->next = newhead;
        newhead = p;
    
    }   
    *head = newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

链表的排序（升序）

#include <stdio.h>
#include "linklist.h"

Node *find_max(Node *head){
	Node *pmax = head;
	while(head != NULL){
		if(pmax->data < head->data){
			pmax = head;
		}
		head = head->next;
	}
	return pmax;
}
void move_max(Node **head, Node *pmax){
	if(pmax == NULL){
		puts("Error：空链表");
		return;
	}
	if(pmax == *head){
		*head = (*head)->next;
		return;
	}
	else{
		Node *find = *head;
		while(find->next != pmax) find = find->next;
		find->next = pmax->next;
	}
}

void add_newlist(Node **new_head,Node *pmax){
	pmax->next = *new_head;
	*new_head = pmax;
}
void linklist_sort(Node **head){
	struct node *new_head = NULL;
	struct node *pmax = NULL;
	while(*head != NULL)
	{
		/*从原链表中找到最大值*/
		pmax = find_max(*head);
		/*将最大值从旧链表中移除*/
		move_max(&(*head), pmax);
		/*将最大值加入新的链表*/
		add_newlist(&new_head, pmax);
	}
	*head = new_head;
}
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

链表的排序（降序：操作原链表实现）

/*
 * 函数原型：Node *find_max(Node *head,Node *first_pmax)
 * 函数功能：找出未排序节点中的最大值
 * 参数说明：head：链表头指针，first_pmax：第一次找出的最大值地址
 */
Node *find_max(Node *head,Node *first_pmax){
	Node *pmax = head;
	while(head != first_pmax){
		if(pmax->data < head->data){
			pmax = head;
		}
		head = head->next;
	}
	return pmax;
}
/*
 * 函数原型：void move_max(Node **head, Node *pmax)
 * 函数功能：从原链表中移除最大节点
 * 参数说明：*head：链表头指针，pmax：最大节点地址
 */
void move_max(Node **head, Node *pmax){
	if(pmax == NULL){
		puts("Error：空链表");
		return;
	}
	if(pmax == *head){
		*head = (*head)->next;
	}
	else{
		Node *find = *head;
		while(find->next != pmax) find = find->next;
		find->next = pmax->next;
	}
	pmax->next = NULL;
}
/*
 * 函数原型：void insert_to_tail(Node *head,Node *pmax)
 * 函数功能：把最大节点接到原链表末尾
 * 参数说明：head：头指针，pmax：最大节点地址
 */
void insert_to_tail(Node *head,Node *pmax){
	Node *find = head;
	while(find->next != NULL) find = find->next;
	find->next = pmax;
}
/* 
 * 函数原型：void linklist_sort1(Node **head)
 * 功能说明：每次找到最大数据节点从来，从链表中移除后，接到链表末尾,实现降序
 * 参数说明：*head：链表头指针
 */
void linklist_sort(Node **head){
	Node *new_head = NULL;
	Node *pmax = NULL;
	/*先找出最大值接到链表末尾*/
	Node *first_pmax = find_max(*head,NULL);	
	move_max(&(*head), first_pmax);
	insert_to_tail(*head,first_pmax);
	
    for(int i = 0;i < linkList_length(*head)-1;i++){
		/*继续从原链表中找到最大值*/
		pmax = find_max(*head,first_pmax);
		/*将最大值从原链表中移除*/
		move_max(&(*head), pmax);
		/*将最大值接到链表末尾*/
		insert_to_tail(*head,pmax);
	}
}
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

链表数据的文件保存和读取

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include "linklist.h"

void fileWrite(Node* head){
	FILE *fp = fopen("./list.txt","w");
	if(fp == NULL){
		perror("write");
		fclose(fp);
		exit(-1);
	}
	while(head != NULL){
			fprintf(fp,"%d\t",head->data);
			head = head->next;
	}
	fclose(fp);
}
int fileRead(Node **head){
	FILE *fp = fopen("./list.txt","r");
	if(fp == NULL){
		perror("write");
		exit(-1);
	}
	int temp,count = 0;
	Node *tail = NULL;
	while(EOF != fscanf(fp,"%d",&temp)){
		Node *p = create_node();
		p->data = temp;
		/*判断链表是否为空*/
		if(*head == NULL){
			*head = p;
		}
		else{
			tail->next = p; 
		}
		/*读取个数*/
		count++;
		/*尾指针指向新创建的节点*/
		tail = p;	
	}
	return count;
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/515604