C语言 单向链表 C语言数据结构之单向链表详解分析
DDsoup 人气:0链表的概念：链表是一种动态存储分布的数据结构，由若干个同一结构类型的结点依次串连而成。
链表分为单向链表和双向链表。
链表变量一般用指针head表示，用来存放链表首结点的地址。
每个结点由数据部分和下一个结点的地址部分组成，即每个结点都指向下一个结点。最后一个结点称为表尾，其下一个结点的地址部分的值为NULL（表示为空地址）。
特别注意：链表中的各个结点在内存中是可以不连续存放的，具体存放位置由系统分配。
例如：int *ptr ;
因此不可以用ptr++的方式来寻找下一个结点。
使用链表的优点：
不需要事先定义存储空间大小，可以实时动态分配，内存利用效率高；
可以很方便地插入新元素（结点) ，使链表保持排序状态，操作效率高。
下面用课本的例子来讲解：
/*用链表实现学生成绩信息的管理*/
#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); /*调用插入函数*/
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指向待插入的新的学生记录结点*/
/*原链表为空链表时的插入*/
if(head == NULL){
head = ptr;
head->next = NULL;
}else{
while((ptr->num > ptr2->num)&&(ptr2->next != NULL)){
ptr1 = ptr2;
ptr2 = ptr2->next; /*ptr1,ptr2各往后移一个结点*/
}
if(ptr->num <= ptr2->num){ /*在ptr1与ptr2之间插入新结点*/
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)/*ptr2所指结点符合删除要求*/{
ptr1->next=ptr2->next;
free(ptr2);
}
else{
ptr1 = ptr2; /*ptr1后移一个结点*/
ptr2 = ptr1->next; /*ptr2指向ptr1的后一个结点*/
}
}
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 结构的动态内存空间，新申请到的空间要被强制类型转换成
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; /*把原来链表的尾结点的next域指向该新增的结点*/
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 ;
其他内容省略。
加载全部内容