双向链表的建立、插入、查找和删除
#include <stdio.h> #include <stdlib.h> typedef int ListData; typedef struct dnode { ListData data; struct dnode *llink,*rlink; }DblNode; typedef DblNode* DblList; DblList CreatList(DblList &first)//创建双向链表 { first=(DblList)malloc(sizeof(DblNode)); ListData x; if(first==NULL) { printf("存储分配错!\n"); exit(1); } first->llink=first->rlink=NULL; DblNode *p,*q=first; printf("Please input the elements of the list:\n"); do { scanf("%d",&x); p=(DblNode*)malloc(sizeof(DblNode)); p->data=x; p->llink=q; q->rlink=p; q=p; }while(getchar()!='\n'); q->rlink=NULL; return first; } DblList Insert(DblList &first,int i,ListData x)//向链表中插入某个节点 { DblNode *p=first,*q; for(int k=0;k<i-1;k++)//找到第i-1个结点,即要插入位置的前驱 { if(p==NULL) break; else p=p->rlink; } if(p==NULL||i<=0)printf("无效的插入位置!\n"); else { q=(DblNode*)malloc(sizeof(DblNode)); q->data=x; q->llink=p; q->rlink=p->rlink; if(p->rlink!=NULL) p->rlink->llink=q; p->rlink=q; } return first; } DblList Delete(DblList &first,ListData x)//删除链表中某个节点 { DblNode *p=first->rlink; while(p!=NULL&&p->data!=x) { p=p->rlink; } if(p==NULL)printf("无效的删除!\n"); else { if(p->rlink!=NULL) p->rlink->llink=p->llink; p->llink->rlink=p->rlink; free(p); } return first; } int Findv(DblList first,ListData x)//按值查找 { DblNode *p=first->rlink; int i=1; while(p!=NULL&&p->data!=x) { p=p->rlink; i++; } if(p==NULL){printf("查找失败!\n");return 0;} else return i; } ListData Finds(DblList first,int s)//按序号查找 { DblNode *p=first; for(int k=0;k<s;k++) { if(p==NULL) break; else p=p->rlink; } if(s<=0||p==NULL){printf("查找失败!\n");return-1;} return p->data; } void OutPut(DblList first)//输出链表中元素 { printf("Output the elements of the List:\n"); DblNode *p=first->rlink; while(p!=NULL) { printf("%d\t",p->data); p=p->rlink; } printf("\n"); } int main() { DblList first=NULL; int s;ListData x; first=CreatList(first); OutPut(first); printf("要插入的值和位置分别为:\t"); scanf("%d%d",&x,&s); first=Insert(first,s,x); OutPut(first); printf("按值查找要查找的值为:\t"); scanf("%d",&x); s=Findv(first,x); if(s!=0) printf("按值查找该值所在位置为:\t%d\n",s); printf("按序号查找要查找的位置为:\t"); scanf("%d",&s); x=Finds(first,s); if(x!=-1) printf("按序号查找该位置的值为:\t%d\n",x); printf("要删除的结点值为:\t"); scanf("%d",&x); first=Delete(first,x); OutPut(first); return 0; }运行结果：
