链表的两种实现方式

这是关于线性表链式存住的两种实现方式,一个使用指针,一个使用c++中的引用。其实这两种方式是大同小异的。

The first method will use pointer in 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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
/*first inlcude all those need header files.*/
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"

/*define those constants needed*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/*define the initial size allocated.*/
#define MAXSIZE 20

/*define the return type of a function*/
typedef int Status;
typedef int ElemType;

/*define a struct Node with the name Node, and make LinkList a pointer point to Node*/
typedef struct Node {
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;

/*initialize the LinkList*/
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node));
    if(!(*L))
    	return ERROR;
    (*L)->next=NULL;

    return OK;
}

Status ListEmpty(LinkList L){
    if(L->next)
    	return FALSE;
    else
    	return TRUE;
}

/*if the linklist already exists, set it to empty*/
Status ClearList(LinkList *L)
{
	LinkList p,q;
	p=(*L)->next;     /*p points to the first node*/
	while(p)          /*it means not to the end of the linklist*/
	{
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL;  /*pointer field for the head Node will be null*/
	return OK;
}

/*return the length of the linklist*/
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next;  /*p points to the first node*/
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/*get the i th element of L and returning its value using e*/
Status GetElem(LinkList L,int i,ElemType *e) {
	int j;
	LinkList p;		/* declare a node "p" */
	p = L->next;		/* let p point to the first node of L */
	j = 1;		
	while (p && j<i)
	{
		p = p->next;  /* let p point to the next node */
		++j;
	}
	if ( !p || j>i )
		return ERROR;  /*  the i th element does not exist */
	*e = p->data;   /*  get the data of the i th element */
	return OK;
}

/* locate element e in L */
int LocateElem(LinkList L,ElemType e) {
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* find the element */
                return i;
        p=p->next;
    }

    return 0;
}
	
/*insert at the location of the i th element*/ 	
Status ListInsert(LinkList *L,int i,ElemType e)
{
	int j;
	LinkList p,s;
	p = *L;
	j = 1;
	while (p && j < i)     /* find the i th node */
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	s = (LinkList)malloc(sizeof(Node));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

/*delete the i th element, returning its value using e*/

Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i)
	    return ERROR;
	q = p->next;
	p->next = q->next;			
	*e = q->data;
	free(q);
	return OK;
}

/*print out all elements*/

Status visit(ElemType c) {
    printf("%d ",c);
    return OK;
}

Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/*create the data for the n elements randomly, create a linked list with head node*/

void CreateListHead(LinkList *L, int n)
{
	LinkList p;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;
	for (i=0; i<n; i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100+1;
		p->next = (*L)->next;
		(*L)->next = p;						
	}
}

/*create the data for the n elements randomly, create a linked list with tail node*/

void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(Node));
	r=*L;
	for (i=0; i<n; i++)
	{
		p = (Node *)malloc(sizeof(Node));
		p->data = rand()%100+1;
		r->next=p;
		r = p;
	}
	r->next = NULL;
}

/*in the main function you  have to do the following initializations*/

int main()
{
    LinkList L;
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
	/*blahblah*/
}

The following is a version using c++’s reference “&”, it is a little different, but mostly wil be the same as the above.

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
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct LNode  		
{
	ElemType data;
	struct LNode *next;		
} LinkList;

/*creating the linked list by inserting at the head*/

void CreateListF(LinkList *&L,ElemType a[],int n)
{
	LinkList *s;int i;
	L=(LinkList *)malloc(sizeof(LinkList));  	
	L->next=NULL;
	for (i=0;i<n;i++)
	{
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=a[i];
		s->next=L->next;			
		L->next=s;
	}
}

/*creating the linked list by inserting at the tail*/
void CreateListR(LinkList *&L,ElemType a[],int n)
{
	LinkList *s,*r;int i;
	L=(LinkList *)malloc(sizeof(LinkList));  	
	L->next=NULL;
	r=L;					
	for (i=0;i<n;i++)
	{
		s=(LinkList *)malloc(sizeof(LinkList));
		s->data=a[i];
		r->next=s;			
		r=s;
	}
	r->next=NULL;			
}

/*and blah and blah*/