C---链表

链表的遍历

struct test 
{
     int data
     struct test *next;
}；


void printlink(struct test *head)
{
     while(head!=NULL){
         printf("%d",head->data);
         head = head->next;     
     }
 
}
int main()
{
     struct test t1 = {1,NULL};
     struct test t2 = {2,NULL};	
     struct test t3 = {3,NULL};
     
     t1.next = &t2;
     t2.next = &t3;
     
     printlink(&t1);
    

	return 0;
}
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
28
29

计算链表节点个数

int getlinknode(struct test *head)
{
     int cnt =0;
       while(head !=NULL){
          cnt++;
          
          head = head->next;     
      }
      return cnt;
}

int main()
{
           int ret = getlinknode(&t1);
           printf("node = %d\n",ret);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

查找结点

int searchnode(struct test *head,int data) //（链表头，要找的节点）
{
       while(head !=NULL){
            if(head->data == data){
                   return 1;   
            }  
            head = head->next;     
       }
       
      return 0;
}

int main(){
int t = searchnode(&t1,5);
     if(t==1){
         printf("有\n");     
     }else if(t ==0){
         printf("没有\n");     
     }
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

节点后插入新节点

int insertFromBehind(struct test *head,int data,struct test *new)
{
  struct test *p = head;
         while(p != NULL){
              if(p->data == data){
                  new->next = p->next;
                  p->next = new;          
                  return 1;    
              }      
              p = p->next;   
         }
         return 0;
}

int main()
{
    struct test new = {5,NULL};
    
     insertFromBehind(&t1,3,&new);
     printlink(&t1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 new->next = p->next;
                  p->next = new; 
1
2

原理如图：

节点前插入新节点

分为两种情况：

1.目标节点为头节点 （引起链表头变化）

思想：这个函数返回值是个指针，把这个指针给链表头，去引起main函数里链表头变化

struct test *insertfromfor(struct test *head,int data,struct test *new)
{
         struct test *p = head;
         if(p->data == data){
              new->next = head;
              return new;         //把新的头返回给main        
         }
}

int main()
{
  struct test *head = NULL;	
  struct test new2 = {7,NULL};
  head = &t1;  
  
   head = insertfromfor(head,1,&new2);    //让头等于新的头
   printf("after insert fromfor:\n");
   printlink(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.目标节点不是头节点

添加进这部分就可以：struct test *insertfromfor(struct test *head,int data,struct test *new)

while(p->next !=NULL){
             if(p->next->data == data){
                  new->next = p->next;
                  p->next = new;
                  printf("insert ok\n");
                  return head;   //在这里return head 不要忘也不要弄错位置
             }
             p = p->next;         
         }
1
2
3
4
5
6
7
8
9
10
11

节点前插入新节点（两种情况）完整版

struct test *insertfromfor(struct test *head,int data,struct test *new)
{
         struct test *p = head;
         if(p->data == data){
              new->next = head;
              return new;         
         }
         while(p->next !=NULL){
             if(p->next->data == data){
                  new->next = p->next;
                  p->next = new;
                  printf("insert ok\n");
                  return head;
             }
             p = p->next;         
         }
}

int main()
{
     struct test new2 = {7,NULL};
     struct test new3 = {8,NULL};

      head = insertfromfor(head,1,&new2);
      printf("after insert fromfor:\n");
      printlink(head);
     
      head = insertfromfor(head,1,&new3);  //这里的1已经不是头了，在上一步操作后就变了
      printf("after insert fromfor not head:\n");
      printlink(head);
}

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
28
29
30
31
32

删除节点

课外知识：gcc … -g

              添加一个gdb调试的手段
1

删节点分两种情况

1.删除头节点

struct test *deletnode(struct test *head,int data)
{
       struct test *p = head;         
       if(p->data == data){
          head = head->next;
          free(p);
          return head;      
      }
}

int main()
{
      head = deletnode(head,1);
      printlink(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.删的不是头节点

struct test *deletnode(struct test *head,int data)
{
        struct test *p = head;
        while(p->next != NULL){              
           if(p->next->data == data){
                p->next = p->next->next ;          
           }
           return head;
      }
}

int main()
{
        head = deletnode(head,2);
        printlink(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

头插法动态创建链表

新来的是头，头一直在变，最后返回头

struct test *creathead(struct test *head)
{
       struct test *new ; 
       int i;
       for(i=0;i<5;i++){
            new =(struct test *) malloc(sizeof(struct test));
            printf("输入内容：\n");
            scanf("%d",&(new->data));
            
            if(head==NULL){
                head = new;
                           
            }else{
              new->next = head;
              head = new;              
            }
       }
       return head;
}

int main()
{
       struct test *head = NULL;
       head = creathead(head);
    
       printlink(head);
}
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

优化：

struct test *insertfromhead(struct test *head,struct test *new)
{
    
            if(head==NULL){
                head = new;                          
            }else{
                 new->next = head;
                 head = new;              
            }    
             return head;
}

struct test *creatlink(struct test *head)
{
       
        struct test *new;
      
        while(1){
            new =(struct test *)malloc(sizeof(struct test));
            printf("输入内容：\n");
            scanf("%d",&(new->data));
            
            if(new->data==0){
                 printf("0 quit\n") ;
                 return head;           
            }           
            
            head = insertfromhead(head,new);
}
}

int main()
{
     struct test *head = NULL;	 
     head = creatlink(head);
    
     printlink(head);
         
	 return 0;
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40

尾插法动态创建链表

思想：遍历到最后一个节点，让最后一个节点的next= new

#include 
#include 
 
struct test
{
	int data;
	struct test *next;
};
 
void printLink(struct Ltest* head)
{
	struct test* p = head;
 
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}	
	putchar('\n');    
}
 
struct test* insertfromtail(struct test *head,struct test *new)    //把creatlink中准备好的data连起来
{ 
	struct test *p = head;   //要用p这个指针，否则容易和head混淆。（用p可以改位置，不用的话就改头了）
    if(p == NULL){
        head = new;
        return head;
    }
    while(p->next! =NULL){    
        p = p->next;
    }
    p->next = new;
    
    return head;
}
 
struct test* createLink(struct test *head)    //  提示输入，获取内容，放到data里
{
	struct test *new = NULL;
 
	while(1){
		printf("input your new node data:\n");
		new = (struct test*)malloc(sizeof(struct test));
		scanf("%d",&(new->data));
		if(new->data == 0){
			printf("0 quit\n");
			free(new);            //如果第一次输入数据为0，则新节点new，malloc的空间没用，则free掉
			return head;
		}
		head = insertfromtail(head,new);       
	} 
}
 
int main()
{
 
	struct test *head = NULL;
 
	head = createLink(head);
    
	printLink(head);	//打印链表
 
	return 0;
}
 
 
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

尾插法这里经常犯的错误：
1.尾插法的思想就是把p移到最后，再操作新节点的加入。
2.提示输入，获取新节点的内容之后。再malloc

更改节点（自己写的🤭）

不是头节点：

改头节点