数据结构-表（顺序表、链表）定义和基本 *** 作（基于HHU课程作业）_C

数据结构-表（顺序表、链表）定义和基本 *** 作（基于HHU课程作业）

前言
顺序表
- 顺序表的定义
- 基本 *** 作
- - 建立SolutionList.h的头文件，并在SolutionList.cpp中对函数进行实现
  - 建立顺序表
  - 插入算法insertPost_seq(palist,p,x), 在palist所指的顺序表中，下标为p的元素后插入值为x的元素，反馈是否成功（67-1）
  - 删除算法deleV_seq(palist,x)，在palist所指的顺序表中，删除一个值为x的元素，反馈是否成功（67-2）
  - 将线性表翻转，仍使用原有的空间（67-3）
  - 删除线性表中重复的数据，仍使用原有空间（67-12）
链表
- 链表定义
- 基本 *** 作
- - 建立SolutionNode.h的头文件，并在SolutionNode.cpp中对函数进行实现
  - 删除单链表中重复元素
  - 链表 *** 作完整代码

前言

课程学习用书为《算法与数据结构-C语言描述（第三版）》
此次使用语言为C++，为了使程序清晰，建立了多个.h和.cpp的类进行实现
完整代码上传至Github可自行下载：

https://github.com/BilboJunzhou/List-Algorithms-and-data-structures

其中包括顺序表和链表的定义和一些基本 *** 作，使用时引用头文件即可

顺序表顺序表的定义

这里我建立了SeqLest的头文件对顺序表进行定义，方便后续在不同的程序中继承使用：
SeqLest.h
建立了struct结构体，包括三个变量
MaxNum：可以重新定义顺序表的最大长度
n：顺序表的大小（及当前存储数据量）
element：成员变量，方便起见，我定义为Int类型，可根据需求修改
在9-11行，通过malloc函数对element进行空间申请，大小为：MaxNum*sizeof(Typedata)，MaxNum默认大小为100，也可提供期望大小进行修改

#ifndef SQLEST_H
#define SQLEST_H
#define MAXNUM 100
struct SeqList
{
	int MaxNum;
	int n;
	int* element;
	SeqList() :MaxNum(MAXNUM), n(0), element((int*)malloc(sizeof(int)* MaxNum)) {}
	SeqList(int m) :MaxNum(MAXNUM), n(0), element((int*)malloc(sizeof(int)* MaxNum)) {}
	SeqList(int m, int MAX) :MaxNum(MAX), n(0), element((int*)malloc(sizeof(int)* MAX)) {}

};
#endif

基本 *** 作建立SolutionList.h的头文件，并在SolutionList.cpp中对函数进行实现

SolutionList.h:

#pragma once
#ifndef SOLUTIONLIST_H
#define SOLUTIONLIST_H
#include"SeqList.h"
class SolutionList {
public:
	int insertPre_seq(SeqList &palist, int p, int x);// 作业第1题（顺序表）
	bool deleteV_seq(SeqList& palist, int x);// 作业第2题（顺序表）
	void UPDown(SeqList& palist);// 作业第3题，传地址形式（顺序表）
	void DeleteRepeat(SeqList& palist);//作业第12题，传地址形式（顺序表 ）
	int locate_seq(SeqList palist, int x);// 在顺序表中求某一元素的下标
	void TurnBack(int& a, int& b);// 调换两个数据的值
	void GetSeq(SeqList palist); // 输出顺序表中的所有值
	bool insertBack(SeqList& palist, int x);// 在palist末尾插入元素
	SeqList SetSeqList(); // 建立顺序表
};
#endif

这里我对各别函数进行举例，完整代码在前言的GitHub链接中自行下载

建立顺序表插入算法insertPost_seq(palist,p,x), 在palist所指的顺序表中，下标为p的元素后插入值为x的元素，反馈是否成功（67-1）

int SolutionList::insertPre_seq(SeqList &palist, int p, int x)
{
    if (palist.n>=palist.MaxNum)
    {
        cout << "Overflow!" << endl;
        return 0;
    }
    if (p<0||p>palist.n)
    {
        cout << "Not exost!" << endl;
        return 0;
    }
    int q;
    for (q = palist.n - 1; q >= p; q--)
        palist.element[q + 1] = palist.element[q];
    palist.element[q] = x;
    palist.n = palist.n + 1;
    return 1;
}

删除算法deleV_seq(palist,x)，在palist所指的顺序表中，删除一个值为x的元素，反馈是否成功（67-2）

bool SolutionList::deleteV_seq(SeqList& palist, int x)
{
    for (int i = 0; i < palist.n; i++) {
        if (palist.element[i] == x)
        {
            for (int j = i; j < palist.n - 1; j++)palist.element[j] = palist.element[j + 1];
            palist.n--;
            return true;
        }
    }
    return false;
}

将线性表翻转，仍使用原有的空间（67-3）

void SolutionList::UPDown(SeqList& palist)
{
    for (int i = 0; i < palist.n/2; i++)
    {
        TurnBack(palist.element[i], palist.element[palist.n - i]);
    }
}

void SolutionList::TurnBack(int& a, int& b)
{
    int x = a; a = b; b = x;
}

删除线性表中重复的数据，仍使用原有空间（67-12）

建立哈希表，先判断当前元素是否在map中存在，如果不存在存储入map然后查询下一个，否则对当前元素进行删除 *** 作

void SolutionList::DeleteRepeat(SeqList& palist)
{
    unordered_map<int, int> map;
    int i = 0;
    while (i < palist.n)
    {
        if (map.find(palist.element[i]) != map.end())
        {
            for (int j = i; j < palist.n-1; j++)
            {
                palist.element[j] = palist.element[j + 1];
            }
            palist.n--;
        }
        else {
            map[palist.element[i]] = 1;
            i++;
        }
    }
}

