当前位置：首页 > 范文大全 > 实用文>链表的c语言实现①

链表的c语言实现①

2022-12-30 08:03:34 收藏本文下载本文

“千山万里”通过精心收集，向本站投稿了10篇链表的c语言实现①，以下是小编收集整理后的链表的c语言实现①，仅供参考，希望对大家有所帮助。

链表的c语言实现①

篇1：链表的c语言实现③

3、删除

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

以下便是应用删除算法的实例：

#include

#define N 10

typedef struct node

{

char name[20];

struct node *link;

}stud;

stud * creat(int n) /*建立新的链表的函数*/

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->link=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->link=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->link=NULL;

p=s;

}

return(h);

}

stud * search(stud *h,char *x) /*查找函数*/

{

stud *p;

char *y;

p=h->link;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

stud * search2(stud *h,char *x) /*另一个查找函数，返回的是上一个查找函数的直接前驱结点的指针，*/

/*h为表头指针，x为指向要查找的姓名的指针*/

/*其实此函数的算法与上面的查找算法是一样的，只是多了一个指针s，并且s总是指向指针p所指向的结点的直接前驱，*/

/*结果返回s即是要查找的结点的前一个结点*/

{

stud *p,*s;

char *y;

p=h->link;

s=h;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0)

return(s);

else

{

p=p->link;

s=s->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

void del(stud *x,stud *y) /*删除函数，其中y为要删除的结点的指针，x为要删除的结点的前一个结点的指针*/

{

stud *s;

s=y;

x->link=y->link;

free(s);

}

main

{

int number;

char fullname[20];

stud *head,*searchpoint,*forepoint;

number=N;

head=creat(number);

printf(“请输入你要删除的人的姓名:”);

scanf(“%s”,fullname);

searchpoint=search(head,fullname);

forepoint=search2(head,fullname);

del(forepoint,searchpoint);

一、循环链表

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链，

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

二、双向链表

双向链表其实是单链表的改进。

当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在c语言中双向链表结点类型可以定义为：

typedef struct node

{

int data; /*数据域*/

struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/

}JD;

当然，也可以把一个双向链表构建成一个双向循环链表。

双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。

篇2：链表的c语言实现⑤

3、删除

删除某个结点，其实就是插入某个结点的逆操作，还是对于双向循环链表，要在连续的三个结点s,p,q中删除p结点，只需把s的右链域指针指向q，q的左链域指针指向s，并收回p结点就完成了。

下面就是一个应用双向循环链表删除算法的例子：

#include

#define N 10

typedef struct node

{

char name[20];

struct node *llink,*rlink;

}stud;

stud * creat(int n)

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->llink=NULL;

h->rlink=NULL;

p=h;

for(i=0;i〈n;i++)

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p-〉rlink=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->llink=p;

s->rlink=NULL;

p=s;

}

h->llink=s;

p->rlink=h;

return(h);

}

stud * search(stud *h,char *x)

{

stud *p;

char *y;

p=h->rlink;

while(p!=h)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->rlink;

}

printf(“没有查找到该数据!”);

}

void print(stud *h)

{

int n;

stud *p;

p=h->rlink;

printf(“数据信息为：\n”);

while(p!=h)

{

printf(“%s ”,&*(p->name));

p=p->rlink;

}

printf(“\n”);

}

void del(stud *p)

{

(p->rlink)->llink=p->llink;

(p->llink)->rlink=p->rlink;

free (p);

}

main()

{

int number;

char studname[20];

stud *head,*searchpoint;

number=N;

clrscr();

head=creat(number);

print(head);

printf(“请输入你要查找的人的姓名:”);

scanf(“%s”,studname);

searchpoint=search(head,studname);

printf(“你所要查找的人的姓名是:%s\n”,*&searchpoint->name);

del(searchpoint);

print(head);

}

在这里列举了一个应用单链表基本算法的综合程序，双向链表和循环链表的综合程序大家可以自己去试一试。

#include

#define N 10 typedef struct node

{

char name[20];

struct node *link;

}stud;

stud * creat(int n)

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->link=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->link=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->link=NULL;

p=s;

}

return(h);

}

stud * search(stud *h,char *x)

