C语言——单向链表

C语言——单向链表

        链表的概念：链表是一种动态存储分布的数据结构，由若干个同一结构类型的结点依次串连而成。

        链表分为单向链表和双向链表。

        链表变量一般用指针head表示，用来存放链表首结点的地址。

        每个结点由数据部分和下一个结点的地址部分组成，即每个结点都指向下一个结点。最后一个结点称为表尾，其下一个结点的地址部分的值为NULL（表示为空地址）。

        特别注意：链表中的各个结点在内存中是可以不连续存放的，具体存放位置由系统分配。

例如：int *ptr ; 

        因此不可以用ptr++的方式来寻找下一个结点。

        使用链表的优点：

        不需要事先定义存储空间大小，可以实时动态分配，内存利用效率高；

        可以很方便地插入新元素（结点) ，使链表保持排序状态， *** 作效率高。

下面用课本的例子来讲解：

 
#include
#include
#include
struct stud_node{
	int num;
	char name[24];
	int score;
	struct stud_node *next;
};
struct stud_node *Create_Stu_Doc();   
struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud);   
struct stud_node *DeleteDoc(struct stud_node *head,int num);       
void Print_Stu_Doc(struct stud_node *head);              

int main(void)
{
	struct stud_node *head,*p;
	int choice,num,score;
	char name[20];
	int size = sizeof(struct stud_node);
	
	do{
		printf("1:Createn 2:Insertn 3: Deleten 4:Printn 0:Exitn");
		scanf("%d",&choice);
		switch(choice){
			case 1:
			    head = Create_Stu_Doc();
			    break;
			case 2:
				printf("Input num,name and score:n");
				scanf("%d %s %d",&num,name,&score);
				p = (struct stud_node *)malloc(size);
				p->num = num;
				strcpy(p->name,name);
				p->score = score;
				head = InsertDoc(head,p);
				break;
			case 3:
				printf("Input num:n");
				scanf("%d",&num);
				head = DeleteDoc(head,num);
				break;
			case 4:
				Print_Stu_Doc(head);
				break;
			case 0:
				break;
		}
	}
	while(choice != 0);
	
	return 0;
 } 

struct stud_node *Create_Stu_Doc(){
	struct stud_node *head,*p;
	int num,score;
	char name[20];
	int size = sizeof(struct stud_node);
	
	head = NULL;
	printf("Input num,name and score:n");
	scanf("%d %s %d",&num,name,&score);
	while(num != 0){
		p=(struct stud_node *)malloc(size);
		p->num = num;
		strcpy(p->name,name);
		p->score = score;
		head = InsertDoc(head,p);    
		scanf("%d %s %d",&num,name,&score); 
	}
	return head;
} 

struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud){
	struct stud_node *ptr,*ptr1,*ptr2;
	ptr2 = head;
	ptr = stud;             
	
	if(head == NULL){
		head = ptr;
		head->next = NULL;
	}else{
		while((ptr->num > ptr2->num)&&(ptr2->next != NULL)){
			ptr1 = ptr2;
			ptr2 = ptr2->next;          
		}                             
		if(ptr->num <= ptr2->num){      
			if(head == ptr2){
			head=ptr;
		}
		else{
			ptr1->next = ptr;
			ptr->next = ptr2;
		}
		}
		else{                         
			ptr2->next = ptr;          
			ptr->next =NULL; 
		}
	}
	return head;
} 

struct stud_node *DeleteDoc(struct stud_node *head,int num){
	struct stud_node *ptr1,*ptr2;
	 
	while(head != NULL && head->num==num){
		ptr2=head;
		head=head->next;
		free(ptr2);
	}
	if(head==NULL){
        return NULL;	
	}          
	
	ptr1=head;
	ptr2=head->next;      
	while(ptr2 != NULL){
		if(ptr2->num == num){
			ptr1->next=ptr2->next;
			free(ptr2);
		}
		else{
			ptr1 = ptr2;          
			ptr2 = ptr1->next;         
		}
	} 
	return head;
} 

void Print_Stu_Doc(struct stud_node *head){
	struct stud_node *ptr;
	  if(head==NULL){
	  	printf("nNo Recordsn");
	  	return;
	  }
	  printf("nThe Students'Records Are:n");
	  printf("Numt Namet Scoret");
	  for(ptr=head;ptr!=NULL;ptr=ptr->next){
	  	printf("%dt%st%dn",ptr->num,ptr->name,ptr->score);
	  }
} 

       申请大小为 struct stud_node 结构的动态内存空间，新申请到的空间要被强制类型转换成

struct stud_node 型的指针，并保存到指针变量p中，如下：

        struct stud_node*p；

        p = ( struct stud_node *)malloc(sizeof( struct stud_node ));

链表的建立：

       上面程序中链表结点是按照学生学号排序的，若向根据数据输入的顺序来建立链表，如下：

struct stud_node *Create_Stu_Doc(){
	int num,score;
	char name[20];
	int size = sizeof(struct stud_node);
	struct stud_node *head,*tail,*p;
	head=tail=NULL;
	printf("Input num,name and score:n");
	scanf("%d %s %d",&num,name,&score);
	while(num!=0){
		p=(struct stud_node *)malloc(size);
		p->num = num;
		strcpy(p->name,name);
		p->score = score;
		p->next = NULL;
		if(head == NULL){
			head = p;
		}else{
			tail->next=p;       
			tail=p;
		}
		scanf("%d %s %d",&num,name,&score);
	}
	return head;
} 

       由于按数据输入建立链表时，新增加的结点会加在链表末尾，所以该新增结点的 next 域应置成 NULL ：   p->next = NULL.

链表的遍历：

       为了逐个显示链表每个结点的数据，程序要不断从链表中读取结点内容，显然需要用到循环。

在for语句中将ptr的初值置为表头head，当ptr不为NULL时循环继续，否则循环结束。不可以用ptr++来寻找下一个结点。

链表的插入：

       插入原则：先连后断。

       首先找到正确位置，然后插入新的结点。寻找正确位置是一个循环的过程：从链表head开始，把要插入的结点stud的num分量值与链表中结点的num分量值逐一比较，直到出现要插入结点的值比第 i 结点的num分量值大，比第 i+1结点的分量值小。所以先与第 i+1 结点相连。再将 i 结点 与 i+1结点断开，并让 i 结点与 stud 结点相连。

链表的删除：

       删除原则：先接后删。

       若被删除结点是表头则 head=head->next ; 

       其他内容省略。