欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双向链表各种操作(尾插法建表、初始化、求表长、查找、删除、插入、取值)17计科班教学用

程序员文章站 2024-03-22 13:21:58
...
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char ElemType;
typedef int Status;
typedef struct DuLNode
{
     ElemType   data;       //数据域
     struct DuLNode  *prior;   //前驱指针域
     struct DuLNode  *next;   //后继指针域
}DuLNode,*DuLinkList;  
//初始化双向链表 
Status InitList_L(DuLinkList &L){ 
L=new DuLNode;
L->next=NULL;  //后继指针为NULL 
L->prior=NULL; //前驱指针为NULL
return OK;
} 
//利用尾插法建立双向链表
void CreateList_L(DuLinkList &L,int n){ 
      //正位序输入n个元素的值,建立带表头结点的双向链表L 
      L=new DuLNode; 
      L->next=NULL;
	  L->prior=NULL; 
	  DuLNode *p;	
      DuLNode *r=L;//尾指针r指向头结点 
      for(int i=0;i<n;++i){
		p=new DuLNode;//生成新结点 
		cin>>p->data;//输入元素值 
		p->next=NULL; 
		p->prior=r;
		r->next=p; //插入到表尾 
		r=p;//r指向新的尾结点 
      } 
}//CreateList_L 
//双向链表元素输出 
void Out_LinkList(DuLNode *p){
	 printf("The Created LinkList Elem Is:");
	 while(p!=NULL)
	 {
	  cout<<p->data<<" "; 
	  p=p->next;
	 } 
}//Out_LinkList
//求表长,返回L中数据元素个数
int  ListLength_L(DuLinkList L){
	int  i=0; 
    DuLinkList p;
    p=L->next;  //p指向第一个结点               
     while(p){//遍历单链表,统计结点数
           i++;
           p=p->next;    } 
    return i;                             
 }
//取值,获取线性表L中的某个数据元素的内容
Status GetElem_L(DuLinkList L,int i,ElemType &e){ 
    DuLNode *p=L->next;
	int j=1; //初始化
     while(p&&j<i){	//向后扫描,直到p指向第i个元素或p为空 
       p=p->next; ++j; 
     } 
     if(!p || j>i)return ERROR; //第i个元素不存在 
     e=p->data; //取第i个元素 
     return OK; 
}
//在线性表L中查找值为e的数据元素 
DuLNode *LocateELem_L(DuLinkList L,ElemType e) {
 //返回L中值为e的数据元素的地址,查找失败返回NULL
  DuLNode *p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	
}
//在带头结点的双向链表L中查找第i个元素,返回结点的地址
DuLNode *GetElemP_DuL(DuLinkList L, int i) {
	//在带头结点的双向链表L中查找第i个元素,返回结点的地址
	int j;
	DuLinkList p;
	p = L->next;
	j = 1; //初始化,p指向第一个结点,j为计数器
	while (j < i && p) { //顺链域向后扫描,直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return NULL; //第i个元素不存在
	return p;
} //GetElemP_DuL

//双向链表的插入 
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   DuLinkList p;
   DuLNode *s;
   if(!(p=GetElemP_DuL(L,i))) return ERROR;//在L中确定第i个元素的位置指针p 
   s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;  
   p->prior->next=s;
   s->next=p;  
   p->prior=s;
   return OK;
}
//双向链表的删除 
Status ListDelete_DuL(DuLinkList &L,int i)
{
   DuLinkList p;
   if(!(p=GetElemP_DuL(L,i)))
   return ERROR;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   delete p; 
   return OK;
}
int main(){
	//第一步 初始化双向链表
	 DuLinkList L;
	 DuLNode *p,*q,*Locate_Address;
	 int Init_flag,GetElem_flag;
	 int n=5;//建立双向链表时需要创建节点的个数 
	 Init_flag=InitList_L(L);
	 if(Init_flag)
	 cout<<"Init OK!"<<endl;
	 else
	 cout<<"Init ERROR!"<<endl;
	//第二步 利用尾插法建立双向链表
	cout<<"Please Input The DuLinkList Elem_Value( "<<n<<" values):"<<endl;
	CreateList_L(L,n);
	cout<<"Create DuLinkList OK!"<<endl;
	Out_LinkList(L->next);//输出现有双向链表中元素
	cout<<endl;
	//第三步 双向链表按照位置i取值
	int GetElem_i;
	ElemType GetElem_e;
	cout<<"Please Input The  GetElem_i: ";
	cin>>GetElem_i;
	GetElem_flag=GetElem_L(L,GetElem_i,GetElem_e);
	if(GetElem_flag)
	cout<<"GetElem Is OK:"<<GetElem_e<<endl;
	else
	cout<<"GetElem Is ERROR!"<<endl;
	//第四步 双向链表按值查找,如果找到返回地址,否则返回null 
    ElemType Locate_e;
	cout<<"Please input LocateElem value:"; 
	cin>>Locate_e;
    Locate_Address=LocateELem_L(L,Locate_e); 
    if(Locate_Address!=NULL)
    cout<<"LocateElem Is OK, The Address Is:"<<Locate_Address<<endl;
	else
	cout<<"LocateElem Is ERROR!"<<endl;
    //第五步 双向链表的插入操作
	ElemType ListInsert_e; 
	int ListInsert_i,ListInsert_flag;
	cout<<"Please Input The DuListInsert_i:";
	cin>>ListInsert_i;
	cout<<"Please Input The DuListInsert_e:";
	cin>>ListInsert_e;
	ListInsert_flag=ListInsert_DuL(L,ListInsert_i,ListInsert_e);
	if(ListInsert_flag)
	{
		cout<<"DuListInsert Is OK!"<<endl;
		cout<<"The DuLinkList of Length is: "<<ListLength_L(L)<<endl;
		Out_LinkList(L->next);//输出现有单链表中元素	
	}
	else
	cout<<"DuListInsert Is ERROR!"<<endl; 
	cout<<endl;
    //第六步 双向链表删除操作
	int delete_i,delete_flag;
	cout<<"Please input The delete_i:";
	cin>>delete_i;
	delete_flag=ListDelete_DuL(L,delete_i);
	if(delete_flag)
	{
		cout<<"DuListDelete is Ok!"<<endl;
		cout<<"The DuLinkList of length is: "<<ListLength_L(L)<<endl;
		Out_LinkList(L->next);//输出现有单链表中元素	
	}
	else
	cout<<"DuListDelete Is ERROR!"<<endl;
	
	return OK; 
}
 

双向链表各种操作(尾插法建表、初始化、求表长、查找、删除、插入、取值)17计科班教学用