顺序表与链表_顺序表和链表

顺序表与链表

一.顺序表
1.定义：将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。
顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中
顺序表可以分为静态顺序表和动态顺序表
2.结构定义：

#define MAXSIZE 100 
typedef int ElemType;
typedef struct Seqlist {
   //静态顺序表
    ElemType data[MAXSIZE];
    size_t size;
}Seqlist;
typedef struct Seqlist {
   //动态顺序表
	ElemType *base;
	size_t   capacity;
	size_t   size;
}Seqlist;
1
2
3
4
5
6
7
8
9
10
11
12
13

3.基本操作
（1）顺序表初始化

void SeqlistInit(Seqlist *pst, size_t capacity) {
   //顺序表初始化
	pst->capacity = capacity;
	pst->base = (ElemType*)malloc(sizeof(ElemType)* pst->capacity);
	assert(pst->base != NULL);
	memset(pst->base, 0, sizeof(ElemType)*pst->capacity);
	pst->size = 0;
}
1
2
3
4
5
6
7
8

（2）顺序表的头插及头删

void SeqlistPushFront(Seqlist *pst, ElemType v) {
   //顺序表头插
	//检查容量
	if (pst->size >= pst->capacity) {
   
		printf("顺序表容量不足，%d不能插入\n", v);
		return;
	}
	//移动数据
	for (int i = pst->size; i > 0; i--) {
   
		pst->base[i] = pst->base[i - 1];
	}
	//插入数据
	pst->base[0] = v;
	pst->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void SeqlistPopFront(Seqlist *pst) {
   //顺序表头删
	if (pst->size == 0) {
   
		printf("顺序表已空！不能进行删除！\n");
		return;
	}
	for (int i = 0; i < pst->size - 1; i++) {
   
		pst->base[i] = pst->base[i + 1];
	}
	pst->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（3）顺序表的尾插及尾删

void SeqlistPushBack(Seqlist *pst, ElemType v) {
   //顺序表尾插
	//检查容量
	if (pst->size >= pst->capacity) {
   
		printf("顺序表容量不足，%d不能插入\n", v);
		return;
	}
	pst->base[pst->size++] = v;
}
1
2
3
4
5
6
7
8
9
10

void SeqlistPopBack