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

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

demo1

 // lianbiao.cpp : Defines the entry point for the console application.

 //

 #include "stdafx.h"

 #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 ;

     printf("输出创建的链表：");

     display(head);

     pnew=(NODE *)malloc(sizeof(NODE));

     if (pnew==NULL) {

         printf("创建失败！");

         return ;

     }

     pnew->score=;

     insert(head,pnew, );   //将新节点插入节点3的后面

     printf("插入后的链表：");

     display(head);

     pdelete(head,);   //删除节点3

     printf("删除后的链表：");

     display(head);

     Pfree(head);

     return ;

 }

 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 () {                                    //创建链表

         scanf("%d", &score);

         if (score<)                            //成绩为负是退出循环

             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=; 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==) //删除的是头指针，返回

         return;

     p=head;

     for (j=; 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("\n");

 }

 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);

 }

demo2

 #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("\n\n请输入学生的信息以学号为0结束:\n");

     do {

         printf("ID\t成绩\n");

         if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {

             printf("\n错误!不能申请所需的内存!\n");

             exit();

         }

         scanf("%d\t%f",&tmp->id,&tmp->score);

         tmp->next=NULL;

         if (tmp->id!=) {

             if (head==NULL) {

                 head=tmp;

                 pthis=head;

             } else {

                 pthis->next=tmp;

                 pthis=pthis->next;

             }

         }

     } while (tmp->id!=);

     free(tmp);

 }

 //搜索链表找到第一个符合条件的项目输出

 void search(int id) {

     printf("\n\n查询结果\n");

     printf("ID\t成绩\n");

     printf("-------------------------------\n");

     if (head==NULL) {

         printf("\n错误!没有数据!\n");

         return;

     }

     pthis=head;

     while (pthis!=NULL) {

         if (pthis->id==id) {

             printf("%d\t%.2f\n",pthis->id,pthis->score);

             return;

         } else {

             pthis=pthis->next;

         }

     }

     printf("\n没有找到!\n");

 }

 //列表输出链表中的所有项

 void list() {

     printf("\n\n数据列表\n");

     printf("ID\t成绩\n");

     printf("-------------------------------\n");

     if (head==NULL) {

         printf("错误,没有数据!\n");

         return;

     }

     pthis=head;

     while (pthis!=NULL) {

         printf("%d\t%.2f\n",pthis->id,pthis->score);

         pthis=pthis->next;

     }

 }

 //插入数据

 void insert() {

     int i,p;

     struct student *tmp;

     if (head==NULL) {

         printf("\n\n数据不存在，无法插入!\n");

         return;

     }

     printf("\n请输入插入点:\n");

     scanf("%d",&p);

     if (p<) {

         printf("输入不合法!");

         return;

     }

     printf("\n\n请输入学生的信息:\nID\t成绩\n");

     if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {

         printf("\n错误!不能申请所需的内存!\n");

         exit();

     }

     scanf("%d\t%f",&tmp->id,&tmp->score);

     tmp->next=NULL;

     if (tmp->id!=) {

         pthis=head;

         if (p==) {

             tmp->next=head;

             head=tmp;

         } else {

             for (i=; i<p-; i++) {

                 if (pthis->next->next==NULL) {

                     printf("\n找不到插入点，您输入的数据太大!\n");

                     return;

                 }

                 pthis=pthis->next;

             }

             tmp->next=pthis->next;

             pthis->next=tmp;

         }

     } else {

         printf("\n数据无效!\n");

         free(tmp);

     }

 }

 //追加数据

 void append() {

     struct student *tmp;

     printf("\n\n请输入学生的信息:\nID\t成绩\n");

     if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {

         printf("\n错误!不能申请所需的内存!\n");

         exit();

     }

     scanf("%d\t%f",&tmp->id,&tmp->score);

     tmp->next=NULL;

     if (tmp->id!=) {

         if (head==NULL) {

             head=tmp;

         } else {

             pthis=head;

             while (pthis->next!=NULL) {

                 pthis=pthis->next;

             }

             pthis->next=tmp;

         }

     } else {

         free(tmp);

         printf("\n数据无效!\n");

     }

 }

 //删除数据

 void del() {

     int p,i;

     struct student *tmp;

     if (head==NULL) {

         printf("\n\n没有数据，无法删除!\n");

         return;

     }

     printf("\n\n请输入要删除的记录号:\n");

     scanf("%d",&p);

     if (p<) {

         printf("\n输入不合法!\n");

         return;

     }

     if (p==) {

         pthis=head;

         head=pthis->next;

         free(pthis);

         pthis=head;

     } else {

         pthis=head;

         for (i=; i<p-; i++) {

             pthis=pthis->next;

             if (pthis->next==NULL) {

                 printf("\n\n指定记录不存在，无法删除!\n");

                 return;

             }

         }

         tmp=pthis->next;

         pthis->next=pthis->next->next;

         free(tmp);

     }

 }

 //程序主函数

 void main() {

     char command=;

     int id=;

 //主循环

     do {

         printf("\n\n\t 菜单\n");

         printf("-------------------------------\n");

         printf("\ta,输入数据\n");

         printf("\tb,查询记录\n");

         printf("\tc,数据列表\n");

         printf("\td,追加记录\n");

         printf("\te,插入记录\n");

         printf("\tf,删除记录\n");

         printf("\tg,退出系统\n");

         printf("-------------------------------\n");

         printf("\t请选择:");

         command=getch();

 //命令处理

         switch (command) {

         case 'a':

             if (head==NULL) {

                 input();

                 break;

             } else {

                 printf("\n\n数据已经存在！\n");

                 break;

             }

         case 'b':

             printf("\n\n要查询的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');

 }

http://www.oschina.net/code/snippet_105637_43706

巴特西

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

最新文章

热门文章