(转)c语言_链表实例讲解(两个经典例子)

建立一个学生成绩的线性链表，对其实现插入，删除，输出，最后销毁。

 

#include <stdio.h>
#include <stdlib.h>

struct grade
 {
    int score;
    struct grade *next; 
 };
typedef struct grade NODE;  //typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。
                             //使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，
        //另一个是简化一些比较复杂的类型声明。
 struct grade *create();   //创建链表
 void insert(NODE *head,NODE *pnew,int i);   //插入链表
 void pdelete(NODE *head,int i);   //删除列表
 void display(NODE *head);   //输出链表
 void Pfree(NODE *head);    //销毁链表
 
int main(int argc, char *argv[])
{
 struct grade *head,*pnew;
 head=create();
 if(head==NULL)
 return 0;
 printf("输出创建的链表：");
 display(head);
 pnew=(NODE *)malloc(sizeof(NODE));
 if(pnew==NULL)
 {
  printf("创建失败！");
  return 0;
 }
 pnew->score=88;
 insert(head,pnew, 3);   //将新节点插入节点3的后面
 printf("插入后的链表：");
 display(head);
 pdelete(head,3);   //删除节点3
 printf("删除后的链表：");
 display(head);
 Pfree(head);
 return 0;
}

struct grade *create()
{
 NODE *head,*tail,*pnew;
     int score;
    head=(NODE *)malloc(sizeof(NODE));  //创建头节点。
  if(head==NULL)  //创建失败返回
  {
   printf("创建失败！");
   return NULL;
   }
    head->next=NULL;  //头节点指针域置NULL
 tail=head;  // 开始时尾指针指向头节点
 printf("输入学生成绩：");
 while(1)    //创建链表
 {
  scanf("%d",&score);
  if(score<0)  //成绩为负是退出循环
    break;
  pnew=(NODE *)malloc(sizeof(NODE));  //创建新节点
  if(pnew==NULL)  //创建失败返回
  {
   printf("创建失败！");
   return NULL;
  } 
  pnew->score=score;  //新节点数据域存放输入的成绩
  pnew->next=NULL;   //新节点指针域置NULL
  tail->next=pnew;  //新节点插入到表尾
  tail=pnew;   //为指针指向当前的尾节点
 }
 return head;  //返回创建链表的头指针
}
void insert(NODE *head,NODE *pnew,int i)
{
 NODE *p;
 int j;
   
    p=head;
    for(j=0;j<i&&p!=NULL;j++)  //p指向要插入的第i个节点
      p=p->next;
    if(p==NULL)  //节点i不存在
 {
  printf("与插入的节点不存在！");
  return;
 } 
 
 pnew->next=p->next;   //插入节点的指针域指向第i个节点的后继节点
 p->next=pnew;    //犟第i个节点的指针域指向插入的新节点
}

void pdelete(NODE *head,int i)
{
 NODE *p,*q;
 int j;
 if(i==0)  //删除的是头指针，返回
   return;
 p=head;
 for(j=1;j<i&&p->next!=NULL;j++)
   p=p->next;  //将p指向要删除的第i个节点的前驱节点
 if(p->next==NULL)  //表明链表中的节点不存在
 {
  printf("不存在！");
  return;
 } 
 q=p->next;  //q指向待删除的节点
 p->next=q->next;  //删除节点i，也可写成p->next=p->next->next
 free(q);   //释放节点i的内存单元
}
void display(NODE *head)
{
 NODE *p;
 for(p=head->next;p!=NULL;p=p->next)
   printf("%d ",p->score);
 printf(" "); 
}
void pfree(NODE *head)
{
 NODE *p,*q;
 
 p=head;
 while(p->next!=NULL)    //每次删除头节点的后继节点
 {
  q=p->next;  
  p->next=q->next;
  free(q);
 }
 free (head);  //最后删除头节点
}
void Pfree(NODE *head)
{
 NODE *p,*q;
 p=head;
 while(p->next!=NULL)
 {
  q=p->next;
  p->next=q->next;
  free(q);
 }
 free(p);
}

转自：http://hi.baidu.com/y%C9%D9%B0%D7y/blog/item/fa9f1c5b1525b500367abe80.html

链表是C语言中比较难，但是又比较重要的数据结构，相信有很多人在为它而头痛哦。
我做了一个链表的程序，发出来与大家共享，希望大家能用得着。


#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <stdlib.h>

//链表单元定义，链表相关变量
struct student
{
int id;
float score;
struct student *next;
} *head,*pthis;

//输入数据创建链表
void input()
{
struct student *tmp;
printf(" 请输入学生的信息以学号为0结束: ");
do
{
printf("ID 成绩 ");
if((tmp=(struct student*)malloc(sizeof(struct student)))==NULL)
{
printf(" 错误!不能申请所需的内存! ");
exit(0);
}
scanf("%d %f",&tmp->id,&tmp->score);
tmp->next=NULL;
if(tmp->id!=0)
{
if(head==NULL)
{
head=tmp;
pthis=head;
}
else
{
pthis->next=tmp;
pthis=pthis->next;
}
}
}
while(tmp->id!=0);
free(tmp);
}

