欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析

 更新時間:2021年11月03日 14:47:07   作者:DDsoup  
鏈表可以說是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了,而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的,不同元素之間在邏輯上相鄰,但是在物理上并不一定相鄰。在維護(hù)一組數(shù)據(jù)集合時,就可以使用鏈表,這一點和數(shù)組很相似

鏈表的概念:鏈表是一種動態(tài)存儲分布的數(shù)據(jù)結(jié)構(gòu),由若干個同一結(jié)構(gòu)類型的結(jié)點依次串連而成。

鏈表分為單向鏈表和雙向鏈表。

鏈表變量一般用指針head表示,用來存放鏈表首結(jié)點的地址。

每個結(jié)點由數(shù)據(jù)部分和下一個結(jié)點的地址部分組成,即每個結(jié)點都指向下一個結(jié)點。最后一個結(jié)點稱為表尾,其下一個結(jié)點的地址部分的值為NULL(表示為空地址)。

特別注意:鏈表中的各個結(jié)點在內(nèi)存中是可以不連續(xù)存放的,具體存放位置由系統(tǒng)分配。

例如:int *ptr ;

因此不可以用ptr++的方式來尋找下一個結(jié)點。

使用鏈表的優(yōu)點:

不需要事先定義存儲空間大小,可以實時動態(tài)分配,內(nèi)存利用效率高;

可以很方便地插入新元素(結(jié)點) ,使鏈表保持排序狀態(tài),操作效率高。

下面用課本的例子來講解:

/*用鏈表實現(xiàn)學(xué)生成績信息的管理*/ 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
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:Create\n 2:Insert\n 3: Delete\n 4:Print\n 0:Exit\n");
		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);    /*調(diào)用插入函數(shù)*/
		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;             /*ptr指向待插入的新的學(xué)生記錄結(jié)點*/
	/*原鏈表為空鏈表時的插入*/
	if(head == NULL){
		head = ptr;
		head->next = NULL;
	}else{
		while((ptr->num > ptr2->num)&&(ptr2->next != NULL)){
			ptr1 = ptr2;
			ptr2 = ptr2->next;         /*ptr1,ptr2各往后移一個結(jié)點*/ 
		}                             
		if(ptr->num <= ptr2->num){     /*在ptr1與ptr2之間插入新結(jié)點*/ 
			if(head == ptr2){
			head=ptr;
		}
		else{
			ptr1->next = ptr;
			ptr->next = ptr2;
		}
		}
		else{                         
			ptr2->next = ptr;          /*新插入結(jié)點成為尾結(jié)點*/
			ptr->next =NULL; 
		}
	}
	return head;
} 
/*刪除操作*/
struct stud_node *DeleteDoc(struct stud_node *head,int num){
	struct stud_node *ptr1,*ptr2;
	/*要被刪除結(jié)點為表頭結(jié)點*/ 
	while(head != NULL && head->num==num){
		ptr2=head;
		head=head->next;
		free(ptr2);
	}
	if(head==NULL){
        return NULL;	
	}         /*鏈表為空*/ 
	/*要被刪除結(jié)點為非表頭結(jié)點*/
	ptr1=head;
	ptr2=head->next;      /*從表頭的下一個結(jié)點搜索所有符合刪除要求的結(jié)點*/
	while(ptr2 != NULL){
		if(ptr2->num == num)/*ptr2所指結(jié)點符合刪除要求*/{
			ptr1->next=ptr2->next;
			free(ptr2);
		}
		else{
			ptr1 = ptr2;         /*ptr1后移一個結(jié)點*/ 
			ptr2 = ptr1->next;        /*ptr2指向ptr1的后一個結(jié)點*/ 
		}
	} 
	return head;
} 
/*遍歷操作*/
void Print_Stu_Doc(struct stud_node *head){
	struct stud_node *ptr;
	  if(head==NULL){
	  	printf("\nNo Records\n");
	  	return;
	  }
	  printf("\nThe Students'Records Are:\n");
	  printf("Num\t Name\t Score\t");
	  for(ptr=head;ptr!=NULL;ptr=ptr->next){
	  	printf("%d\t%s\t%d\n",ptr->num,ptr->name,ptr->score);
	  }
} 

申請大小為 struct stud_node 結(jié)構(gòu)的動態(tài)內(nèi)存空間,新申請到的空間要被強制類型轉(zhuǎn)換成

struct stud_node 型的指針,并保存到指針變量p中,如下:

struct stud_node*p;

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

鏈表的建立:

上面程序中鏈表結(jié)點是按照學(xué)生學(xué)號排序的,若向根據(jù)數(shù)據(jù)輸入的順序來建立鏈表,如下:

/*按輸入順序建立單向鏈表*/
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;       /*把原來鏈表的尾結(jié)點的next域指向該新增的結(jié)點*/
			tail=p;
		}
		scanf("%d %s %d",&num,name,&score);
	}
	return head;
} 

由于按數(shù)據(jù)輸入建立鏈表時,新增加的結(jié)點會加在鏈表末尾,所以該新增結(jié)點的 next 域應(yīng)置成 NULL : p->next = NULL.

鏈表的遍歷:

為了逐個顯示鏈表每個結(jié)點的數(shù)據(jù),程序要不斷從鏈表中讀取結(jié)點內(nèi)容,顯然需要用到循環(huán)。

在for語句中將ptr的初值置為表頭head,當(dāng)ptr不為NULL時循環(huán)繼續(xù),否則循環(huán)結(jié)束。不可以用ptr++來尋找下一個結(jié)點。

鏈表的插入:

插入原則:先連后斷。

首先找到正確位置,然后插入新的結(jié)點。尋找正確位置是一個循環(huán)的過程:從鏈表head開始,把要插入的結(jié)點stud的num分量值與鏈表中結(jié)點的num分量值逐一比較,直到出現(xiàn)要插入結(jié)點的值比第 i 結(jié)點的num分量值大,比第 i+1結(jié)點的分量值小。所以先與第 i+1 結(jié)點相連。再將 i 結(jié)點 與 i+1結(jié)點斷開,并讓 i 結(jié)點與 stud 結(jié)點相連。

鏈表的刪除:

刪除原則:先接后刪。

若被刪除結(jié)點是表頭則 head=head->next ;

其他內(nèi)容省略。

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解分析的文章就介紹到這了,更多相關(guān)C語言 單向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論