读书人
栏目▼

c++ 设计一个类 线性表 顺序结构解决

发布时间： 2012-02-26 20:19:44 作者： rapoo

c++ 设计一个类 线性表 顺序结构
设计一个类描述一个线性表，
要求采用顺序结构进行存储。并实现：
（1）设计一个成员函数对线性表进行初始化；
（2）设计一个成员函数插入结点到线性表中；
（3）设计一个成员函数删除线性表中的一个结点；
（4）设计一个成员函数实现线性表按关键字排序（递增）；
（5）设计一个成员函数输出排序后的线性表；
（6）并设计程序演示。


[解决办法]
放到C++ 版里 ,回的人N 多
[解决办法]
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

template <typename T>
class Vector {
public:
Vector();
~Vector();
void insert(T, int);
void add(T);
T remove(int);
void sort();
T get(int) const;
void print() const;
int getSize() const {
return this-> size;
}

int getCapacity() const {
return this-> capacity;
}

private:
int size;
int capacity;
T* data;
const static int CREASE_LENGTH = 32;

T NO_ELEMENT;
};

template <typename T>
Vector <T> ::Vector():size(0), capacity(16) {
data = new T[capacity];
memset(&NO_ELEMENT, -1111111, sizeof(T));
}

template <typename T>
Vector <T> ::~Vector() {
delete[] data;
}

template <typename T>
void Vector <T> ::add(T d) {
if (size + 1 > capacity) {
T* temp = new T[capacity + CREASE_LENGTH];
if (NULL == temp) {
cout < < "Cann 't allocation Memory. " < < endl;
return;
}
capacity += CREASE_LENGTH;
memcpy(temp, data, capacity * sizeof(T));
data = temp;
temp = NULL;
cout < < "reallocation: [capacity " < < capacity < < ", size " < < size < < "] " < < endl;
}
data[size++] = d;
}

template <typename T>
void Vector <T> ::insert(T d, int loc) {
if (loc < 0 || loc > size) {
cout < < "Insert Exception: Bad allocation. " < < endl;
return;
}

if (size + 1 > capacity) {
T* temp = new T[capacity + CREASE_LENGTH];
if (NULL == temp) {
cout < < "Cann 't allocation Memory. " < < endl;
return;
}
capacity += CREASE_LENGTH;
memcpy(temp, data, capacity * sizeof(T));
data = temp;
temp = NULL;
cout < < "Reallocation: [capacity " < < capacity < < ", size " < < size < < "] " < < endl;
}

for (int i = size; i > loc; i--) {
data[i] = data[i - 1];
}
data[loc] = d;
size++;
}

template <typename T>
T Vector <T> ::remove(int loc) {
if (loc < 0 || loc > = size) {
cout < < "Remove Exception: Bad allocation. " < < endl;
return NO_ELEMENT;


}

T temp = data[loc];
for (int i = loc; i < size - 1; i++) {
data[i] = data[i+1];
}
size--;

return temp;
}

template <typename T>
T Vector <T> ::get(int loc) const {
if (loc < 0 || loc > = size) {
cout < < "Remove Exception: Bad allocation. " < < endl;
return NO_ELEMENT;
}

return data[loc];
}

template <typename T>
void Vector <T> ::sort() {
for (int i = 0; i < size - 1; i++) {
int k = i;
for (int j = i + 1; j < size; j++) {
if (data[j] < data[k]) {
k = j;
}
}

if (k != i) {
T temp = data[k];
data[k] = data[i];
data[i] = temp;
}
}
}

template <typename T>
void Vector <T> ::print() const {
cout < < "[ ";
for (int i = 0; i < size - 1; i++) {
cout < < data[i] < < ", ";
}
cout < < data[size - 1] < < "] " < < endl;
}

int main() {
Vector <int> vec;
cout < < "Initial size: " < < vec.getSize() < < endl;
cout < < "Initial capacity: " < < vec.getCapacity() < < endl;

srand(time(0));
for (int i = 0; i < 20; i++) {
vec.add(rand() % 100);
}
vec.print();
cout < < "Current size: " < < vec.getSize() < < endl;
cout < < "Current capacity: " < < vec.getCapacity() < < endl;

cout < < "Random remove: " < < endl;
vec.remove(vec.getSize() - rand() % (vec.getSize() + 1));
vec.print();

cout < < "After sort: " < < endl;
vec.sort();
vec.print();

//cout < < vec.get(1) < < endl;
cout < < "Random insert: " < < endl;
vec.insert(rand() % 500, rand() % vec.getSize());
vec.insert(rand() % 500, rand() % vec.getSize());
vec.print();

cout < < "After sort: " < < endl;
vec.sort();
vec.print();


return 0;
}
[解决办法]
上面的程序存在内存泄漏,重新修改了一下:
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

template <typename T>
class Vector {
public:
Vector();
~Vector();
void insert(T, int); // 插入一个结点在链表中指定的位置
void add(T); // 插入一个结点在链表尾
T remove(int); // 从链表中删除指定位置的元素, 返回删除的元素.
int contains(T) const; // 查找给定的元素,如果找到,返回元素在链表中的位置,没找到,返回-1
void sort(); // 对链表进行升序排序
void reverse(); // 反转链表
T get(int) const; // 取得链表中第i个位置的元素
void print() const; // 打印出链表中的所有元素
int getSize() const { // 取得链表中元素的个数


return this-> size;
}

int getCapacity() const { // 取得链表最大能容纳元素的个数
return this-> capacity;
}

private:
int size; // 链表元素的个数
int capacity; // 链表能容纳元素的最大数
T* data; // 存储链表的元素数组
const static int CREASE_LENGTH = 32; // 每次增加链表容量的个数.

T NO_ELEMENT; // 当给定非法的下标从链表中取元素时,返回此标志,表示取得的值非法.
};

