链表

2018-06-17 22:38:40来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 

 

  与顺序表相同,链表也是一种线性表,它的数据逻辑组织形式是一维的。而与顺序表不同的是,链表的物理存储结构是用一组地址任意的存储单元存储数据的。也就是说,它不像链表一样占据一段连续的内存空间,而是将存储单元分散在内存的任意地址上。在链表结构中,每一个数据元素记录都存放在链表的一个结点中(node),而每一个结点之间由指针将其连接一起,这样就形成一条如同“链”的结构。

  在C语言中,链表的每一个结点可以是一个结构体元素,当然也可以是其他的构造类型元素。在链表的每一个结点中,都必须有一个专门存放指针(地址)的域,用这个指针域来存放后继结点的地址,这样就达到连接后继结点的目的。一条链表通常有有一个表头,用来存放第一个结点的地址。此外,一条链表的最后一个结点的指针域要置空,表示该结点为链表的结尾,因为它没有后继结点。

 

                                        上图是链表的结构示意图

  一个链表结点可用C语言描述如下:

typedef struct node{
ElemType data;
struct node* next;
}LNode,*LinkList;

创建一个链表如下:

LinkList CreatLinkList(int n){
/*建立一个长度为n的链表*/
LinkList p,r,list=NULL;
ElemType e;
int i;
for(i=1;i<=n;i++){
Get(e);//输入获取数据
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=NULL;
if(!list)
   list=p;
else
  r->next=p;
 r=p;
}
return list;
}

上述的代码思路是:调用函数 CreatLinlList(n);的时候,当i=1的时候,list是为null,此时将p的值赋值给表头(list),同时将p的值给此时的r,第二次i=2的时候list不为null,而此时p的值是一个新的结点,这是就要用到r了,r是上一个p的值,将r->next=p,表示将新的p值接上上一个值,此时重新将r值更新为这次的p值,之后循环。

  向链表中插入结点(下面介绍的是在指针q指向的结点后面插入结点):

(1)先创建一个新的结点,并将指针p指向该结点

(2)将q指向的结点的next域的值(q->next)赋值给p->next;

(3)在将q->next=p;

 

 

 

上图就是插入的过程.

代码如下:

void insertList(LinkList *list,LinkList q,ElemType e){
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
if(!*list){
*list=p;//向空链表插入元素
p->next=NULL;
}
else{
p->next=q->next;
q->next=p;
}
}

删除链表元素代码如下:

void delLink(LinkList *list,LinkList q){
LinkList r;
if(q==*list){
*list=q->next;
free(q);
}
else{
for(r=*list;r->next!=q;r=r->next);//遍历链表找到q的前驱结点
if(r->next!=NULL){
r->next=q->next;
free(q);
}
}
}

 销毁一个链表代码如下:

void destroyLinkList(LinkList *list){
LinkList p,q;
p=*list;
while(p){
q=p->next;
free(p);
p=q;
}
*list=NULL;
}

 案例分析:

#include "stdio.h"
#include <stdlib.h>
typedef int ElemType;
typedef struct node{
ElemType data;
struct node* next;
}LNode,*LinkList;
LinkList CreatLinkList(int n){
/*建立一个长度为n的链表*/
LinkList p,r,list=NULL;
ElemType e;
int i;
for(i=1;i<=n;i++){
scanf("%d",&e);//输入获取数据
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=NULL;
if(!list)
   list=p;
else
  r->next=p;
 r=p;
}
return list;
}
void insertList(LinkList *list,LinkList q,ElemType e){
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
if(!*list){
*list=p;//向空链表插入元素
p->next=NULL;
}
else{
p->next=q->next;
q->next=p;
}
}
void delLink(LinkList *list,LinkList q){
LinkList r;
if(q==*list){
*list=q->next;
free(q);
}
else{
for(r=*list;r->next!=q;r=r->next);//遍历链表找到q的前驱结点
if(r->next!=NULL){
r->next=q->next;
free(q);
}
}
}
void destroyLinkList(LinkList *list){
LinkList p,q;
p=*list;
while(p){
q=p->next;
free(p);
p=q;
}
*list=NULL;
}
void main()
{
    int e,i;
    LinkList l,q;
    q=l=CreatLinkList(1);
    scanf("%d",&e);
    while(e){
    insertList(&l,q,e);
    q=q->next;
    scanf("%d",&e);
    }
    q=l;
    printf("The content of the linklist:\n");
    while(q)
    {
        printf("%d ",q->data);
        q=q->next;
    }
    q=l;
    printf("\nDelete the fifth element\n");
    for(i=0;i<4;i++)
    {
        if(q==NULL){
        printf("the length of the linklist is smaller than 5!\n");
        getchar();
        return;
        }
        q=q->next;
    }
    delLink(&l,q);
    q=l;
    while(q)
    {    
        printf("%d ",q->data);
        q=q->next;
    }
    destroyLinkList(&l);
    getchar();


}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1969 积木大赛

下一篇:浅谈 extern &quot;C&quot;