投稿
  1. 首页
  2. C

链表头插法尾插法，反转单链表，C代码

搬砖是什么意思 • 2022-6-10 • C • 阅读 87

链表头插法尾插法，反转单链表，C代码,第1张

#include 
#include 

typedef struct node{
    int data;
    struct node *next;
}lnode;

// 头插法创建链表
lnode* createHead(){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=p->next;
        p->next=q;
    }
    return head;
}


// 尾插法创建链表
lnode* createTail(){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return head; //head是头
}


//遍历链表
void print(lnode *list){
    lnode *p=list->next;
    while(p!=NULL){
        printf("%d\n",p->data);
        p=p->next;
    }
}
int main()
{
    lnode *list;
    list=createTail();//创建一个单链表，尾插法
    print(list);
    return 0;
}
定义结构体 
//typedef 给struct node 起了个名字叫 lnode
// lnoe qw 等价于 struct node
typedef struct node{
    int data; //存放数据域
    struct node *next;//存放指针域
}lnode;
头插法(插入是逆序) 
// 头插法创建链表
lnode* createHead(){
	//定义了三个指针类型的lnode head是头指针
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=p->next;
        p->next=q;
    }
    return head;
}
尾插法（插入是正序） 

// 尾插法创建链表
lnode* createTail(){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return head; //head是头
}
遍历链表 
//遍历链表
void print(lnode *list){
    lnode *p=list->next;
    while(p!=NULL){
        printf("%d\n",p->data);
        p=p->next;
    }
}
计算单链表长 
int listlen(lnode *list){
    lnode *p=list->next;
    int len =0;
    while(p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}
统计链表中 x出现的次数 
int  count_x_in_list(lnode *list,int x){
    lnode *p=list->next;
    int count=0;
    while(p!=NULL){
        if(p->data==x)
            count++;
        p=p->next;
    }
    return count;
}
翻转链表思路1

将原先链表遍历一遍，放到数组中，然后使用头插法，将这个数组构建成单链表
1.遍历原先链表，数据放到数组中

//翻转链表 1,2,3,4,5 变成 5,4,3,2,1
lnode* fan(lnode *list){
    lnode *test,*p=list->next;
    int a[1000];
    int i=0;
    while(p!=NULL){
        a[i++]=p->data;
        p=p->next;
    }
    test=headcr(a,i);
    return test;
}

2.使用头插法，根据数据构建一个新的链表

//头插法建立,根据数组建立单链表
lnode* headcr(int a[],int len){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < len; i++) {
        q=(lnode *) malloc(sizeof(lnode));
        q->data=i;
        q->next=p->next;
        p->next=q;
    }
    return head;
}

翻转链表思路2 新建两个指针一前一后 逐个断链再链接

// 翻转链表
lnode* reverse(lnode *list){
    // p是当前 ,prev是前一个 ,next是后一个
    lnode *p,*prev,*next;
    prev=NULL;
    p=list->next;
    while(p){
        next=p->next;
        p->next=prev;
        prev=p;
        p=next;
    }
    return prev;
}
链表的插入 
// 链表的插入
void insert(lnode *list,int i,int e){
    lnode *p,*q;
    int j=0;
    p=list;
    while(p!=NULL && j<i-1){
        j++;
        p=p->next;
    }
    q=(lnode *)malloc(sizeof(lnode));
    q->data=e;
    q->next=p->next;
    p->next=q;
}
链表的按序号删除 
//链表的删除按序号删除
void delete1(lnode *list,int i){
    lnode *p,*q;
    p=list;
    int j=0;
    while(p && j<i-1){
        j++;
        p=p->next;
    }
    q=p->next;
    p->next=q->next;
    free(q);
}
删除第一个元素 
void delete2(lnode *list,int key){
    lnode *p,*q;
    p=list;
    q=list->next;
    while(p && q){
        if(q->data==key){
            p->next=q->next;
            free(q);
            break;
        }
        p=p->next;
        q=q->next;
    }
    
}
删除表中所有值为x的 
//删除单链表中所有值为key的结点
void delete3(lnode *list,int key){
    lnode *p,*q;
    p=list;
    q=p->next;
    while(p && q){
        if(q->data==key){
            p->next=q->next;
            free(q);
            q=p->next;
        }
        p=p->next;
        q=q->next;
    }
}
单链表去重 
//单链表去重
void divsum(lnode *list){
    lnode *p;
    p=list->next;
    while(p){
        delete3(p,p->data);
        p=p->next;
    }
}

链表查找算法

