当前位置:编程学习 > C/C++ >>

数据结构基础(一):单链表 双链表 循环链表

(1)单链表
 
 
编程实现一个单链表的建立/测长/打印。
 
#include <stdio.h>
#include <string.h>
typedef struct student
{
   int data;
   struct student *next;
}node;
//建立单链表
node *creat()
{
  node *head,*p,*s;
  int x,cycle=1;
  head = (node*)malloc(sizeof(node));//最初头部没有值,只是用来指向第一个元素
  p=head;
  while(cycle)
  {
     printf("\nplease input the data");
     scanf("%d",&x);
     if(x!=0)
     {
       s=(node *)malloc(sizeof(node)); //为元素分配内存
       s->data = x;
       printf("\n%d",s->data);
       p->next = s;                   //前一个元素的指针指向现在的元素
       p=s;                           //现在的元素成为前一个元素
     }
     else cycle = 0;
  }
  head = head->next;                  //将头指向第一个元素
  p->next = NULL;                     //尾部指向NULL
  printf("\n yyy %d",head->data);
  return(head);
}
//单链表测长
int length(node *head)
{
 int n=0;
 node *p;
 p = head;                            //链表初始
 while(p!=NULL)                       //链表结束
 {
   p=p->next;
   n++;
 } 
 return(n);
}
//单链表打印
void print(node *head)               //链表初始
{                                    //链表结束
  node *p;int n;
  n = length(head);
  printf("\nNow,These %d records are:\n",n);
  p = head;
  if(head!=NULL)
  while(p!=NULL)
  {
   printf("\n uuu %d ",p->data);
   p = p->next;
  }
}
 
 
编程实现单链表删除节点。
如果删除的是头节点,则把head指针指向头节点的下一个节点。同时free p1;
如果删除的是中间节点,则把p2的next指向p1的next,同时free p1;
代码如下:
node *del(node *head, int num)
{
  node *p1,*p2;
  p1 = head;
  while(num!=p1->data && p1->next!=NULL) //挨着遍历,p2为找到的那个元素的前一个元素
  {
    p2=p1;
    p1=p1->next; 
  }
  if(num==p1->data)
  {
    if(p1==head)       //要删除的是头节点
    {
      head = p1->next;
      free(p1);
    }
    else 
    {
     p2->next = p1->next;//要删除的是中间节点(含尾节点)
     free(p1);
    }
  }
  else
  printf("\n%d cound not be found",num);
  return(head);          //链表操作一般返回头节点
}
 
编写程序实现单链表的插入。
如果插入在头节点以前,则p0的next指向p1,头节点指向p0;
如果插入中间节点,则先让p2的next指向p0,再让p0指向p1;
如果插入尾节点,则先让p1的next指向p0,再让p0指向空;
代码如下:
/*这里链表默认按从小到达排序*/
node *insert(node *head, int num)
{
 node *p0,*p1,*p2;
 p1 = head;
 p0 = (node *)malloc(sizeof(node));
 p0->data = num;
 while(p0->data>p1->data && p1->next!=NULL)
 {
  p2=p1;
  p1=p1->next;
 }
 if(p0->data<=p1->data)//判断不可少,因为可能到链表末尾了
 {
   if(head==p1)
   {
     p0->next = p1;
     head = p0;
   }
   else
   {
     p2->next = p0;
     p0->next = p1;
   }
 }
 else
 {
      p1->next = p0;
      p0->next = NULL;
 }
 return(head);
}
 
编程实现单链表的排序
代码如下:
/*单链表排序 双重循环 两两比较 每次找出剩下元素中最大的*/
node *sort(node *head)
{
 node *p,*p2,*p3;
 int n; int temp;
 n = length(head);
 if(head==NULL || head->next ==NULL)
 return head;
 p = head;
 for(int i=1;i<n;i++)
 {
   for(int j=1;j<=n-i;j++)
   {
     if(p->data>p->next->data)   //两两比较,比后者大则互换
     {
      temp = p->data;
      p->data = p->next->data;
      p->next->data = temp;
     }
     p = p->next;
   }
 }
 return head;
}
 
编程实现单链表的逆置。
代码如下:
/*进行单链表逆置,首先要让p2的next指向p1
再让p1等于p2,p2等于p3,也就是说每次只调换一个箭头,
形成一个循环
*/
node *reverse(node *head)
{
  node *p1,*p2,*p3;
  if(head==NULL||head->next==NULL)
  return head;
  p1=head,p2=p1->next;
  while(p2)
  {
    p3=p2->next;
    p2->next = p1;
    p1 = p2;
    p2 = p3;
  }
  head->next = NULL;
  head = p1;
  return head;
}
 
 
有一个C语言用来删除单链表的头元素的函数,请找出其中的问题并加以纠正。
void RemoveHead(node* head)
{
  free(head);
  head = head->next;
}
当然不对,先free(head)之后,就找不到head了,下一句head = head->next 就不能正确链接了
正确答案如下:
(1)
void RemoveHead(node* head)
{
   node *p;
  &
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,