数据结构之单链表详解二

栏目: 数据库 · 发布时间: 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++ Primer 中文版（第 5 版）

[美] Stanley B. Lippman、[美] Josée Lajoie、[美] Barbara E. Moo / 王刚、杨巨峰 / 电子工业出版社 / 2013-9-1 / CNY 128.00

这本久负盛名的 C++经典教程，时隔八年之久，终迎来史无前例的重大升级。除令全球无数程序员从中受益，甚至为之迷醉的——C++ 大师 Stanley B. Lippman 的丰富实践经验，C++标准委员会原负责人 Josée Lajoie 对C++标准的深入理解，以及C++ 先驱 Barbara E. Moo 在 C++教学方面的真知灼见外，更是基于全新的 C++11标准进行了全面而彻底的内容更新。......一起来看看《C++ Primer 中文版（第 5 版）》这本书的介绍吧!

码农工具