数据结构之单链表详解二

栏目: 数据库 · 发布时间: 6年前

内容简介:​ 上篇博客讲到了单链表的实现和简单的使用,今天我们再详细介绍一下单链表。其实链表与数组不同在于,数组在分配内存的时候是连续的内存空间地址,是物理地址的连续,也可以叫做静态分配内存。链表,单向链表,双链表他的内存是动态的,也就是说你要用的时候,再生成下一个节点即可,不需要一次性就把内存要一块过去,可以一点点要,扩展也方便一些。但是数组的时间复杂度要小于链表,在一定情况下,效率更高,比如查询。但是删除元素的话,链表更方便一些,因为链表只有把next指针指向其他节点,就可以方便完成增加和删除,数组是需要

​ 上篇博客讲到了单链表的实现和简单的使用,今天我们再详细介绍一下单链表。其实链表与数组不同在于,数组在分配内存的时候是连续的内存空间地址,是物理地址的连续,也可以叫做静态分配内存。链表,单向链表,双链表他的内存是动态的,也就是说你要用的时候,再生成下一个节点即可,不需要一次性就把内存要一块过去,可以一点点要,扩展也方便一些。但是数组的时间复杂度要小于链表,在一定情况下,效率更高,比如查询。但是删除元素的话,链表更方便一些,因为链表只有把next指针指向其他节点,就可以方便完成增加和删除,数组是需要换掉整个内存,整个数据都要移动。

​ 我们这篇就来讲一下如何对单链表进行元素删除操作,顺便实现一下数组数据的删除,让大家有直观的感受,对比俩种数据结构差异。

2.单链表删除

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define N 10 
typedef struct node
{
 char name[20];
 struct node *link;
}stud;

stud * creat(int n) /*建立新的链表的函数*/
{
 stud *p,*h,*s;
 int i;
 if((h=(stud *)malloc(sizeof(stud)))==NULL)
 {
  printf("不能分配内存空间!");
  exit(0);
 }
 h->name[0]=’\0’;
 h->link=NULL;
 p=h;
 for(i=0;i<n;i )
 {
  if((s= (stud *) malloc(sizeof(stud)))==NULL)
  {
   printf("不能分配内存空间!");
   exit(0);
  }
  p->link=s;
  printf("请输入第%d个人的姓名",i 1);
  scanf("%s",s->name);
  s->link=NULL;
  p=s;
 }
 return(h);
}

stud * search(stud *h,char *x) /*查找函数*/
{
 stud *p;
 char *y;
 p=h->link;
 while(p!=NULL)
 {
  y=p->name;
  if(strcmp(y,x)==0)
   return(p);
  else p=p->link;
 }
 if(p==NULL)
 printf("没有查找到该数据!");
}

stud * search2(stud *h,char *x) /*另一个查找函数,返回的是上一个查找函数的直接前驱结点的指针,*/
/*h为表头指针,x为指向要查找的姓名的指针*/
/*其实此函数的算法与上面的查找算法是一样的,只是多了一个指针s,并且s总是指向指针p所指向的结点的直接前驱,*/
/*结果返回s即是要查找的结点的前一个结点*/
{
 stud *p,*s;
 char *y;
 p=h->link;
 s=h;
 while(p!=NULL)
 {
  y=p->name;
  if(strcmp(y,x)==0)
   return(s);
  else
  {
   p=p->link;
   s=s->link;
  }
 }
 if(p==NULL)
  printf("没有查找到该数据!");
}

void del(stud *x,stud *y) /*删除函数,其中y为要删除的结点的指针,x为要删除的结点的前一个结点的指针*/
{
 stud *s;
 s=y;
 x->link=y->link;
 free(s);
}

main()
{
 int number;
 char fullname[20];
 stud *head,*searchpoint,*forepoint;
 number=N;
 head=creat(number);
 printf("请输入你要删除的人的姓名:");
 scanf("%s",fullname);
 searchpoint=search(head,fullname);
 forepoint=search2(head,fullname);
 del(forepoint,searchpoint);
}

假如我们已经知道了要删除的结点p的位置,那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址,并回收p结点即可。

3.数组删除

下面我们来实现一下数组的元素删除

#include <stdio.h>

//查找和删除的业务逻辑
 /*****************************************
 *1、查找要删除数字的下标
 *2、从下标开始,后面一个覆盖前面一个数字
 *3、数组总长度-1
 ******************************************/
