數據結構學習記錄連載4（上一篇中提高要求實現）
1.給出提高要求2的函數實現
/*
* 函數名稱: Concatenate
* 輸 入: source,target
* source: 需要連接的對象
* target: 被連接的對象
* 輸 出:
* 功能描述: 將對象source連接到單鏈表target的尾部
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
void Concatenate(LinkList<T>& target, LinkList<T>& source)
{
ListNode<T> *q = source.head;
while (q->next != NULL)
{
target.Insert(q->next->data, target.size);
q = q->next;
}
}
注意事項：實現時不要直接把兩個鏈表連接起來就好了，這樣造成同一塊內存會釋放兩遍，造成運行完時報錯，其實就是析構函數中出錯。
而是需要用要到深拷貝的原理實現，就是取出source的數據插入到target中。上一篇中以給出測試程序。
2.提高要求2的實現：說明：本來只是修改上一篇中某些函數的實現就可以了，但是作為程序的完整性我在這里也全部給出
（1）ListNode.h結點類：
/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：ListNode.h
* 摘 要： 節點類的定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
#include<iostream.h>
#include<stdio.h>
template<class T> class LinkList; //前視定義，否則，無法定義友元
template<class T> class ListNode
{
friend class LinkList<T>; //定義友元
private:
ListNode<T> *next; //指向下一個結點的指針
ListNode<T> *prev; //指向上一個結點的指針
public:
T data;
ListNode(ListNode<T> *ptrNext=NULL, ListNode<T> *ptrPrev=NULL); //構造函數，用于構造頭結點
ListNode(const T& item, ListNode<T> *ptrNext, ListNode<T> *ptrPrev);//構造函數，非頭結點
~ListNode() {}; //析構函數
friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
};
template<class T>
ListNode<T>::ListNode(ListNode<T> *ptrNext, ListNode<T> *ptrPrev)
:next(ptrNext),prev(ptrPrev)
{
}
template<class T>
ListNode<T>::ListNode(const T &item, ListNode<T> *ptrNext, ListNode<T> *ptrPrev)
{
data = item;
next = ptrNext;
prev = ptrPrev;
}
（2）LinkList.h鏈表類定義與實現（雙向循環鏈表）：
/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：LinkList.h
* 摘 要： 雙向循環鏈表類的定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
#include "ListNode.h"
template <class T>
class LinkList
{
private:
ListNode<T> *head; //指向頭結點的指針
int size; //單鏈表的元素個數
ListNode<T> *currPtr; //當前結點
public:
LinkList(void); //構造函數
~LinkList(); //析構函數
//線性表操作要求的成員函數
int GetListSize(void) const; //返回鏈表的元素個數
int ListIsEmpty(void) const; //判斷單鏈表是否為空
ListNode<T> *Index(int pos); //定位
void Insert(const T& item, int pos); //插入
T Delete(int pos); //刪除
T GetData(int pos); //取元素
void ClearList(void); //清空鏈表
//遍歷單鏈表的成員函數
ListNode<T> *Reset(int pos=0); //把第pos個結點設置為當前結點currPtr
ListNode<T> *Next(void); //currPtr指向下一個結點
int EndOfList(void) const; //currPtr是否指在鏈表尾
friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
};
/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：LinkList.cpp
* 摘 要： 雙向循環鏈表的各個功能函數的現實
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
template <class T>
LinkList<T>::LinkList(void)
{
size = 0;
head = new ListNode<T>();
head->next = head;
head->prev = head;
}
template <class T>
LinkList<T>::~LinkList()
{
ClearList(); //釋放所有非頭結點的結點
delete head; //釋放頭結點
}
/*
* 函數名稱: GetListSize
* 輸 入:
* 輸 出:
* 功能描述: 返回順序表的元素個數size
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
int LinkList<T>::GetListSize(void) const
{
return size;
}
/*
* 函數名稱: ListIsEmpty
* 輸 入:
* 輸 出:
* 功能描述: 判斷是否為空,空返回1;非返回0
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
int LinkList<T>::ListIsEmpty(void) const
{
return size == 0 ? 1 : 0;
}
/*
* 函數名稱: Index
* 輸 入: pos
* pos: 定位數據元素結點
* 輸 出:
* 功能描述: 定位至第pos個數據元素結點，返回指向第pos個結點的指針
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
ListNode<T> *LinkList<T>::Index(int pos)
{
if (pos < -1 || pos > size)
{
cout << "參數pos越界出錯!" << endl;
exit(0);
}
if (pos == -1)
{
return head;
}
ListNode<T> *p = head->next;
int i = 0;
while (p != NULL && i <pos)
{
p = p->next;
i++;
}
return p;
}
/*
* 函數名稱: Insert
* 輸 入: pos
* pos: 插入數據元素結點的位置
* item: 插入數據結點的數據
* 輸 出:
* 功能描述: 在pos個結點之前插入一個data域為item的新結點
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
void LinkList<T>::Insert(const T& item, int pos)
{
if (pos < 0 || pos > size)
{
cout << "參數pos越界出錯!" << endl;
exit(0);
}
ListNode<T> *p = Index(pos);
ListNode<T> *newNode = new ListNode<T>(item, NULL, NULL);
newNode->prev = p->prev;
newNode->next = p;
p->prev->next = newNode;
p->prev = newNode;
size++;
}
/*
* 函數名稱: Delete
* 輸 入: pos
* pos: 刪除數據元素結點的位置
* 輸 出:
* 功能描述: 刪除第pos個結點，并返回被刪除結點的data
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
T LinkList<T>::Delete(int pos)
{
if (0 == size)
{
cout << "鏈表以空無元素可刪!" << endl;
exit(0);
}
T temp;
if (pos < 0 || pos > size-1)
{
cout << "參數pos越界出錯!" << endl;
exit(0);
}
ListNode<T> *p = Index(pos);
p->prev->next = p->next;
p->next->prev = p->prev;
temp = p->data;
delete p;
size--;
return temp;
}
/*
* 函數名稱: ClearList
* 輸 入: pos
* pos: 刪除數據元素結點的位置
* 輸 出:
* 功能描述: 清空表為初始化狀態
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
void LinkList<T>::ClearList(void)
{
ListNode<T> *p = head->next;
ListNode<T> *q;
while (p != head)
{
q = p;
p = p->next;
delete q;
}
size = 0;
}
/*
* 函數名稱: Reset
* 輸 入: pos
* pos: 數據元素結點的位置
* 輸 出:
* 功能描述: 使currPtr指向結點pos，并返回currPtr
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
ListNode<T> *LinkList<T>::Reset(int pos)
{
if (pos < -1 || pos > size - 1)
{
cout << "參數pos越界出錯!" << endl;
exit(0);
}
if (pos == -1)
{
return head;
}
if (pos == 0)
{
currPtr = head->next;
}
else
{
currPtr = head->next;
ListNode<T> prevPtr = head;
for (int i=0; i<pos; i++)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
}
return currPtr;
}
/*
* 函數名稱: Next
* 輸 入:
* 輸 出:
* 功能描述: 使currPtr指向下一個結點
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
ListNode<T> *LinkList<T>::Next(void)
{
if (currPtr != NULL)
{
currPtr = currPtr->next;
}
return currPtr;
}
/*
* 函數名稱: EndOfList
* 輸 入:
* 輸 出:
* 功能描述: currPtr是否指在鏈表尾
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
int LinkList<T>::EndOfList(void) const
{
return currPtr == NULL ? 1 : 0;
}
/*
* 函數名稱: GetData
* 輸 入: pos
* pos: 需要得到結點數據的位置
* 輸 出:
* 功能描述: 獲取pos處結點的數據
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
T LinkList<T>::GetData(int pos)
{
if (pos < 0 || pos > size-1)
{
cout << "參數pos越界出錯!" << endl;
exit(0);
}
ListNode<T> *p = Index(pos);
return p->data;
}
/*
* 函數名稱: Concatenate
* 輸 入: source,target
* source: 需要連接的對象
* target: 被連接的對象
* 輸 出:
* 功能描述: 將對象source連接到單鏈表target的尾部
* 作 者: 吳友強
* 日 期: 2009年10月13日
* 修 改:
* 日 期:
*/
template <class T>
void Concatenate(LinkList<T>& target, LinkList<T>& source)
{
ListNode<T> *q = source.head;
while (q->next != NULL)
{
target.Insert(q->next->data, target.size);
q = q->next;
}
}
（3）LinkListTest.cpp測試程序：
/*
* Copyright (c) 2009,FreshAir團隊嵌入式軟件研發組
* All rights reserved.
*
* 文件名稱：LinkListTest.cpp
* 摘 要： 雙向循環鏈表類的定義
*
* 當前版本：1.0
* 作 者： 吳友強
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/
#include <iostream.h>
#include <stdlib.h>
#include "LinkList.h"
int main(int argc, char *argv[])
{
// LinkList<int> targetList, sourceList;
//
// for (int i=0; i<10; i++)
// {
// targetList.Insert(i+10, i);
// }
//
// for (i=0; i<5; i++)
// {
// sourceList.Insert(i+5, i);
// }
// cout << "測試GetData()成員函數結果如下:" << endl;
// int n = linkList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << linkList.GetData(i) << " ";
// }
//
// cout << endl << "測試遍歷成員函數結果如下:" << endl;
// ListNode<int> *p = linkList.Reset(0);
//
// while (!linkList.EndOfList())
// {
// cout << p->data << " ";
// p = linkList.Next();
// }
//
// cout << endl << "測試Delete()成員函數結果如下:" << endl;
// n = linkList.GetListSize();
// for (i=n-1; i>=0; i--)
// {
// linkList.Delete(i);
// }
//
// cout << "測試GetData()成員函數結果如下:" << endl;
// n = linkList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << linkList.GetData(i) << " ";
// }
// Concatenate(targetList, sourceList);
//
// int n = targetList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << targetList.GetData(i) << " ";
// }
LinkList<int> myList;
for (int i=0; i<100; i++)
{
myList.Insert(i+10, i);
}
cout << "插入100個元素輸出如下：" << endl;
int n = myList.GetListSize();
for (i=0; i<n; i++)
{
cout << myList.GetData(i) << " ";
}
for (i=99; i>=0; i--)
{
myList.Delete(i);
}
cout << endl << "刪除100個元素輸出如下：" << endl;
n = myList.GetListSize();
for (i=0; i<n; i++)
{
cout << myList.GetData(i) << " ";
}
return 0;
}
說明：注釋部分測試基本功能函數，其他測試提高要求。
浙公網安備 33010602011771號