实验一 顺序表和单链表的建立和操作_在高级语言(如c语言)环境下:数组具有随机存取的特性,因此,借助数组来描述顺序

一、实验目的

1.了解顺序表的结构特点及有关概念
2.掌握顺序表建立、插入、删除的基本操作算法
3.了解单链表的结构特点、描述方法及有关概念
4.掌握单链表建立、插入、删除的基本操作算法

二、顺序表

在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。采用静态分配的顺序存储结构来表示。

包含的基本操作有：

1.建立顺序表: Status creatlist(sequenlist *L)
2.插入一个元素:Status insert(sequenlist *L,elemtype x,int i)
3.删除一个元素: Status dellist(sequenlist *L,int i)
4.输出顺序表: void printout(sequenlist *L)（辅助函数）

顺序线性表的插入

 在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：
  L=(a1，…a i-1，e，ai，ai+1，…，an) 
1
2

算法思想
(1) 进行合法性检查，1<=i<=n+1;
(2) 检查线性表是否已满；
(3) 将第n个至第i个元素逐一向后移动一个单元；
(4) 在第i个位置处插入新元素；
(5) 将表的长度加1.

顺序线性表的删除

在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点ai(1≦i≦n)，使其成为线性表：
       L= (a1，…ai-1，ai+1，…，an)
1
2

实现步骤
(1)进行合法性检查，1<=i<=n;
(2)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。
(3) 线性表长度减1。

#include "stdio.h"
#include "malloc.h"
#define maxsize 1024


typedef char elemtype;
typedef struct
{
   
	elemtype list[maxsize];
	int length;
}sequenlist;


//创建顺序表 
void creatlist(sequenlist *L);
//插入元素 
int insert(sequenlist *L,elemtype x,int i); 
//删除元素 
int dellist(sequenlist *L,int i);
//输出顺序表 
void printout(sequenlist *L);

//创建顺序表 
void creatlist(sequenlist *L)
{
   
	int n,i;
	char tmp;
	printf("请输入数据的个数：");
	scanf("%d",&n);
	for(i = 0; i < n; i ++)
	{
   
		printf("list[%d] = ",i);
		fflush(stdin);//清空输入缓冲区，通常是为了确保不影响后面    的数据的读入
		scanf("%c",&tmp);
		L -> list[i] = tmp;
	 } 
	 L -> length = n-1;
}

//插入元素 
int insert(sequenlist *L,elemtype x,int i)
{
   
	int j;
	if(L -> length == maxsize - 1)//判满
	{
   
		printf("overflow");
		return 0;
	}
	else if((i < 0) || (i > L -> length)) //判插入位置是否合法
	{
   
		printf("error,please input the right 'i'\n");
		return 0;
	}
	else
	{
   
		for(j = L-> length; j >= i; j --)
			L -> list[j+1] = L -> list[j];
		L -> list[i] = x;
		L -> length = L -> length + 1;
	}
	return 1;
}

//删除元素 
int dellist(sequenlist *L,int i)
{
   
	if((i < 0) || (i > L -> length))
	{
   
		printf("error,please input the right 'i'\n");
		return 0;
	}
	else
	{
   
		for( ; i < L -> length; i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83