#include <iostream> using namespace std; //打印选项 void printTheSelect() { cout<<"\n1.初始化双向链表 2.打印双向链表\n3.逆序打印双向链表\n"; cout<<"4.求链表长度 5.判断链表是否为空\n6.清空链表\n"; cout<<"7.插入元素\n8.删除元素\n9.删除链表\n0.退出 "; } typedef struct DuLnode { int data; //数据 struct DuLnode *prior; //前驱 struct DuLnode *next; //后继 }DuLnode,*DuLinkList; //初始化双向链表 void initDlist(DuLinkList &L) { int x; DuLinkList p,q;//p,q就是struct DuLnode * //L = new DuLnode; L = (DuLinkList)malloc(sizeof(DuLnode)); L->next = NULL; L->prior = NULL; p = L; cout<<"输入双向链表的元素,每输入一个元素后按回车,输入0表示结束.\n"; cin>>x; while(x != 0)//尾插法 { q = (DuLinkList)malloc(sizeof(DuLnode)); q->data = x; q->next = NULL; q->prior = p; p->next = q; p = q; cin>>x; } cout<<"双向链表构造完毕!\n"; } //打印双向链表 void printDlist(DuLinkList &L) { DuLinkList p; if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else if(L->next == NULL) { cout<<"链表为空!\n"; } else { cout<<"链表的元素为: "; p = L->next;//p指向第一个元素 while(p) { cout<<p->data<<" "; p = p->next; } cout<<endl; } } //逆序打印双向链表 void printDlistFromLast(DuLinkList &L) { DuLinkList p; if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else if( L->next == NULL ) { cout<<"链表为空!\n"; } else { p = L->next;// while(p->next) { p = p->next; } //p指向了最后一个 while(p->prior) { cout<<p->data<<" "; p = p->prior; } } } //求链表长度 int lengthDlist(DuLinkList &L) { int i = 0; if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else { DuLinkList p = L->next; while(p) { i++; p = p->next; } } return i; } //判断链表是否为空 void isEmptyOrNotDlist(DuLinkList &L) { if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else if( L->next == NULL ) { cout<<"链表为空!\n"; } else { cout<<"链表非空!\n"; } } //把双向链表置空(头结点保留) void clearTheDlist(DuLinkList &L) { if(L==NULL) { cout<<"链表不存在,请先初始化!\n"; } else { DuLinkList p,q; p = q = L->next; //是p、q指向第一个元素 L->next = NULL; while(p) //逐个释放元素所占内存 { p = p->next; free(q); q = p; } } } //删除双向链表 void delTheDlist(DuLinkList &L) { clearTheDlist(L); free(L); L = NULL; } //在双向链表中第i个位置后面插入元素m void insertElmToDlist(DuLinkList &L) { int i,m; cout<<"输入插入的元素:\n"; cin>>m; cout<<"输入插入的位置:\n"; cin>>i; DuLinkList p,q; p = L; int j = 0; if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else if(L->next == NULL) { cout<<"链表为空,请初始化后再进行插入数据操作!\n"; } else if( i<1 || i>lengthDlist(L)+1 ) { cout<<"插入位置错误!\n"; } else { while( j<i-1 )//找到前一个元素 { p = p->next; j++; } if( j == lengthDlist(L) ) //如果在最后一个元素后面插入m { q = (DuLinkList)malloc(sizeof(DuLnode)); q->data = m; q->next = NULL; q->prior = p; p->next = q; } else { q = (DuLinkList)malloc(sizeof(DuLnode)); q->data = m; q->next = p->next; p->next->prior = q; q->prior = p; p->next = q; } } } //删除双向链表中的第i个元素 void delElmFromDlist(DuLinkList &L) { int i; cout<<"输入要删除的位置:"; cin>>i; int j = 0; DuLinkList p = L; if(L == NULL) { cout<<"链表不存在,请先初始化!\n"; } else if( i<1 || i>lengthDlist(L) ) { cout<<"删除的位置不存在!\n"; } else { while( j<i )//找到第i个元素 { p = p->next; j++; } if( j == lengthDlist(L) )//如果是最后一个元素 { p->prior->next = NULL; free(p); } else { p->prior->next = p->next; p->next->prior = p->prior; free(p); } } } int main() { int i; DuLinkList L = NULL; printTheSelect(); cout<<"请输入操作:"; cin>>i; while( 0 != i) { switch(i) { case 1:initDlist(L); break; case 2:printDlist(L); break; case 3:printDlistFromLast(L); break; case 4:cout<<"链表长度为:"<<lengthDlist(L)<<endl; break; case 5:isEmptyOrNotDlist(L); break; case 6:clearTheDlist(L); break; case 7:insertElmToDlist(L); break; case 8:delElmFromDlist(L); break; case 9:delTheDlist(L); break; default:cout<<"输入错误,请重新输入!\n"; break; } printTheSelect(); cout<<"请输入操作:"; cin>>i; } if(0 == i) { cout<<"程序退出....\n"; } return 0; }
版权属于:东哥笔记 - DongGe.me
本文链接:https://dongge.org/blog/49.html
自2017年12月26日起,『转载以及大段采集进行后续编辑』须注明本文标题和链接!否则禁止所有转载和采集行为!