int main()
{
    int count = 7;                //数组元素个数
    double Nums[] = {423.2, 457.7, 409.0, 412.3, 407.6, 580.3, 320.5};
    int JudgementNum;             //用户进行下一步操作的判断数
    double InsertNum;             //用户要插入的数据
    double DeleteNum;             //用户要删除的数据
    int DeleteIndex = -1;         //删除某个数据的下标(索引),要给一个不可能的初值,方便判断。

    int i;                        //循环变量

    printf("当前采集到的数据为:\n");
    for(i = 0; i < count; i++)
    {
        printf("%.2lf\t", Nums[i]);
    }
    printf("\n\n是否需要删除部分数据?\n提示:输入数字1进行删除操作,输入数字0确认当前数据采集无误。\n");
    printf("请输入:");
    scanf("%d", &JudgementNum);
    if(JudgementNum == 1)
    {
        printf("\n请输入要删除的数据:");
        scanf("%lf", &DeleteNum);
        for(i = 0; i < count; i++)       //穷举法,是常用算法之一
        {
            if(DeleteNum == Nums[i])     //Nums[i]表示数组中的第i个元素
            {
                //找到后并记录当前数据的下标(索引)
                DeleteIndex = i;
                break;                   //找到了要删除的数据,直接跳出循环,提升效率
            }
        }
        //根据索引的判断,如果你要删除的数的下标和所给定索引的初值相同,那么肯定就是没找到。
        if(DeleteIndex == -1)
        {
            printf("没有找到该数据,删除失败!\n");
        }
        else
        {
            //如果找到了,建立一个循环并且从下标开始,数组中的元素后面一个覆盖前面一个,且数组长度 - 1
            for(i = DeleteIndex; i < count - 1; i++)
            {
                Nums[i] = Nums[i+1];
            }
                count--;
            //并打印输出后的结果
            printf("\n第%d个数据将被删除,删除后的结果为:\n", DeleteIndex + 1);
            for(i = 0; i < count; i++)
            {
                printf("%.2lf\t", Nums[i]);
            }
        }
    }else if(JudgementNum == 0)
    {
        printf("当前数据采集无误并保存!");
    }
    else
    {
        printf("删除数据操作发生错误!");
    }
    //注意:以下程序实现的是删除数据之后的插入操作
    printf("\n\n是否需要添加部分数据?\n提示:输入数字1进行添加操作,输入数字0保存当前数据。\n");
    printf("请输入:");
    scanf("%d",&JudgementNum);
    if(JudgementNum == 1)
    {
        printf("\n请输入要添加的数据:");
        scanf("%lf", &InsertNum);
        //进行添加操作,再数组长度+1
        Nums[count] = InsertNum;
        count++;
        printf("\n添加数据后的结果为:\n");
        for(i = 0; i < count; i++)
        {
            printf("%.2lf\t", Nums[i]);
        }
    }else if(JudgementNum == 0)
    {
        printf("当前数据已被保存。\n");
    }
    else
    {
        printf("添加数据操作发生错误\n");
    }
    return 0;
}

C中定义好一组数后,是通过访问元素下标来访问元素,所以正如注释数组如果找到了元素,删除以后,还做了被删除元素后面的数据,先去移动的操作,因为数组内存空间是连续的,你直接删除元素,但是数组空间会有空隙,要后面的元素不断填满,直到末尾数据也移动到了前一位即可。

3.单链表插入

下面,我们再讲一下单链表的插入,单链表的基本大家就算了解了。实际业务开始其实和我所举的例子还有差别,因为我们现在是直接调用。但是业务中,我们的代码是要给别人调用的,所以会有封装这样要求,但是其实也不难。我会在文章后面加上业务代码实现的。

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define N 10 
typedef struct node
{
 char name[20];
 struct node *link;
}stud;

stud * creat(int n) /*建立单链表的函数*/
{
 stud *p,*h,*s;
 int i;
 if((h=(stud *)malloc(sizeof(stud)))==NULL)
 
 h->name[0]='';
 h->link=NULL;
 p=h;
 for(i=0;i<n;i++)
 {
  if((s= (stud *) malloc(sizeof(stud)))==NULL)
  
  p->link=s;
  printf("请输入第%d个人的姓名:",i+1);
  scanf("%s",s->name);
  s->link=NULL;
  p=s;
 }
 return(h);
}

stud * search(stud *h,char *x) /*查找函数*/
{
 stud *p;
 char *y;
 p=h->link;
 while(p!=NULL)
 {
  y=p->name;
  if(strcmp(y,x)==0)
   return(p);
  else p=p->link;
 }
 if(p==NULL)
  printf("没有查找到该数据!");
}

void insert(stud *p) /*插入函数,在指针p后插入*/
{
 char stuname[20];
 stud *s; /*指针s是保存新结点地址的*/
 if((s= (stud *) malloc(sizeof(stud)))==NULL)
 
 printf("请输入你要插入的人的姓名:");
 scanf("%s",stuname);
 strcpy(s->name,stuname); /*把指针stuname所指向的数组元素拷贝给新结点的数据域*/
 s->link=p->link; /*把新结点的链域指向原来p结点的后继结点*/
 p->link=s; /*p结点的链域指向新结点*/
}

