Double circular linked list

Standard

This is the code I got from Data Structure course.

You could get it on https://github.com/wxia11/dll-note

//==================================================================

//”doublist.h”
//Double circular linked list

//class node
template <class type> class doublist;
template <class type> class node {
friend class doublist<type>;
private:
node <type> * prior, * next;
type data;
node <type> ( ): prior (NULL), next (NULL) { };
//constructor for header node
node <type> ( type item, node <type> * prior0, node <type> * next0):
data (item), prior (prior0), next (next0) { };
//constructor for other nodes
~node ( ) { };
};

//class doublist
template <class type> class doublist{
private:
node <type> * head, * pcurrent;
public:
doublist ( );
~doublist ( );
int Length ( ) const;                  //get length of dll
type GetCurrent ( );                  //get the value of current dll
int Locate (const type & x);     //locate the node which has data x
void Insert ( const type & x );  //insert new node which has value x before current node
void DeleteCurrent ( );              //delele current node
int  IsEmpty ( );
void Clear (void);
void Head ( ) {pcurrent = head;}     //pcurrent(current pointer) points to header node
node <type> * Next ( );     //pcurrent points to the next node of current node
node <type> * Prior ( );      //pcurrent points to the prior node of current node
};

//==================================================================

//”doublist.cpp”
//Double circular linked list

#include “doublist.h”
template <class type> doublist <type> :: doublist(){
//constructor, create header node
head = pcurrent = new node <type>();
head->prior = head->next = head;
}
template <class type>
int doublist <type> ::Length() const{
//get the length of dll
node <type> * p = head->next;  //define pointer p,points to the first element in list
int sum = 0;
while ( p != head) {sum++; p= p-> next;}
return sum;
}
template <class type>
int doublist <type> :: Locate (const type & x){
/* find the node which has value x, p (current pointer) points to this node, and return 1; or return 0 and don’t change the pointer*/
node <type> * p = head->next;
while ( p != head && p-> data!= x)   //find the node with data x
p = p->next;
if (p != head) {pcurrent = p; return 1;}    //got it
else return 0;                         //didn’t find it
}
template <class type>
void doublist <type> :: Insert (const type & x){
/* create a new node that has data x, then insert it prior to current node. ??How about an empty list??*/
node <type> * newnode = new node <type> (x , pcurrent->prior , pcurrent);
/* create new node, its data is x, its prior (prior pointer) points to the node piror to current node (pointed by pcurrent), its next (next pointer) points to current node (pointed by pcurrent).*/
pcurrent->prior->next = newnode;  //If list is empty, which means head->next = newnode, at this time, pcurrent->prior is head
pcurrent->prior = newnode;
pcurrent = pcurrent->prior;
}

template <class type>
void doublist <type> :: DeleteCurrent(){
/*delete current node in dll, and pcurrent points to next node*/
if (pcurrent != head )  {
node <type> * p = pcurrent;  /* define p, which points to the node pointed by pcurrrent */
pcurrent = pcurrent->next;  // move pcurrent to next node
pcurrent->prior = p->prior;  // change pcurrent in order to pull out p
p->prior->next = pcurrent;
delete p;        //
}
if (pcurrent == head) pcurrent = head->next;
}
template <class type>
void doublist <type> :: Next(){
/* Make pcurrent point to next node; if current node is the last node, then make pcurrent point to the first node in dll */
pcurrent = pcurrent->next;  // pcurrent move to next node
if (pcurrent == head) pcurrent = head->next;
/* If the list is empty, pcurrent points to header node.*/
/* If current node is tailer node, at this time, pcurrent points to header node. ???? */
return pcurrent;
}

template <class type>
void doublist <type> :: Prior(){
/* Make pcurrent point to the node prior to current node; if the node is header node, then make pcurrent point to tailer node */
pcurrent = pcurrent->prior;  // pcurrent move to prior
if(pcurrent == head) pcurrent = head->prior;
/* If the list is empty, pcurrent points to header node.*/
/* If current node is header node, at this time, pcurrent points to tailer node. ???? */
}

Push a new repo to Github

Standard

1. Create a new repository on github, then you can get a url or ssh link of your new repository.

For example, the url is https://github.com/user000/new_repo.git, the ssh link is git@github.com:user000/new_repo.git.

 

2. Create a new repository on command line:

mkdir new_repo

cd new_repo

touch README.md

git init

git add README.md

git commit -m "first commit"

 

3. Push repository from command line

git remote add origin https://github.com/user000/new_repo.git

git push -u origin master

 

You can change the url by using:

git remote set-url origin https://github.com/user000/new_repo2.git

 

namespace

Standard

void minusOne(void* a) {
    *(int*)a-=1;
}

namespace cl {
typedef long long color;
}

int main() {
    int a=10;
    long long b=10;
    cl::color c=0;
    cl::color a1=0;
    minusOne(&a);
    minusOne(&b);
    return 0;
}

Aside

1.

void minusOne(int* a) {
*a-=1;
}
int main() {
int a=10;
long long b=10;
minusOne(&a);
minusOne((int*)&b);   //minusOne(&b); won’t work.
return 0;
}

2. void pointer can accept any type of pointer

void minusOne(void* a) {
*(int*)a-=1; //??????
}
int main() {
int a=10;
long long b=10;
minusOne(&a);
minusOne(&b);
return 0;
}

void pointer

const

Standard

1.

struct A {
private:
    int i;
public:
    const int& getI() {return i;}
    int& getI_unsafe() {return i;}
};

int main() {
    A a;
    //a.getI()=10;
    a.getI_unsafe()=10;
    int t=a.getI();
    return 0;
}

2.

struct A{
private:
    int i;
protected:
    A() {}
public:
    const int& getI() const {return i;}
    int& getI_unsafe() {return i;}
};
struct B : private A {B() {} const A* returnA() {return this;}};

int main() {
    B a;
    
    //const A* ap=a.returnA();ap->getI_unsafe()=10; //This won’t work
    A* ap=(A*)a.returnA(); //very stupid code
    ap->getI_unsafe()=10;
    
    int t=ap->getI();
    return 0;
}

 

Preprocessor Branch

Standard

1.

#include <iostream>
#define LINUX 0
#define WINDOWS 1
#define MAC 2
#define OS WINDOWS

#if OS==WINDOWS
int main() {
    std::cout<<“Do stuff A”;
    return ;
}
#else
int main() {
    std::cout<<“Do stuff B”;
    return ;
}
#endif

2. Macro

There is zero interpret before Macro. The real compiler never see Macro. Macro copy and paste before compile.

#include <iostream>
#define LINUX 0
#define WINDOWS 1
#define MAC 2
#define OS WINDOWS

/*Macro*/
#define SWAP(a,b) { auto i=a;\
    a=b;\
    b=i;} //cannot “auto i”;

#define ASSERT(i,m) if(!i) std::cout<<m

#if OS==WINDOWS

bool isPositive(int a) {
    return a>0;
}

bool isNotZero(int a) {
    return a!=0;
}

int main() {
    std::cout<<“Do stuff A”;
    int r=10;
    int c=34;    
    SWAP(r,c);
    //(float)c=(float)0;  //(float)c is wrong; Expression is must be a modifiable lvalue.
    //SWAP((float)r,c);  //Thus (float)r in Macro is wrong.
    ASSERT(isNotZero(12),”12 is zero”);
    ASSERT(isNotZero(0),”0 is zero”);
    ASSERT(isPositive(10),”10 is not positive”);
    ASSERT(isPositive(-2),”-2 is not positive”);
    return 0;
}
#else
int main() {
    std::cout<<“Do stuff B”;
    return ;
}
#endif