鏈表的基本操作

1、2.鏈表的基本操作對鏈表施行的操作有很多種，最基本的操作是在鏈表中插入結(jié)點(diǎn)、在鏈表中刪除結(jié)點(diǎn)、在鏈 表中查找結(jié)點(diǎn)等。鏈表結(jié)點(diǎn)的插入在空鏈表中插入一個結(jié)點(diǎn)空鏈表就是頭指針為空的鏈表。用如下語句申請一個new結(jié)點(diǎn)：new=(struct node)calloc(1,sizeof(struct node);為new結(jié)點(diǎn)填充數(shù)據(jù):將要存儲的數(shù)據(jù)對應(yīng)傳遞給new結(jié)點(diǎn)數(shù)據(jù)域的各個成員。修改有關(guān)指針的指向：將new的next成員置空，使new結(jié)點(diǎn)成為鏈表的最后一個結(jié)點(diǎn)； 將head指向new結(jié)點(diǎn)。在鏈表的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)要在鏈表head的C、D結(jié)點(diǎn)之間出入一個new結(jié)點(diǎn)，就是將new結(jié)點(diǎn)變成C結(jié)點(diǎn)的下一

2、 個結(jié)點(diǎn)，而new結(jié)點(diǎn)的下一個結(jié)點(diǎn)為D結(jié)點(diǎn).操作過程為：使new的指針域存儲結(jié)點(diǎn)D的首地址。使C結(jié)點(diǎn)的指針域存儲結(jié)點(diǎn)new的地址。例2建立學(xué)生成績鏈表，鏈表有3個結(jié)點(diǎn)。#include #define N 3struct s_nodechar num4;int score;struct s_node *next;；main()structsnode*creat_node(void);/*生成鏈表結(jié)點(diǎn)的函數(shù)*/structsnode*creat_list(int n);/*建立鏈表的函數(shù)*/void out_list(struct s_node *head);/*輸出鏈表函數(shù)*/struct s

3、_node *head=NULL;head=creat_list(N);out_list(head);struct s_node *creat_node(void)/*生成鏈表結(jié)點(diǎn)的函數(shù)*/struct s_node *p;int score;fflush(stdin);p=(struct s_node *)calloc(1,sizeof(struct s_node);gets(p-num);scanf(%d”,&score);p-score=score;p-next=NULL;return(p);/*建立鏈表的函數(shù)*/struct s_node * creat_list(int n)stru

4、ct s_node *new,*p;struct s_node *head;int i;if(n=1)new=creat_node();head=new;p=new;for(i=2;inext=new;p=new;if(n=1)return(head);elsereturn(NULL);void out_list(struct s_node *head)/*輸出鏈表函數(shù)*/struct s_node *p;if(head!=NULL)p=head;while(p!=NULL)printf(%s %dn”,p-num,p-score);p=p-next;鏈表結(jié)點(diǎn)的刪除從鏈表中刪除結(jié)點(diǎn)，就是撤銷結(jié)

5、點(diǎn)在鏈表中的鏈接，把結(jié)點(diǎn)從鏈表中孤立出來。在鏈表鏈表 中刪除結(jié)點(diǎn)一般有兩個過程：一是把指定的結(jié)點(diǎn)從鏈表中拿下來，它需要通過修改有關(guān)結(jié)點(diǎn) 的指針域來完成；二是釋放該結(jié)點(diǎn)使用的內(nèi)存空間，它需要使用free()函數(shù)來完成。如下是在head鏈表中刪除p結(jié)點(diǎn)的delete_p()函數(shù)：void delete_p(struct node *head,struct node *p)struct node *q;if(p=NULL)printf(no foundn);return;if(p=head)head=p-next;q=p；elseq=p-next;p-next=q-next;printf(ndele

6、te :%dn,q-data);free(q);鏈表結(jié)點(diǎn)的查找在鏈表中進(jìn)行查找，就是從鏈表的第一個結(jié)點(diǎn)開始，沿著指針鏈，用查找值與鏈表結(jié)點(diǎn)逐個 比較的過程。找到符合要求的結(jié)點(diǎn)之后，停止查找過程，返回相應(yīng)的結(jié)點(diǎn)指針，否則返回一 個空指針。例3查找值為x的結(jié)點(diǎn)并刪除 #include struct node int data;struct node *next;；struct node * creat_number(int n)/*建立鏈表的函數(shù)*/struct node *new,*p;struct node *head;int i;if(n=1)new=(struct node *)mallo

7、c(sizeof(struct node);new-data=1;new-next=NULL;head=new;p=new;for(i=2;idata=i;new-next=NULL;p-next=new;p=new;if(n=1)return(head);elsereturn(NULL);void out_list(struct node *head)/*輸出鏈表函數(shù)*/struct node *p;if(head!=NULL)p=head;while(p!=NULL)printf(%dn”,p-data);p=p-next;struct node *find_x(struct node *

8、head,int x)/雍鏈表中查找的函數(shù)*/struct node *p,*q;p=q=head;while(p!=NULL&p-data!=x)q=p;p=p-next;if(p=NULL)return(NULL);elsereturn(q);void delete_p(struct node *head,struct node *p)/*在鏈表中刪除 p 結(jié)點(diǎn)的函數(shù)*/struct node *q;if(p=NULL)printf(no foundn);return;if(p=head)head=p-next;q=p；elseq=p-next;p-next=q-next;printf(ndelete :%dn,q-data);free(q);main()int n,x;struct node *head=NUL