您當(dāng)前位置：首頁(yè) > php開源 > 綜合技術(shù) > 線性表-順序表、鏈表類模板的實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 第2周）

線性表-順序表、鏈表類模板的實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 第2周）

來(lái)源：程序員人生發(fā)布時(shí)間：2016-08-03 09:05:39 閱讀次數(shù)：2525次

學(xué)習(xí)完課程后，自己用C++實(shí)現(xiàn)了簡(jiǎn)單的順序表和鏈表，并用約瑟夫問題做了測(cè)試，不保證完全正確。
其中有1點(diǎn)需要注意1下：C++中類模板聲明頭文件和實(shí)現(xiàn)頭文件不可以分離到.h和.cpp中，否則沒法正常編譯，詳見：https://www.zhihu.com/question/20630104

源碼
1.順序表
//seqlist.h

#pragma once
#include <iostream>
using namespace std;

template <class T> class seqlist
{
private:
    T* aList;  //存儲(chǔ)順序表的實(shí)例
    int maxSize;  //順序表實(shí)例的最大長(zhǎng)度
    int curLen;  //順序表確當(dāng)前長(zhǎng)度
    int position;//當(dāng)前處理位置
public:
    seqlist(const int size);
    ~seqlist();
    void clear();       //置空線性表
    int length();
    bool isEmpty();     //線性表為空時(shí)，返回true
    bool append(const T value);     //在表尾添加1個(gè)元素value,表的長(zhǎng)度增1
    bool insert(const int p, const T value);    //在位置p上插入1個(gè)元素value，表的長(zhǎng)度增1
    bool delet(const int p);        //刪除位置p上的元素，表的長(zhǎng)度減1
    bool getPos(int& p, const T value);     //查找值為value的元素并返回其位置
    bool getValue(const int p, T& value);   //把位置p元素值返回到變量value
    bool setValue(const int p, const T value);      //用value修改位置p的元素值
};

template <class T> seqlist<T>::seqlist(const int size)
{
    maxSize=size;
    aList = new T[maxSize];
    curLen=position=0;
}


template <class T> seqlist<T>::~seqlist()
{
    delete []aList;
}

template <class T> void seqlist<T>::clear()
{
    delete [] aList;
    curLen=position=0;
    aList=new T[maxSize];
}

template <class T> int seqlist<T>::length()
{
    return curLen;
}

template <class T> bool seqlist<T>::isEmpty()
{
    if (curLen==0) {
        return true;
    }
    else {
        return false;
    }
}

template <class T> bool seqlist<T>::append(const T value)
{
    if (curLen>=maxSize)  //檢查順序表是不是溢出
    {
        cout << "The list is overflow" << endl;
        return false;
    }
    aList[curLen]=value;
    curLen++;
    return true;
}

//設(shè)元素類型為T，aList是存儲(chǔ)順序表的數(shù)組，maxSize是其最大長(zhǎng)度；
//p為新元素value的插入位置，插入成功則返回true，否則返回false
template <class T> bool seqlist<T>::insert(const int p, const T value)
{
    if (curLen>=maxSize)  //檢查順序表是不是溢出
    {
        cout << "The list is overflow" << endl;
        return false;
    }
    if (p<0 || p>curLen)  //檢查插入位置是不是合法
    {
        cout << "Insertion point is illegal" << endl;
        return false;
    }
    for(int i=curLen; i>p; i--)
        aList[i]=aList[i-1];   //從表尾curLen⑴起往右移動(dòng)直到p
    aList[p]=value;  //位置p處插入新元素
    curLen++;    //表的實(shí)際長(zhǎng)度增1
    return true;
}

//設(shè)元素的類型為T；aList是存儲(chǔ)順序表的數(shù)組；p為行將刪除元素的位置
//刪除成功則返回true, 否則返回false
template <class T> bool seqlist<T>::delet(const int p)  
{
    if (curLen<=0)  //檢查順序表是不是為空
    {
        cout << "No element to delete" << endl;
        return false;
    }
    if (p<0 || p>curLen-1)  //檢查刪除位置是不是合法
    {
        cout << "deletion is illegal" << endl;
        return false;
    }
    for(int i=p; i<curLen; i++)
        aList[i]=aList[i+1];
    curLen--;
    return true;
}

