数据结构——双向链表的有关操作
不是循环链表的双向链表
１．利用尾插法建立一个双向链表。
２．遍历双向链表。
３．实现双向链表中删除一个指定元素。
４．在非递减有序双向链表中实现插入元素e仍有序算法。
５．判断双向链表中元素是否对称若对称返回1否则返回0。
６．设元素为正整型,实现算法把所有奇数排列在偶数之前。
７．在主函数中设计一个简单的菜单调试上述算法。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#define Maxsize 100using namespace std;typedef int Elemtype;typedef struct node{ int data; struct node *pre,*next;}dnode,*dlistlink;dlistlink creat_dlist()//建立带头节点双向链表{ dlistlink L,p,q; L=(dnode *)malloc(sizeof(dnode)); L->pre=NULL; q=L; int x; printf("please enter x:\n"); scanf("%d",&x); while(x!=0) { p=(dnode *)malloc(sizeof(dnode)); if(p==NULL) return 0; p->data=x; q->next=p; p->pre=q; q=p; scanf("%d",&x); } q->next=NULL; return L;}void display(dlistlink L)//遍历带头节点双链表{ dlistlink p; p=L->next; printf("遍历结果为：\n"); while(p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n");}int delete_dlist(dlistlink L,int e)//删除双链表中的一个指定元素 { dlistlink p; p=L->next; while(p!=NULL) { if(p->data==e) { p->pre->next=p->next; p->next->pre=p->pre; return 1; } else p=p->next; } return 0; } int Insertdnode(dlistlink L,int e)//插入指定元素在非递减有序双链表中 { dlistlink p,q; p=L->next; while(p!=NULL) { if(p->data>=e) p=p->next; else break; } p=p->pre; q=(dnode *)malloc(sizeof(dnode)); if(q==NULL) return 0; q->data=e; q->next=p->next; p->next=q; q->pre=p; q->next->pre=q; return 1; } int dlist_duicheng(dlistlink h)//判断双向链表是否对称 { dlistlink p,q; p=h->next; q=h->next;int i=1; while(q->next!=NULL) { q=q->next; i++; } if(i%2) { while(p!=q) { if(p->data!=q->data) return 0; p=p->next; q=q->pre; } } else { while(p->next!=q) { if(p->data!=q->data) return 0; p=p->next; q=q->pre; } if(p->data==q->data) return 1; } return 1; } void odd_dlist(dlistlink h)//实现所有的奇数都排在偶数前面 { dlistlink p,q; p=h->next; while(p!=NULL) { if(p->data%2!=0) { q=p->next; if(p->next!=NULL) { p->next->pre = p->pre; p->pre->next = p->next; } else p->pre->next=NULL; //删除 p->next=h->next; h->next->pre=p; p->pre=h; h->next=p;//插到头结点后面 p=q; } else p=p->next; } } void init(){ printf("*****************菜单*******************\n"); printf("1.运用尾差法创建双链表\n"); printf("2.遍历双向链表\n"); printf("3.实现双链表删除一个指定元素\n"); printf("4.在非递减有序双向链表中实现插入元素e仍有序\n"); printf("5.判断双向链表中元素是否对称若对称返回1否则返回0\n"); printf("6.实现算法把所有奇数排列在偶数之前\n"); printf("0.退出\n"); printf("请选择操作序号：\n");}int main(){ init(); dlistlink h; int n,t,s,flag=1; while(~scanf("%d",&n)) { switch(n) { case 1: h=creat_dlist();break; case 2: display(h); break; case 3:printf("请输入要删除的数：\n"); scanf("%d",&t); if(delete_dlist(h,t)) printf("删除成功\n"); else printf("删除失败\n"); break; case 4:printf("请输入要插入的数：\n"); scanf("%d",&t); if(Insertdnode(h,t)) { printf("插入成功，结果为：\n"); display(h); } else printf("插入失败\n"); break; case 5:if(dlist_duicheng(h)) printf("该链表对称\n"); else printf("该链表不对称\n"); break; case 6:odd_dlist(h); display(h); break; case 0:flag=0;break; } if(flag==0) break; } return 0;}