[数据结构与算法]【Day2·超详细】数据结构 之 线性表链式存储

导读

本篇文章将会总结单链表的基本操作（初始化，插入，删除......）、进阶操作（排序，去重，翻转，有序表的拼接......）进行介绍，并附加完整的c代码和测试图。代码完全自制手打，可以随便copy，发现问题可以在评论区说哦

注意所有的单链表都有头结点！

单链表的基本操作

单链表的结构：

数据域采用整型

单链表基本函数汇总，以及测试效果图，用的是C语言代码，可以直接复制自行测试！

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 2
#define OVERFLOW 0
typedef struct LNode{
	int data;
	struct LNode* next;
}LNode,*LinkList;
typedef int Status;
LinkList CreatList(void);//创建链表 ****
Status  DestroyList(LinkList L);//销毁  ****
Status  ClearList(LinkList L);//清空  ****
Status  ListEmpty(LinkList L);//判空  ****
int     ListLength(LinkList L);//求长度  ****
Status  ListTraverse(LinkList L);//遍历  ****
Status  InsertList(LinkList L,int i,int e);//插入  ****
Status  DeleteList(LinkList L,int i,int *e);//删除  ****
Status  LocateElem(LinkList L,int e,int *i);//定位元素  ****
Status  GetElem(LinkList L,int *e,int i);//获取元素 
int main()
{
	printf("创造一个单链表：");
	LinkList L=CreatList();
	printf("其长度为：%d\n",ListLength(L));
	printf("遍历链表：");
	ListTraverse(L);
	int i; int e;
	printf("分别输入你想在第几个位置插入什么元素：");
	scanf("%d%d",&i,&e);
	InsertList(L,i,e);
	printf("插入完之后再次进行遍历：");
	ListTraverse(L);
	printf("下面开始定位元素：\n");
	printf("你想要定位元素的值为：");
	scanf("%d",&e);
	LocateElem(L,e,&i);
	printf("%d在链表中的位置为：%d",e,i);
	return 0; 
} 
LinkList CreatList(void)
{
	LinkList p=(LinkList)malloc(sizeof(LNode));
	p->next=NULL;
	LinkList pTail=p;
	int i,num,temp;
	LinkList q;
	printf("输入你想要的结点个数：");
	scanf("%d",&num);
	for(i=1;i<=num;i++)
	{
		printf("输入第%d个结点的值：",i);
		scanf("%d",&temp);
		q=(LinkList)malloc(sizeof(LNode));
		pTail->next=q;
		q->next=NULL;
		q->data=temp;
		pTail=q;
	}
	return p;
}
Status DestroyList(LinkList L)
{
	LinkList p=L->next;
	LinkList q;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	free(L);
	return OK;
}
Status ClearList(LinkList L)
{
	LinkList p=L->next;
	LinkList q;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	return OK;
}
Status  ListEmpty(LinkList L)
{
	if(L->next==NULL)
	return TRUE;
	else 
	return FALSE;
}
int  ListLength(LinkList L)
{
	LinkList p=L->next;
	int cnt=0;
	while(p)
	{
		cnt++;
		p=p->next;
    } 
    return cnt;
}
Status  ListTraverse(LinkList L)
{
	LinkList p=L->next;
    if(ListEmpty(L))
    {
    	printf("这是一个空表！\n");
    	return OK;
	}
	printf("表内的元素有：");
	while(p)
	{
		printf("%d ",p->data);
		p=p->next; 
    } 
    printf("\n");
    return OK;
}
Status  InsertList(LinkList L,int i,int e)//把元素e插入第i个位置 
{
	if(i>ListLength(L)+1)
	{
		printf("输入的位置有误！\n");
		return ERROR;
	}
	int j=1;
	LinkList p=(LinkList)malloc(sizeof(LNode));
	p->data=e;
	LinkList q=L;
	for(j=1;j<i;j++)
	q=q->next;
	p->next=q->next;
	q->next=p;
	return OK;
}
Status  DeleteList(LinkList L,int i,int *e)//删除第i个位置的元素
{
	if(i>ListLength(L))
	{
		printf("输入的位置有误\n");
		return ERROR;
	}
	LinkList p=L;
	int j;
	for(j=1;j<i;j++)
	p=p->next;
	*e=p->next->data;
	LinkList q=p->next;
	p->next=q->next;
	free(q);
	return OK;
} 
Status  LocateElem(LinkList L,int e,int *i)
{
	LinkList p=L->next;
	int cnt=0;
	while(p)
	{
		cnt++;
		if(p->data==e)
		{
			*i=cnt;
			return OK;
		}
		p=p->next;
	}
	printf("没有找到！\n");
	return ERROR;
}
Status  GetElem(LinkList L,int *e,int i)
{
	if(i>ListLength(L))
	{
		printf("输入的位置有误！\n");
		return ERROR;
	}
	int j;
	LinkList p=L->next;
	for(j=1;j<i;j++)p=p->next;
	*e=p->data;
	return OK;
}