//查找算法 查找第i个位置上的(按位查找)
void find(lnode *list,int i){
    lnode *p;
    p=list;
    int j=0;
    while(p && j<i){
        j++;
        p=p->next;
    }
    if(j==i)
        printf("查找成功 :%d",p->data);
    else
        printf("查找失败");
}

//按值查找 找给给指定相等的第一个节点
void findfirst(lnode *list,int key){
    lnode *p;
    p=list;
    int i=0;
    while(p){
        if(p->data==key){
              printf("查找成功 %d",i);
              break;
        }
        p=p->next;
        i++;
    }
    if(p==NULL)
        printf("查找失败");
}
合并单链表 
//合并两个有序单链表 {1,3,5,7,9} {2,4,6,7,8,10}
//第一步后  先按照顺序插入到链表位置 {1,2,3,4,5,6,7,7,8,9}
//第二部 将剩余结点插入到pc链表中  {1,2,3,4,5,6,7,7,8,9,10}
//第三步 单链表去重 {1,2,3,4,5,6,7,8,9,10}
lnode* mergelinkList(lnode *la,lnode *lb){

    lnode *pa=la->next,*pb=lb->next;
    lnode *pc,*p,*q;
    pc=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    printf("\n");
    // 先按照顺序插入到链表位置
    while(pa!=NULL && pb!=NULL){
        if(pa->data > pb->data)
        {
            q=(lnode *)malloc(sizeof(lnode));
            q->data=pb->data;
            q->next=NULL;
            p->next=q;
            p=q;
            
            pb=pb->next;
        }
        if(pa->data <= pb->data)
        {
            q=(lnode *)malloc(sizeof(lnode));
            q->data=pa->data;
            q->next=NULL;
            p->next=q;
            p=q;
            
            pa=pa->next;
        }

    }
    //将剩余结点插入到pc链表中
    if(pa!=NULL)
        p->next=pa;
    else
        p->next=pb;
        
        
    //单链表去重
    divsum(pc);
    return pc;
}
总体 
#include 
#include 

//结构体
typedef struct node{
    int data;
    struct node *next;
}lnode;

// 头插法创建链表
lnode* createHead(){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=p->next;
        p->next=q;
    }
    return head;
}

