#include<stdio.h> #include<stdlib.h> #define OVERFLOW 0 #define ERROR 0#define OK 1 #define Length 5typedef int Status;typedef int ElemType;typedef struct LNode{ ElemType data; struct LNode *next;}LNode,*LinkList;////////////////////////////////建立单链线性表///////////////////////////////////////////////////////////////////////////////////////void CreateList_L(LinkList &L,int n){ //逆位序输入n个元素的值,建立带表头结点的单链线性表L L=(LinkList)malloc(sizeof(LNode)) ; L->next=NULL; //先建立一个带头结点的单链表 for(int i=n;i>0;--i){ LinkList p=(LinkList)malloc(sizeof(LNode)); //生成新结点 printf("输入元素%d:\n",i); scanf("%d",&p->data) ; //输入元素值 p->next=L->next; L->next=p; } printf("\n单链表创建成功!\n"); LinkList q=L->next; for(int i=0;i<n;i++){ printf("%d ",q->data); q=q->next; }}////////////////////////////////得到指定元素///////////////////////////////////////////////////////////////////////////////////////Status GetElem_L(LinkList L,int i,ElemType &e){ //得到线性链表L的第i个元素并将其赋给e //L为带头结点的单链表的头指针 //当第i哥元素存在时,其值赋给e并且返回OK,否则返回ERROR LNode *p=L->next; //初始化,p指向第一个结点,j为计数器 int j=1; //计数器 while(p&&j<i){ //顺指针向后查找,直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p||j>i){ //第i个元素不存在 return ERROR; } e=p->data; //取第i个元素 return OK; }////////////////////////////////插入元素///////////////////////////////////////////////////////////////////////////////////////Status ListInsert_L(LinkList &L,int i,ElemType e){ //在带头结点的单链线性表中第i个位置之前插入元素e LinkList p=L; int j=0; while(p&&j<i-1){ //寻找第i-1个结点 p=p->next; ++j; } if(!p||j>i-1){ return ERROR; } LinkList s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; printf("\n插入操作成功!\n"); LinkList q=L->next; for(int i=0;i<Length+1;i++){ printf("%d ",q->data); q=q->next; } return OK;}////////////////////////////////删除元素///////////////////////////////////////////////////////////////////////////////////////Status ListDelete_L(LinkList &L,int i,ElemType e){ //在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 LinkList p=L; int j=0; while(p->next&&j<i-1){ //寻找第i个结点,并令p指向其前驱 p=p->next; ++j; } if(!(p->next||j>i-1)){ //删除位置不合理 return ERROR; } LNode *q=p->next; //删除并释放结点 p->next=q->next; e=q->data; free(q); printf("\n删除操作成功!\n"); LinkList r=L->next; for(int i=0;i<Length;i++){ printf("%d ",r->data); r=r->next; } return OK; }////////////////////////////////合并单链表///////////////////////////////////////////////////////////////////////////////////////void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { //已知单链表La和Lb的元素按值非递减排列 //归并La和Lb得到新的单链表Lc,Lc的元素也按值非递减排列 LinkList pa=La->next; LinkList pb=Lb->next; LinkList pc=La; Lc=pc; while(pa&&pb){ if(pa->data<pb->data){ pc->next=pa; pc=pa; pa=pa->next; } else{ pc->next=pb; pc=pb; pb=pb->next; } } pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点 printf("\n合并后的单链表为:\n"); LinkList r=Lc->next; for(int i=0;i<Length*2;i++){ printf("%d ",r->data); r=r->next; }}////////////////////////////////主函数///////////////////////////////////////////////////////////////////////////////////////int main(){ /////////////////////创建一个单链表//////////////////////////////// printf("\n-------------------------创建一个单链表------------------------------\n"); LinkList L; CreateList_L(L,Length); /////////////////////得到指定元素//////////////////////////////// printf("\n-------------------------得到指定元素------------------------------\n"); ElemType e; GetElem_L(L,3,e); //得到第五个元素 printf("\n得到的元素是:%d",e); /////////////////////插入指定元素//////////////////////////////// printf("\n-------------------------插入指定元素------------------------------\n"); ListInsert_L(L,3,666); //在第三个元素之前插入666 /////////////////////删除指定元素//////////////////////////////// printf("\n-------------------------删除指定元素------------------------------\n"); ListDelete_L(L,5,e); //删除第五个元素 /////////////////////合并有序单链表La和Lb至Lc//////////////////////////////// printf("\n-------------------------合并有序单链表La和Lb至Lc------------------------------\n"); LinkList La,Lb,Lc; CreateList_L(Lc,0); printf("\n输入单链表La:\n") ; CreateList_L(La,Length); printf("\n\n\n输入单链表Lb:\n") ; CreateList_L(Lb,Length); printf("\n\n"); MergeList_L(La,Lb,Lc); printf("\n"); system("pause"); return 0;}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。