{

stud *p;

char *y;

p=h->link;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

stud * search2(stud *h,char *x)

{

stud *p,*s;

char *y;

p=h->link;

s=h;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0)

return(s);

else

{

p=p->link;

s=s->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

void insert(stud *p)

{

char stuname[20];

stud *s;

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

printf(“\n请输入你要插入的人的姓名:”);

scanf(“%s”,stuname);

strcpy(s->name,stuname);

s->link=p->link;

p->link=s;

}

void del(stud *x,stud *y)

{

stud *s;

s=y;

x->link=y->link;

free(s);

}

void print(stud *h)

{

stud *p;

p=h->link;

printf(“数据信息为：\n”);

while(p!=NULL)

{

printf(“%s ”,&*(p->name));

p=p->link;

}

void quit()

{

exit(0);

}

void menu(void)

{

clrscr();

printf(“\t\t\t单链表C语言实现实例\n”);

printf(“\t\t|————————————————|\n”);

printf(“\t\t| |\n”);

printf(“\t\t| [1] 建立新表 |\n”);

printf(“\t\t| [2] 查找数据 |\n”);

篇3：链表的c语言实现④

双向链表的基本运算：

1、查找

假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们同样从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾，

下例就是应用双向循环链表查找算法的一个程序。

#include

#define N 10

typedef struct node

{

char name[20];

struct node *llink,*rlink;

}stud;

stud * creat(int n)

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->llink=NULL;

h->rlink=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->rlink=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->llink=p;

s->rlink=NULL;

p=s;

}

h->llink=s;

p->rlink=h;

return(h);

}

stud * search(stud *h,char *x)

{

stud *p;

char *y;

p=h->rlink;

while(p!=h)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->rlink;

}

printf(“没有查找到该数据!”);

}

void print(stud *h)

{

int n;

stud *p;

p=h->rlink;

printf(“数据信息为：\n”);

while(p!=h)

{

printf(“%s ”,&*(p->name));

p=p->rlink;

}

printf(“\n”);

}

main

{

int number;

char studname[20];

stud *head,*searchpoint;

number=N;

clrscr();

head=creat(number);

print(head);

printf(“请输入你要查找的人的姓名:”);

scanf(“%s”,studname);

searchpoint=search(head,studname);

printf(“你所要查找的人的姓名是:%s”,*&searchpoint->name);

}

2、插入

对于双向循环链表，我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。

假若s,p,q是连续三个结点的指针，若我们要在p前插入一个新结点r，则只需把s的右链域指针指向r，r的左链域指针指向s，r的右链域指针指向p，p的左链域指针指向r即可。

在p,q之间插入原理也一样。

下面就是一个应用双向循环链表插入算法的例子：

#include

#define N 10

typedef struct node

{

char name[20];

struct node *llink,*rlink;

}stud;

stud * creat(int n)

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->llink=NULL;

h->rlink=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->rlink=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->llink=p;

s->rlink=NULL;

p=s;

}

h->llink=s;

p->rlink=h;

return(h);

}

stud * search(stud *h,char *x)

{

stud *p;

char *y;

p=h->rlink;

while(p!=h)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->rlink;

}

printf(“没有查找到该数据!”);

}

void print(stud *h)

{

int n;

stud *p;

p=h->rlink;

printf(“数据信息为：\n”);

while(p!=h)

{

printf(“%s ”,&*(p->name));

p=p->rlink;

}

printf(“\n”);

}

void insert(stud *p)

{

char stuname[20];

stud *s;

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

printf(“请输入你要插入的人的姓名:”);

scanf(“%s”,stuname);

strcpy(s->name,stuname);

s->rlink=p->rlink;

p->rlink=s;

s->llink=p;

(s->rlink)->llink=s;

}

main()

{

int number;

char studname[20];

stud *head,*searchpoint;

number=N;

clrscr();

head=creat(number);

print(head);

printf(“请输入你要查找的人的姓名:”);

scanf(“%s”,studname);

searchpoint=search(head,studname);

printf(“你所要查找的人的姓名是:%s\n”,*&searchpoint->name);

insert(searchpoint);

print(head);

}

篇4：链表的c语言实现①

准备：动态内存分配

一、为什么用动态内存分配

但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组，比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组：

float score[30];

但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？

在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。

所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点：

1、不需要预先分配存储空间；

2、分配的空间可以根据程序的需要扩大或缩小。

二、如何实现动态内存分配及其管理

要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数

1、malloc函数

malloc函数的原型为：

void *malloc (unsigned int size)

其作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。

下例是一个动态分配的程序：

#include

main()

{

int count,*array; /*count是一个计数器，array是一个整型指针，也可以理解为指向一个整型数组的首地址*/

if((array(int *) malloc(10*sizeof(int)))==NULL)

{

printf(“不能成功分配存储空间。”);

exit(1);

}

for (count=0;count〈10;count++) /*给数组赋值*/

array[count]=count;

for(count=0;count〈10;count++) /*打印数组元素*/

printf(“%2d”,array[count]);

}

