数据结构 | 线性表

发表于 2018/04/01 更新于 2024/10/18

作者

次浏览 13 分钟阅读

线性表是一种典型的线性结构。

线性表的顺序实现

顺序表是线性表的顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素.

顺序表具备如下两个基本特征：

顺序表中的所有元素所占的存储空间是连续的；
顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设顺序表的每个元素需占用$K$个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺序表中第$i+1$个数据元素的存储位置 $LOC(a_{i}+1)$ 和第 $i$ 个数据元素的存储位置 $LOC(a_{i})$ 之间满足下列关系为:

$LOC(a_{i+1})=LOC(a_i)+K$ $LOC(a_{i})=LOC(a_{1})+(i-1) * K$

顺序表的常见操作:

插入($O(n)$)

删除($O(n)$)

查找

排序
分解
合并
复制($O(n)$)
逆转($O(n)$)

代码:

#include <stdio.h>
#include <stdlib.h>

// 实现两个顺序表的归并

typedef struct _List
{
	int * elem ;
	int length ;
	int listsize;
}List , *pList;

void MerginList (pList p1 , pList p2 , pList p3);
void InitList (pList p);

int main ()
{
	int i ;

	List L1 , L2 , L3;
	InitList (&L1);
	L1.length = 7;
	InitList (&L2);
	L2.length = 9;
	for (i  = 0 ; i < L1.length ; i++)
		L1.elem[i] = i*2+1;
	for (i = 0 ; i < L2.length ; i++)
		L2.elem[i] = i*1+5;

	puts ("L1 :");
	for (i  = 0 ; i < L1.length ; i++)
		printf (" %d ",L1.elem[i]);
	printf ("\n");

	puts ("L2 :");
	for (i  = 0 ; i < L2.length ; i++)
		printf (" %d ",L2.elem[i]);
	printf ("\n");

	MerginList (&L1 , &L2 , &L3);

	puts ("L3 :");

	for (i = 0 ; i < L3.length ; i++)
		printf (" %d ",L3.elem[i]);
	printf ("\n");


	return 0;
}

void MerginList (pList p1 , pList p2 , pList p3)
{
	int i=0 , j = 0;
	int *p ;
	int listsize = p1->length + p2->length;

	p3->elem = (int *)malloc(listsize*sizeof(int));
	p3->length = listsize;
	p3->listsize = listsize;

	p = p3->elem ;

	while (i < p1->length && j < p2->length)
	{
		if (p1->elem[i] < p2->elem[j])
		{
			(*p) = p1->elem [i];
			i++;
			p++;
		}
		else
		{
			(*p) = p2->elem[j];
			j++;
			p++;
		}

	}

	while (i < p1->length)
	{
		(*p) = p1->elem [i];
		i++;
		p++;
	}
	while (j < p2->length)
	{
		(*p) = p2->elem [j];
		j++;
		p++;
	}
}

void InitList (pList p)
{
	p->elem = (int *) malloc (sizeof(int)*10);
	p->length = 0;
	p->listsize = 10;
}

线性表的链式实现

链表指线性表的链式存储结构。

一组任意的存储单元存储线性表的数据元素，因此，为了表示每个数据元素 $a_i$ 与其直接后继数据元素 $a_{i+1}$ 之间的逻辑关系，对数据元素 $a_i$ 来说，除了存储其本身的信息(数据域)之外，还需存储一个变量指示其直接后继的信息(指针域)。

这两部分信息组成数据元素 $a_{i}$ 的存储映象，称为结点。NN 个结点链结成一个链表。该链表就是传统的单向链表。

有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，它指向表中第一个结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针。在单链表中，取得第 I 个数据元素必须从头指针出发寻找，因此，链表是非随机存取的存储结构。

以上提到的链表指针域只包括一个指针，指向下一个数据的地址，如果我们将链表最后一个结点指针域的指针指向链表的头结点地址，就构成了一个环状的存储结构，我们称作循环链表。

当然我们可以给每个结点的指针域再添加一个指针，使其指向前一个数据结点的地址，这样就构成了双向链表，而将头结点的前一个结点指向尾结点，同时将尾结点的下一个结点指向头结点就构成了双向循环链表。

如果链表的尾结点的指针域指向了该链表之前的任意一个结点，我们称该链表为有环链表。

链表表常见操作:

插入($O(n)$)

删除($O(n)$)

查找
排序
分解
合并
复制($O(n)$)
逆转($O(n)$)

普通链表

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 用链表实现排序以及归并问题

typedef struct _Node // 接受链表的指针
{
	int data;
	struct _Node *next ;
}Node , *pNode;

void addStack (pNode *pl,int a);  // 添加新元素
void TraStack (pNode pl);         // 遍历栈区
void MerginStack (pNode p1 , pNode p2 , pNode *p3); // 合并栈