//搜索链表找到第一个符合条件的项目输出
void search(int id)
{
printf(" 查询结果 ");
printf("ID 成绩 ");
printf("------------------------------- ");
if(head==NULL)
{
printf(" 错误!没有数据! ");
return;
}
pthis=head;
while(pthis!=NULL)
{
if(pthis->id==id)
{
printf("%d %.2f ",pthis->id,pthis->score);
return;
}
else
{
pthis=pthis->next;
}
}
printf(" 没有找到! ");
}

//列表输出链表中的所有项
void list()
{
printf(" 数据列表 ");
printf("ID 成绩 ");
printf("------------------------------- ");
if(head==NULL)
{
printf("错误,没有数据! ");
return;
}
pthis=head;
while(pthis!=NULL)
{
printf("%d %.2f ",pthis->id,pthis->score);
pthis=pthis->next;
}
}

//插入数据
void insert()
{
int i,p;
struct student *tmp;
if(head==NULL)
{
printf(" 数据不存在，无法插入! ");
return;
}
printf(" 请输入插入点: ");
scanf("%d",&p);
if(p<0)
{
printf("输入不合法!");
return;
}
printf(" 请输入学生的信息: ID 成绩 ");
if((tmp=(struct student*)malloc(sizeof(struct student)))==NULL)
{
printf(" 错误!不能申请所需的内存! ");
exit(0);
}
scanf("%d %f",&tmp->id,&tmp->score);
tmp->next=NULL;
if(tmp->id!=0)
{
pthis=head;
if(p==0)
{
tmp->next=head;
head=tmp;
}
else
{
for(i=0;i<p-1;i++)
{
if(pthis->next->next==NULL)
{
printf(" 找不到插入点，您输入的数据太大! ");
return;
}
pthis=pthis->next;
}
tmp->next=pthis->next;
pthis->next=tmp;
}
}
else
{
printf(" 数据无效! ");
free(tmp);
}
}

//追加数据
void append()
{
struct student *tmp;
printf(" 请输入学生的信息: ID 成绩 ");
if((tmp=(struct student*)malloc(sizeof(struct student)))==NULL)
{
printf(" 错误!不能申请所需的内存! ");
exit(0);
}
scanf("%d %f",&tmp->id,&tmp->score);
tmp->next=NULL;
if(tmp->id!=0)
{
if(head==NULL)
{
head=tmp;
}
else
{
pthis=head;
while(pthis->next!=NULL)
{
pthis=pthis->next;
}
pthis->next=tmp;
}
}
else
{
free(tmp);
printf(" 数据无效! ");
}
}

//删除数据
void del()
{
int p,i;
struct student *tmp;
if(head==NULL)
{
printf(" 没有数据，无法删除! ");
return;
}
printf(" 请输入要删除的记录号: ");
scanf("%d",&p);
if(p<0)
{
printf(" 输入不合法! ");
return;
}
if(p==0)
{
pthis=head;
head=pthis->next;
free(pthis);
pthis=head;
}
else
{
pthis=head;
for(i=0;i<p-1;i++)
{
pthis=pthis->next;
if(pthis->next==NULL)
{
printf(" 指定记录不存在，无法删除! ");
return;
}
}
tmp=pthis->next;
pthis->next=pthis->next->next;
free(tmp);
}
}

//程序主函数
void main()
{
char command=0;
int id=0;

//主循环
do
{
printf(" 菜单 ");
printf("------------------------------- ");
printf(" a,输入数据 ");
printf(" b,查询记录 ");
printf(" c,数据列表 ");
printf(" d,追加记录 ");
printf(" e,插入记录 ");
printf(" f,删除记录 ");
printf(" g,退出系统 ");
printf("------------------------------- ");
printf(" 请选择:");
command=getch();

//命令处理
switch(command)
{
case 'a':
if(head==NULL)
{
input();
break;
}
else
{
printf(" 数据已经存在！ ");
break;
}
case 'b':
printf(" 要查询的ID:");
scanf("%d",&id);
search(id);
break;
case 'c':
list();
break;
case 'd':
append();
break;
case 'e':
insert();
break;
case 'f':
del();
break;
}
}
while(command!='g');
}

