【C语言】第九章链表

链表的概念：

1.什么是链表——>数据结构——>数据存放（集合）的思想

链表的每一项都是一个结构体 a->b的地址 b->c的地址                                 

数组：

特点：元素地址连续

缺点：增加元素，删，改，查         不灵活

1.2链表和数组区别及实现

#include "stdio.h"

struct Test{
	int data;
	struct Test *next;
};

int main()
{
	int arr[3] = {1,2,3};
	int i;
	int len;
	len = sizeof(arr)/sizeof(arr[0]);
	for(i=0;idata,t1.next->next->data);
	
	return 0;
}

1.3链表静态添加和动态遍历 

#include "stdio.h"

void printLink(struct Test *head)
{
        struct Test *point;
        point = head;
        while(1)
        {
                if(head != NULL)
                {
                        printf("%d",point->data);
                        point = point->next;
                }
                else
                {
                        printf("n");
                        break;
                }
        }
}

struct Test
{
        int data;
        struct Test *next;
};

int main()
{
   int i;

   int array[] = {1,2,3};
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
        printLink(&t1);
   return 0;
}

 1.4链表遍历中的point=point-next

 1.5统计链表节点个数及链表查找 

1.链表的个数计算

#include "stdio.h"


struct Test
{
        int data;
        struct Test *next;
};


void printLink(struct Test *head)
{
        struct Test *point;
        point = head;
        while(point != NULL){
                        printf("%d",point->data);
                        point = point->next;
        }
        printf("n");
}

int getshu(struct Test *d)
{
        int cnt = 0;
        while(d != NULL)
        {
                cnt++;
                d=d->next;
        }
        return cnt;
}
int main()
{
   int i;
   int ret;
   int array[] = {1,2,3};
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
        printLink(&t1);
   ret = getshu(&t1);
   printf("sum = %dn",ret);
   return 0;

}

2.链表的查找

#include "stdio.h"


struct Test
{
	int data;
	struct Test *next;
};


void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	while(point != NULL){
			printf("%d",point->data);
			point = point->next;
	}  
	printf("n");
}

int getshu(struct Test *d)
{
	int cnt = 0;
	while(d != NULL)
	{
		cnt++;
		d=d->next;
	}
	return cnt;
}

int findshu(struct Test *d,int data)
{
	while(d != NULL)
	{
		if(d->data == data){
			return 1;
		}
		d = d->next;
	}
	return 0;
}
int main()
{
   int i;
   int ret;
   int array[] = {1,2,3};
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
	printLink(&t1);
   ret = getshu(&t1);
   printf("sum = %dn",ret);

   ret = findshu(&t1,1);
  	 if(ret == 0)
	{
		printf("no 1n");
	}
	else
	{
		printf("have 1n");
	}
   ret = findshu(&t1,8);
   if(ret == 0)
	{
		printf("no 8n");
	}	
	else
	{
		printf("have 8n");
	}
   return 0;

}

  1.6 链表从指定节点后方插入新节点

插入新节点：

节点后：

节点前：

#include "stdio.h"


struct Test
{
	int data;
	struct Test *next;
};

int charubenhind(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;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	while(point != NULL){
			printf("%d  ",point->data);
			point = point->next;
	}  
	printf("n");
}

int getshu(struct Test *d)
{
	int cnt = 0;
	while(d != NULL)
	{
		cnt++;
		d=d->next;
	}
	return cnt;
}

int findshu(struct Test *d,int data)
{
	while(d != NULL)
	{
		if(d->data == data){
			return 1;
		}
		d = d->next;
	}
	return 0;
}
int main()
{
   int i;
   int ret;
   int array[] = {1,2,3};
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
	printLink(&t1);
   charubenhind(&t1,1,&new);
	
	printLink(&t1);
 return 0;

}

  1.7链表从指定节点前方插入新节点

前方插入：

1.第一个节点是目标节点修改链表头

2.第一个节点是中间节点添加链表元素

1. 第一个节点是目标节点修改链表头

#include "stdio.h"
struct Test
{
	int data;
	struct Test *next;
};
//1.第一个节点是链表头
struct Test* inserFromfor(struct Test *head,int data,struct Test *new)
{
	struct Test *p = head;
	if(p->data == data)
	{
		new->next = head;
		return new;
	}
}
int charubenhind(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;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	while(point != NULL){
			printf("%d  ",point->data);
			point = point->next;
	}  
	printf("n");
}

int getshu(struct Test *d)
{
	int cnt = 0;
	while(d != NULL)
	{
		cnt++;
		d=d->next;
	}
	return cnt;
}

int findshu(struct Test *d,int data)
{
	while(d != NULL)
	{
		if(d->data == data){
			return 1;
		}
		d = d->next;
	}
	return 0;
}
int main()
{
   int i;
   int ret;
   int array[] = {1,2,3};
   struct Test *head = NULL;
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
	printLink(head);
   charubenhind(head,1,&new);
	printLink(head);
	struct Test new2 = {101,NULL};
	head = inserFromfor(head,1,&new2);
	printLink(head);
}

 2.第一个节点是中间节点添加链表元素

#include "stdio.h"


struct Test
{
	int data;
	struct Test *next;
};

struct Test* inserFromfor(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;
			return head;
		}
		p = p->next;
	}
	printf("no this data%d",data);
	return head;
}
int charubenhind(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;
}

void printLink(struct Test *head)
{
	struct Test *point;
	point = head;
	while(point != NULL){
			printf("%d  ",point->data);
			point = point->next;
	}  
	printf("n");
}

int getshu(struct Test *d)
{
	int cnt = 0;
	while(d != NULL)
	{
		cnt++;
		d=d->next;
	}
	return cnt;
}

int findshu(struct Test *d,int data)
{
	while(d != NULL)
	{
		if(d->data == data){
			return 1;
		}
		d = d->next;
	}
	return 0;
}
int main()
{
   int i;
   int ret;
   int array[] = {1,2,3};
   struct Test *head = NULL;
   for(i=0;idata,t1.next->next->data,t1.next->next->next->data);
	printLink(head);
   charubenhind(head,1,&new);
	
	printLink(head);

	struct Test new2 = {101,NULL};
	head = inserFromfor(head,1,&new2);
	printLink(head);
	struct Test new3 = {103,NULL};
	head = inserFromfor(head,1,&new3);
	printLink(head);
 return 0;

}