原创

单链表的创建的两种方式-头插法和尾插法

温馨提示:
本文最后更新于 2021年02月04日,已超过 1,149 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

如果对单链表的基本操作不熟悉可以参考:单链表的基本操作

头插法

每次将新生成的结点插入到最前面。所以如果我们要想插入的元素在链表中是正序的话,我们在插入元素的时候需要逆序输入。
file
算法描述

/*(3)头插法创建链表*/
int CreateListHead_L(LinkList &L,int n){
    for(int i=n;i>0;i--){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素:",n-i+1);
        scanf("%d",&newNode->data);//将输入的值赋给新创建结点的data域 
        newNode->next = L->next;//将新生成的结点指向头结点的下一个结点 
        L->next = newNode;//将头结点指向新生成的结点 
    }
    return 0;
}

尾插法

每次将新生成的结点插入到最后面,所以在这里我们需要一个指向最后一个结点的指针,我们把它叫做尾指针。
file
算法描述

/*(4)尾插法创建链表*/
int CreateListRear_L(LinkList &L,int n){
    LinkList r=L;//尾指针指向此链表
    for(int i=0;i<n;i++){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素:",i+1);
        scanf("%d",&newNode->data);
        newNode->next = r->next;//将新生成的结点指向头结点的下一个结点 
        r->next = newNode;//将新生成的结点指向头结点的下一个结点 
        r = newNode;//将尾指针指向新生成的结点,新结点每次都插入到最后 
    }
    return 0;
}

完整代码

#include <stdio.h>
#include <stdlib.h>
//定义一个链表的结点(元素) 
typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指向自己类型的指针域  
}LNode,*LinkList;//LinkList 为LNode类型的指针 

/*(1)初始化操作*/ 
int InitList_L(LinkList &L) {
    L=(LinkList)malloc(sizeof(LNode));//生成一个LNode类型的 头 结点 
    L->next=NULL;
    return 0;
}

/*(2)获取链表的长度 */
int GetListLength_L(LinkList L){
    LinkList p = L->next; 
    int j = 0;
    while(p){
        p = p->next;
        j++;
    }
    return j;
}

/*(3)头插法创建链表*/
int CreateListHead_L(LinkList &L,int n){
    for(int i=n;i>0;i--){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素:",n-i+1);
        scanf("%d",&newNode->data);//将输入的值赋给新创建结点的data域 
        newNode->next = L->next;//将新生成的结点指向头结点的下一个结点 
        L->next = newNode;//将头结点指向新生成的结点 
    }
    return 0;
} 

/*(4)尾插法创建链表*/
int CreateListRear_L(LinkList &L,int n){
    LinkList r=L;//尾指针指向此链表
    for(int i=0;i<n;i++){
        LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成新的结点 
        printf("请输入第 %d 个的元素:",i+1);
        scanf("%d",&newNode->data);
        newNode->next = r->next;//将新生成的结点指向头结点的下一个结点 
        r->next = newNode;//将新生成的结点指向头结点的下一个结点 
        r = newNode;//将尾指针指向新生成的结点,新结点每次都插入到最后 
    }
    return 0;
} 
/*(5)取值(获取链表指定位置的数据) */
int GetElem_L(LinkList L,int i){
    int j=0;
    LinkList p=L->next;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    return p->data;
} 

main(){
     LinkList L;
     LNode l;
    //初始化
    int initStatus;//初始化状态 
    int isEmpty;//是否为空 
    int headInsertStatus;//头插法插入状态 
    int rearInsertStatus;//删除状态 
    int listLength;//链表长度 
    int num;//插入元素的个数 

    initStatus = InitList_L(L);
    if(initStatus==0){
        printf("初始化成功!\n");
    } else{
        printf("初始化失败!\n");
    } 
    /*头插法*/ 
    printf("【头插法】\n");
    printf("请输入创建元素的个数:");
    scanf("%d",&num);
    headInsertStatus = CreateListHead_L(L,num);
    if(headInsertStatus==0){
        printf("头插法插入成功!\n");
    } else{
        printf("头插法插入失败!\n");
    } 
    /*尾插法*/ 
    printf("【尾插法】\n");
    printf("请输入创建元素的个数:"); 
    scanf("%d",&num);
    rearInsertStatus = CreateListRear_L(L,num);
    if(rearInsertStatus==0){
        printf("尾插法插入成功!\n");
    } else{
        printf("尾插法插入失败!\n");
    } 

   listLength = GetListLength_L(L); 
   printf("链表长度为:%d\n",listLength);

   int t = GetElem_L(L,2);
   printf("链表第一个元素为:%d\n",GetElem_L(L,1));
   printf("链表第二个元素为:%d\n",GetElem_L(L,2));
   printf("链表第三个元素为:%d\n",GetElem_L(L,3));
   printf("链表第四个元素为:%d\n",GetElem_L(L,4));
   printf("链表第五个元素为:%d\n",GetElem_L(L,5));
}

file

正文到此结束
本文目录