C++数据结构

来源：百度知道 编辑：UC知道 时间：2024/06/08 13:01:06
在SingleList中增加一个成员函数，将单链表逆置，直接实现该函数并分析其时间复杂度，要求设计的算法的空间复杂度为O(n)

希望可以写明 具体操作步骤和核心算法的代码
#include "linearlist.h"
template <class T> class SingleList;
template <class T>
class Node
{
private:
T element;
Node<T> *link;
friend class SingleList<T>;
};
template<class T>
class SingleList:public LinearList<T>
{
public:
SingleList() {first = NULL;n=0;}
~SingleList();
bool IsEmpty() const;
int Length() const;
bool Find(int i,T&x) const;
int Search(T x) const;
bool Insert(int i ,T x) ;
bool Delete(int i);
bool Update(int i;T x);
void Clear();
void output (ostream& out ) const;
private :
Node<T>* frist;
};

核心代码见reverselink()，如果不懂hi我！很明显空间复杂度为O(n),因为我只有一次遍历链表，就是while循环遍历它。
核心思想：
1.链表是必须带有头节点的；
2.先把头节点取出来(head = L)，并且断链(head->next = NULL)，并记住头节点以后的节点(p = head ->next)。
3.每次从p中取一个节点，插入到头节点之后(即head之后)，直到p == NULL.

#include <iostream>
using namespace std;

typedef struct LNode
{
int data;
LNode* next;
}*List;

void CreateLink(List L)
{
int data;
List p, q;
printf("请输入结点[-1]退出:");
scanf("%d", &data);

while(data != -1)
{
//创建新结点并赋值
p = new LNode ;
p->data = data;
p->next = NULL;

//如果只有头结点，直接连在头结点后面
if (L->next == NULL)
L->next = p;
else//如果存在其他的结点，则循环连接在q后面，q是指向链表中最后一个结点。
q->next = p;
q = p;
printf("请输入结点号[-1]退出:");
scanf("%d", &data);
}
}

void ReverseLink(List L)
{
List head, p, pre; <