数据结构之单链表详解二

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

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

好了，我们下篇博客，双链表见！

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

查看所有标签

猜你喜欢:

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

码农书籍

编写高质量代码

秦小波 / 机械工业出版社华章公司 / 2011-12-28 / 59.00元

在通往“Java技术殿堂”的路上，本书将为你指点迷津！内容全部由Java编码的最佳实践组成，从语法、程序设计和架构、工具和框架、编码风格和编程思想等五大方面对Java程序员遇到的各种棘手的疑难问题给出了经验性的解决方案，为Java程序员如何编写高质量的Java代码提出了151条极为宝贵的建议。对于每一个问题，不仅以建议的方式从正反两面给出了被实践证明为十分优秀的解决方案和非常糟糕的解决方案，而且还......一起来看看《编写高质量代码》这本书的介绍吧!

码农工具