// 尾插法创建链表
lnode* createTail(){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    for (int i = 0; i < 10; i++) {
        q=(lnode *)malloc(sizeof(lnode));
        q->data=i;
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return head; //head是头
}

//遍历链表（带头结点）
void print(lnode *list){
    lnode *p=list->next;
    while(p!=NULL){
        printf("%d  ",p->data);
        p=p->next;
    }
}

//遍历链表（不带头结点）
void print1(lnode *list){
    lnode *p=list;
    while(p!=NULL){
        printf("%d  ",p->data);
        p=p->next;
    }
}

// 计算链表长度
int listlen(lnode *list){
    lnode *p=list->next;
    int len =0;
    while(p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}

//计算单链表中出现x的次数
int  count_x_in_list(lnode *list,int x){
    lnode *p=list->next;
    int count=0;
    while(p!=NULL){
        if(p->data==x)
            count++;
        p=p->next;
    }
    return count;
}

//头插法建立,根据数组建立单链表
lnode* headcr(int a[],int len){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < len; i++) {
        q=(lnode *) malloc(sizeof(lnode));
        q->data=i;
        q->next=p->next;
        p->next=q;
    }
    return head;
}
//尾插法建立,根据数组建立单链表
lnode* endcr(int a[],int len){
    lnode *head,*p,*q;
    head=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    for (int i = 0; i < len; i++) {
        q=(lnode *) malloc(sizeof(lnode));
        q->data=a[i];
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return head;
}

//翻转链表 1,2,3,4,5 变成 5,4,3,2,1
lnode* fan(lnode *list){
    lnode *test,*p=list->next;
    int a[1000];
    int i=0;
    while(p!=NULL){
        a[i++]=p->data;
        p=p->next;
    }
    test=headcr(a,i);
    return test;
}
// 翻转链表
lnode* reverse(lnode *list){
    // p是当前 ,prev是前一个 ,next是后一个
    lnode *p,*prev,*next;
    prev=NULL;
    p=list->next;
    while(p){
        next=p->next;
        p->next=prev;
        prev=p;
        p=next;
    }
    return prev;
}
// 链表的插入
void insert(lnode *list,int i,int e){
    lnode *p,*q;
    int j=0;
    p=list;
    while(p!=NULL && j<i-1){
        j++;
        p=p->next;
    }
    q=(lnode *)malloc(sizeof(lnode));
    q->data=e;
    q->next=p->next;
    p->next=q;
}
//链表的删除按序号删除
void delete1(lnode *list,int i){
    lnode *p,*q;
    p=list;
    int j=0;
    while(p && j<i-1){
        j++;
        p=p->next;
    }
    q=p->next;
    p->next=q->next;
    free(q);
}

//删除单链表中值为key的第一个数字
void delete2(lnode *list,int key){
    lnode *p,*q;
    p=list;
    q=list->next;
    while(p && q){
        if(q->data==key){
            p->next=q->next;
            free(q);
            break;
        }
        p=p->next;
        q=q->next;
    }
    
}
//删除单链表中所有值为key的结点
void delete3(lnode *list,int key){
    lnode *p,*q;
    p=list;
    q=p->next;
    while(p && q){
        if(q->data==key){
            p->next=q->next;
            free(q);
            q=p->next;
        }
        p=p->next;
        q=q->next;
    }
}

//单链表去重
void divsum(lnode *list){
    lnode *p;
    p=list->next;
    while(p){
        delete3(p,p->data);
        p=p->next;
    }
}

//查找算法 查找第i个位置上的(按位查找)
void find(lnode *list,int i){
    lnode *p;
    p=list;
    int j=0;
    while(p && j<i){
        j++;
        p=p->next;
    }
    if(j==i)
        printf("查找成功 :%d",p->data);
    else
        printf("查找失败");
}
//按值查找 找给给指定相等的第一个节点
void findfirst(lnode *list,int key){
    lnode *p;
    p=list;
    int i=0;
    while(p){
        if(p->data==key){
              printf("查找成功 %d",i);
              break;
        }
        p=p->next;
        i++;
    }
    if(p==NULL)
        printf("查找失败");
}
//合并两个有序单链表 {1,3,5,7,9} {2,4,6,7,8,10}
//第一步后  先按照顺序插入到链表位置 {1,2,3,4,5,6,7,7,8,9}
//第二部 将剩余结点插入到pc链表中  {1,2,3,4,5,6,7,7,8,9,10}
//第三步 单链表去重 {1,2,3,4,5,6,7,8,9,10}
lnode* mergelinkList(lnode *la,lnode *lb){

    lnode *pa=la->next,*pb=lb->next;
    lnode *pc,*p,*q;
    pc=p=(lnode *)malloc(sizeof(lnode));
    p->next=NULL;
    printf("\n");
    // 先按照顺序插入到链表位置
    while(pa!=NULL && pb!=NULL){
        if(pa->data > pb->data)
        {
            q=(lnode *)malloc(sizeof(lnode));
            q->data=pb->data;
            q->next=NULL;
            p->next=q;
            p=q;
            
            pb=pb->next;
        }
        if(pa->data <= pb->data)
        {
            q=(lnode *)malloc(sizeof(lnode));
            q->data=pa->data;
            q->next=NULL;
            p->next=q;
            p=q;
            
            pa=pa->next;
        }

    }
    //将剩余结点插入到pc链表中
    if(pa!=NULL)
        p->next=pa;
    else
        p->next=pb;
        
        
    //单链表去重
    divsum(pc);
    return pc;
}



int main()
{
    // lnode *list;    
    // list=createTail();//创建一个单链表，尾插法
    // print(list);    //打印单链表
    // printf("\n");
    // int len=listlen(list);//计算单链表长度
    // printf("单链表长度:%d\n",len);
    // int countx=count_x_in_list(list,5);
    // printf("x 在链表中出现的次数%d\n",countx);
    
    //翻转链表
    // lnode* newlist= reverse(list);
    // print1(newlist);
    
    //在链表的第2个位置插入99
    // print(list);
    // printf("\n");
    
    
    //删除第2个结点
    // delete1(list,2);
    // print(list);
    
    // 删除元素2
    // delete2(list,99);
    
    //单链表去重
    // divsum(list);
    // print(list);
    
    //查找 *** 作
    // find(list,4);
    // findfirst(list,8);
    
    //合并两个有序单链表
    //先创建两个
    int arr[]={1,3,5,7,9};
    int brr[]={2,4,6,7,8,10};
    lnode *la,*lb,*lc;
    
    la=endcr(arr,5);
    lb=endcr(brr,6);
    print(la);
    printf("\n");
    print(lb);
    
    lc=mergelinkList(la,lb);
    printf("\n");
    print(lc);
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1296135.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
搬砖是什么意思 搬砖是什么意思 一级用户组
0 0
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表（0条）

保存