#include<stdio.h> #include<stdlib.h> typedef int elemtype; typedef struct node/*单链表结构体的定义*/ { elemtype data; struct node *next; } node,*linklist; void main_menu();/*主菜单函数*/ node* creatfromhead();/*从头结点插入建立单链表*/ node* get(linklist l);/*单链表的遍历*/ node* reverselist(linklist l);/*将带头结点的单链表逆置*/ node* creatfeidijian();/*头插法建立非递减单链表*/ node* combine(linklist la,linklist lb);/*将两个非递减链表合成一个非递减连表*/ node* inslist(linklist l,elemtype e);/*在非递减有序链表中插入一个元素使链表仍然有序*/ node* deletelist(linklist l,elemtype *x);/*在非递减单链表中删除值为x的结点*/ int main()/*主函数*/ { int input; main_menu(); return 0; } void main_menu()/*主菜单函数*/ { int input; printf("\t\t\t单链表的建立及其简单操作\t\t\n\n"); printf("\t\t 1 从头结点插入建立单链表\n"); printf("\t\t 2 单链表的遍历\n"); printf("\t\t 3 将带头结点的单链表逆置\n"); printf("\t\t 4 头插法建立非递减单链表\n"); printf("\t\t 5 将两个非递减链表合成一个非递减连表\n"); printf("\t\t 6 在非递减有序链表中插入一个元素使链表仍然有序\n"); printf("\t\t 7 在非递减单链表中删除值为x的结点\n"); printf("\t\t 0 退出\n"); printf("\t\t注意事项:初始化单链表的时候以“0”结束初始化!!!!\n"); printf("请输入需要操作的项目序号:"); scanf("%d",&input); switch(input) { case 1:{ node* head; printf("请输入一个单链表用“0”来结束输入:"); head=creatfromhead(); printf("初始化后的单链表为:"); get(head); printf("\n\n"); main_menu(); break; } case 2:{ node* head; printf("请首先输入一个单链表用“0”来结束输入:"); head=creatfromhead(); printf("单链表的遍历结果为:"); get(head); printf("\n\n"); main_menu(); break; } case 3:{ node* head; printf("请输入需要逆置的单链表:"); head=creatfromhead(); printf("初始化后的单链表为:"); get(head); printf("单链表的逆置结果为:"); head=reverselist(head); get(head); printf("\n\n"); main_menu(); break; } case 4:{ node* head; printf("请输入一个非递减单链表序列:"); head=creatfromhead(); printf("初始化后的单链表为:"); get(head); printf("\n\n"); main_menu(); break; } case 5:{ node* la,*lb,*head; printf("请输入非递减的单链表la:"); la=creatfromhead(); printf("单链表la为:"); get(la); printf("请输入非递减的单链表lb:"); lb=creatfromhead(); printf("单链表lb为:"); get(lb); head=combine(la,lb); printf("合并之后的新的单链表为:"); get(head); printf("\n\n"); main_menu(); break; } case 6:{ node* head;elemtype e; printf("请输入一个非递减单链表序列:"); head=creatfromhead(); printf("初始化后的单链表为:"); get(head); printf("请输入一个需要插入的元素:"); scanf("%d",&e); head=inslist(head,e); printf("插入之后的单链表为:"); get(head); printf("\n\n"); main_menu(); break; } case 7:{ node* head;elemtype e; printf("请输入一个非递减单链表序列:"); head=creatfromhead(); printf("初始化后的单链表为:"); get(head); printf("请输入一个需要删除的元素:"); scanf("%d",&e); head=deletelist(head,e); printf("删除之后的单链表为:"); get(head); printf("\n\n"); main_menu(); break; } case 0: { exit(0);break; } } } node* creatfromhead()/*头插法建立单链表*/ { linklist l; node *s; int c; int flag=1; l=(node*)malloc(sizeof(node)); if(l==NULL) { printf("申请空间失败!!"); return 0; } l->next=NULL; while(flag) { scanf("%d",&c); if(c!=0) { s=(node*)malloc(sizeof(node)); if(s==NULL) { printf("申请空间失败!!"); return 0; } s->data=c; s->next=l->next ; l->next=s; } else flag=0; } return l; } node* get(linklist l)/*单链表的遍历*/ { node *p; p=l->next; while(p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } node* reverselist(linklist l)/*将带头结点的单链表逆置*/ { node *q,*p; p=l->next; l->next=NULL; while(p!=NULL) { q=p->next; p->next=l->next; l->next=p; p=q; } return l; } node* creatfeidijian()/*头插法建立非递减单链表*/ { linklist l; node *s; int c; int flag=1; printf("%s","请输入一个非递减数列!!"); l=(node*)malloc(sizeof(node)); if(l==NULL) { printf("申请空间失败!!"); return 0; } l->next=NULL; while(flag) { scanf("%d",&c); if(c!=0) { s=(node*)malloc(sizeof(node)); if(s==NULL) { printf("申请空间失败!!"); return 0; } s->data=c; s->next=l->next ; l->next=s; } else flag=0; } return l; } node* combine(linklist la,linklist lb) /*将两个非递减链表合成一个非递减连表*/ { node *pa,*pb,*r; linklist lc; pa=la->next; pb=lb->next; lc=la; lc->next=NULL;r=lc; while(pa!=NULL&&pb!=NULL) { if(pa->data<=pb->data) { r->next=pa;r=pa;pa=pa->next; } else { r->next=pb;r=pb;pb=pb->next; } } if(pa) r->next=pa; else r->next=pb; free(lb); return(lc); } node *inslist(linklist l,elemtype e) /*在非递减有序链表中插入一个元素使链表仍然有序*/ { node *s,*p; p=l; while(l!=NULL) { if(e>=l->data&&e<=l->next->data) { s=(node*)malloc(sizeof(node)); s->data=e; s->next=l->next; l->next=s; break; } else l=l->next; } return p; } node * deletelist(linklist l,elemtype x) /*在非递减单链表中删除值为x的结点*/ { node *p,*r,*q; p=l->next;q=l; while(p!=NULL) { if(p->data==x) { r=p; p=r->next; q->next=p; free(r); break; } else { q=p;/*保留前驱节点*/ p=p->next; } } if(p==NULL) printf("删除失败,没有找到相应的元素\n"); return l; }