わかりましたので、C で循環両端キューを作成する必要がある割り当てに取り組んでいます。すべての機能を実装しており、それらをテストしています。「リバース」機能まではすべて良好でした。
これは簡単だと思いました。新しいリンクを作成し、Sentinel の代わりに接続します。古いセンチネルを強制終了してから、deque のセンチネルを新しいリンクに設定します。
ただし、これを実行すると malloc エラーが発生し、C を初めて使用するため、デバッグ方法がわかりません。
- - - - エラー - - - -
prog(10346) malloc: *オブジェクト 0x7faf13c03920 のエラー: 解放中のポインタが割り当てられていませんでした。malloc_error_break にブレークポイントを設定してデバッグします。
コード
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include "cirListDeque.h"
/* Double Link Struture */
struct DLink {
TYPE value;/* value of the link */
struct DLink *next;/* pointer to the next link */
struct DLink *prev;/* pointer to the previous link */
};
# define TYPE_SENTINEL_VALUE DBL_MAX
/* ************************************************************************
Deque ADT based on Circularly-Doubly-Linked List WITH Sentinel
************************************************************************ */
struct cirListDeque {
int size;/* number of links in the deque */
struct DLink *Sentinel; /* pointer to the sentinel */
};
/* internal functions prototypes */
struct DLink* _createLink (TYPE val);
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk);
void _removeLink(struct cirListDeque *q, struct DLink *lnk);
/* ************************************************************************
Deque Functions
************************************************************************ */
/* Initialize deque.
param: q pointer to the deque
pre: q is not null
post: q->backSentinel is allocated and q->size equals zero
*/
void _initCirListDeque (struct cirListDeque *q)
{
struct DLink* lnk = (struct DLink*)malloc(sizeof(struct DLink));
assert(lnk != 0); //sentinel made
q->Sentinel = lnk;
q->Sentinel->next = q->Sentinel->prev = q->Sentinel;
q->size = 0;
}
/*
create a new circular list deque
*/
struct cirListDeque *createCirListDeque()
{
struct cirListDeque* newCL = malloc(sizeof(struct cirListDeque));
_initCirListDeque(newCL);
return(newCL);
}
/* Create a link for a value.
param: val the value to create a link for
pre: none
post: a link to store the value
*/
struct DLink * _createLink (TYPE val)
{
struct DLink* lnk = (struct DLink*) malloc(sizeof(struct DLink));
lnk->value = val;
return(lnk);
}
/* Adds a link after another link
param: q pointer to the deque
param: lnk pointer to the existing link in the deque
param: newLnk pointer to the new link to add after the existing link
pre: q is not null
pre: lnk and newLnk are not null
post: the new link is added into the deque after the existing link
*/
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk)
{
lnk->next->prev = newLnk; //right connects to new
newLnk->next = lnk->next; //new connect to right
newLnk->prev = lnk; //new connect to left
lnk->next = newLnk; //left connect to new
q->size++;
}
/* Adds a link to the back of the deque
param: q pointer to the deque
param: val value for the link to be added
pre: q is not null
post: a link storing val is added to the back of the deque
*/
void addBackCirListDeque (struct cirListDeque *q, TYPE val)
{
struct DLink* lnk = _createLink(val);
_addLinkAfter(q, q->Sentinel->prev, lnk);
}
/* Adds a link to the front of the deque
param: q pointer to the deque
param: val value for the link to be added
pre: q is not null
post: a link storing val is added to the front of the deque
*/
void addFrontCirListDeque(struct cirListDeque *q, TYPE val)
{
struct DLink* lnk = _createLink(val);
_addLinkAfter(q, q->Sentinel, lnk);
}
/* Get the value of the front of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: none
ret: value of the front of the deque
*/
TYPE frontCirListDeque(struct cirListDeque *q)
{
return q->Sentinel->next->value;
}
/* Get the value of the back of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: none
ret: value of the back of the deque
*/
TYPE backCirListDeque(struct cirListDeque *q)
{
return q->Sentinel->prev->value;
}
/* Remove a link from the deque
param: q pointer to the deque
param: lnk pointer to the link to be removed
pre: q is not null and q is not empty
post: the link is removed from the deque
*/
void _removeLink(struct cirListDeque *q, struct DLink *lnk)
{
//assert(!isEmptyList(lst));
lnk->next->prev = lnk->prev; //connect right link to left link
lnk->prev->next = lnk->next; //connect left link to right link
q->size--;
free(lnk);
}
/* Remove the front of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the front is removed from the deque
*/
void removeFrontCirListDeque (struct cirListDeque *q) {
_removeLink(q, q->Sentinel->next);
}
/* Remove the back of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the back is removed from the deque
*/
void removeBackCirListDeque(struct cirListDeque *q)
{
_removeLink(q, q->Sentinel->prev);
}
/* De-allocate all links of the deque
param: q pointer to the deque
pre: none
post: All links (including backSentinel) are de-allocated
*/
void freeCirListDeque(struct cirListDeque *q)
{
while (q->size > 0){
removeFrontCirListDeque(q);
}
free(q->Sentinel);
}
/* Check whether the deque is empty
param: q pointer to the deque
pre: q is not null
ret: 1 if the deque is empty. Otherwise, 0.
*/
int isEmptyCirListDeque(struct cirListDeque *q) {
return q->size == 0;
}
/* Print the links in the deque from front to back
param: q pointer to the deque
pre: q is not null and q is not empty
post: the links in the deque are printed from front to back
*/
void printCirListDeque(struct cirListDeque *q)
{
struct DLink *current;
int x = 0;
assert(!isEmptyCirListDeque(q));
current = q->Sentinel->next;
while(current != q->Sentinel){
printf("value: %f\t", current->value);
current = current->next;
x++;
if (x >= 6){
printf("\n");
x = 0;
}
}
}
/* Reverse the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the deque is reversed
*/
void reverseCirListDeque(struct cirListDeque *q)
{
//struct DLink *temp = _createNewLink(0); //try this allocat then assign then move
struct DLink *newSent = (struct DLink*) malloc(sizeof(struct DLink));
newSent->next = q->Sentinel->prev;
newSent->prev = q->Sentinel->next;
q->Sentinel->next->prev = newSent;
q->Sentinel->prev->next = newSent;
free(q->Sentinel);
q->Sentinel = newSent;
/* A different approach that didn't work.
temp->next = q->Sentinel->prev;
q->Sentinel->prev = q->Sentinel->next;
q->Sentinel->next = temp->next;
free(temp);*/
}