上例中动态分配了10个整型存储区域，然后进行赋值并打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)语句可以分为以下几步：

1）分配10个整型的连续存储空间，并返回一个指向其起始地址的整型指针

2）把此整型指针地址赋给array

3）检测返回值是否为NULL

2、free函数

由于内存区域总是有限的，不能不限制地分配下去，而且一个程序要尽量节省资源，所以当所分配的内存区域不用时，就要释放它，以便其它的变量或者程序使用，

这时我们就要用到free函数。

其函数原型是：

void free(void *p)

作用是释放指针p所指向的内存区。

其参数p必须是先前调用malloc函数或calloc函数（另一个动态分配存储区域的函数）时返回的指针。给free函数传递其它的值很可能造成死机或其它灾难性的后果。

注意：这里重要的是指针的值，而不是用来申请动态内存的指针本身。例：

int *p1,*p2;

p1=malloc(10*sizeof(int));

p2=p1;

……

free(p2) /*或者free(p2)*/

malloc返回值赋给p1，又把p1的值赋给p2，所以此时p1，p2都可作为free函数的参数。

malloc函数是对存储区域进行分配的。

free函数是释放已经不用的内存区域的。

所以由这两个函数就可以实现对内存区域进行动态分配并进行简单的管理了。

一、单链表的建立

有了动态内存分配的基础，要实现链表就不难了。

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

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

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

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

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

例：

typedef struct node

{

char name[20];

struct node *link;

}stud;

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

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

下面就来看一个建立带表头（若未说明，以下所指链表均带表头）的单链表的完整程序。

#include

#include /*包含动态内存分配函数的头文件*/

#define N 10 /*N为人数*/

typedef struct node

{

char name[20];

struct node *link;

}stud; stud * creat(int n) /*建立单链表的函数，形参n为人数*/

{

stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/

int i; /*计数器*/

if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空间并检测*/

{

printf(“不能分配内存空间!”);

exit(0);

}

h->name[0]='\0'; /*把表头结点的数据域置空*/

h->link=NULL; /*把表头结点的链域置空*/

p=h; /*p指向表头结点*/

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存储空间并检测*/

篇5：链表的c语言实现②

二、单链表的基本运算

建立了一个单链表之后，如果要进行一些如插入、删除等操作该怎么办？所以还须掌握一些单链表的基本算法，来实现这些操作，单链表的基本运算包括：查找、插入和删除。下面我们就一一介绍这三种基本运算的算法，并结合我们建立单链表的例子写出相应的程序。

1、查找

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

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

以下是应用查找算法的一个例子：

#include

#include /*包含一些字符串处理函数的头文件*/

#define N 10

typedef struct node

{

char name[20];

struct node *link;

}stud;

stud * creat(int n) /*建立链表的函数*/

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->link=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->link=s;

printf(“请输入第%d个人的姓名”,i+1);

scanf(“%s”,s->name);

s->link=NULL;

p=s;

}

return(h);

}

stud * search(stud *h,char *x) /*查找链表的函数，其中h指针是链表的表头指针，x指针是要查找的人的姓名*/

{

stud *p; /*当前指针，指向要与所查找的姓名比较的结点*/

char *y; /*保存结点数据域内姓名的指针*/

p=h->link;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0) /*把数据域里的姓名与所要查找的姓名比较，若相同则返回0，即条件成立*/

return(p); /*返回与所要查找结点的地址*/

else p=p->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

main

{

int number;

char fullname[20];

stud *head,*searchpoint; /*head是表头指针，searchpoint是保存符合条件的结点地址的指针*/

number=N;

head=creat(number);

printf(“请输入你要查找的人的姓名:”);

scanf(“%s”,fullname);

searchpoint=search(head,fullname); /*调用查找函数，并把结果赋给searchpoint指针*/

}

2、插入（后插）

假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可，

(p->link=s;s->link=q)，这样就完成了插入操作。

下例是应用插入算法的一个例子：

#include

#define N 10

typedef struct node

{

char name[20];

struct node *link;

}stud;

stud * creat(int n) /*建立单链表的函数*/

