C语言数据结构实现链表逆序并输出
将一个链表逆序并输出。我用了两种方法来实现，第一种是借助了一个新的空链表；第二种是在原来链表的基础上直接实现逆序。
实例代码：
头文件：
|
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
155
|
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int ElemType;
typedef struct Node
{//结点结构
ElemType value; //值域
struct Node *next;//指针域
}Node,*ptr_Node;
typedef struct LinkList
{//链表结构
ptr_Node head; //链表头结点指针
ptr_Node tail;//链表尾结点指针
int length; //链表长度
}LinkList,*ptr_LinkList;
ptr_LinkList CreateList(void)
{//创建一个空链表
ptr_LinkList linklist;
linklist=(LinkList *)malloc(sizeof(LinkList));
if(!linklist)
{
printf("allocation failed.\n");
}
linklist->head=NULL;
linklist->tail=NULL;
linklist->length=0;
return linklist;
}
bool IsListEmpty(ptr_LinkList linklist)
{//判断链表是否为空
if(linklist->length==0)
{
return true;
}
return false;
}
void InsertListHead(ptr_LinkList linklist,ElemType element)
{//在表头插入值为element的结点作为新的表头
ptr_Node ptr_node;
ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点
if(!ptr_node)
{
printf("allocation failed.\n");
}
else
{
ptr_node->value=element;
if(linklist->length==0)
{
linklist->head=ptr_node;
linklist->tail=linklist->head;
linklist->tail->next=NULL;
}
else
{
ptr_node->next=linklist->head;
linklist->head=ptr_node; //链表头
}
linklist->length++; //链表长度加1
}
}
void InsertListTail(ptr_LinkList linklist,ElemType element)
{
ptr_Node ptr_node;
ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点
if(!ptr_node)
{
printf("allocation failed.\n");
}
else
{
ptr_node->value=element;
if(linklist->length==0)
{
linklist->head=ptr_node;
linklist->tail=linklist->head;
linklist->tail->next=NULL;
}
else
{
linklist->tail->next=ptr_node;
linklist->tail=ptr_node; //链表尾
}
linklist->length++; //链表长度加1
}
}
void InsertListPosition(ptr_LinkList linklist,int pos,ElemType element)
{
int i;
ptr_Node ptr_node;
ptr_Node temp_ptr_node;
if(pos<1 || pos>linklist->length)
{
printf("The insert position is invalidate.\n");
}
else
{
ptr_node=(Node *)malloc(sizeof(Node)); //生成插入结点
if(!ptr_node)
{
printf("allocation failed.\n");
}
ptr_node->value=element;
if(pos==1)
{
InsertListHead(linklist,element);
}
else if(pos==linklist->length)
{
InsertListTail(linklist,element);
}
else
{
temp_ptr_node=linklist->head;
for(i=1;i<pos-1;i++)
{//找到第pos-1个结点
temp_ptr_node=temp_ptr_node->next;
}
ptr_node->next=temp_ptr_node->next;
temp_ptr_node->next=ptr_node;
linklist->length++;
}
}
}
void Destroy(ptr_LinkList linklist)
{//销毁链表
ptr_Node p=linklist->head;
ptr_Node q;
while(p)
{//释放每个结点空间
q=p->next;
free(p);
p=NULL;
p=q;
}
}
void Traverse(ptr_LinkList linklist)
{//输出整个链表
ptr_Node p;
p=linklist->head;
while(p)
{
printf("%4d",p->value);
p=p->next;
}
}
|
头文件中实现了链表的几个基本的操作，有的是必须的，有些是非必须的。
实现代码：
|
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
|
#include "stdafx.h"
#include "LinkList.h"
#include <conio.h>
ptr_LinkList InvertList(ptr_LinkList list)
{//该方法借助一个新的空链表来实现链表逆序
ptr_LinkList inverted_linklist;
ptr_Node p;
p=list->head;
inverted_linklist=CreateList();//创建一个空链表
while(p)
{//将list链表中的结点值逆序输入新创建的链表中，实现链表反转
InsertListHead(inverted_linklist,p->value);
p=p->next;
}
return inverted_linklist;
}
void InvertLinkList(ptr_LinkList linklist)
{//该方法直接对原有链表实现逆序，不借助其他链表
ptr_Node p,q,r,m;
m=p=linklist->head;
q=p->next;
r=q->next;
while(r)
{//依次对链表中的结点进行反转
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p; //最后一个结点反转
linklist->head=q;
linklist->tail=m;
linklist->tail->next=NULL;
}
int _tmain(int argc, _TCHAR* argv[])
{
ptr_LinkList linklist;
ptr_LinkList list;
linklist=CreateList();
if(linklist)
{
printf("We have created a new linklist.\n");
}
InsertListHead(linklist,12);
InsertListHead(linklist,35);
InsertListHead(linklist,66);
InsertListHead(linklist,06);
InsertListHead(linklist,11);
InsertListHead(linklist,54);
InsertListHead(linklist,79);
Traverse(linklist);
printf("\n");
printf("The first method:\n");
list=InvertList(linklist);
Traverse(list);
printf("\n");
printf("The second method:\n");
InvertLinkList(linklist);
Traverse(linklist);
printf("\n");
getch();
return 0;
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://toigel.blog.51cto.com/2141741/600286