首页 > 代码库 > c++实现数据结构1.顺序表

c++实现数据结构1.顺序表

头文件seqlist.h

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

#include<iostream>
using namespace std;

template <class Type>
class seqlist
{
public:
	seqlist()
	{
		capacity = DefaultSize;
		base = new Type[capacity];
		size = 0;
	}
	seqlist(int sz)
	{
		capacity = sz > DefaultSize ?

sz : DefaultSize; base = new Type[capacity]; size = 0; } ~seqlist() { delete []base; } public: bool Full()const { if (size > capacity) return true; return false; } bool Empty()const { if (size == 0) return true; return false; } bool push_back(Type const x) { if (Full()) return false; else { base[size] = x; size++; } return true; } bool push_front(Type const x) { if (Full()) return flse; else { for (int i = size; i > 0; ++i) { base[i] = base[i - 1]; } base[0] = x; } return true; } void show_list() { for (int i = 0; i < size; ++i) { cout << base[i] << "->"; } cout << "end" << endl; } void pop_back() { size--; } void pop_front() { for (int i = 0; i < size-1; ++i) { base[i] = base[i + 1]; } size--; } bool insert_val(Type x) { if (Empty() || size == capacity) return false; sort(); int i = 0; while (x > base[i] && i < size) { i++; } insert_pos(i,x); return true; } bool insert_pos(int pos,Type x) { if (pos <0 || pos>size) return false; else { for (int i = size; i > pos; --i) { base[i] = base[i - 1]; } base[pos] = x; } size++; } int find(Type key) { for (int i = 0; i < size; ++i) { if (base[i] == key) return i; } cout << "no exit" << endl; return -1; } bool delete_pos(int pos) { if (pos<0 || pos > size) return false; else { for (int i = pos; i < size - 1; ++i) { base[i] = base[i + 1]; } size--; } } bool delete_val(Type key) { if (Empty()) return false; else { int pos = find(key); delete_pos(pos); } return true; } void sort() { Type tmp; for (int i = 1; i<size; ++i) { tmp = base[i]; int j; for ( j = i; tmp < base[j - 1]; --j) { base[j] = base[j - 1]; } base[j] = tmp; } } void resever() { if (size == 0 || size == 1) return; for (int i = 0; i < (size / 2); ++i) { Type tmp = base[i]; base[i] = base[size - i-1]; base[size - i-1] = tmp; } } int length() { return size; } void clear() { size = 0; } void destory() { delete[]base; } private: enum { DefaultSize = 8 }; Type *base; int capacity; int size; }; #endif

主程序

#include"seqlist.h"

void main()
{
	seqlist<int> mylist;
	int select = 1;
	int item;
	int pos;
	while (select)
	{
		cout <<"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"<< endl;
		cout <<"&                                      &"<< endl;
		cout <<"& [1]  push_back   [2]  push_fornt     &"<< endl;
		cout <<"& [3]  show_list   [4]  pop_back       &"<< endl;
		cout <<"& [5]  pop_front   [6]  insert_val     &"<< endl;
		cout <<"& [7]  insert_pos  [8]  find           &"<< endl;
		cout <<"& [9]  delete_pos  [10] delete_val     &"<< endl;
		cout <<"& [11] sort        [12] resever        &"<< endl;
		cout <<"& [13] length      [14] clear          &"<< endl;
		cout <<"& [15] destroy     [0]  quit_system    &"<< endl;
		cout <<"&                                      &"<< endl;
		cout <<"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"<< endl;
		cout << "please choose->" ;
		cin >> select;
		switch (select)
		{
			case 1:
				cout << "please cin data end with -1:" << endl;
				while (cin >> item, item != -1)
				{
					mylist.push_back(item);
				}
				break;
			case 3:
				mylist.show_list();
				break;
			case 4:
				mylist.pop_back();
				break;
			case 5:
				mylist.pop_front();
				break;
			case 6:
				cout << "please cin the data you want insert:";
				cin >> item;
				mylist.insert_val(item);
				break;
			case 7:
				cout << "please cin pos and data:";
				cin >> pos >> item;
				mylist.insert_pos(pos, item);
				break;
			case 8:
				cout << "please cin the data you want find ,it will back its pos: ";
				cin >> item;
				cout<<mylist.find(item)<<endl;
				break;
			case 9:
				cout << "please cin the pos you want delete: ";
				cin >> pos;
				mylist.delete_pos(pos);
				break;
			case 10:
				cout << "please cin the data you want to dalete: ";
				cin >> item;
				mylist.delete_val(item);
				break;
			case 11:
				cout << "sort !"<<endl;
				mylist.sort();
				break;
			case 12:
				mylist.resever();
				break;
			case 13:
				cout<<mylist.length()<<endl;
				break;
			case 14:
				mylist.clear();
				break;
			case 15:
				mylist.destory();
					break;
		default:
			break;
		}
	}
}

技术分享技术分享

c++实现数据结构1.顺序表