int main ()
{

	int i , a ;
	pNode one = NULL;
	pNode two = NULL;
	pNode zero;

	srand ((unsigned int)time(NULL));
	for (i = 0 ; i < 10 ; i++)
	{
		a = rand() %60;
		addStack(&one , a);
	}

	for (i = 0 ; i < 10 ; i++)
	{
		a = rand() %60;
		addStack(&two , a);
	}

	TraStack (one);
	TraStack (two);

	zero = (pNode)malloc(sizeof(Node));
	zero->data = 0;
	zero->next = NULL;
	MerginStack (one,two,zero);
	TraStack (zero);

	return 0;
}

void addStack (pNode *pl,int a)
{
	pNode previous=NULL ;	// 用于指向插入点的上一个结点
	pNode next ;		// 用于指向插入点的下一个结点
	pNode New ;			// 用于指向插入点的新结点

	next = (*pl);       // 将next 指向要插入链表的首位置

	while (next != NULL && a > next->data)
	{
		previous=next;
		next = next->next;
	}

	New = (pNode) malloc (sizeof(Node));
	New->data = a;
	New->next = next;

	if (previous == NULL)
		(*pl) = New;
	else
		previous->next = New;

}

void TraStack (pNode pl)
{
	while (pl != NULL)
	{
		printf ("%d -> ",pl->data);
		pl = pl->next;
	}

	printf ("End\n");
}
void MerginStack (pNode p1 , pNode p2 , pNode p3)  
// 注意指针本质之间的灵活调用 解决此类问题要站在内存本质的角度上去思考指针问题
{
	pNode one = p3 ;

	while (p1 != NULL && p2 != NULL)
	{
		if (p1->data < p2->data)
		{
			one->next = p1 ;
			p1 = p1->next;
			p3->data++;
			one = one->next;
		}
		else
		{
			one->next = p2;
			p2 = p2->next;
			p3->data++;
			one = one->next;
		}
	}

	while (p1!=NULL)
	{
		one->next = p1 ;
		p1 = p1->next;
		p3->data++;
		one = one->next;
	}
	while (p2!=NULL)
	{
		one->next = p2;
		p2 = p2->next;
		p3->data++;
		one = one->next;
	}

	one=NULL;
}

静态链表 :

用数组描述的链表，即称为静态链表。在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MaxSize 20
typedef struct _SlinkList
{
	int data; // 存放数据
	int cur ; // 存放游标
}SlinkList , *pSlinkList ;

void InitList (pSlinkList pl);                   // 初始化静态链表
int MallocSL (pSlinkList pl);                    // 从备用链表中获取结点
void FreeSL (pSlinkList pl , int i );            // 将指定的结点回收到备用链表
void AddData (pSlinkList pl , int data ,int e);  // 将数据添加到指定位置
void TravelSL (pSlinkList pl);                   // 遍历静态链表区
void Adddata (pSlinkList pl , int data);         // 将数据初始化

int main ()
{
	int i;
	int a;
	SlinkList one[MaxSize];

	InitList (one); // 初始化静态链表

	srand ((unsigned int)time(NULL));
	for (i = 0 ; i < 15 ; i++)
	{
		a = rand()%50;
		Adddata (one,a);
	}

	TravelSL (one);

	AddData (one , 12 , 3);
	AddData (one , 11 , 1);


	TravelSL (one);

	return 0;
}

void InitList (pSlinkList pl)
{
	int i ;
	for (i = 0 ; i < MaxSize-1 ; i++)
		pl[i].cur = i+1;
	pl[i].cur = 0 ; // 最后一个游标存放第一个有数据的位置
					// 如果是 0 则说明没有任何数据

}

int MallocSL (pSlinkList pl)
{
	int i = pl[0].cur;   // 返回备用链表首结点的位置

	if (i == MaxSize-1)
		return 0;
	pl[0].cur=pl[i].cur;  // 重置备用链表首结点
	return i;

}

void AddData (pSlinkList pl , int data ,int e)
{
	int i ;
	int x = MaxSize-1 , y;
	int a ;

	if (!(a = MallocSL(pl))) // 为新的结点分配内存
	{
		puts ("error to malloc");
		return ;
	}
	pl[a].data = data;

	for (i = 0 ; i < e; i++)
	{
		y = x;        // 指向前一个
		x = pl[x].cur ;// 指向下一个
		if (y == 0)
		{
			puts ("error to insert");
			return ;
		}
	}

	pl[y].cur = a ;
	pl[a].cur = x ;    // 链接工作

}

void Adddata (pSlinkList pl , int data)
{
	int x = MaxSize-1;
	int a = MallocSL (pl);

	pl[a].cur = 0;
	pl[a].data = data;
	if (pl[MaxSize-1].cur==0)
		pl[MaxSize-1].cur = a;

	else
	{
		while (pl[x].cur != 0)
			x = pl[x].cur;
		pl[x].cur = a;
	}

}

void TravelSL (pSlinkList pl)
{
	int x = MaxSize-1;

	while (pl[x].cur != 0)
	{
		x = pl[x].cur;
		printf (" %d ->",pl[x].data);
	}

	printf (" End\n");
}

Base

算法

本文由作者按照 CC BY 4.0 进行授权

线性表的顺序实现

线性表的链式实现

静态链表 :

热门标签