链表链表定义

这里我建立了ListNode的头文件对顺序表进行定义，方便后续在不同的程序中继承使用：
ListNode.h

#pragma once
#ifndef LISTNODE_H
#define LISRNODE_H
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
#endif

基本 *** 作建立SolutionNode.h的头文件，并在SolutionNode.cpp中对函数进行实现

#ifndef SOLUTION_H
#define SOLUTION_H
#include "ListNode.h"
class SolutionNode {
public:
	ListNode* SetList();// 建立单向链表
	ListNode* SetCircularList();// 建立循环链表
	void getList(ListNode* head);// 输出链表数据
	bool insertPost_seq(ListNode* head, int p, int x); //作业第1题（链表）
	bool deleteV_seq(ListNode* head, int x);//作业第2题（链表）
	ListNode* UpSitDown(ListNode* head);// 作业第3题（链表）
	bool set_val_at_p(ListNode* head, ListNode* p, int x);// 作业第6题（链表）
	bool CirList_Delete(ListNode* list, int x, int k);//作业第9题（链表）
	void RemoveRepeat(ListNode* head);// 作业第12题（链表）
	void Delete_Last(ListNode* list);//作业第14题（链表）
};
#endif

删除单链表中重复元素

建立哈希表，先判断当前元素是否在map中存在，如果不存在存储入map然后查询下一个，否则对当前元素进行删除 *** 作

void SolutionNode::RemoveRepeat(ListNode* head)
{
	unordered_map<int, int> map;
	if (!head)
		return;
	while (head->next)
	{
		if (map.find(head->next->val)!=map.end())
		{
			head->next = head->next->next;
		}
		else
		{
			map[head->val] = 1;
			head = head->next;
		}
	}
}

链表 *** 作完整代码

具体 *** 作比较简单，代码内有注释，可自行查看理解

#include <iostream>
#include <unordered_map>
#include "SolutionNode.h"
#include "ListNode.h"

using namespace std;

// 链表倒置,迭代法
ListNode* SolutionNode::UpSitDown(ListNode* head)
{
	ListNode* prev = nullptr;
	ListNode* curr = head;
	while (curr) {
		ListNode* next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}


// 建立链表，返回头结点
ListNode* SolutionNode::SetList()
{
	int NOWINT;
	cout << "Start building a linked list,when pressing the Ctrl + z to end setup." << endl;
	ListNode* head = new ListNode();
	ListNode* curr = head;
	while (cin >> NOWINT)
	{
		ListNode* NewList = new ListNode(NOWINT);
		curr->next = NewList;
		curr = curr->next;
	}
	return head->next;
}

// 建立循环列表	
ListNode* SolutionNode::SetCircularList()
{
	int NOWINT;
	cout << "Start building a circular list,when pressing the Ctrl + z to end setup." << endl;
	ListNode* head = new ListNode();
	ListNode* curr = head;
	while (cin >> NOWINT)
	{
		ListNode* NewList = new ListNode(NOWINT);
		curr->next = NewList;
		curr = curr->next;
	}
	curr->next = head->next;
	return head->next;
}

void SolutionNode::getList(ListNode* head)
{
	while (head)
	{
		cout << head->val << ' ';
		head = head->next;
	}
	printf("\n");
}

// 删除循环链表的前驱节点
void SolutionNode::Delete_Last(ListNode* list)
{
	ListNode* curr = list;
	while (list != curr->next->next)
	{
		curr = curr->next;
	}
	curr->next = list;
}

// 删除循环链表中值为x的节点
bool SolutionNode::deleteV_seq(ListNode* head, int x)
{
	ListNode* curr = head;
	while (curr)
	{
		if (curr->next->val == x)
		{
			curr->next = curr->next->next;
			return true;
		}
	}
	return false;
}

// 在下标为p的链表后插入值为x的节点
bool SolutionNode::insertPost_seq(ListNode* head, int p, int x)
{
	ListNode* InitVal = new ListNode(x);
	if (!head)return false;
	for (int i = 0; i < p; i++)
	{
		head = head->next;
		if (!head)return false;
	}
	InitVal->next = head->next;
	head->next = InitVal;
	return true;
}

// 从第x个节点以后删除k个节点
bool SolutionNode::CirList_Delete(ListNode* list, int x, int k)
{
	for (int i = 0; i < x - 1; i++) {
		list = list->next;
		if (!list) {
			cout << "Failed to delete because the length is insufficient";
			return false;
		}
	}
	ListNode* curr = list;
	for (int i = 0; i < k; i++)
	{
		curr = curr->next;
		if (!curr) {
			cout << "Failed to delete because the length is insufficient";
			return false;
		}
	}
	list->next = curr;
	return true;
}

// 在指定头结点中的P空间位置插入X节点，并返回是否成功
bool SolutionNode::set_val_at_p(ListNode* head, ListNode* p, int x)
{
	ListNode* setX = new ListNode(x);
	while (head)
	{
		if (head->next == p)
		{
			head->next = setX;
			setX->next = p;
			return true;
		}
		head = head->next;
	}
	return false;
}

// 建立哈希表，存储之前没有出现的数据，如果出现则删除
void SolutionNode::RemoveRepeat(ListNode* head)
{
	unordered_map<int, int> map;
	if (!head)
		return;
	while (head->next)
	{
		if (map.find(head->next->val)!=map.end())
		{
			head->next = head->next->next;
		}
		else
		{
			map[head->val] = 1;
			head = head->next;
		}
	}
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/564178.html

数据结构-表（顺序表、链表）定义和基本 *** 作（基于HHU课程作业）

发表评论

评论列表（0条）