数据结构之单链表详解二

栏目: 数据库 · 发布时间: 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;
}

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


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

查看所有标签

猜你喜欢:

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

Java语言精粹

Java语言精粹

Jim Waldo / 王江平 / 电子工业出版社 / 2011-6 / 39.00元

这是一本几乎只讲java优点的书。 Jim Waldo先生是原sun微系统公司实验室的杰出工程师,他亲历并参与了java从技术萌生、发展到崛起的整个过程。在这《java语言精粹》里,jim总结了他所认为的java语言及其环境的诸多精良部分,包括:类型系统、异常处理、包机制、垃圾回收、java虚拟机、javadoc、集合、远程方法调用和并发机制。另外,他还从开发者的角度分析了在java技术周围......一起来看看 《Java语言精粹》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具