单链表基本操作(2)_6-1 单链表

单链表基本操作(2)

• 公共结构体
• 模拟测试链表
• 展示链表数据
• 定位
  
  1. 
     
  2. 按号定位
  3. 按值定位
• 求链表长度
• 插入
• 删除
• 合并

1.公共结构体

创建结构类型,在CS.c文件中

typedef struct node{
    int data;
    struct node *next;
}LINKLIST;
1
2
3
4
5
6

2.模拟测试链表

在Link.h写出方法声明

/*
 模拟链表数据
 */
LINKLIST *testLinkList();
1
2
3
4
5

在Link.c中实现此方法

#include "Link.h"

LINKLIST *testLinkList(){
    LINKLIST  *Q,*L;
    Q=(LINKLIST *)malloc(sizeof(LINKLIST));
    L=Q;
    Q->data=-1;
    Q->next=NULL;

    int x=0;
    LINKLIST *temp;
    while(x!=10){
        x++;
        temp=(LINKLIST *)malloc(sizeof(LINKLIST));
        temp->data=x;
        temp->next=NULL;
        Q->next=temp;
        Q=temp;
    };
    return L;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

使用的是尾插入方式插入数据

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {
    LINKLIST *SQ=testLinkList();
}
1
2
3
4
5
6

3.展示链表数据

link.h 声明方法

/*
  打印链表中的节点数据
 */

void showLinkList(LINKLIST *Q);
1
2
3
4
5
6

link.c 实现方法

void showLinkList(LINKLIST *Q){
    LINKLIST *p;
    p=Q;
    printf("list=[");
    while (p!=NULL) {
        if(p->data==-1){
            printf("%d",p->data);
        }else{
            printf(",%d",p->data);
        }
        p=p->next;
    }
    printf("]\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

    LINKLIST *SQ=testLinkList();
    showLinkList(SQ);
}
1
2
3
4
5
6
7
8

打印结果:

list=[-1,1,2,3,4,5,6,7,8,9,10]
1
2

4.定位

4.1按号定位

link.h 声明

/*
 查找链表中指定位置的元素是否存在--按号定位
 */
LINKLIST *locbn(LINKLIST *Q,int i);
1
2
3
4
5

link.c 实现

LINKLIST *locbn(LINKLIST *Q,int i){
    LINKLIST *p;

    int j=0;
    //1.判断查找的位置是否小于等于0,因为不存在此节点,则直接返回NULL
    if(i<=0){
        return NULL;
    }
    p=Q;
    //2.判断当前计数j是否等于i,如果不等于,则表示还没有找到要查找的位置,并且当前p不能为NULL
    while (j!=i&& p!=NULL) {
        //3.判断条件不成立,则继续查找下一个节点
        p= p->next;
        //4.计数器自增+1
        j++;
    }
    return  p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

     printf("定位->按号定位\n");
     //按号定位
     LINKLIST *SQ=testLinkList();
    int index=8;
    LINKLIST *p=locbn(SQ,index);
    if(p!=NULL){
        printf("SQ in %d node of data =%d \n",index,p->data);
    }else{
        printf("SQ 不存在此 %d 位置的节点 \n",index);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

打印结果:

定位->按号定位
SQ in 8 node of data =8 
1
2
3

4.2按值定位

link.h 声明

/*
 查找链表中指定位置的元素是否存在--按值定位
 */
LINKLIST *locbv(LINKLIST *Q,int x);
1
2
3
4
5

link.c 实现

LINKLIST *locbv(LINKLIST *Q,int x){
    LINKLIST *p;
    p=Q;
    //1.当前节点不能为NULL,并且查找的数据域data不等于要查找的数值x,则表示还没找到要查找的数值
    while (p!=NULL && p->data!=x){
        //2.条件不成立,则继续往下一个节点查找
        p=p->next;
    }

    return p;
}
1
2
3
4
5
6
7
8
9
10
11

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

     //按值定位
      printf("定位->按值定位\n");
      LINKLIST *SQ=testLinkList();
     int value=80;
     LINKLIST *pv=locbn(SQ,value);
    if(pv!=NULL){
        printf(" %d in linkst ,值为 %d\n",value,pv->data);
    }else{
        printf("SQ 不存在此 %d 值的节点 \n",value);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

打印结果:

定位->按值定位
SQ 不存在此 80 值的节点
1
2
3

5.求链表长度

link.h 声明方法

/*
 求链表长度
 */
int  lenll(LINKLIST *Q);
1
2
3
4

link.c 实现方法

int  lenll(LINKLIST *Q){

    int  len=0;
    LINKLIST *p;
    p=Q;
    //1.第一判断链表不为NULL,并且下一个指针域也不为NULL
    //3.len变量自增+1
    for(;p!=NULL && p->next!=NULL;len++){
        //2.将指针域赋给当前节点变量,即:往下查找一个节点
        p=p->next;
    }
    return len;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

    LINKLIST *SQ=testLinkList();
    //求链表长度
    printf("求链表长度\n");
    int  len=lenll(SQ);
    printf("链表长度=%d \n",len);

}
1
2
3
4
5
6
7
8
9
10
11
12

打印结果:

求链表长度
链表长度=10 
1
2
3

6.插入

link.h 声明方法

/*
 向指定位置插入结点
 */
LINKLIST * insterByPosition(LINKLIST *Q,int position);
1
2
3
4
5

link.c 实现方法

LINKLIST * insterByPosition(LINKLIST *Q,int position){
    LINKLIST  *q;
    //为了不改变原来的链表
    q=Q;
    //1.先找到指定位置的position-1位置的节点
     LINKLIST * preInsterNode= locbn(q, position-1);
    if(preInsterNode==NULL){//前一个结点为NULL,则插入的节点位置不存在
        printf("Loction position errer!");
    }else{
        LINKLIST *insterNode=(LINKLIST *)malloc(sizeof(LINKLIST));
        //2.判断查插入的节点是否为NULL,为NULL,则插入失败
        if(insterNode==NULL){
            printf("inster node is NULL");
        }else{
            insterNode->data=position;
            //3.将插入的结点的指针域指向插入位置的后一个结点
            insterNode->next=preInsterNode->next;
            //4.将插入结点位置的前一个指针域指向插入插入的节点;
            preInsterNode->next=insterNode;

            printf("inster success\n");
        }
    }
    return q;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

    LINKLIST *SQ=testLinkList();
    //插入
    printf("插入结点\n");
    showLinkList(SQ);
    LINKLIST *insterAfterList= insterByPosition(SQ, 2);
    showLinkList(insterAfterList);
}
1
2
3
4
5
6
7
8
9
10
11
12

打印结果:

插入结点
list=[-1,1,2,3,4,5,6,7,8,9,10]
inster success
list=[-1,1,2,2,3,4,5,6,7,8,9,10]
1
2
3
4
5

7.删除

link.h 声明方法

/*
 删除指定位置的节点
 */
LINKLIST * delete(LINKLIST *Q,int index);
1
2
3
4
5

link.c 实现方法

LINKLIST * delete(LINKLIST *Q,int index){
    LINKLIST *p;
    p=Q;
    LINKLIST *preNode,*deleteNode;
    //1.判断链表的长度是否小于要删除节点的位置,如果小于,则表示链表中不存在此节点,否则就存在
    if(lenll(p)<index){
        printf("Location error!\n");
    }else{
        //2.获取删除节点的前一个结点
        preNode=locbn(Q, index-1);
        //3.通过前一个结点找到要删除的节点,即:删除节点的下一个节点
        deleteNode=preNode->next;
        //4.然后把删除节点的指针域赋给了删除节点前一个节点的指针域
        preNode->next=deleteNode->next;
        //5.同时要释放删除节点的
        free(deleteNode);
        deleteNode=NULL;
        printf("Locatio delete success!\n");
    }

    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

    LINKLIST *SQ=testLinkList();
    //删除
      printf("删除某个结点\n");
      showLinkList(SQ);
      LINKLIST *deleteAfterList= delete(SQ, 5);
      showLinkList(deleteAfterList);
}
1
2
3
4
5
6
7
8
9
10
11
12

打印结果:

删除某个结点
list=[-1,1,2,3,4,5,6,7,8,9,10]
Locatio delete success!
list=[-1,1,2,3,4,6,7,8,9,10]
1
2
3
4
5

8.合并

link.h 声明方法

/*
 合并A和B,将B合并到A链表后面
 */
LINKLIST *conll(LINKLIST *A,LINKLIST *B);
1
2
3
4
5

link.c 实现方法

LINKLIST *conll(LINKLIST *A,LINKLIST *B){
    LINKLIST *conP;
    conP=A;
    //1.判断要合并的B是否为BULL,和指针域是否为NULL,因为链表一般有一个头结点,应该查找从首节点开始合并
    if(B==NULL || B->next==NULL){
        return conP;
    }
    //2.如果A节点为NULL,那么也不能拼接
    if(A==NULL){
        return B;
    }
    //3.查找A链表的终结点
    while (A->next!=NULL) {
        A=A->next;
    }
    //4.将B插入到conP的最后面
    A->next=B->next;
    //5.释放B链表
    free(B);

    printf("合并成功\n");
    return conP;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include <stdio.h>
#include "Link.h"
int main(int argc, const char * argv[]) {

   //合并节点
    printf("合并链表\n");
    //创建两个链表
    LINKLIST *A=testLinkList();
    LINKLIST *B=testLinkList();
    //展示要合并链表的节点
    showLinkList(A);
    showLinkList(B);
    //合并
    LINKLIST *AB= conll(A, B);

    //展示合并后的链表
    showLinkList(AB);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

打印结果:

合并链表
list=[-1,1,2,3,4,5,6,7,8,9,10]
list=[-1,1,2,3,4,5,6,7,8,9,10]
合并成功
list=[-1,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]
1
2
3
4
5
6

释放某个对象的方法,使用free()方法,则要引入:

#include <stdlib.h>
1
2

这是对链表的基本操作,大家有好的建议,请大家提出,互相学习和进步.
源码下载