{

stud *p,*h,*s;

int i;

if((h=(stud *)malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

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

h->link=NULL;

p=h;

for(i=0;i

{

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

p->link=s;

printf(“请输入第%d个人的姓名:”,i+1);

scanf(“%s”,s->name);

s->link=NULL;

p=s;

}

return(h);

}

stud * search(stud *h,char *x) /*查找函数*/

{

stud *p;

char *y;

p=h->link;

while(p!=NULL)

{

y=p->name;

if(strcmp(y,x)==0)

return(p);

else p=p->link;

}

if(p==NULL)

printf(“没有查找到该数据!”);

}

void insert(stud *p) /*插入函数，在指针p后插入*/

{

char stuname[20];

stud *s; /*指针s是保存新结点地址的*/

if((s= (stud *) malloc(sizeof(stud)))==NULL)

{

printf(“不能分配内存空间!”);

exit(0);

}

printf(“请输入你要插入的人的姓名:”);

scanf(“%s”,stuname);

strcpy(s->name,stuname); /*把指针stuname所指向的数组元素拷贝给新结点的数据域*/

s->link=p->link; /*把新结点的链域指向原来p结点的后继结点*/

p->link=s; /*p结点的链域指向新结点*/

}

main()

{

int number;

char fullname[20]; /*保存输入的要查找的人的姓名*/

stud *head,*searchpoint;

number=N;

head=creat(number); /*建立新链表并返回表头指针*/

printf(“请输入你要查找的人的姓名:”);

scanf(“%s”,fullname);

searchpoint=search(head,fullname); /*查找并返回查找到的结点指针*/

insert(searchpoint); /*调用插入函数*/

}

篇6：C实现通用数据结构单链表

单链表的接口定义：

1、list_init

void list_init(List *list, void (*destroy)(void *data));

返回值 void

描述初始化由参数list指定的链表，该函数必须在链表做其他操作之前调用，当调用list_destroy时，destroy参数提供了一种释放动态分配数据的方法，如果链表采用malloc动态分配的数据，destroy应该设置为free来释放这些数据

复杂度 O(1)

2、list_destroy

void list_destroy(List *list);

返回值 void

描述销毁由参数list指定的链表，调用该函数以后任何函数都不能再执行，除非重新执行list_init函数。list_destroy将list中的所有元素都移除，每移除一个元素都会调用此函数

复杂度 O(n) n为链表元素的个数

3、list_ins_next

int list_ins_next(List *list, ListElmt *element, const void *data);

返回值如果插入元素成功返回0，否则返回-1

描述在指定的list的element元素后面插入一个元素，如果element为NULL，则在链表的头部插入新的元素，该元素包含一个指向data的指针

复杂度 O(1)

4、list_rem_next

int list_rem_next(List *list, ListElmt *element, void **data);

返回值如果移除元素成功返回0，否则返回-1

描述移除在指定的list的element后面的那个元素，如果element为NULL，则移除链表的头元素，调用返回后，data指向已经移除元素的数据

复杂度 O(1)

5、list_size

int list_size(const List *list);

返回值如果list中元素的个数

描述这是一个宏，用来计算指定list中元素的个数

复杂度 O(1)

6、list_head

ListElmt *list_head(const List *list);

返回值指向链表头元素的指针

描述这是一个宏，返回由参数list指定的链表头元素的指针

复杂度 O(1)

7、list_tail

ListElmt *list_tail(const List *list) ((list)->tail);

返回值指向链表尾元素的指针

描述这是一个宏，返回由参数list指定的链表尾元素的指针

复杂度 O(1)

8、list_is_head

int list_is_head(const ListElmt *element);

返回值如果element元素是链表头元素返回0，否则返回-1

描述这是一个宏，用来判断element元素是否是list的头元素

复杂度 O(1)

9、list_is_tail

int list_is_tail(const ListElmt *element);

返回值如果element元素是链表尾元素返回0，否则返回-1

描述这是一个宏，用来判断element元素是否是list的尾元素

复杂度 O(1)

10、list_data

void *list_data(const ListElmt *element);

返回值结点中保存的数据

描述这是一个宏，返回由element元素中保存的数据

复杂度 O(1)

11、list_next

ListElmt *list_next(const ListElmt *element) ;

返回值返回element所指定结点的下一个结点

描述这是一个宏，返回链表中element所指定结点的下一个结点

复杂度 O(1)

单链表的实现和分析

抽象数据类型的头文件（list.h）：

#ifndef LIST_H

#define LIST_H

#include

//为单链表的结点定义一个结构体.

typedef struct ListElmt_ {

void *data; //数据域

struct ListElmt_ *next; //指针域

} ListElmt;

//为单链表定义一个结构体.

typedef struct List_ {

int size; //容量

int (*match)(const void *key1, const void *key2); //匹配函数

void (*destroy)(void *data); //撤销操作

ListElmt *head; //头指针

ListElmt *tail; //尾指针

} List;

//公共接口

void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif

初始化单链表：

void list_init(List *list, void (*destroy)(void *data)) { //初始化list

list->size = 0;

list->destroy = destroy; //设置为定义的析构函数

list->head = NULL;

list->tail = NULL;

return;

}

回收单链表：

void list_destroy(List *list) {

//移除每一个元素

while (list_size(list) >0) {

if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) { //不断地移除链表的头结点

list->destroy(data); //调用一个用户定义的函数来释放动态分配的数据.

}

//现在没有操作了,释放结构体作为预防措施

memset(list, 0, sizeof(List));

return;

}

插入新节点作为指定结点的直接后继结点:

int list_ins_next(List *list, ListElmt *element, const void *data) {

ListElmt *new_element; //为结点动态分配存储空间

if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) //假如分配失败

return -1;

// 将元素插入链表

new_element->data = (void *)data;

if (element == NULL) {

//插入到链表的头部

if (list_size(list) == 0)

list->tail = new_element;

new_element->next = list->head;

list->head = new_element;

} else {

//插入到除了链表头部以外指定的其他地方

if (element->next == NULL)

list->tail = new_element;

new_element->next = element->next;

element->next = new_element;

}

list->size++; //表长增加

return 0;

}

删除指定结点的直接后继结点:

int list_rem_next(List *list, ListElmt *element, void **data) {

ListElmt *old_element;

//不允许从一个空的list中移除元素.

if (list_size(list) == 0)

return -1;

// 从list中移除元素.

if (element == NULL) {

// 移除表头的结点.

*data = list->head->data;

old_element = list->head;

list->head = list->head->next;

if (list_size(list) == 1) //如果list只有一个元素，则直接删除尾结点

list->tail = NULL;

} else {

// 移除非头结点.

if (element->next == NULL)

return -1;

*data = element->next->data;

old_element = element->next;

element->next = element->next->next;

if (element->next == NULL) //移除指定结点后，后继为NULL，则用尾结点指向

list->tail = element;

}

//释放分配的抽象数据类型.

free(old_element);

//调整list的长度. *

list->size--;

return 0;

}

注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next 这些宏实现了链表中的一些简单操作，它们提供了快速访问和检测结构体成员的能力，

这些操作的时间复杂度都是O(1)

完整的测试代码如下：

// Completed on .10.22 21:00

// Language: C99

// 博客地址：www.cnblogs.com/archimedes/

#include

#include “list.h”

static void print_list(const List *list) {

ListElmt *element;

int *data, i;

fprintf(stdout, “List size is %d\n”, list_size(list));

i = 0;

element = list_head(list);

while (1) {

data = list_data(element);

fprintf(stdout, “list[%03d]=%03d\n”, i, *data);

i++;

if (list_is_tail(element))

break;

else

element = list_next(element);

}

return;

}

int main(int argc, char **argv) {

List list;

ListElmt *element;

int *data, i;

//初始化list

list_init(&list, free);

element = list_head(&list);

for (i = 10; i >0; i--) {

if ((data = (int *)malloc(sizeof(int))) == NULL)

return 1;

*data = i;

if (list_ins_next(&list, NULL, data) != 0) //逐个插入元素

return 1;

}

print_list(&list); //打印初始list

element = list_head(&list); //指向头结点

for (i = 0; i < 7; i++)

element = list_next(element);

data = list_data(element);

fprintf(stdout, “Removing an element after the one containing %03d\n”, *data);

if (list_rem_next(&list, element, (void **)&data) != 0) //删除指定结点

return 1;

print_list(&list);

fprintf(stdout, “Inserting 011 at the tail of the list\n”);

*data = 11;

if (list_ins_next(&list, list_tail(&list), data) != 0) //插入指定结点

return 1;

print_list(&list);

fprintf(stdout, “Removing an element after the first element\n”);

element = list_head(&list);

if (list_rem_next(&list, element, (void **)&data) != 0)

return 1;

print_list(&list);

fprintf(stdout, “Inserting 012 at the head of the list\n”);

*data = 12;

if (list_ins_next(&list, NULL, data) != 0)

return 1;

print_list(&list);

fprintf(stdout, “Iterating and removing the fourth element\n”);

element = list_head(&list);

element = list_next(element);

if (list_rem_next(&list, element, (void **)&data) != 0)

return 1;

print_list(&list);

fprintf(stdout, “Inserting 013 after the first element\n”);

*data = 13;

if (list_ins_next(&list, list_head(&list), data) != 0)

return 1;

print_list(&list);

i = list_is_head(&list, list_head(&list));

fprintf(stdout, “Testing list_is_head...Value=%d (1=OK)\n”, i);

i = list_is_head(&list, list_tail(&list));

fprintf(stdout, “Testing list_is_head...Value=%d (0=OK)\n”, i);

i = list_is_tail(list_tail(&list));

fprintf(stdout, “Testing list_is_tail...Value=%d (1=OK)\n”, i);

i = list_is_tail(list_head(&list));

fprintf(stdout, “Testing list_is_tail...Value=%d (0=OK)\n”, i);

fprintf(stdout, “Destroying the list\n”);

list_destroy(&list);

return 0;

}

篇7：Go语言单链表实现方法

作者：OSC首席键客字体：[增加减小] 类型：

1. singlechain.go代码如下：

代码如下:

//////////

//单链表 -- 线性表

package singlechain

//定义节点

type Node struct {

Data int

Next *Node

}

* 返回第一个节点

* h 头结点

func GetFirst(h *Node) *Node {

if h.Next == nil {

return nil

}

return h.Next

}

* 返回最后一个节点

* h 头结点

func GetLast(h *Node) *Node {

if h.Next == nil {

return nil

}

i := h

for i.Next != nil {

i = i.Next

if i.Next == nil {

return i

}

return nil

}

//取长度

func GetLength(h *Node) int {

var i int = 0

n := h

for n.Next != nil {

i++

n = n.Next

}

return i

}

//插入一个节点

//h: 头结点

//d:要插入的节点

//p:要插入的位置

func Insert(h, d *Node, p int) bool {

if h.Next == nil {

h.Next = d

return true

}

i := 0

n := h

for n.Next != nil {

i++

if i == p {

if n.Next.Next == nil {

n.Next = d

return true

} else {

d.Next = n.Next

n.Next = d.Next

return true

}

n = n.Next

if n.Next == nil {

n.Next = d

return true

}

return false

}

//取出指定节点

func GetLoc(h *Node, p int) *Node {

if p < 0 || p >GetLength(h) {

return nil

}

var i int = 0

n := h

for n.Next != nil {

i++

n = n.Next

if i == p {

return n

}

return nil

}

2. main.go代码如下：

代码如下:

package main

import “fmt”

import “list/singlechain”

func main {

//初始化一个头结点

var h singlechain.Node

//往链表插入10个元素

for i := 1; i <= 10; i++ {

var d singlechain.Node

d.Data = i

singlechain.Insert(&h, &d, i)

fmt.Println(singlechain.GetLoc(&h, i))

}

fmt.Println(singlechain.GetLength(&h))

fmt.Println(singlechain.GetFirst(&h))

fmt.Println(singlechain.GetLast(&h))

fmt.Println(singlechain.GetLoc(&h, 6))

}

希望本文所述对大家的Go语言程序设计有所帮助，

篇8：C语言：链表的建立、插入和删除

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性，但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，

难于统一。我们只能够根据可能的最大需求来定义数组，经常会造成一定存储空间的浪费。

我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。

7.4.1 单链表

图7 - 3是单链表的结构。

单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。

图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。

看一下链表节点的数据结构定义：

struct node

{

int num;

struct node *p;

} ;

在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。

在链表节点的数据结构中，非常非凡的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。

• 单链表的创建过程有以下几步：

1 ) 定义链表的数据结构。

2 ) 创建一个空表。

3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。

4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新

节点接到表尾。

5 ) 判定一下是否有后续节点要接入链表，若有转到3 )，否则结束。

• 单链表的输出过程有以下几步

1) 找到表头。

2) 若是非空表，输出节点的值成员，是空表则退出。

