当前位置: article > 正文

【笔记】C++链表实现线性表基本操作

作者：小蓝xlanll | 2024-04-22 21:26:06

踩

【笔记】C++链表实现线性表基本操作

文章目录

1. 线性表

线性表 $(l i n e a r l i s t)$ 是一种数据结构，是由 $n$ 个具有相同特性的数据元素构成的序列。

线性表中元素的个数 n 即为线性表的长度，当 $n = 0$ 时称为空表。线性表的相邻元素之间存在着序偶关系。

如用 $(a_0 ,\cdots ,a_{i-1} ,a_i ,a_{i+1} ,\cdots,a_{n-1})$ 表示一个长度为 $n$ 的线性表，则称 $a_{i-1}$ 是 $a_i$ 的前驱， $a_{i+1}$ 是 $a_i$ 的后继。

2.线性表的一般操作

将线性表变为空表；
返回线性表的长度，即表中元素个数；
获取线性表某位置的元素；
定位某个元素在线性表中的位置；
在线性表中插入一个元素；
删除某个元素；
判断线性表是否为空；
遍历输出线性表的所有元素；
线性表排序。

3.线性表的表示方法

线性表可以用链表来实现。链表是通过指针链接在一起的一组数据项（结点）。

链表的每个结点都是同类型的结构，该结构中一般包含两类信息：

数据域，存储业务相关的数据（如财务系统的数据域为财务信息，车辆管理系统的业务信息为车辆信息）；
指针域，用于构建结点的链接关系。单链表的实现只需要一个指针。

为简单起见，本文实现的线性表的数据域都只有一个整数。

4.C++实现

4.1 顺序构建线性表

node结构

struct node{
    int data;
    node * next;
};
1
2
3
4

main()：顺序构建线性表

int main()
{
	int n,i;
	node *t;
	node *head=NULL; // 头指针为NULL，表示线性表为空，结点数为0
	// 输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		// 为新节点动态分配空间
		t = new node;
		cin>>t->data;  // 输入结点数据
		t->next=NULL;  // 结点指针域值为空
		// 调用函数插入结点
		head = insertTail(head, t);
	}
	// 输出链表
	printList(head);
	// 删除结点，释放空间
	delList(head);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

函数insertTail：向表尾添加新节点

