2018/1/31 20:02:42当前位置推荐好文程序员浏览文章

1.链表的概念

链表是由若干个结点组成,是一种线性表。结点一般由数据域与指针域,数据域存放数据,指针域存放指向下一结点的地址,从而形成一个链式结构。链表有带头节点head的,也有没有带头节点head的,头节点的数据域不存放数据,而指针域指向下一结点(该结点称为第一个结点),链表的最后一个结点的指针域指向NULL,即空地址,表示链表的结尾。

struct node{      int data;      node next;}

每次使用新结点时需临时分配内存空间给新结点,可以使用C语言的malloc或者C++的new。

malloc用法:

node p=(node)malloc(sizeof(node));

sizeof的作用就是返回一个对象或者类型所占的内存字节数,sizeof(node)就是返回node类型所占的内存字节数,malloc的作用分配内存空间,malloc(sizeof(node))就是向内存申请一块大小为sizeof(node)的空间,并且返回指向这块空间的指针,但该指针类型是void,返回类型是 void 类型,void 表示未确定类型的指针。C,C++规定,void 类型可以强制转换为任何其它类型的指针,所以在malloc前面加上(node )进行强制转换,转换成node型指针,赋值给node型的变量p。

new的用法:

node p=new node;(只需要new+类型名即可分配一块该类型的内存空间)

在使用完malloc,必须用free释放空间,new相对应就是delete。
free用法:free(p);
delete用法:delete(p);

2. 链表的基本操作

2.1 链表的创建

//创建链表struct node create(){    struct node p,pre,phead;    int len,i=1,j;    phead=(struct node)malloc(sizeof(struct node));    phead->next=NULL;    pre=phead;        printf("设定链表长度为:");    scanf("%d",&len);    while(i<len)    {                printf("第%d个结点的数据是:",i);        scanf("%d",&j);        p=(struct node)malloc(sizeof(struct node));        if(NULL==p)        {            printf("分配失败");            exit(-1);        }        p->data=j;        p->next=NULL;        pre->next=p;                pre=p;                i++;    }    return phead;} 

2.2 打印

void print(struct node phead){    struct node p;         p=phead;    while(p->next!=NULL)//在这一步曾经用p->data!=NULL来做条件,导致输出异常,我认为的是因为到最后一个结点有数据,但没有下一节点,会造成溢出     {        p=p->next;        printf("%d",p->data);    }}

2.3 查找

void search(struct node phead){    struct node p=phead;    int count=0,flag=0,a;    printf("请输入要查找的元素是:");    scanf("%d",&a);    while(p->next!=NULL)    {        p=p->next;        count++;        if(p->data==a)        {            printf("%d在第%d个结点\n",a,count);            flag=1;        }    }    if(flag==0)    {        printf("没有这个元素");    }}

2.4 删除

如果要删除p,就是pre->next=p->next;free(p);

void Delete(struct node phead){    struct node p,pre;    int a;    p=phead->next;    pre=phead;    printf("请输入要删除的元素是:");    scanf("%d",&a);    while(p!=NULL)    {        if(p->data==a)        {            pre->next=p->next;            free(p);            p=pre->next;        }        else        {            pre=p;            p=p->next;        }    }} 

2.5 插入

插入的重点是先 pnew->next=p;
后pre->next=pnew;

void insert(struct node phead){    struct node pnew;    int a,c;    pnew=(struct node)malloc(sizeof(struct node));    struct node pre=phead,p=phead->next;    printf("新插入结点的数据是:");    scanf("%d",&a);    printf("在哪个元素的位置插入:");    scanf("%d",&c);     while(p!=NULL)    {        if(c==p->data)        {            pnew->next=p;            pre->next=pnew;            pnew->data=a;            break;             }        else        {            pre=p;            p=p->next;        }    }} 
网友评论