• 数据结构与算法之-链表
  • 发布于 1周前
  • 19 热度
    0 评论
今天给大家介绍的是一种最基础,但面试中最常问到的数据结构——链表。学习新知识之前,首先需要具有一定的基础知识,打好基础,才能更进一步了解更复杂的知识体系。链表也是如此,在学习链表之前,首先需要学好C语言的基础逻辑,然后学习结构体,有了这些基础知识,才能打开链表知识的大门。

链表的知识体系大致可以分为三部分

1.创建

2.查找

3.删除


今天给大家分享的代码将这三部分都复合在一起,以帮助大家对链表有更深刻的理解。
#include<stdio.h>
#include<stdlib.h>
//定义结构体
typedef struct node{
         intdata;
         structnode * next;
}ElemSN;
//创建链表
ElemSN * Createlink(int a[],int n)
{
         ElemSN* head, * tail;//创建头尾指针
         head=tail=(ElemSN* )malloc(sizeof(ElemSN));
         head->data=a[0];
         head->next=NULL;
         for(inti=1;i<n;i++)
         {
                  tail=tail->next=(ElemSN *)malloc(sizeof(ElemSN));//循环内多次动态分配单元
                  tail->data=a[i];
                  tail->next=NULL;
         }
         returnhead;
}

/*算法思想:两指针联动 一个一次走一步 另一个一次走一步
当跨度大的链表遍历完链表所有的结点时
跨度小的链表刚好处于链表的中间*/
ElemSN * Centerpoint(ElemSN * h)
{
         ElemSN* p, * q;
         p=q=h;
         while(q&&q->next) 
         {
                  q=q->next->next;   //q指针一次走两步
                  p=p->next;         //p指针一次走一步
         }
         returnp;
}
//输出链表
ElemSN * Printlink(ElemSN * h)
{
         ElemSN* p;
         for(p=h;p;p=p->next)
         printf("%3d",p->data);
}
int main(void)
{
         inta[4]={23,5,48,98};
         ElemSN* head, * p;
         head=Createlink(a,4);
         Printlink(head);
         printf("\n");
         p=Centerpoint(head);
         printf("最中间的结点:%d",p->data);
}
#include<stdio.h>
#include<stdlib.h>
//定义结构体
typedef struct node{
         intdata;
         structnode * next;
}ElemSN;
//创建链表
ElemSN * Createlink(int a[],int n)
{
         ElemSN* head, * tail;
         head=tail=(ElemSN* )malloc(sizeof(ElemSN));
         head->data=a[0];
         head->next=NULL;
         for(inti=1;i<n;i++)
         {
                  tail=tail->next=(ElemSN *)malloc(sizeof(ElemSN));
                  tail->data=a[i];
                  tail->next=NULL;
         }
         returnhead;
}

/*算法思想:两指针联动 奇数输出最中间结点偶数输出中间较后的结点 */
ElemSN * Centrepoint(ElemSN * h)
{
         ElemSN* q, * p;
         for(p=q=h;q&&q->next;p=p->next,q=q->next->next);  
         returnp;
}
int main(void)
{
         inta[6]={1,2,3,4,5,6};
         ElemSN* head, * pm;
         head=Createlink(a,6);
         pm=Centrepoint(head);
         printf("%d",pm->data);
}
删除链表最大的结点 数据域值不重复
#include<stdio.h>
#define N 6
#include<stdlib.h>
typedef struct node{
         intdata;
         structnode * next;
}ElemSN;
ElemSN * CreateLink(int a[])
{
         ElemSN* h,* tail;
   h=tail=(ElemSN * )malloc(sizeof (ElemSN));
         h->data=a[0];
         h->next=NULL;
         for(intloop=1;loop<N;loop++){
                  tail=tail->next=(ElemSN *)malloc(sizeof (ElemSN));
                  tail->data=a[loop];
                  tail->next=NULL;
         }
         returnh;
} 
ElemSN * DelMaxNode(ElemSN * h)
{
         ElemSN* p, * q, * Pmax, * qmax;              
         Pmax=h;
         for(q=h,p=h->next;p;q=p,p=p->next)              //查找
         {
                  if(p->data>Pmax->data)
                  {
                           Pmax=p;
                           qmax=q;
                  }
         }
                  if(Pmax-h)                                //删除
                   qmax->next=Pmax->next;          
                  else
                           h=h->next;
                            
                  free(Pmax);                
    return h;
}
void Printlink(ElemSN * h)
{
         ElemSN* p;
         for(p=h;p;p=p->next)
         printf("%5d",p->data);
}
int main(void)
{
         inta[6]={3,2,5,8,4,7};
         ElemSN* head, * Pkey;
         //创建单向链表
         head=CreateLink(a);
         //删除最大结点
         Pkey=DelMaxNode(head);
         Printlink(head);
}


用户评论