复习##ADT1：链表

ADT1：链表
大一下学链表的时候大致讲了这样几种分类：
1、有无哨兵节点
2、是否是双向链表
3、有两个头节点还是一个头节点
事实上，最后用的最多的还是单头单链有哨兵的类型

大一的时候链表一般用于不确定输入数据量的时候（不老实的话可以数组空间MAXSIZE开大点，然后初始化为0或者用static类型，然后用EOF来输入）
学ds之后，链表成了很多ADT的表示形式，因为其”指向下一个数据“的特征

主要的操作有：
MakeEmpty：开个空链表
IsEmpty:检查是否为空
Insert:插入节点
Delete：删除节点
BP：遍历节点
Find：寻找节点
等等

基本的原则应该有：
1、任何指针用之前一定要检查指向是否为空
2、记得malloc
3、当没有用哨兵节点的时候要注意头节点的情况
还有个问题：
初始化的时候Next最好置为NULL

考虑是否需要哨兵的问题：
先回顾一下建立链表（最普通的线性表）的过程

void MakeList(){
	List Head,p,q;
	Head=(List)malloc(sizeof(struct listnode));
	int data;
	scanf("%d",&data);
	Head->Element=data;
	Head->Next=NULL;
	q=Head;
	if(data!=-1)scanf("%d",&data);
	while(data!=-1){
	if(Head->Next!=NULL){
		p=(List)malloc(sizeof(struct listnode));
		p->Element=data;
		p->Next=NULL;
		q=q->Next;
		q->Next=p;
		}
	else {
		p=(List)malloc(sizeof(struct listnode));
		p->Element=data;
		p->Next=NULL;
		q->Next=p;
	
	}
	scanf("%d",&data);
	}
}
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

这是在没有头节点的情况下的，可以看出来代码结构其实是不太统一的，写得时候甚至有点别扭，事实上在许多操作中，留一个头节点会增强代码的统一性，减少分类讨论的麻烦
例如删除操作，如果我们没有哨兵节点，那我们需要考虑头节点的情况
当我们有头节点的时候我们的操作就比较简单而统一：

void Delete(List L,ElementType x){
	List p;
	p=L;
	while(p->Next){
		if(p->Next->Element==x){
		if(p->Next->Next)p->Next=p->Next->Next;
		else p->Next=NULL;
	}
}
1
2
3
4
5
6
7
8
9

暂时想到这些