?单链表的进阶操作

去重：刚开始的时候，用指针p指向链表第一个元素，让Phead->next指向空，这一步实际是把链表一分为二了，再用一个q指向包含头结点的那部分的第一个元素。然后进行循环，每循环一次，p往右走一步，直到走到那部分的尽头。每次循环都做什么呢？每次循环都要检查p此时指向的元素的值和包含头结点那部分的链表有没有重复元素，即设置循环：while(q&&q->data!=p->data)q=q->next;，结局有两个，一是q为null，此时说明没有重复的，利用头插法把p指向的元素插入phead后面，另外一种结局是data相同，此时说明元素重复，则直接free（p）

Status PurgeList(LinkList L)
{
	LinkList p=L->next;
	L->next=NULL;
	LinkList q;
	while(p)
	{
		q=L->next;
		while(q&&q->data!=p->data)q=q->next;
		if(q)
		{
			LinkList t=p->next;
			free(p);
			p=t;
		}
		else
		{
			LinkList t=p->next;
			p->next=L->next;
			L->next=p;
			p=t;
		}
	}
	return OK;
}

颠倒：由于去重本质是头插法构造，所以最后元素是反的，那么我们可以再利用“分割链表”这个思想去把元素颠倒过来，所以这个函数的代码与去重几乎一样

Status ReverseList(LinkList L)
{
	LinkList p=L->next;
	L->next=NULL;
	while(p)
	{
		LinkList t=p->next;
		p->next=L->next;
		L->next=p;
		p=t;
	}
	return OK;
}

测试图：

排序：这个实际就是一个普通的冒泡排序（当然也可以用其它的）只不过i的初始化相当于p指向第一个元素，i++相当与p=p->next

void SortList(LinkList L)
{
	int i,j,t,len=ListLength(L);
    LinkList p,q;
	for(i=1,p=L->next;i<len;i++,p=p->next)
	{
		for(j=i+1,q=p->next;j<=len;j++,q=q->next)
		{
			if(p->data>q->data)
			{
				t=p->data;
				p->data=q->data;
				q->data=t;
			}
		}
	}
}

有序表的拼接：在一个函数当中传入两个单链表La和Lb，函数返回值设置为LinkList，以La的头结点最为合并后的表的头结点，定义三个辅助指针pa pb?pc分别指向La Lb Lc的最后一个结点，刚开始Lc为空表，所以pc指向Lc，由于以La的头结点最为合并后的表的头结点，所以，Lc=pc=La,然后进行循环，pa?pb任意一个为null则循环结束，每一次循环，就往Lc中加入一个新元素，最后让pc接上剩余的La或Lb：

LinkList MergeList(LinkList La,LinkList Lb)
{
	LinkList Lc,pa,pb,pc;
	pa=La->next; pb=Lb->next;
	Lc=pc=La;
	while(pa&&pb)
	{
		if(pa->data<=pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
    } 
    pc->next=pa?pa:pb;
    free(Lb);
    return Lc;
}

测试如下：

?主函数内容

int main()
{
?? ?LinkList L;
?? ?L=CreatList();
?? ?ListTraverse(L);
?? ?PurgeList(L);
?? ?printf("去重之后");
?? ?ListTraverse(L);
?? ?ReverseList(L);
?? ?printf("颠倒之后");?
?? ?ListTraverse(L);?
?? ?SortList(L);
?? ?printf("排序之后");
?? ?ListTraverse(L);?
?? ?LinkList L1;
?? ?L1=CreatList();
?? ?LinkList L2;
?? ?L2=MergeList(L,L1);
?? ?printf("合并之后");
?? ?ListTraverse(L2);?
?? ?return 0;
}