数据结构——单链表（基本操作 一）

前言

数据结构是计算机专业中的一门专业基础必修课，学好常见的数据结构可以为后续课程的学习打下良好的基础,也是学习计算机专业其他课程的必备条件

1.单链表基本操作的实现

1.1 按位序插入(带头结点)

// 定义结构体
typedef struct LNode() {
	ElemType data;
	struct LNode *next;
}LNode, LinkList*;

bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1) return false;  //判断插入的位置是否合法
	LNode *p;  //指针p指向当前扫描到的结点 
    int j=0;   //当前p指向的是第几个结点
    p = L;     //L指向头结点，头结点是第0个结点（不存数据）

	// 循环找到第 i-1 个结点
	while(p!=NULL && j<i-1) { // 如果i>length p指向NULL
		p=p->next; // p指向下一结点
		j++; 
	}
	if(p==NULL) return false;
	
	// 在第 i-1个结点后插入结点
	LNode *s = (LNode *)malloc(sizeof(LNode)); // 
	s->data = e;
	s->next = p->next;
	p->next = s;   //将结点s连到p后
	// !!!!! 后两步千万不能颠倒
	return true;
}
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

1.2 按位序插入(不带头结点)

typedef struct LNode() {
	ElemType data;
	struct LNode *next;
}LNode, LinkList*;

bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1) return false;  //判断插入的位置是否合法
	
	//插入到第1个位置时的操作有所不同！
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;          //头指针指向新结点
        return true;
    }
    
	LNode *p;  //指针p指向当前扫描到的结点 
    int j=1;   //当前p指向的是第几个结点
    p = L;     //L指向头结点，头结点是第0个结点（不存数据）

	// 循环找到第 i-1 个结点
	while(p!=NULL && j<i-1) { // 如果i>length p指向NULL
		p=p->next; // p指向下一结点
		j++; 
	}
	if(p==NULL) return false;
	
	// 在第 i-1个结点后插入结点
	LNode *s = (LNode *)malloc(sizeof(LNode)); // 
	s->data = e;
	s->next = p->next;
	p->next = s;   //将结点s连到p后
	// !!!!! 后两步千万不能颠倒
	return true;
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

1.3 按位序删除结点(带头结点)

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListDelete(LinkList &L, int i, ElenType &e){
    if(i<1) return false;

    LNode *p;       //指针p指向当前扫描到的结点 
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    if(p==NULL) 
        return false;
    if(p->next == NULL) //第i-1个结点之后已无其他结点
        return false;

    LNode *q = p->next;         //令q指向被删除的结点
    e = q->data;                //用e返回被删除元素的值
    p->next = q->next;          //将*q结点从链中“断开”
    free(q)                     //释放结点的存储空间

    return true;
}

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

1.4 指定结点的删除

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    
    LNode *q = p->next;      //令q指向*p的后继结点
    p->data = p->next->data; //让p和后继结点交换数据域
    p->next = q->next;       //将*q结点从链中“断开”
    free(q);
    return true;
} 
1
2
3
4
5
6
7
8
9
10

总结

本节就介绍单链表基本操作的一部分，下节继续。
如果感觉对你有用的话，点个关注吧！