（转）结构体链表

链表

1。是由结构体和指针构成的。

2。包括两个部分一个是数据域和指针域。

3。链表中的结点分为两类：头结点和一般结点。头结点是没有数据域的。

4。基本操作有：初始化链表，增加结点和删除结点，求链表的长度等等。

struct Linknode{

    int data;

    struct Linknode *next;

};

这个地方有个知识点：这个是链表的数据结构是有结构体和指针构成。结构体名为Linknode.但这里面没有定义结构体变量，只有我们定义了结构体变量才能使用结构体。

结构体变量怎么定义呢？

有两种方式：

1。struct Linknode Linklist;

2.typedef struct linknode Linklist.

一般我们都希望采用第2种，这样的好处是: 当我们再定义结构体变量时，可以用：Linklist p;而如果我们采用第一种还必须采用 struct Linknode p;对比一下就可以知道第2种要简单很多。那么下面我们都采用第2种方式来定义结构体变量。

上面我们已经定义了一个链表：

1。初始化链表。

#include<stdio.h>

#include<stdlib.h>

int InitLinkList(Linklist **Lnode)

{

    *Lnode=(Linklist)malloc(sizeof(Linklist));//*Lnode等于L，对与*Lnode的分配空间相当与对主函数中的L分配空间。

    if(!*Lnode)

        return 0;

   （*Lnode）->next=NULL;

}

在初始化链表的时候，我们用到了2级指针为什么呢？因为我们希望在InitLinkList函数生成的头结点，主函数中也能指向这个头结点。如果我们用一级指针的话，用malloc分配空间的时候，它将会返回分配空间的首地址给指针变量Lnode，而不能使是的空间被主函数中指针变量L得到这个地址。所以我们要用2级指针。

void main()

{

    Linklist *L;

    InitLikList(&L);

}

2。增加链表结点

增加链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。

InsertLinkList(Linklist *Lnode)

{

    Linklist *p,*q;

    int d;

 {

    scanf("%d",&d);

     if(d==-9999)

         break;

    p=Lnode->next;//p指向头结点

//通过while循环和指针变量p定位要插入的结点q的位置。

while（p）

p=p->next;

//生成一个要插入的结点

q=(Linklist)malloc(sizeof(Linklist));//申请要插入的结点空间

q->data=d;//填充要插入结点的数据域

q->next=p->next;//首先填充要插入结点q的指针域进行填充。

p->next=q;//然后把定位好的p指针域进行修改指向q.

 

}while(9);//循环退出的条件是输入的数据-9999

 

}

void main()

{

Linklist *L;

InitLinkList(&L);//生成一个头结点

InsertLinkList(L);//插入结点

}

3。求链表的长度：

int LengthLinkList(Linklist *Lnode)

{

int i=0;

Linklist *p;

p=Lnode->next;//p指向链表的第一个结点。

while(p)

{

i++;

p=p->next;

}

return i;

}

void main()

{

Linklist *L;

InitLinkList(&L);//生成一个头结点

InsertLinkList(L);//插入一个结点

LengthLinkList(L)//求链表的长度。

}

4.删除结点

删除链表结点其实很简单，一般用到三个结构体指针变量和一个循环结构。

DestroyLinkList(Linklist *Lnode)

{

Linklist *p,*q;

p=Lnode;//p指向链表的头结点

while(p)

{

q=p->next;//q指向当前结点的下一个结点。

free(p);//释放当前结点

p=q;//p指向下一个结点

}

}

void main()

{

Linklist *L;

InitLinkList(&L);//生成一个头结点

InsertLinkList(L);//插入结点

LengthLinkList(L)//求链表的长度。

DestroyLinkList(L);//删除链表结点

}

单链表这块内容只要你掌握好了基本的知识点，一切问题都OK了，这基本的知识点有：结构体变量，结构体指针变量，头结点和一般结点，数据域和指针域，while循环。

本文转自：http://blog.csdn.net/zzymusic/article/details/5294960