template <typename T>
Vector <T> ::Vector():size(0), capacity(16) {
data = new T[capacity]; // 为链表元素初始化一段空间
memset(&NO_ELEMENT, -1111111, sizeof(T)); // 非法链表值
}

template <typename T>
Vector <T> ::~Vector() {
delete[] data;
}

template <typename T>
void Vector <T> ::add(T d) {
if (size + 1 > capacity) { // 当增加元素时,可以链表容量不够,重新分配空间
T* temp = new T[capacity + CREASE_LENGTH];
if (NULL == temp) { // 如果分配内存不成功,则函数返回
cout < < "Cann 't allocation Memory. " < < endl;
return;
}
capacity += CREASE_LENGTH;
memcpy(temp, data, capacity * sizeof(T));
delete[] data; // 记得释放以前链表的空间,以免造成内存泄漏
data = temp;
temp = NULL;
cout < < "reallocation: [capacity " < < capacity < < ", size " < < size < < "] " < < endl;
}
data[size++] = d;
}

template <typename T>
void Vector <T> ::insert(T d, int loc) {
if (loc < 0 || loc > size) {
cout < < "Insert Exception: Bad allocation. " < < endl;
return;
}

if (size + 1 > capacity) {
T* temp = new T[capacity + CREASE_LENGTH];
if (NULL == temp) {
cout < < "Cann 't allocation Memory. " < < endl;
return;
}
capacity += CREASE_LENGTH;
memcpy(temp, data, capacity * sizeof(T));
delete[] data;
data = temp;
temp = NULL;
cout < < "Reallocation: [capacity " < < capacity < < ", size " < < size < < "] " < < endl;
}

for (int i = size; i > loc; i--) {
data[i] = data[i - 1];
}
data[loc] = d;
size++;
}

template <typename T>
T Vector <T> ::remove(int loc) {
if (loc < 0 || loc > = size) { // 判断给定的位置是否合法,不合法,则函数返回
cout < < "Remove Exception: Bad allocation. " < < endl;
return NO_ELEMENT;
}

T temp = data[loc];
for (int i = loc; i < size - 1; i++) {
data[i] = data[i+1]; // 删除元素后,要把链表中的元素移动.
}
size--;

return temp;
}

template <typename T>
int Vector <T> ::contains(T d) const {
for (int i = 0; i < size; i++) {
if (data[i] == d) {
return i; // 返回给定元素在链表中的下标位置
}
}

return -1;
}

template <typename T>
T Vector <T> ::get(int loc) const {


if (loc < 0 || loc > = size) {
cout < < "Get Exception: Bad allocation. " < < endl;
return NO_ELEMENT;
}

return data[loc];
}

template <typename T>
void Vector <T> ::sort() {
// 选择法对链表进行排序.
for (int i = 0; i < size - 1; i++) {
int k = i;
for (int j = i + 1; j < size; j++) {
if (data[j] < data[k]) {
k = j;
}
}

if (k != i) {
T temp = data[k];
data[k] = data[i];
data[i] = temp;
}
}
}

template <typename T>
void Vector <T> ::reverse() {
// 反转链表,只需要计算一半位置,左右两边的值进行交换.
int middle = size / 2;
T temp;
for (int i = 0; i < middle; i++) {
temp = data[i];
data[i] = data[size - 1 - i];
data[size - 1 - i] = temp;
}
}

template <typename T>
void Vector <T> ::print() const {
cout < < "[ ";
for (int i = 0; i < size - 1; i++) {
cout < < data[i] < < ", ";
}
cout < < data[size - 1] < < "] " < < endl;
}

int main() {
Vector <int> vec;
cout < < "Initial size: " < < vec.getSize() < < endl;
cout < < "Initial capacity: " < < vec.getCapacity() < < endl;

srand(time(0));
for (int i = 0; i < 20; i++) {
vec.add(rand() % 100);
}
vec.print();
cout < < "Current size: " < < vec.getSize() < < endl;
cout < < "Current capacity: " < < vec.getCapacity() < < endl;

cout < < "Random remove: " < < endl;
vec.remove(vec.getSize() - rand() % (vec.getSize() + 1));
vec.print();

cout < < "After sort: " < < endl;
vec.sort();
vec.print();

cout < < vec.get(-1) < < endl;
cout < < "Random insert: " < < endl;
vec.insert(rand() % 500, rand() % vec.getSize());
vec.insert(rand() % 500, rand() % vec.getSize());
vec.print();

cout < < "After sort: " < < endl;
vec.sort();
vec.print();

cout < < "After reverse: " < < endl;
vec.reverse();
vec.print();


return 0;
}

[解决办法]
这个啊，去看 <STL源码剖析> ，基本上，国内的数据结构方面的习题的详尽解答都在上面放着了。
[解决办法]
可以去看《数据结构与算法分析－－C++描述》
[解决办法]
课本上不可能有完整的代码的，
最好看看数据结构和算法实现的参考书
，那里一般会有完整的详尽的代码。

读书人网 >C++

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net