=====================

  • #include <stdio.h>   
  • #include <string.h>   
  • #include <stdlib.h>   
  • typedef struct student  
  • {  
  •     int num;  
  •     char name[16];  
  •     struct student *next;  
  • }node;  
  • node *creat()//创建链表   
  • {  
  •     int x;  
  •     int cycle = 1;  
  •     char stu_name[16];  
  •     node *head,*p,*s;  
  •     head =(node*)malloc(sizeof(node));  
  •     p = head;  
  •     while(cycle)  
  •     {  
  •         printf("please input the student number:");  
  •         scanf("%d",&x);  
  •         if(x != 0)  
  •         {  
  •             printf("please input the student name:");  
  •             scanf("%s",stu_name);  
  •         //  printf("STU_NAME:%s/n", stu_name);   
  •             s = (node *)malloc(sizeof(node));  
  •                         if(NULL == s)  
  •                         {  
  •                         exit(1);  
  •                         }  
  •             s->num = x;  
  •             memcpy(s->name, stu_name, 16);  
  •             p->next = s;  
  •             p = s;   
  •         }  
  •         else  
  •             cycle = 0;  
  •     }  
  •     head = head->next;  
  •     p->next = NULL;  
  •     return head;  
  • }  
  • int length(node *head)//链表测长   
  • {  
  •     int n = 0;  
  •     node *p;  
  •     p = head;  
  •     while(p != NULL)  
  •     {  
  •         n++;  
  •                 p = p->next;  
  •                   
  •     }  
  •     return (n);  
  • }  
  • node *insert(node *head, int num, int length)//链表插入,NUM表示在第几个位置插入   
  • {  
  •     int n=num;  
  •     int i = 1;  
  •     node *p0,*p1,*p2;  
  •     p1 = head;  
  •     p0 = (node *)malloc(sizeof(node));  
  •     printf("please input the student number:");  
  •     scanf("%d", &p0->num);  
  •     printf("please input the student name:");  
  •     scanf("%s", &p0->name);  
  •     if(n == 1)//插入表头   
  •     {  
  •         p0->next = p1;  
  •         head = p0;  
  •         return (head);  
  •     }  
  •     while(i < n-1)//找到要插入的前置节点   
  •     {  
  •         p1 = p1->next;  
  •         i++;  
  •     }  
  •     p2 = p1->next;  
  •     p1->next = p0;  
  •     p0->next = p2;  
  •     if(n == length+1)//插入表尾   
  •     {  
  •         p1->next = p0;  
  •         p0->next = NULL;  
  •     }  
  •     return (head);  
  • }  
  • node *delete(node *head, int location, int length)//删除链表节点   
  • {  
  •     int n = location;  
  •     int i = 1;  
  •     node *p1,*p2;  
  •     p1 = head;  
  •     if(n == 1)  
  •     {  
  •         head = p1->next;  
  •         free(p1);  
  •         return (head);  
  •     }  
  •     while(i < n-1)//找到要删除的节点的前置节点   
  •     {  
  •         p1 = p1->next;  
  •         i++;  
  •     }  
  •     if(n < length)  
  •     {  
  •         p2 = p1->next;  
  •         p1->next = p2->next;  
  •         free(p2);  
  •     }  
  •     if(n == length)  
  •     {  
  •         p2 = p1->next;  
  •         p1->next = NULL;  
  •         free(p2);  
  •     }  
  •     return (head);  
  • }  
  • void print(node *head)  
  • {  
  •     while(head != NULL)  
  •     {  
  •         printf("students:%d/n", head->num);  
  •                 printf("student name: %s/n", head->name);  
  •         head = head->next;  
  •                   
  •     }  
  • }  
  • node *invert(node *head)//链表逆置   
  • {  
  • node *p1,*p2,*p3;  
  • p1 = head;  
  • p2 = p1->next;  
  • while(p2)  
  • {  
  • p3 = p2->next;  
  • p2->next = p1;  
  • p1=p2;  
  • p2=p3;  
  • }  
  • head->next = NULL;  
  • head = p1;  
  • return (head);  
  • }  
  • int main(int argc, char **argv)  
  • {  
  •     int len,insert_num,del_num;  
  •     node *stu_node;  
  •     stu_node = creat();  
  •     print(stu_node);  
  •     len = length(stu_node);  
  •     printf("there are %d node/n", len);  
  •     printf("what dou you want to do?/n[a]打印链表 [b]逆置链表 [c]删除节点 [d]插入节点: ");  
  • char ch,c;  
  • c = getchar();//用于清除缓冲区中的/n字符   
  • scanf("%c",&ch);  
  •     switch (ch)  
  •     {  
  •         case 'a': print(stu_node);  
  •               break;  
  •         case 'b': stu_node = invert(stu_node);  
  •               print(stu_node);  
  •               break;  
  •         case 'c':   
  •               printf("which node dou you want to detele?:");  
  •               scanf("%d", &del_num);  
  •               stu_node = delete(stu_node, del_num, len);  
  •               print(stu_node);  
  •               break;  
  •         case 'd':  
  •               printf("which location dou you want to insert:");  
  •               scanf("%d",&insert_num);  
  •               stu_node = insert(stu_node , insert_num, len);  
  •               print(stu_node);  
  •               break;  
  •     }  
  •     return 0;  
  • }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xuyuantao/p/3250014.html