双向链表各种操作(尾插法建表、初始化、求表长、查找、删除、插入、取值)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;
}
上一篇: spring 依赖注入到直接new 对象
下一篇: LSTM时间序列预测