main()
{
 int number;
 char fullname[20]; /*保存输入的要查找的人的姓名*/
 stud *head,*searchpoint;
 number=N;
 head=creat(number); /*建立新链表并返回表头指针*/
 printf("请输入你要查找的人的姓名:");
 scanf("%s",fullname);
 searchpoint=search(head,fullname); /*查找并返回查找到的结点指针*/
 insert(searchpoint); /*调用插入函数*/
}

4.单链表封装实现

4.1 单链表头文件

这是封装的单链表头文件

typedef void LinkList;
/*
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
	LinkListNode* next;
};
*/
typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* next;
}LinkListNode;

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

4.1 单链表封装实现

这是封装实现

#include<stdio.h>
#include "stdlib.h"
#include "string.h"

#include "linklist.h"

typedef struct _tag_LinkList
{
	//这个句柄里面,需要保存所有节点信息。需要有一个起始点
	//就是带头节点的链表。。。
	LinkListNode header;
	int length;
}TLinkList;

LinkList* LinkList_Create()
{
	TLinkList *ret = (TLinkList *)malloc(sizeof(TLinkList));
	if (ret == NULL)
	{
		return NULL;
	}
	//memset(ret, 0, sizeof(TLinkList));
	ret->header.next = NULL;
	ret->length = 0;
	return ret;
}

void LinkList_Destroy(LinkList* list)
{
	if (list == NULL)
	{
		return ;
	}
	free(list);
	return ;
}

void LinkList_Clear(LinkList* list)
{

	TLinkList *tList =NULL;
	
	if (list == NULL)
	{
		return ;
	}
	tList = (TLinkList *)list;
	tList->length = 0;
	tList->header.next = NULL;
	return ;
}

int LinkList_Length(LinkList* list)
{

	TLinkList *tList = (TLinkList *)list;
	if (tList == NULL)
	{
		return -1;
	}

	return tList->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;

	tList = (TLinkList *)list;
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}

	//让node节点链接后续链表
	node->next = current->next ;
	//让前边的链表。链接node
	current->next = node;
	tList->length ++;	
	return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{

	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;
	LinkListNode *ret = NULL;
	tList = (TLinkList *)list;

	if (list == NULL || pos <0 ||pos>=tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;

	return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;
	LinkListNode *ret = NULL;
	tList = (TLinkList *)list;

	if (list == NULL || pos <0 ||pos>=tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;

	//删除算法
	current->next =ret->next;
	tList->length--;

	return ret;
}

4.3 调用示例

这是调用demo

#include<stdio.h>
#include "stdlib.h"
#include "string.h"
#include "linklist.h"

typedef struct Teacher
{
	LinkListNode node;
	char name[64];
	int age;
}Teacher;

int main()
{
	Teacher		t1,t2, t3;
	int			length, i = 0;

	LinkList		*list = NULL;
	t1.age = 31;
	t2.age = 32;
	t3.age = 33;


	list = LinkList_Create();

	length = LinkList_Length(list);

	//业务节点是teacher和算法分类的。。。。思想
	LinkList_Insert(list, (LinkListNode *)&t1, LinkList_Length(list));
	LinkList_Insert(list, (LinkListNode *)&t2, LinkList_Length(list));
	LinkList_Insert(list, (LinkListNode *)&t3, LinkList_Length(list));

	//遍历链表 
	for (i=0; i<LinkList_Length(list); i++)
	{
		Teacher *tmp = (Teacher *)LinkList_Get(list, i);
		if (tmp != NULL)
		{
			printf("age:%d ", tmp->age);
		}
	}

	while(LinkList_Length(list) > 0)
	{
		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
		if (tmp != NULL)
		{
			printf("age:%d ", tmp->age);
		}
	}
	LinkList_Destroy(list);

	return 0;
}

​ 好了,我们下篇博客,双链表见!


以上所述就是小编给大家介绍的《数据结构之单链表详解二》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C#入门经典

C#入门经典

[美] Karli Watson、Christian Nagel / 齐立波、黄静 / 清华大学出版社 / 2008-12 / 118.00元

这是一本成就无数C#程序员的经典名著,厚而不“重”,可帮助您轻松掌握C#的各种编程知识,为您的职业生涯打下坚实的基础,《C#入门经典》自第1版出版以来,全球销量已经达数万册,在中国也有近8万册的销量,已经成为广大初级C#程序员首选的入门教程,也是目前国内市场上最畅销的C#专业店销书,曾两次被CSDN、《程序员》等机构和读者评选为“最受读者喜爱的十大技术开发类图书”!第4版面向C#2008和.NET......一起来看看 《C#入门经典》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器