C语言实现链表功能(单链表基础版本)
浏览数:6 

所谓链表,就是用一组任意的存储单元存储线性表元素的一种数据结构。

链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。

所谓单链表,是指数据接点是单向排列的。一个单链表结点,其结构类型分为两部分:

1、数据域:用来存储本身数据

2、链域或称为指针域:用来存储下一个结点地址或者说指向其直接后继的指针。


struct stu{

   char            name[32];

   struct stu      *next;

};

这样就定义了一个单链表的结构,其中char name[20]是一个用来存储姓名的字符型数组,指针*link是一个用来存储其直接后继的指针。

定义好了链表的结构之后,只要在程序运行的时候爱数据域中存储适当的数据,如有后继结点,则把链域指向其直接后继,若没有,则置为NULL。

单链表的基本运算:

建立了一个单链表之后,如果要进行一些如插入、删除等操作该怎么办?所以还须掌握一些单链表的基本算法,来实现这些操作。单链表的基本运算包括:查找、插入和删除。

1、查找

对单链表进行查找的思路为:对单链表的结点依次扫描,检测其数据域是否是我们所要查好的值,若是返回该结点的指针,否则返回NULL。

因为在单链表的链域中包含了后继结点的存储地址,所以当我们实现的时候,只要知道该单链表的头指针,即可依次对每个结点的数据域进行检测。

2、插入(后插)

假设在一个单链表中存在2个连续结点p、q(其中p为q的直接前驱),若我们需要在p、q之间插入一个新结点s,那么我们必须先为s分配空间并赋值,然后使p的链域存储s的地址,s的链域存储q的地址即可。(p->link=s;s->link=q),这样就完成了插入操作。

3、删除

假如我们已经知道了要删除的结点p的位置,那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址,并回收p结点即可。


下面是自己写的简单的单链表代码:


#include<stdio.h>

#include<string.h>

#include<stdlib.h>

struct stu{

   char                    name[32];

   struct stu      *next;

};

/*创建链表,参数n是初始化链表时建立的数据个数

prev:指向当前结点的前一个结点

cur:指向当前结点

head:保存表头结点的指针*/

struct stu* CreatList(int n){

   int i;

   char age[12];

   struct stu *prev,*cur,*head;

   head=(struct stu*)malloc(sizeof(struct stu));

   if(head==NULL){

       printf("Can't alloc memory\n");

       return NULL;

   }

   prev=head;

   head->name[0]='\0';

   head->next=NULL;

   for(i=1;i<=n;i++){

       cur=(struct stu*)malloc(sizeof(struct stu));

       if(cur==NULL){

           printf("Can't alloc memory\n");

           return NULL;                

       }

       prev->next=cur;

       printf("请输入第%d个数据的姓名\n",i);

       printf("请输入姓名:");

       scanf("%s",cur->name);

       cur->next=NULL;

       prev=cur;

   }

   printf("创建链表成功!\n");

   return head;

}/*这样就写好了一个可以建立包含N个人姓名的单链表了。

写动态内存分配的程序应注意,请尽量对分配是否成功进行检测。*/


/*查找链表的函数,其中head指针是链表的表头指针,_name指针是要查找的人的姓名

返回值:返回与所要查找结点的地址*/

struct stu* SearchCur(struct stu *head,char *_name){

   struct stu  *cur,*tmp;

   char                *str;

   cur=head->next;

   while(cur!=NULL){

       str=cur->name;

       if( strcmp(str,_name)==0 ){

           printf("找到所需的数据\n");    

           return cur;

       }

       cur=cur->next;

   }

   if(cur==NULL)

       printf("没有找到所需的数据\n");  

}

/*查找链表的函数,其中head指针是链表的表头指针,_name指针是要查找的人的姓名

返回值:返回的是上一个查找函数的直接前驱结点的指针*/

struct stu * SearchFront(struct stu *head,char* _name){

   struct stu *cur,*fro;

   char             *str;

   cur=head->next;

   fro=head;

   while(cur!=NULL){

       str=cur->name;

       if(strcmp(_name,str)==0){

           printf("找到所需的数据\n");    

           return fro;

       }

       cur=cur->next;

       fro=fro->next;

   }

   if(cur==NULL)

       printf("没有找到所需的数据\n");  

}

void Insert(struct stu *prev,char *_name){

   struct stu *ins;

   if((ins=(struct stu*)malloc(sizeof(struct stu)))==NULL){

       printf("Can't alloc memory\n");

       exit(1);            

   }

   strcpy(ins->name,_name);

   ins->next=prev->next;

   prev->next=ins;

}

void Delete(struct stu *fro,struct stu *del){

   struct stu *tmp;

   tmp=del;

   fro->next=del->next;

   free(tmp);

}

/*遍历链表,打印链表数据*/

void Print(struct stu *head){

   struct stu *cur;

   cur=head->next;

   while(cur!=NULL){

       printf("%s\n",cur->name);

       cur=cur->next;

   }

}

int main(){

   int number=3;

   char _name[32];

   struct stu *head,*cur,*fro;

   head=CreatList(number);

   if(head==NULL)

       return -1;


   Print(head);


   printf("请输入删除的姓名:");

   scanf("%s",_name);  

   cur=SearchCur(head,_name);

   if(cur==NULL)

       return -1;


   fro=SearchFront(head,_name);

   Delete(fro,cur);


   Print(head);


   printf("\n");

   return 0;  

}

输出结果:

请输入第1个数据的姓名

请输入姓名:kevin

请输入第2个数据的姓名

请输入姓名:tim

请输入第3个数据的姓名

请输入姓名:jobs

创建链表成功!

kevin

tim

jobs

请输入删除的姓名:tim

找到所需的数据

找到所需的数据

kevin

jobs


联系管理员
 
 
 
 
 工作时间
周一至周五 :9:30-17:30
马上建站
会员登录
登录
我的资料
留言
回到顶部