数据结构 -双链表的创设及其各功能的实现

数据结构 -----双链表的创建及其各功能的实现

 <pre name="code" class="cpp">#ifndef _DCLIST_H
#define _DCLIST_H

#include<iostream>
#include<assert.h>
using namespace std;


typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node *next;
	struct Node *prev;
}Node;

typedef struct List
{
	Node   *first;
	Node   *last;
	size_t size;
}List;

void InitList(List *list);
void push_back(List *list, ElemType x);
void push_front(List *list, ElemType x);
void show_list(List *list);
bool pop_back(List *list);
bool pop_front(List *list);
Node* find(List *list, ElemType key);
bool delete_val(List *list, ElemType key);
bool insert_val(List *list, ElemType x);
bool resver(List *list);
void destroy(List *list);
void clear(List *list);
bool Isempty(List *list);
bool modify(List *list,ElemType x);
 bool length(List *list);
 void sort(List *list);  
Node *next(List *list,ElemType x);
Node *prio(List *list,ElemType x);
#endif

#include"DCList.h"

void InitList(List *list)
{
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	list->first = list->last = s;
	list->first->prev = list->last;
	list->last->next = list->first;
	list->size = 0;
}

void push_back(List *list, ElemType x)
{
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;

	s->prev = list->last;
	//s->prev = list->first;
	list->last->next = s;
	 
	list->last = s;
	list->last->next = list->first;
	list->first->prev = list->last;
	list->size++;
}

void push_front(List *list, ElemType x)
{
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;

	s->prev = list->first;
	s->next = list->first->next;
	list->first->next = s;
	s->next->prev = s;

	if(list->size == 0)
		list->last = s;

	list->size++;
}

void show_list(List *list)
{
	Node *p = list->first->next;
	while(p != list->first)
	{
		cout<<p->data<<"-->";
		p = p->next;
	}
	cout<<"Over!"<<endl;
}

Node* find(List *list, ElemType key)
{
	Node *p = list->first->next;
	while(p != list->first && p->data != key)
		p = p->next;

	if(p != list->first)
	 
		return p;
	return NULL;
}

bool delete_val(List *list, ElemType key)
{
	Node *q = find(list,key);
	if(q == NULL)
		return false;

	if(q == list->last)
		list->last = q->prev;
	q->next->prev = q->prev;
	q->prev->next = q->next;
	free(q);
	list->size--;
	return true;
}

bool insert_val(List *list, ElemType x)
{
	Node *p = find(list,x);
	if(p != NULL)
		return false;

	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;

	p = list->first;
	while(p->next != list->first)
	{
		if(x<p->next->data)
			break;
		p = p->next;
	}

	s->next = p->next;
	p->next->prev = s;

	s->prev = p;
	p->next = s;
	
	if(p == list->last)
	{
		list->last = s;
	}

	list->size++;
	return true;
}

bool resver(List *list)
{
	Node *p = list->first->next;
	Node *q = p->next;
	p->next = list->first;
	list->first->prev = p;
	list->last = p;

	while(q!=list->first)
	{
		p = q;
		q = q->next;

		p->next = list->first->next;
		p->next->prev = p;
		p->prev = list->first;
		list->first->next = p;
	}
	return true;
}
void destroy(List *list)
{ 
	 clear(list);
	 free(list->first);
	 list->first = list->last = NULL;
	 list->size = 0;
	  
        
}
void clear(List *list)
{
  Node *s = list->first->next;
  while(s != list->first)
  {
    list->first->next= s->next;
	free(s);
    s = list->first->next;
  }
  list->last = list->first;
  list->size  =  0;
}
bool pop_back(List *list)
{ 
  if(Isempty(list))
  {
	  cout<<"链表已经为空"<<endl;
	  return false;  
  
  }
   Node *s = list->last->prev;
   free(list->last);
   s->next = list->first;
     
    list->last = s;
   list->size--;
   return true;
}
bool  pop_front(List *list)
{
	 if(Isempty(list))
	  {
		  cout<<"链表已经为空"<<endl;
		  return false;  
  
	  }
	   Node *s = list->first->next;
       list->first->next = s->next;
	   s->next->prev = list->first;
	   if(list->size == 1)
       {
	      list->last = list->first;
	   }	   
	   free(s);
	   list->size--;
	   return true;
   
}
bool Isempty(List *list)  
{  
    return (list->size == 0);  
}
 bool modify(List *list,ElemType x)  
{  
    Node *s = find(list,x);  
    ElemType item;  
    if(s != NULL) 
  	{  
        cout<<"请输入要替换的数:";  
        cin>>item;  
        s->data = item;  
        return true;  
    }  
    else
	{  
        cout<<"链表中没有找到你要替换的数"<<endl;  
        return false;  
    } 
}
 bool length(List *list)
 {
	Node *s = list->first->next;
	int p=1;
	while(s != list->last)
	{
		p++;
		s = s->next;
	}
	if(Isempty(list))
	p=0;

	cout<<p<<endl;
	return true;
 }
 void sort(List *list)  
{  
    Node *s = list->first->next; 
    Node *p = s->next; 
   
    s->next = list->first;  
    list->last = s;  
  
    while(p != list->first)  
    {  
        s = p;  
        p = p->next;  
        insert_val(list,s->data);  
        free(s);//调用insert_val（list,s->data）会创建结点 
    }  
  
}  
Node *prio(List *list,ElemType x)  
{  
    Node *s = find(list,x);  
    if(s != NULL)  
    {  
        if(s == list->first->next)  
        {  
            cout<<"没有前驱!"<<endl;  
        }  
        else  
        {  
            return s->prev;  
        }  
    }  
    else  
    {  
        cout<<"没有找到这个数!"<<endl;  
        return NULL;  
    }  
}  
 
