大话数据结构-3.6 线性表的链式存储结构 55- 高飞网

3.6 线性表的链式存储结构 55

2015-12-28 08:31:39.0

线性表的链式存储结构

    为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对于数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其后继的信息(即直接后继的存储位置)。存储数据元素信息的域称为数据域,存储直接后继位置的域称为指针域。这两部分称为结节。n个结点链成一个链表,即为线性表的链式存储结构。


    链接的第一个存储位置叫做头指针,第一个结点叫头结点,头结点只有指针或,没有数据域。最后一个没有后继,指针域指向NULL,最后一个结点只有数据域。


头指针与头结点的不同

头指针头结点

. 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。

. 头指针具有标识作用,所以常用头指针冠以指针的名字。

. 无论链表是否为空,头指针均不为空,头指针是链表的必要元素。

头结点是为了操作链接表的方便而设立的,放在第一个结点之前,数据域一般无意义。

. 有了头结点,对第一个结点前的插入结点和删除第一个结点,其操作与其他结点的操作就统一了。

. 头结点不是链接必须的。

只有头指针、有头结点、空链表分别表示如下:


单链接的代码表示:

/* 线性表的链式存储结构 */
typedef int ElemType ;      //ElemType类型根据实际情况而定,这里假设为int
typedef struct Node
{
    ElemType data;  
    struct Node * next;
}Node,*LinkedList;


由定义可知:结点由存储元素的数据域存放后继结点地址的指针组成。

假设p是指针链表第i个的指针,则数据域可以用p->data表示,指针域为p->next。所以,p-data = ai,p->next = ai+1。如下图:

单链表的读取

    由于单链表不像顺序链表那样通过索引直接获取,只能获取第一个元素开始,找到下一个元素,然后通过一个计数器计数。因此,单链表的读取时间复杂度取决于索引i的大小。时间复杂度为O(n)。


单链表的插入

    假设存储元素e的结点为s,要实现结点p、p->next、s之间的逻辑关系的变化,只需要将结点s插入到p和p->next之间即可。这时不用变动其他结点,只需要s->next和p-next的指针做一些变化即可。

s->next = p->next ; p->next = s;

图示如下:


单链表的删除

    假设存储元素a的结点为q,那么删除q的单链表操作,其实就是将它的前继结点的指针绕过,指向它的后继结点。

q = p->next; p->next = q->next;

总结:

    单链表的插入和删除操作由两部分组成,第一是遍历查找第i个元素,第二是插入和删除元素。因为查询的时间复杂度为O(n),插入和删除是一个常数次数的操作,因此插入和删除的时间复杂度都为O(n)。但如果知道第i个位置,不管插入多少个元素,时间复杂度都为O(1)。因此,对于插入或删除操作越频繁的操作,单链表的效率优势越明显。


单链表的整表创建

    顺序存储结构的创建,其实就是数组的初始化过程,即声明一个类型和大小的数组并赋值的过程。但单链表是一种动态结构,要从空表的初始状态依次建立的过程。单链表的状态思路:

  1. 声明一个结点p和计数器变量i;
  2. 初始化一个空链表L;
  3. 让L的头结点的指针指向NULL,即建立一个带头结点的单链表;
  4. 循环:1)生成一个新结点赋值给p;2)生成一个随机数赋值给p的数据域p->data;3)将p结点插入到尾结点。


单链表的整表删除

思路:

  1. 声明一个结点p和q;
  2. 将第一个结点赋值给p
  3. 循环:1)将下一结点赋值给q;2)释放p;3)将q赋值给p。


单链表的完整代码

LinkedList.h

/* 线性表的链式存储结构 */
typedef int ElemType ;      //ElemType类型根据实际情况而定,这里假设为int
typedef struct Node
{
    ElemType data;  
    struct Node * next;
}Node,*LinkedList;

#define OK 1
#define ERROR 0
typedef int Status;
/* 线性表通用操作  */
Status InitList(LinkedList *L);     //建立一个空的线性表L
Status ListEmpty(LinkedList L);     //若线性表为空返回true,否则返回false
Status ClearList(LinkedList *L);    //将线性表清空
Status GetElem(LinkedList L,int i,ElemType *e);     //将线性表L中第i个位置元素值返回给e
int LocateElem(LinkedList L,ElemType e);    //在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
Status ListInsert(LinkedList *L,int i,ElemType e);      //在线性表L中的第i个位置插入新元素e
Status ListDelete(LinkedList *L,int i,ElemType *e);     //删除线性表L中第i个位置元素,并用e返回值值
int ListLength(LinkedList L);   //返回线性表L的元素个数