template <class T> bool seqlist<T>::getPos(int& p, const T value)
{
    for(int i=0; i<curLen; i++) 
        if (aList[i]==value) {
            p=i;
            return true;
        }           
        cout << "can not find element: " << value << endl;
        return false;
}

template <class T> bool seqlist<T>::getValue(const int p, T& value)
{
    if (curLen<=0)  //檢查順序表是不是為空
    {
        cout << "No element" << endl;
        return false;
    }
    if (p<0 || p>curLen-1)  //檢查刪除位置是不是合法
    {
        cout << "getvalue is illegal" << endl;
        return false;
    }
    value = aList[p];
    return true;
}

template <class T> bool seqlist<T>::setValue(const int p, const T value)
{
    if (curLen<=0)  //檢查順序表是不是為空
    {
        cout << "No element" << endl;
        return false;
    }
    if (p<0 || p>curLen-1)  //檢查刪除位置是不是合法
    {
        cout << "setvalue is illegal" << endl;
        return false;
    }
    aList[p] = value;
    return true;
}

//source.cpp

#include <iostream>
#include "seqlist.h"
#include <stdio.h>
using namespace std;


void josephus_seq(seqlist<int>& palist, int s, int m)
{
    int del = s;  
    int w=0;
    for(int i=palist.length(); i>0; i--) {
        del=(del+m-1)%i;   //要?jiǎng)h除的元素的索引
        if (del==0) del = i;
        palist.getValue(del-1, w);   //求出第del個(gè)元素的值
        printf("Out element %d \n", w);   //元素出列
        palist.delet(del-1);   //刪除出列的元素
    }
}


int main() {
    seqlist<int> jos_alist(100);
    int n, s, m;
    printf("\n please input the values(<100) of n = ");  //參與游戲的人數(shù)
    scanf("%d", &n);
    printf("please input the values of s = ");   //開始的人
    scanf("%d", &s);
    printf("please input the values of m = ");   ///單詞計(jì)數(shù)
    scanf("%d", &m);
    for (int i=0; i<n; i++) {
        jos_alist.append(i+1);
    }
    josephus_seq(jos_alist, s, m);
    return 0;
}

2.鏈表
//lnklist.h

#pragma once

template <class T> 
class Link
{
public:
    T data;  //用于保存結(jié)點(diǎn)元素的內(nèi)容
    Link<T> *next;  //指向后繼結(jié)點(diǎn)的指針
    Link(const T info, Link<T>* nextValue=NULL) {
        data=info;
        next= nextValue;
    }
    Link():next(NULL) {}
};


template <class T> 
class lnkList:public Link<T> {
private:
    Link<T> *head, *tail;      //單鏈表的頭尾指針
    Link<T>* setPos(const int i);    //返回第i個(gè)元素的指針值
public:
    lnkList();   //構(gòu)造函數(shù)
    ~lnkList();     //析構(gòu)函數(shù)
    bool isEmpty();     //判斷鏈表是不是為空
    void clear();       //置空線性表
    int length();    //返回此鏈表當(dāng)前實(shí)際長(zhǎng)度
    bool append(const T value);     //在表尾添加1個(gè)元素value,表的長(zhǎng)度增1
    bool insert(const int i, const T value);    //在位置i上插入1個(gè)元素value，表的長(zhǎng)度增1
    bool delet(const int i);        //刪除位置i上的元素，表的長(zhǎng)度減1
    bool getValue(const int i, T& value);   //把位置i元素值返回到變量value
    bool getPos(int& i, const T value);     //查找值為value的元素并返回其位置
};

template <class T>
lnkList<T>::lnkList() {
    head=NULL;
    tail=NULL;
}

template <class T>
lnkList<T>::~lnkList() {
    if (head==NULL)
    {
        return;
    }
    Link<T>* cur=head;
    while(cur != NULL) {
        Link<T>* del=cur;
        cur = cur->next;
        delete del;
    }
    delete cur;
    head=NULL;
    tail=NULL;
}

template <class T>
Link<T>* lnkList<T>::setPos(const int i) {
    int count=0;
    Link<T>* p=head;  //循鏈定位，若i為0則定位到第1個(gè)結(jié)點(diǎn)
    while(p != NULL && count<i) {
        p=p->next;
        count++;
    }
    return p;   //指向結(jié)點(diǎn)i
}

