1. 首页
  2. 文章中心
  3. 数据结构

数据结构—链表的前插法与后插法

98 阅读 0 评论
我是靠谱客的博主 安详大船，这篇文章主要介绍数据结构—链表的前插法与后插法，现在分享给大家，希望可以做个参考。

在进行单链表的基本运算之前必须先建立单链表，建立单链表的常用方法有两种：头插法建表和尾插法建表

头插法建表，从一个空表开始，读取字符数组a中的字符，生成新节点，将读取的数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头上，直到读完字符数组a的所有元素为止。

头插法建表虽然简单，但生成的链表中节点的次序和原数组的次序相反，若希望两者的次序一致，可采用尾插法建立

尾插法建表，该算法是将新节点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾节点

前插法

复制代码
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 int ElemType;
 
typedef struct Node {
    ElemType data;               
    struct Node *next;          
}Node,*LinkedList;

LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node)); 
    if(L == NULL) { 
        printf("申请内存空间失败n");
    }
    L->next = NULL;                  
 	return L;
}

LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   
    L->next = NULL;                     
     
    ElemType x;                         
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));    
        p->data = x;                      
        p->next = L->next;                    
        L->next = p; 
    }
    return L; 
} 

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) {
    Node *pre;                     
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                  
	}
    Node *p;                                
    p = (Node *)malloc(sizeof(Node));
    p->data = x; 
    p->next = pre->next;
    pre->next = p;
     
    return L;                           
} 

LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre;                    
    p = L->next;
    pre = L; 
	/**************************
		添加上 per = L; 就行了
		原因 : 刚开始 per 没有赋值如果删除第一个元素 
			   可能造成因为per为空指针的情况下指针失陪的情况 
	***************************/
	while(p->data != x) {               
        pre = p; 
        p = p->next;
    }
    pre->next = p->next;          
    free(p);
    return L;
} 

int findder(LinkedList L,int x) { //查找功能 
	/*
	* @ x 所要查找的值 
	* @ L 所要操作的链表
	* 返回 -1 时表示链表中没有所在得值 
	*/ 
	LinkedList start; int i = 1;
	L = L->next;
	for (start = L;start != NULL;start = start->next) {
		if ( start->data == x ) {
			return i;
		}
		i++;
	} 
	return -1;
}

LinkedList Delete(LinkedList L,int st,int en) { // 多组数据删除功能 
	/*
	* @ st 删除的起始位置 
	* @ en 删除的终止为止 
	* @ L 所要操作的的链表 
	*/
	bool flag1 = false;
	Node *per,*p;
	per = L;
	L = L->next; int i = 1;
	LinkedList start;
	for (start = L;start != NULL ; start = start->next ) {
		if ( st == i ) {
			flag1 = true;
		}
		if ( en == i ) {
			per->next = start->next;
			break;
		}
		i++;
		if ( !flag1 )
			per = start;
	}
	return L;
}

int main() {
    LinkedList list,start;
 	printf("请输入单链表的数据："); 
   	list = LinkedListCreatH();
	for(start = list->next; start != NULL; start = start->next) {
		printf("%d ",start->data);
	}
	printf("n");
    int i;
    ElemType x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("n");
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x); 
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("n"); 
    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
#include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;
 
typedef struct Node {
    ElemType data;               
    struct Node *next;          
}Node,*LinkedList;

LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node)); 
    if(L == NULL) { 
        printf("申请内存空间失败n");
    }
    L->next = NULL;                  
 	return L;
}

void LinkedListCreatH(LinkedList &list) {
    Node *L,*s;
    list = new Node; list->next = NULL;
    L = list; ElemType x;
    while ( ~scanf("%d",&x) ) {
    	s = new Node;	
    	s->data = x; s->next = L->next; L->next = s;
    	L = s;
	}
} 

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) {
    Node *pre;                     
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                  
	}
    Node *p;                                
    p = (Node *)malloc(sizeof(Node));
    p->data = x; 
    p->next = pre->next;
    pre->next = p;
     
    return L;                           
} 

LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre;                    
    p = L->next;
    pre = L;
    while(p->data != x) {               
        pre = p; 
        p = p->next;
    }
    pre->next = p->next;          
    free(p);
    return L;
} 

int main() {
    LinkedList list,start;
 	printf("请输入单链表的数据："); 
   	LinkedListCreatH(list);
	for(start = list->next; start != NULL; start = start->next) {
		printf("%d ",start->data);
	}
	printf("n");
    int i;
    ElemType x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("n");
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x); 
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("n"); 
    return 0;
}

最后

以上就是安详大船最近收集整理的关于数据结构—链表的前插法与后插法的全部内容，更多相关数据结构—链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(65)

相关文章

apache poi读取excel中的颜色,真是坑爹啊
apache poi读取excel中的颜色,真是坑爹啊
排序算法02——插入排序(直接、折半)、快速排序
排序算法02——插入排序(直接、折半)、快速排序
插入排序
插入排序
【数据结构】内部排序之插入排序（直接插入排序，折半插入排序，希尔排序）直接插入排序折半插入希尔排序
【数据结构】内部排序之插入排序（直接插入排序，折半插入排序，希尔排序）直接插入排序折半插入希尔排序
数据结构—链表的前插法与后插法
数据结构—链表的前插法与后插法
插入排序2------折半插入排序
插入排序2------折半插入排序
算法之排序 插入排序（二）折半插入排序
算法之排序 插入排序（二）折半插入排序
直接插入法（和理牌一样的方法）
直接插入法（和理牌一样的方法）

评论列表共有 0 条评论

立即
投稿
返回
顶部