3 ) 跟踪链表的增长，即找到下一个节点的地址。

4) 转到2 )。

[例7-5] 创建一个存放正整数（输入- 9 9 9做结束标志）的单链表，并打印输出。

#include /包*含ma l l o c ( ) 的头文件*/

#include

struct node /*链表节点的结构* /

{

int num;

struct node *next;

} ;

m a i n ( )

{

struct node *creat(); / *函数声明* /

void print();

struct node *head; / * 定义头指针* /

head=NULL;/*建一个空表*/

head=creat(head);/*创建单链表*/

print(head);/*打印单链表*/

}

/******************************************/

struct node*creat(structnode*head)函/数*返回的是与节点相同类型的指针*/

{

struct node*p1,*p2;

p1=p2=(structnode*)malloc(sizeof(structnode));申请/*新节点*/

scanf(“%d”,&p1->num);/*输入节点的值*/

p1->next=NULL;/*将新节点的指针置为空*/

while(p1->num>0)/*输入节点的数值大于0*/

{

if(head==NULL)head=p1;/*空表，接入表头*/

elsep2->next=p1;/*非空表，接到表尾*/

p2=p1;

p1=(structnode*)malloc(sizeof(structnode));申/请*下一个新节点*/

scanf(“%d”,&p1->num);/*输入节点的值*/

}

return head;/*返回链表的头指针*/

}

