Data Structure: 2.Imperative-Style Linked Lists
Problem Description:
In the previous exercise we implemented some basic operations on functional-style linked lists; their distinguishing feature is that the pairs that make up the lists are immutable. In today’s exercise we will implement imperative-style linked lists in which the pairs that make up the lists are mutable.
Your task is to write the same library of functions — nil, isNil, pair, head, tail, nth, length, append, and reverse — for imperative-style mutable linked lists as you wrote in the previous exercise for functional-style immutable linked lists.
Analysis:
We will use the well-known imperative language C instead of our usual language Scheme, because writing Scheme like that would make me cry. The basic data type that implements lists is the List, which is a struct; we will hard-wire the data type as int, but you could change that to a pointer to void if you want to be more general: typedef struct list {
void *data;
struct list *next;
} List;
Instead of providing nil and isNil, we will simply use the built-in NULL for nil and write xs == NULL or xs != NULL to determine if a List is nil. Likewise, getting the components of a pair is so simple we don’t bother to provide functions for them: the head of a list is xs->data and the tail of a list is xs->next.
The insert function adds a new pair to the front of a list by allocating space for the new pair, assigning a value and a pointer to its two fields, and returning the new pair: List *insert(void *data, List *next) {
List *new;
new = malloc(sizeof(List));
new->data = data;
new->next = next;
return new;
}
Getting the nth item in a list, or counting the length of a list, involves chasing pointers down the list in a while loop. Since C doesn’t have a standard error return, we use our own error function, which writes a message to stderr then exits the program with a return value of 2: int nth(List *xs, int n) {
while (n > 0) {
if (xs == NULL) {
error(“nth out of bounds”);
}
n–;
xs = xs->next;
}
return xs->data;
}
int length(List *xs) {
int len = 0;
while (xs != NULL)
{
len += 1;
xs = xs->next;
}
return len;
}
Append walks down its first argument, then modifies the NULL pointer at the end of the list to point to its second argument: List *append(List *xs, List *ys) {
List *new = xs;
while (xs->next != NULL) {
xs = xs->next;
}
xs->next = ys;
return new;
}
Our last function is reverse, which is again destructive, modifying the current list in place by swapping pointers: List *reverse(List *list) {
List *new = NULL;
List *next;
while (list != NULL)
{
next = list->next;
list->next = new;
new = list;
list = next;
}
return new;
}
We haven’t bothered to collect the garbage we created; shame on me. I admit some trouble programming with C; it’s so ugly compared to Scheme.
Code:
You can see the program in action at http://programmingpraxis.codepad.org/JQIFfqOX.
-from ProgrammingProxis
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
We will use the well-known imperative language C instead of our usual language Scheme, because writing Scheme like that would make me cry. The basic data type that implements lists is the List, which is a struct; we will hard-wire the data type as int, but you could change that to a pointer to void if you want to be more general:
typedef struct list {
void *data;
struct list *next;
} List;
Instead of providing nil and isNil, we will simply use the built-in NULL for nil and write xs == NULL or xs != NULL to determine if a List is nil. Likewise, getting the components of a pair is so simple we don’t bother to provide functions for them: the head of a list is xs->data and the tail of a list is xs->next.
The insert function adds a new pair to the front of a list by allocating space for the new pair, assigning a value and a pointer to its two fields, and returning the new pair:
List *insert(void *data, List *next) {
List *new;
new = malloc(sizeof(List));
new->data = data;
new->next = next;
return new;
}
Getting the nth item in a list, or counting the length of a list, involves chasing pointers down the list in a while loop. Since C doesn’t have a standard error return, we use our own error function, which writes a message to stderr then exits the program with a return value of 2:
int nth(List *xs, int n) {
while (n > 0) {
if (xs == NULL) {
error(“nth out of bounds”);
}
n–;
xs = xs->next;
}
return xs->data;
}
int length(List *xs) {
int len = 0;
while (xs != NULL)
{
len += 1;
xs = xs->next;
}
return len;
}
Append walks down its first argument, then modifies the NULL pointer at the end of the list to point to its second argument:
List *append(List *xs, List *ys) {
List *new = xs;
while (xs->next != NULL) {
xs = xs->next;
}
xs->next = ys;
return new;
}
Our last function is reverse, which is again destructive, modifying the current list in place by swapping pointers:
List *reverse(List *list) {
List *new = NULL;
List *next;
while (list != NULL)
{
next = list->next;
list->next = new;
new = list;
list = next;
}
return new;
}
We haven’t bothered to collect the garbage we created; shame on me. I admit some trouble programming with C; it’s so ugly compared to Scheme.
Code:
You can see the program in action at http://programmingpraxis.codepad.org/JQIFfqOX.
-from ProgrammingProxis
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.