LinkedList.c

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

int main(void)
{
	LinkedList L;
	InitList(&L);

	if(ListEmpty(L))
	{
		printf("是空的\n");
		ListInsert(&L,0,3);
		ListInsert(&L,1,13);
		ListInsert(&L,2,23);
		ListInsert(&L,2,33);
		ListInsert(&L,4,43);
		ListInsert(&L,5,53);
		ListInsert(&L,6,63);
		ListInsert(&L,7,73);
		ListInsert(&L,8,83);
		ListInsert(&L,9,93);
		ListInsert(&L,10,103);
		ListInsert(&L,11,113);
		ListInsert(&L,12,123);
	}
	printf("遍历所有元素:\n");
	int len = ListLength(L);
	LinkedList h;int j=0;
	h = L;
	while(h->next)
	{
		h = h->next;
		printf("[%d]%d,",j,h->data);
		j++;
	}
	printf("\n长度为%d\n",len);
	ElemType e;
	GetElem(L,2,&e);
	printf("索引2位置的元素是:%d\n",e);
	printf("查找53的索引位置是:%d\n",LocateElem(L,53));

	printf("删除第6位后\n");
	ElemType ee;
	ListDelete(&L,6,&ee);	
	len = ListLength(L);
	j = 0;
	h = L;
	while(h->next)
	{
		h = h->next;
		printf("[%d]%d,",j,h->data);
		j++;
	}

	printf("\n");


	return 0;
}

//建立一个空的线性表L
Status InitList(LinkedList *L)				
{
	*L = (LinkedList)malloc(sizeof(LinkedList));
	(*L)->next = NULL;
	(*L)->data = 0;
	return OK;		
}
//若线性表为空返回true,否则返回false
Status ListEmpty(LinkedList L)				
{
	return L->next == NULL;		
}
//将线性表清空
Status ClearList(LinkedList *L)			
{
	LinkedList p = (*L)->next,q;
	while(p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;	//头结点的指针域置空
	(*L)->data = 0;		//头结点的数据域表示长度变为0
	return OK;		
}
//将线性表L中第i个位置元素值返回给e
Status GetElem(LinkedList L,int i,ElemType *e)			
{
	int j=0;
	LinkedList p = L->next;//第一个结点
	while(p && j<i)
	{
		p = p->next;
		j++;
	}
	if(!p || j>i)
	{
		printf("第%d个结点不存在\n",i);
		return ERROR;
	}
	*e = p->data;
	return OK;		
}
//在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
int LocateElem(LinkedList L,ElemType e)			
{
	int j =0;
	LinkedList p = L->next;
	while(p)
	{
		if(p->data == e)
		{
			return j;
		}
		p = p->next;
		j++;
	}
	return ERROR;		
}
//在线性表L中的第i个位置插入新元素e
Status ListInsert(LinkedList *L,int i,ElemType e)		
{	
	int j=0;
	LinkedList p,s;		//s为新建的结点的指针
	p = *L;				//p指向表头结点
	while(p && j<i)
	{
		p = p->next;	//往后找
		j++;
	}
	if(!p || j>i)
	{
		printf("第%d个结点不存在!\n",i);
		return ERROR;
	}
	s = (LinkedList )malloc(sizeof(Node));
	s->data = e;
	s->next = p->next;
	p->next = s;
	(*L)->data ++;
	return OK;		
}
//删除线性表L中第i个位置元素,并用e返回值值
Status ListDelete(LinkedList *L,int i,ElemType *e)		
{
	LinkedList p = (*L)->next,q;
	int j = 0;
	while(p && j<i-1)
	{
		p = p->next;
		j++;
	}
	if(!(p->next) || j>i)
	{
		printf("第%d个结点不存在\n",i);
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q);
	return OK;		
}
//返回线性表L的元素个数
int ListLength(LinkedList L)			
{
	return L->data;		
}


相关面试题

http://wuchong.me/blog/2014/03/25/interview-link-questions/