由于一些比赛耽误了太久,最近又拿起了数据结构做起了复习。
写了一个类
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
using namespace std;
template <typename T>
class Arr_Link {
private:
struct Node
{
T* data;
int Length;
};
Node arr_link;
public:
//初始化顺序表
Arr_Link(T* arr, int len) {
int i = 0;
arr_link.Length = 0;
arr_link.data = (T*)malloc(sizeof(T) * (len+1)*len);
while (arr[i] != '\0') {
arr_link.data[i] = arr[i];
i++;
arr_link.Length++;
}
arr_link.data[i] = '\0';
}
//求表长
int length() {
return arr_link.Length;
}
//取表中的第i个元素
T At(int position) {
if (position > arr_link.Length) {
return NULL;
}
else if (position < 0) {
return NULL;
}
else
{
return arr_link.data[position];
}
}
//按值查找,在表中查找第一个值为x的元素,返回位置
int contains(T element) {
int i = 0;
while (i < arr_link.Length) {
if (arr_link.data[i] == element) {
return i;
}
else {
i++;
}
}
}
//插入,在表L的第i个位置插入元素n
bool insert(int position, T element) {
for (int i = arr_link.Length + 1; i >= position; i--) {
arr_link.data[i] = arr_link.data[i - 1];
}
arr_link.data[position] = element;
if (arr_link.data[position] == element) {
return true;
}
else {
return false;
}
}
//删除,删除表的第i个元素
bool Remove(int position) {
for (int i = position; i < arr_link.length; i++) {
arr_link->data[i] = arr_link->data[i + 1];
}
arr_link->data[length] = '\0';
length = length - 1;
}
};
template <typename T>
class Single_Link {
public:
static struct Link{
T data;
Link* next;
};
private:
Link* p;
Link* head;
Link* rear;
public:
Single_Link() {
head = NULL;
p = NULL;
rear = NULL;
}
//头插法建表
void* head_create(T* arr) {
for (int i = 0; arr[i] != '\0'; i++) {
p = (Link*)malloc(sizeof(Link));
p->data = arr[i];
p->next = head;
head = p;
}
return head;
}
//尾插法建表
void* tail_create(T* arr) {
for (int i = 0; arr[i] != '\0'; i++) {
p = (Link*)malloc(sizeof(Link));
p->data = arr[i];
if (head == NULL) head = p;
else rear->next = p;
rear = p;
}
if (rear != NULL) rear->next = NULL;
return head;
}
//查找运算,按照节点序号查找,并返回子列表
Single_Link<T>::Link* find_pos(int pos) {
Link* p ;
int j = 1;
p = head;
while (p != NULL && j < pos) {
p = p->next;
j++;
}
if (j == pos) {
return p;
}
else {
return NULL;
}
}
//查找运算,按照节点值查找,并返回节点位置。
int find_con(T content) {
Link* p;
int position = 0;
p = head;
while (p != NULL) {
if (p->data == content) {
return position;
}
else {
p = p->next;
}
position++;
}
return -1;
}
};
template <typename T>
class double_Link {
public:
struct Link {
T data;
Link* pre;
Link* next;
};
private:
Link* p;
Link* head;
Link* test;
int Count;
public:
double_Link(T* Arr) {
Count = 0;
for (int i = 0; Arr[i] != '\0'; i++) {
Count++;
p = (Link*)malloc(sizeof(Link));
p->data = Arr[i];
p->pre = head;
head = p;
}
while (head->pre != NULL) {
p = head;
head = head->pre;
head->next = p;
}
}
Link* insert(T data,int position) {
if (position > Count || position < 0) {
return NULL;
}
else if(position == 0){
p = head;
test = (Link*)malloc(sizeof(Link));
test->data = data;
test->pre = NULL;
test->next = p;
p->pre = test;
head = test;
return head;
}
p = head;
for (int i = 0; i < position; i++)
{
p = p->next;
}
test = (Link*)malloc(sizeof(Link));
test->data = data;
test->pre = p;
test->next = p->next;
p->next = test;
if(position == Count+1){
test->next->pre = test;
}
return head;
}
int count() {
return Count;
}
Link* remove(int position) {
if (position > count()) {
return NULL;
}
p = head;
for (int pos = 0; pos < position; pos++) {
p = p->next;
}
if (position < count()) {
p->pre->next = p->next;
p->next->pre = p->pre;
}else if(position == count()){
p->pre->next = NULL;
}
delete(p);
return head;
}
int locate_pos(T data) {
p = head;
int pos = 0;
while (p != NULL) {
pos++;
if (p->data == data) {
return pos;
}
else {
p = p->next;
}
}
return NULL;
}
Link* locate_data(int position) {
if (position < 0 || position>count()) {
return NULL;
}
p = head;
for (int pos = 0; pos < position - 1; pos++) {
p = p->next;
}
return p;
}
};
int main(int argc, char* argv[]) {
//自主调用
}