Node *next(List *list,ElemType x)  
{  
    Node *s = find(list,x);  
    if(s != NULL)  
    {  
        if(s == list->last)  
        {  
            cout<<"没有后继"<<endl;  
        }  
        else  
        {  
            return s->next;  
        }  
    }  
    else  
    {  
        cout<<"没有找到要查找的数"<<endl;  
        return NULL;  
    }  
}  

#include"DCList.h"

void main()
{
	List mylist;
	InitList(&mylist);

	int select = 1;
	ElemType item;
	Node *p = NULL;
    int pos;
	Node *s;
	while(select)
	{
		cout<<"**********DCList*******************"<<endl;
		cout<<"******   hello!menu      ***********"<<endl;
		cout<<"* [0] quit_system [1] push_back    *"<<endl;
		cout<<"* [2] push_front  [3] show_seqlist *"<<endl;
		cout<<"* [4] pop_back    [5] pop_front    *"<<endl;
		cout<<"* [6] length      [7] insert_val   *"<<endl;
		cout<<"* [8] sort        [9] delete_val   *"<<endl;
		cout<<"* [10] find       [11]  prio       *"<<endl;
		cout<<"* [12] modify     [13]clear        *"<<endl;
		cout<<"* [14] destroy    [15] next        *"<<endl;
		cout<<"* [16] resver                      *"<<endl;
		cout<<"******************  over  **********"<<endl;
		cout<<"请选择:>";
		cin>>select;
		switch(select)
		{
		case 1:
			cout<<"请输入要插入的数据(-1结束):>";
			while(cin>>item,item!=-1)
			{
				push_back(&mylist,item);
			}
			break;
		case 2:
			cout<<"请输入要插入的数据(-1结束):>";
			while(cin>>item,item!=-1)
			{
				push_front(&mylist,item);
			}
			break;
		case 3:
			show_list(&mylist);
			break;
		case 4:
			pop_back(&mylist);
			break;
		case 5:
			pop_front(&mylist);
			break;
		case 6:
			length(&mylist);
			break;
		case 7:
			cout<<"请输入要插入的数据:";
			cin>>item;
			insert_val(&mylist,item);
			break;
		case 8:
            sort(&mylist);
			break;
		case 9:
			cout<<"请输入要插删除的值:>";
			cin>>item;
			delete_val(&mylist,item);
			break;
		case 10:
			cout<<"请输入要查找的值:>";
			cin>>item;
			p = find(&mylist,item);
			 
		  
             
            if(find(&mylist,item) != NULL)  
                cout<<"已找到"<<endl;  
            else  
                cout<<"未找到:"<<endl;  
        
			break;
		case 11:
	 
            cout<<"请输入要查找前驱的数:>";
			cin>>item;
          s =  prio(&mylist,item);
		  if(s != NULL)  
                cout<<"它的前驱是:"<<s->data<<endl;
				break;
		case 12:
			cout<<"请输入要修改的值:>";
			cin>>item;
            modify(&mylist,item);
			break;
		case 13:
			clear(&mylist);
			break;
		case 14:
            destroy(&mylist);
			break;
	
		case 15:
			cout<<"请输入要查找后继的数:>";
			cin>>item;
             s = next(&mylist,item);
			 if(s != NULL)  
                cout<<"它的后继是:"<<s->data<<endl;  

			break;
		case 16:
			resver(&mylist);
			break;
	
		default:
			break;
		}
	}

}