//* * * * * * * * * * * * * * * * * * * * * * * * //数据结构课程实验 实验一 单链表的插入和删除 * //03计本3班 * // 樊海军 2B0324151138 * //* * * * * * * * * * * * * * * * * * * * * * * * #include #include typedef int ElemType;//单链表结点类型 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; enum BOOL{False,True}; //定义BOOL型 LinkList L; //定义链表 void CmdList() //显示命令列表 { printf("_____________________________________________\n"); printf(" 请选择操作: \n"); printf(" A.显示所有元素\n"); //显示链表元素 printf(" I.插入一个元素\n"); //插入链表元素 printf(" D.删除一个元素\n"); //删除链表元素 printf(" V.链表就地逆置\n"); //就地逆置 printf(" Q.退出程序\n"); //退出 printf("______________________________________________\n"); } void Insert_Sort(LinkList &v,int num) //非递减有序链表插入元素后链表仍有序 { LinkList p1,p2,s; p1=v; p2=v->next; while((p2!=NULL)&&(p2->datanext; } s=(LinkList)malloc(sizeof(LNode)); s->data=num; s->next=p2; p1->next=s; } void CreateList(LinkList &v, int n) //建立链表 { int inchar; int i; v = (LinkList)malloc(sizeof(LNode)); v->next = NULL; // 先建立一个带头结点的单链表 printf("请输入%d个数字:\n",n); for (i=n; i>0; --i) { scanf("%d",&inchar); Insert_Sort(v,inchar); } printf("输入完成!\n\n"); } // CreateList void ListPrint(LinkList v) //显示链表内容 {//显示链表所有元素 LinkList q; q=v->next; printf("链表所有元素:"); while(q!=NULL) {printf("%d ",q->data);q=q->next;} printf("\n"); CmdList(); } BOOL ListInsert(LinkList &v,int e)//插入 { Insert_Sort(v,e); return True; } BOOL ListDelete(LinkList &v,int e) { if(v->next==NULL) //空表 return False; LinkList p,q; p=v; q=p->next; while((q->data!=e)&&(q->next!=NULL))//p指针指向下一个,直到 { p=p->next; q=p->next; } //找到或到链表尾为止 if(q->data!=e) //该元素在链表中不存在) return False; else { p->next=q->next; free(q); return True; } } void ListInvert(LinkList &v)//逆置 { LinkList pa,p,k; pa=v->next; p=k=pa->next; pa->next=NULL; while(p!=NULL) { k=p->next; p->next=pa; pa=p; p=k; } v->next=pa; } void init() { system ("cls"); int num; printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n"); printf("实验一 单链表的插入和删除\n"); printf("03计本3班\n"); printf("樊海军 2B0324151138\n"); printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n"); printf(" 本程序实现单链表的建立、插入、删除和就地逆置等操作。\n"); printf("=================================================================\n"); printf("请输入初始时链表中元素个数:"); //输入生成单链表时的元素个数 scanf("%d",&num); CreateList(L,num); //生成单链表 ListPrint(L); } void ReadCommand(char &c) { do {c=getchar();} while (c!='q'&&c!='Q'&&c!='A'&&c!='a'&&c!='I'&&c!='i'&&c!='D'&&c!='d'&&c!='V'&&c!='v'); } void Interpret(char &c) { BOOL temp; char ch; switch(c) { case 'a':case 'A':ListPrint(L); break; case 'i': case 'I': { printf("请输入要插入的一个数字,例如:3\n"); scanf("%d",&ch); //输入要插入的元素 temp=ListInsert(L,ch); //插入 if(temp==False) printf("插入失败!\n"); //插入失败 else printf("插入成功!\n"); //成功插入 ListPrint(L); break; } case 'd': case 'D':printf("请输入要删除的元素(一个数字),例如:3\n"); scanf("%d",&ch); //输入要删除的元素值 temp=ListDelete(L,ch); //删除 if(temp==False) printf("删除失败!\n"); //删除失败 else printf("成功删除了一个元素:%d\n",ch); //删除成功,显示该元素 ListPrint(L); break; case 'v': case 'V':ListInvert(L); printf("就地逆置成功!\n"); ListPrint(L); break; case 'q': case 'Q': printf("程序结束,按任意键退出!\n"); } } void main() //主函数 { char cmd; init(); do { ReadCommand(cmd); Interpret(cmd); } while (cmd!='q'&&cmd!='Q'); }