node *insertTail(node *h, node *t)
{
    if(h==NULL){
        t->next = NULL; //头指针为空则将t作为新的头指针
        return t;
    }
    node *p = h;
    while(p->next != NULL){
        p = p -> next;
    } //找到链表尾
    p -> next = t;
    return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

函数printList：

void printList(node *h)
{
	cout<<"List:"; 
	while(h)
	{//h为真，即h指向的结点存在，则输出该结点的数据
		cout<<" "<<h->data;  //输出结点数据
		h=h->next;  //将该结点的指针域赋值给h，h就指向了下一个结点
	}
	cout<<endl; //输出换行符
}
1
2
3
4
5
6
7
8
9
10

函数delList：

void delList(node *h)
{
	node *p=h; //指针p指向头结点，第一个要删除的结点
	while(p) //这个结点是存在的
	{
		h = h->next; //头指针h指向下一个结点（下一个结点的地址存在当前结点的指针域中，即h->next中
		delete p; //删除p指向的结点
		p = h; //p指向当前的头结点，即下一个要删除的结点
	}
}
1
2
3
4
5
6
7
8
9
10

4.2 逆序构建线性表

main：逆序构建线性表

int main()
{
	int n,i;
	node *t;
	node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
	//输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		//为新节点动态分配空间
		t = new node;
		cin>>t->data; //输入结点数据
		t->next=NULL;  //结点指针域值为空
		//调用函数插入结点到链表头部
		head = insertHead(head, t);
	}
	//输出链表
	printList(head);
	//删除结点，释放空间
	delList(head);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

函数insertHead：向表头添加新节点

node * insertHead(node *h, node *t)
{
    t->next = h;
    return t;
}
1
2
3
4
5

4.3 排序构建线性表

实现将一个结点按结点数据 data 从小到大的顺序插入到一个有序链表中。根据插入结点 data 的大小，插入点可能是链表头、尾或者中间某个位置。
main()：排序构建线性表

int main()
{
	int n,i;
	node *t;
	node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
	//输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		//为新节点动态分配空间
		t = new node;
		cin>>t->data; //输入结点数据
		t->next=NULL;  //结点指针域值为空
		//调用函数插入结点，按data从小到大排序插入
		head = insertSort(head, t);
	}
	//输出链表
	printList(head);
	//删除结点，释放空间
	delList(head);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

函数insertSort：按data大小向链表中插入新节点

node * insertSort(node *h, node *t)
{
    node *p = NULL, *q = h;
    while(q != NULL && q->data < t->data){
        p = q;
        q = q->next;
    }//q指向要插入的节点位置，p指向其上一个节点

    if(p == NULL){
        t->next = h;
        return t;
    }//插入点是头部指针

    if(q == NULL){
        p->next = t;
        t->next = NULL;
        return h;
    }//插入点是链尾

    p->next = t;
    t->next = q;//插入点在链中
    return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.4 查找元素

int main()
{
	int n,i,num;
	node *t;
	node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
	//输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		//为新节点动态分配空间
		t = new node;
		cin>>t->data; //输入结点数据
		t->next=NULL;  //结点指针域值为空
		//构建有序链表
		head = insertSort(head, t);
	}
	//输入要查找的数
	cin>>num;
	//在链表中查找num
	node *np = search(head,num);
	//输出从np开始的后半截链表（如果np为NULL，则输出空链表）
	printList(np);
	//删除结点，释放空间
	delList(head);

	return 0;
}
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

函数search：

node * search(node * h, int num)
{
    node *p = h;
    while(p){
        if (p->data == num){
            return p;
        }
        p = p->next;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

4.5 删除指定位置的结点

main()删除指定位置的结点：

int main()
{
	int n,i;
	node *t;
	node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
	//输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		//为新节点动态分配空间
		t = new node;
		cin>>t->data; //输入结点数据
		t->next=NULL;  //结点指针域值为空
		//按输入顺序构建链表
		head = insertTail(head, t);
	}
	//输入要删除结点的序号
	cin>>i;
	//在链表中删除序号为i的结点
	head = delAt(head, i);
	//输出链表
	printList(head);
	//删除结点，释放空间
	delList(head);
	return 0;
}
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

函数delAt：

node * delAt(node * h, int i)
{

    if(i==0) return h->next;

    node *p = h, *q = h;
    for(int j = 0; j < i; j++){
        p = q;
        q = q -> next;
    }//q指向要删除的节点，p指向q的上一节点
    
    p->next = q->next;
    return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.6 删除包含特定数据的结点

main：

int main()
{
	int n,i,num;
	node *t;
	node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
	//输入结点数
	cin>>n;
	for(i=0;i<n;i++)
	{
		//为新节点动态分配空间
		t = new node;
		cin>>t->data; //输入结点数据
		t->next=NULL;  //结点指针域值为空
		//按输入顺序构建链表
		head = insertTail(head, t);
	}
	//输入要删除结点包含的数据
	cin>>num;
	//删除包含num的结点
	head = delHas(head, num);
	//输出链表
	printList(head);
	//删除结点，释放空间
	delList(head);

	return 0;
}
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

函数delHas:

node * delHas(node * h, int n)
{
    node *p = h, *q = h;
    if(p->data == n) return h->next;

    while(q){
        if(q->data == n){
            p->next = q->next;
            return h;
        }
        p = q;
        q = q->next;
    }
    return h;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.7 线性表长度

函数listLength：

int listLength(node * h)
{
    node *p = h;
    int n = 0;
    while(p){
        n++;
        p = p->next;
    }
    return n;
}
1
2
3
4
5
6
7
8
9
10

补充：修改链表

使链表逆序

node* revList(node *h){
    node *curNode = h, *nextNode = h->next, *tmp;
    //首节点变成尾结点
    curNode->next = NULL;
    
    while(nextNode){
    	//重新连接
        tmp = nextNode->next;
        nextNode->next = curNode;
		//向后移动
        curNode = nextNode;
        nextNode = tmp;
    }
    return curNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.线性表应用：栈

用前面已经实现的线性表来实现一个整数栈（栈里的数据是整数）。包括三个函数（也是栈的基本功能）：判断栈空的 empty 函数、压栈的 push 函数和弹栈的 pop 函数。

typedef node * intStack; 
1

bool empty(intStack sk)
{
    return (listLength(sk) == 0);
}
// 函数pop：弹栈
// 参数：sk-栈，传引用，弹栈可能会改变sk的值
// 返回值：弹栈的弹出的整数，如果栈空，返回-1
int pop(intStack &sk)
{
    if(empty(sk)) return -1;
    int n = sk->data;
    sk = delAt(sk,0);
    return n;
}
// 函数push：压栈，将整数n压入栈sk中
// 参数：sk-栈，传引用，压栈会改变sk的值，n-要压栈的整数
// 返回值：无，采用链表实现栈，只要还有内存，压栈都会成功
void push(intStack &sk, int n)
{
    node *p = new node;
    p -> data = n;
    sk = insertHead(sk,p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/470595