顺序链表

顺序链表

一张顺序表包括以下特征：

有一个唯一的表名来标识该顺序表；

内存单元连续存储，也就是说，一张顺序表要占据一块连续的内存空间；

数据顺序存放，元素之间有先后关系。

1）顺序表的定义：

有两种定义顺序表的方法：一是静态地定义一张顺序表；二是动态地生成一张顺序表

typedef int ElemType;

/***************************************
*The definition of sequential list
****************************************/
typedef struct Sqlist{
	ElemType Elem_array[MAX_SIZE];
	int length;
}Sqlist;

2）对顺序链表的操作代码如下：

/**************************************
* The basic operation of sequential list
***************************************/
//initialize the sequential list
int init_sqlist(Sqlist *L)
{
	L->length = 0;
}

// Create a sequential list
void create_list(Sqlist *L)
{
	int i;
	printf("Please input the length of the sequential list that want to build:");
	scanf("%d",&L->length);
	printf("Please input %d elements to the sequential list:\n", L->length);
	for(i = 0; i < L->length; i++)
	{
		scanf("%d", &L->Elem_array[i]);
	}
	printf("building the sequential list successfully.\n");
	system("pause");
}

// Get the length of sequential list
int length_list(Sqlist *L)
{
	return L->length;
}

// Judge a sequential list if a null or not
int empty_list(Sqlist *L)
{
	if(L->length == 0)
		return 1;
	else
		return 0;
}

//Judge a sequential list is a full.
int full_list(Sqlist *L)
{
	if(L->length == MAX_SIZE)
		return 1;
	else
		return 0;
}

//Clear the Sequential list
void clear_list(Sqlist *L)
{
	L->length = 0;
}

// Get the element that in the sequential list
int get_list(Sqlist *L, int i)
{
	if(empty_list(L) || i > length_list(L) || i < 1)
	{
		printf("The sequential list is empty or the position is wrong");
		return;
	}
	return L->Elem_array[i - 1];
}

// Print the sequential list
void print_list(Sqlist *L)
{
	int i;
	if(empty_list(L) == 1)
	{
		printf("The sequential list is empty!");
		return;
	}
	else
	{
		for(i = 0; i < L->length; i++)
		{
			printf("%d\t", L->Elem_array[i]);
		}
	}
	printf("\n");
}

/***********************
* search the element 
************************/

// search the element according to position
int locate_list_pos(Sqlist *L, int i)
{
	if(i < 1 || i > length_list(L))
	{
		printf("the position is invalid!");
		return 0;
	}
	return L->Elem_array[i - 1];
}

// search the element according to content.
int locate_list_content(Sqlist *L, ElemType x)
{
	int i = 0;
	while(i < L->length && L->Elem_array[i] != x)
		i++;
	if(i < L->length)
		return (i + 1);
	else
		return 0;
}

/*********************************************
* The insert and delete of the sequential list 
***********************************************/
// Insert a  element in the i position.
void insert_list(Sqlist *L, int i, ElemType x)
{
	int j;
	if(L->length == MAX_SIZE)
		printf("the list full, can't insert!\n");
	else if(i < 1 || i > L->length + 1)
		printf("The inserted position is invalid!\n");
	else
	{
		for(j = L->length - 1; j >= i - 1; j--)
		{
			L->Elem_array[j + 1] = L->Elem_array[j];
		}
		L->Elem_array[i - 1] = x;
		L->length++;
	}
}

// Delete the i element in the sequential list.
void delete_list(Sqlist *L, int i)
{
	int j;
	ElemType x;
	if(i < 1 || i > L->length)
	{
		printf("The deleted position is invalid!\n");
	}
	else
	{
		x = L->Elem_array[i - 1];
		for(j = i; j < L->length; j++)
		{
			L->Elem_array[j - 1] = L->Elem_array[j];
		}
		L->length--;
		printf("%d is deleted\n",x);
	}
}

3）主函数如下：

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

int main()
{
	int p;
	Sqlist L;
	create_list(&L);
//	clear_list(&L);
	print_list(&L);
	system("pause");

	p = locate_list_content(&L, 5);
	printf("The position of the element 5 is %d:\n", p);
	system("pause");

	insert_list(&L, 2, 2);
	printf("After insert element:\n");
	print_list(&L);
	system("pause");

	delete_list(&L, 1);
	print_list(&L);

	system("pause");
	return 0;
}