/*******************************************/

void print(struct node*head)输/*出以head为头的链表各节点的值*/

{

struct node *temp;

temp=head;/*取得链表的头指针*/

while(temp!=NULL)/*只要是非空表*/

{

printf(“%6d”,temp->num);/*输出链表节点的值*/

temp=temp->next;/*跟踪链表增长*/

}

在链表的创建过程中，链表的头指针是非常重要的参数，

因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。

- 链表的建立、插入和删除

7.4.2 单链表的插入与删除

在链表这种非凡的数据结构中，链表的长短需要根据具体情况来设定，当需要保存数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的数据可以依此接到表尾或连结到表头，也可以视情况插入表中；对不再需要的数据，将其从表中删除并释放其所占空间，但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。

1. 链表的删除

在链表中删除一个节点，用图7 - 4描述如下：

[例7-6] 创建一个学生学号及姓名的单链表，即节点包括学生学号、姓名及指向下一个节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将其从链表中删除。

首先定义链表的结构：

struct

从图7 - 4中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删除链表的中

间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表中从头到尾依此查找各节

点，并与各节点的学生姓名比较，若相同，则查找成功，否则，找不到节点。由于删除的节

点可能在链表的头，会对链表的头指针造成丢失，所以定义删除节点的函数的返回值定义为

返回结构体类型的指针。

篇9：栈的实现(C语言实现)

//头文件 #include/*====================栈数据结构利用数组实现====================*/#define MAX 100#define ok 1#define error 0typedef struct Stack{ int data[MAX]; int top;//栈顶 int bottom; //栈底}Stack,*STACK;//初始化栈int InitStack(STACK stack);//销毁int DestroyStack(STACK stack);//清空int ClearStack(STACK stack);//栈空int StackEmpty(STACK stack);//获取栈顶元素int GetTop(STACK stack,int* elem);//压栈int Push(STACK stack,int* elem);//出栈int Pop(STACK stack,int* elem);//返回栈中元素长度int StackLength(STACK stack,int* len);//打印栈中元素int PrintStack(STACK stack);//栈满int StackFull(STACK stack);

//main函数中实现#include “stack.h”int main{ int num=10, num1, i=0,j=0; Stack stack; int initFlag=InitStack(&stack); if(!initFlag) return 0; for(num1=0;num1<10;num1++) Push(&stack,&num1);/* int pushFlag=Push(&stack,&num); if(!pushFlag) return 0;*/// ClearStack(&stack); for(;i<10;i++) { int flag=Pop(&stack,&num1); if(flag) printf(“%d ”,num1); else printf(“Pop error”); } int lenFlag=StackLength(&stack,&num1); if(lenFlag) printf(“len=%d ”,num1); else printf(“StackLength error”);/* int getFlag=GetTop(&stack,&num1); if(getFlag) printf(“%d ”,num1);*/ PrintStack(&stack); return 0;}//初始化栈int InitStack(STACK stack){ if(stack==NULL) return error; stack->bottom=stack->top=0; return ok;}//压栈int Push(STACK stack,int* elem){ int flag=StackFull(stack); if(!flag) return error; stack->data[stack->top] =*elem; ++stack->top; return ok;}//打印栈中所有元素int PrintStack(STACK stack){ int i=0; int flag=StackEmpty(stack); if(!flag) return error; for(i=0;itop;i++) { printf(“%d ”,stack->data[i]); } printf(“\n”); return ok;}//栈空int StackEmpty(STACK stack){ if(stack==NULL || stack->top==stack->bottom) return error; else return ok;}//出栈int Pop(STACK stack,int* elem){ int flag=StackEmpty(stack); if(!flag) return error; *elem=stack->data[stack->top-1]; --stack->top; return ok;}//栈满int StackFull(STACK stack){ if(stack==NULL || stack->top>MAX) return error; else return ok;}//销毁int DestroyStack(STACK stack){ if(stack==NULL) return ok; else { stack->top=stack->bottom; stack=NULL; return ok; }}//清空int ClearStack(STACK stack){ int flag=StackEmpty(stack); if(!flag) return error; else { stack->top=stack->bottom; return ok; }}//获取栈顶元素int GetTop(STACK stack,int* elem){ int flag=StackEmpty(stack); if(!flag) return error; *elem=stack->data[stack->top-1]; return ok;}//返回栈中元素长度int StackLength(STACK stack,int* len){ if(stack==NULL) return error; if(stack->top==stack->bottom) { *len=0; return ok; } else { *len=stack->top; return ok; }}

篇10：C语言编写实现玫瑰花

#include

/*玫瑰花*/

#define FNX(x) (int)(xo+(x)*1.0)

#define FNY(y) (int)(getmaxy()-(yo+(y)*1.0))

#define FNX2(phi) cos(phi)*ac-sin(phi)*bs

#define FNY2(phi) cos(phi)*as+sin(phi)*bc

/*画旋转的椭圆*/

void elli(int xo,int yo,int a,int b,double theta)

{

int i;

double da,c,s,ac,as,bc,bs,xf,yf,phi,x,y;

theta=theta*0.01745;

da=3*0.1745;

c=cos(theta);s=sin(theta);

ac=a*c;as=a*s;bc=b*c;bs=b*s;

x=FNX2(0);y=FNY2(0);

moveto(FNX(x),FNY(y));

for(i=1;i<=360;i++)

{

phi=i*da;xf=x*cos(phi)*0.1;yf=b*sin(phi)*0.1;

x=FNX2(phi);y=FNY2(phi);

lineto(FNX(x),FNY(y));

}

/*花*/

void hua(int x,int y)

{

/*画粉红色玫瑰*/

setcolor(12);

arc(x+65,y-60,150,350,8);

arc(x+66,y-54,300,470,8);

arc(x+65,y-56,30,230,10);

arc(x+64,y-57,300,490,17);

ellipse(x+73,y-30,250,450,27,40);

ellipse(x+59,y-30,100,290,27,40);

ellipse(x+65,y-40,140,270,20,30);

setfillstyle(SOLID_FILL,5);

floodfill(x+65,y-20,12);

/*画红色玫瑰*/

arc(x,y,150,350,12);

arc(x+1,y+8,280,470,12);

arc(x,y+2,30,230,16);

arc(x,y+3,80,240,28);

arc(x+2,y+8,180,330,22);

arc(x-2,y+2,310,460,25);

ellipse(x-12,y+30,120,300,30,40);

ellipse(x+10,y+28,250,423,30,42);

ellipse(x-4,y+10,290,393,30,40);

setfillstyle(SOLID_FILL,4);

floodfill(x+5,y+31,12);

/*画紫色花骨朵*/

ellipse(x+120,y+5,0,360,15,25);

setfillstyle(SOLID_FILL,1);

floodfill(x+120,y,12);

/*画黄色花骨朵*/

ellipse(x-70,y+10,0,360,14,20);

setfillstyle(SOLID_FILL,14);

floodfill(x-70,y+10,12);

setcolor(10);

/*画红花花萼*/

ellipse(x-15,y+32,190,310,30,35);

ellipse(x+16,y+32,235,355,26,35);

ellipse(x,y+35,190,350,43,50);

arc(x,y+82,190,350,6);

setfillstyle(SOLID_FILL,2);

floodfill(x,y+75,10);

/*画粉花花萼*/

ellipse(x+50,y-48,190,320,22,50);

ellipse(x+80,y-48,220,350,22,50);

ellipse(x+65,y-28,180,360,36,50);

floodfill(x+65,y+18,10);

/*画主枝*/

for(i=0;i<3;i++ )

{

ellipse(x-98,y+100+i,255,371,100,80);

ellipse(x-20,y+30+i,260,358,140,140);

ellipse(x+224,y+20+i,180,218,160,140);

}

/*画侧枝*/

ellipse(x+70,y+34,180,233,140,140);

ellipse(x,y+40,205,255,100,120);

ellipse(x+135,y-30,209,249,72,120);

ellipse(x,y+20,263,301,100,120);

ellipse(x+85,y-10,278,305,100,120);

ellipse(x+100,y-62,282,308,90,120);

【链表的c语言实现①】相关文章：

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档

文档为doc格式

实用文图文推荐

链表的c语言实现①相关文章