单链表操作（书本）

2018-08-11

loubth

#include<stdio.h> 
#include<stdlib.h>  
#define OVERFLOW 0  
#define ERROR 0
#define OK  1 
#define Length 5
typedef 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;
} 