C++线程安全型双向链表的实现

#include
#include
using namespace std;

typedef struct Node{
int iVal;
Node *pUp,*pDown;
}DNode,*PNode;

class NodeList{
private:
PNode mHead;
char mName[1024];
CRITICAL_SECTION g_cs;
public:
NodeList(){
mHead=NULL;
mName[0]='\0';
}
~NodeList(){
Clean();
}
PNode Clone(){
PNode tmp=NULL , tmp1=mHead ,tmp2;
while(tmp1){
if(tmp){
tmp2->pDown=new DNode();
tmp2->pDown->iVal=tmp1->iVal;
tmp2->pDown->pDown=NULL;
tmp2->pDown->pUp=tmp2;
tmp2=tmp2->pDown;
}else{
tmp2=new DNode();
tmp2->iVal=tmp1->iVal;
tmp2->pUp=NULL;
tmp2->pDown=NULL;
tmp=tmp2;
}

tmp1=tmp1->pDown;
}
return tmp;
}
bool Append(PNode node){
EnterCriticalSection(&g_cs);
bool bRet=false;
PNode tmp=mHead;
if(node){
if (tmp){
while(tmp->pDown){
tmp=tmp->pDown;
}
tmp->pDown=node;
node->pUp=tmp;
}else{
mHead=node;
}
bRet=true;
}
LeaveCriticalSection(&g_cs);
return bRet;
}
void Append(int val){
PNode tmp=mHead , newNode;
EnterCriticalSection(&g_cs);
if(tmp)
while(tmp->pDown){
tmp=tmp->pDown;
}
newNode=new DNode();
newNode->iVal=val;
newNode->pDown=NULL;
if(tmp){
newNode->pUp=tmp;
tmp->pDown=newNode;
}else{
newNode->pUp=NULL;
mHead=newNode;
}
LeaveCriticalSection(&g_cs);
//cout< }
bool Delete(int val){
EnterCriticalSection(&g_cs);
PNode tmp=mHead;
bool bRet=false;
while(tmp){
if ( tmp->iVal==val){
bRet=true;
break;
}else{
tmp=tmp->pDown;
}
}
if(bRet){
if(tmp==mHead){
mHead=tmp->pDown;
if ( tmp->pDown ){
mHead->pUp=NULL;
}
}else{
tmp->pUp->pDown=tmp->pDown;
if ( tmp->pDown){
tmp->pDown->pUp=tmp->pUp;
}
}
delete(tmp);
//cout<操作:"<<" 删除值"< }else{
//cout<操作:"<<" 删除值"< }
LeaveCriticalSection(&g_cs);
return bRet;
}
void Print(){
PNode tmp=mHead;
int c=0;
cout<操作:"<<" 显示 列表!"< while(tmp){
cout<iVal<<"\t";
tmp=tmp->pDown;
c++;
}
cout<操作:"<<" 显示 元素有"< }
PNode Find(int val,PNode pStart){
PNode Ret=NULL;
PNode tmp=pStart;
while(tmp){
if ( tmp->iVal==val){
Ret=tmp;
break;
}else{
tmp=tmp->pDown;}
}
return tmp;
}
void BJ(){
cout<操作:"<<"并集 开始!"< PNode tmp=mHead;
while(tmp){
if( Find(tmp->iVal,tmp->pDown) ){
this->Delete(tmp->iVal);
tmp=mHead;
}else {
tmp=tmp->pDown;
}
}
cout<操作:"<<"并集 结束!"< }
void JJ(){
cout<操作:"<<"交集 开始!"< PNode tmp=mHead , tmp1=mHead , tmp2=NULL;
mHead=NULL;
while(tmp){
if( Find(tmp->iVal,tmp->pDown) ){
if( ! Find(tmp->iVal,mHead) )
Append(tmp->iVal);
}
tmp=tmp->pDown;
}
tmp2=mHead;
mHead=tmp1;
Clean();
mHead=tmp2;
cout<操作:"<<"交集 结束!"< }
void Clean(){
//cout<操作:"<<"清除 开始!"< while(mHead){
if ( mHead->pDown ){
mHead=mHead->pDown;
delete(mHead->pUp);
}else{
delete(mHead);
mHead=NULL;
}
}
mHead=NULL;
//cout<操作:"<<"清除 结束!"< }
void setName(char *name){
char *tmp=name;
int c=0;
while(*tmp){
this->mName[c]=*tmp;
tmp++;
c++;
}
mName[c]='\0';
}
};
int _tmain(int argc, _TCHAR* argv[])
{
/*(3，5，8，11）， B=（2，6，8，9，11，15，20*/
/*NodeList tmp,tmp1,tmp2,tmp3;
tmp.setName("链表1");
tmp.Append(3);
tmp.Append(5);
tmp.Append(8);
tmp.Append(11);
tmp1.setName("链表2");
tmp1.Append(2);
tmp1.Append(6);
tmp1.Append(8);
tmp1.Append(9);
tmp1.Append(11);
tmp1.Append(15);
tmp1.Append(20);

tmp.Print();
tmp1.Print();
tmp2.setName("链表3");
tmp2.Append(tmp.Clone());
tmp2.Append(tmp1.Clone());
tmp2.Print();
tmp2.BJ();
tmp2.Print();
tmp2.Clean();
tmp2.Print();
tmp2.Append(tmp.Clone());
tmp2.Append(tmp1.Clone());
tmp2.JJ();
tmp2.Print();*/
int k;
cin>>k;
return 0;
}

#include
#include
#include

struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};

CCriticalSection mysec;

struct dllist *head, *tail;

void initial_node(struct dllist *lnode);
void append_node(struct dllist *lnode);
void insert_node(struct dllist *lnode, struct dllist *after);
void remove_node(struct dllist *lnode);

int main(void) {

struct dllist *lnode;
int i = 0;

/* add some numbers to the double linked list */
for(i = 0; i <= 5; i++) {
lnode = (struct dllist *)malloc(sizeof(struct dllist));
lnode->number = i;
append_node(lnode);
}

/* print the dll list */
for(lnode = head; lnode != NULL; lnode = lnode->next) {
printf("%d\n", lnode->number);
}

/* destroy the dll list */
while(head != NULL)
remove_node(head);

return 0;
}

void append_node(struct dllist *lnode) {
if(head == NULL) {
head = lnode;
lnode->prev = NULL;
} else {
tail->next = lnode;
lnode->prev = tail;
}

tail = lnode;
lnode->next = NULL;
}

void insert_node(struct dllist *lnode, struct dllist *after) {
lnode->next = after->next;
lnode->prev = after;

if(after->next != NULL)
after->next->prev = lnode;
else
tail = lnode;

after->next = lnode;
}

void remove_node(struct dllist *lnode) {
if(lnode->prev == NULL)
head = lnode->next;
else
lnode->prev->next = lnode->next;

if(lnode->next == NULL)
tail = lnode->prev;
else
lnode->next->prev = lnode->prev;
}

void initial_node(struct dllist *lnode) {

mysec.Lock();
//临界区锁定，进行数据处理
head = tail = NULL;

mysec.Unlock();//处理后解除临界区的锁定

}