layout: post
title: "线性表实现"
date: 2020-08-31
author: "王玉松"
header-img: ""
categories: Data Structure
tags:
- 线性表
- 链表

线性表实现

一、基本数据结构

使用结点类型定义如下
数据类型是int型

typedef struct Node
{
  int data;
  Node *next;
}Node;

二、基本的数据结构操作

默认使用带头结点的链表操作

//输出链表中的所有元素
void DisplayList(Node *head);

//头插法插入指定元素
void InsertBefore(Node *head, Node *n, int value);

//尾插法插入指定元素
void InsertAfter(Node *head, Node *n, int value);

//头插法插入指定元素(使用数组存储待插入元素)
void InsertArrayBefore(Node *head, Node *p[], int *ip, int length);

//尾插法插入指定元素(使用数组存储待插入元素)
void InsertArrayAfter(Node *head, Node *p[], int *ip, int length);

//删除指定位置的元素(下标从0开始)
void Delete(Node *head, int position);

//查找指定位置的元素并返回该元素
void Get(Node *head, int position, int *value);

//查找首个指定元素的位置并返回该位置
void IndexOf(Node *head, int value, int *position);

//删除第一个元素并返回该元素
void DeleteFirst(Node *head, int *value);

//删除最后一个元素并返回该元素
void DeleteLast(Node *head, int *value);

三、进一步对数据结构进行操作

//在非递减的有序链表中插入一个值为value的元素
void InsertElem(Node *head, int value);

//合并两个有序链表, 元素都存放在A链表中, B链表置空
void MergeList(Node *A, Node *B, int Alength, int Blength);

//删除一个指定值的元素并返回该元素的位置, 若无则返回-1
void DeleteElem(Node *head, int value, int *position);

//删除链表中所有指定值的元素并返回删除结点的个数
//遍历链表, 若后继元素的值等于指定值, 则进行删除操作, counter+1
void DeleteElemCount(Node *head, int value, int *count);

//删除链表中的重复元素
//双重while循环
//首个元素唯一, 不可能被删除
//每个元素进行判断时, 若后续进行删除操作则上层指针不移动, 直至下层遍历结束
void DeleteRepeatElem(Node *head);

//返回指定值的元素的前驱位置
//函数对于特殊情况的考虑,如0元素或1元素以及不存在指定元素的情况
//仅在后继元素存在且后继元素的值不等于指定值时移动指针
//确保指针停在指定值的元素的前驱位置
void GetPreNode(Node *head, int value, int *position);

//原地逆置链表
//函数采用头插法的性质, 元素顺序正好相反
//将元素用头插法重新插入链表完成原地逆置
void ReverseList(Node *head);

//链表循环右移k位
//函数中设置两个指针, p 指向最后一个结点, q 指向 length-k-1 的位置
//相当于链表被 head, p, q 三个指针拆分为带头结点的两个结点
//将 q 指向的"最后一个结点"头查法插入链表即完成循环右移k位
void RotateRight(Node *head, int length, int k);

四、从中获得的关于编写C代码的知识

1. 函数中申请内存时出现问题,尝试在main函数中申请内存并传入指针

2. 采用函数式编程, 方便对函数进行测试, 排查问题

五、相关代码

1. 链表实现