template <class T>
bool lnkList<T>::insert(const int i, const T value) {
    Link<T> *p, *q;
    if ((p=setPos(i-1))==NULL)   //p是位置i結(jié)點(diǎn)的先驅(qū)
    {
        cout <<  "Insertion point is illegal" << endl;
        return false;
    }
    q = new Link<T>(value, p->next);
    p->next = q;
    if (p==tail)  //插入點(diǎn)在鏈尾，插入結(jié)點(diǎn)成為新的鏈尾
    {
        tail = q;
    }
    return true;
}

template <class T>
bool lnkList<T>::delet(const int i) {
    Link<T> *p, *q;  
    if (i==0){  //刪除頭結(jié)點(diǎn)
        q=head;
        head=head->next;
        delete q;
        return true;
    }
    p=setPos(i-1);  
    if (p==NULL || p==tail) {  //刪除的結(jié)點(diǎn)不存在
        cout << "deletion is illegal" << endl;
        return false;
    }
    q=p->next;   //q是真正待刪除結(jié)點(diǎn)
    if (q==tail)  //待刪結(jié)點(diǎn)為尾結(jié)點(diǎn)，則修改尾指針
    {
        tail = p;
        p->next=NULL;
    }
    else
        p->next=q->next;   //刪除結(jié)點(diǎn)q并修改鏈指針
    delete q;
    return true;
}

template <class T>
bool lnkList<T>::isEmpty() {
    if (head==NULL) {
        return true;
    }
    else {
        return false;
    }
}

template <class T>
void lnkList<T>::clear() {
    if (head==NULL)
    {
        return;
    }
    Link<T>* cur=head;
    while(cur != NULL) {
        Link<T>* del=cur;
        cur = cur->next;
        delete del;
    }
    delete cur;
    head=NULL;
    tail=NULL;
}

template <class T>
int lnkList<T>::length() {
    int count=0;
    Link<T>* cur=head;
    while(cur) {
        count++;
        cur = cur->next;
    }
    return count;
}

template <class T>
bool lnkList<T>::append(const T value) {
    Link<T>* newLink = new Link<T>(value);
    if (head==NULL) {
        head=newLink;
        tail=head;
    }
    else {
        tail->next = newLink;
        tail=newLink;
    }
    return true;
}

template <class T>
bool lnkList<T>::getPos(int& i, const T value) {
    Link<T>* cur=head;
    int count=0;
    while(cur) {
        if (cur->data==value)
        {
            i=count;
            return true;
        }
        cur = cur->next;
        count++;
    }
    cout << "can not find element: " << value << endl;
    return false;
}

template <class T>
bool lnkList<T>::getValue(const int i, T& value) {
    int count=0;
    Link<T>* cur=head;  //循鏈定位，若i為0則定位到第1個(gè)結(jié)點(diǎn)
    while(cur != NULL && count<i) {
        cur=cur->next;
        count++;
    }
    if (cur==NULL) {
        return false;
    }
    else {
        value = cur->data;
        return true;
    }
}

//source.cpp

#include <iostream>
#include "lnklist.h"
#include <stdio.h>
using namespace std;

void josephus_seq(lnkList<int>& palist, int s, int m)
{
    int del = s;  
    int w=0;
    for(int i=palist.length(); i>0; i--) {
        del=(del+m-1)%i;   //要?jiǎng)h除的元素的索引
        if (del==0) del = i;
        palist.getValue(del-1, w);   //求出第del個(gè)元素的值
        printf("Out element %d \n", w);   //元素出列
        palist.delet(del-1);   //刪除出列的元素
    }
}

int main() {
    lnkList<int> jos_alist;
    int n, s, m;
    printf("\n please input the values(<100) of n = ");  //參與游戲的人數(shù)
    scanf("%d", &n);
    printf("please input the values of s = ");   //開始的人
    scanf("%d", &s);
    printf("please input the values of m = ");   ///單詞計(jì)數(shù)
    scanf("%d", &m);
    for (int i=0; i<n; i++) {
        jos_alist.append(i+1);
    }
    josephus_seq(jos_alist, s, m);
    return 0;
}

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生

------分隔線----------------------------

上一篇 HDU 4912 LCA+策略

下一篇 Android官方開發(fā)文檔Training系列課程中文版：多樣屏幕之支持不同的屏幕尺寸

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關(guān)注

欄目熱點(diǎn)

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

線性表-順序表、鏈表類模板的實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 第2周）

線性表-順序表、鏈表類模板的實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 第2周）