北京邮电大学 数据结构 实验一 带头结点的单链表构造

北京邮电大学信息与通信工程学院

};

LinkList(T a[], int n);//有参构造函数，使用含有n个元素的数组a初始化单链表 ~LinkList();

//析构函数,(其在void main 函数最后一句语句之后自动执行，旨在//按次序遍历线性表中的各个数据元素 //获取线性表的长度

//获取线性表第i个位置上的元素结点地址 //查找线性表中值为x的元素，找到后返回其位置

释放栈空间)

void PrintList(); int GetLength(); int Locate(T x);

Node * Get(int i);

void Insert(int i, T x);//后插，在线性表的第i个位置上插入值为x的新元素 void insert(int i, T x);//前插，在线性表的第i个位置上插入值为x的新元素 T Delete(int i); Node * front;

//删除线性表第i个元素，并将该元素返回 //头指针

private:

//头插法构造函数 template

LinkList::LinkList(T a[], int n) { }

//尾插法构造函数 //template

//LinkList::LinkList(T a[], int n) //{

// front = new Node < T > ;

for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序 { }

front = new Node < T >;//为头指针申请堆空间 front->next = NULL;//构造空单链表 for (int i = n - 1; i >= 0; i--) { }

Node*s = new Node < T >;//建立新结点 s->data = a[i];//将a[i]写入新结点的数据域 s->next = front->next;//修改新结点的指针域

front->next = s;//修改头结点的指针域，将新结点加入到链表中 for (int j = 0; j < i; j++) { }

if (a[j]>a[j + 1]) { }

T t = a[j + 1]; a[j + 1] = a[j]; a[j] = t;

第13页

北京邮电大学信息与通信工程学院

// Node*r = front;//命名一个新变量进行转换 // for (int i = 0; i < n; i++) // {

//Node*s = new Node < T > ; //s->data = a[i]; //r->next = s; //r = s; //}

//r->next = NULL; //}

template

void LinkList::PrintList()//遍历线性表元素并打印到屏幕 { }

template

LinkList::~LinkList()//析构函数 { }

template

Node * LinkList::Get(int i)//获取线性表第i个位置上的元素结点地址 { }

Node*p = front->next; int k = 1;

while (p && (k != i)) { } return p;

p = p->next; k++;

Node*p = front;//初始化工作指针P while (p)//要释放的结点存在 { }

front = p; p = p->next;

delete front;//释放结点 Node*p = front->next; while (p) { }

cout << endl;

cout << p->data << \\p = p->next;

第14页

北京邮电大学信息与通信工程学院

template

int LinkList::Locate(T x)//按值查找某元素的位置 { } //后插

template

void LinkList::Insert(int i, T x) { }

template

T LinkList::Delete(int i) {

Node*p = front;

if (i != 1) p = Get(i - 1);//若不是在第一个位置删除，获取第i-1个元素的地址 try {

if (p && (p->next)) {

Node*q = p->next;

Node*p = front;

if (i != 1) p = Get(i - 1); try { }

catch (int i) { }

cout << \插入到位置 \处\为错误位置\if (p) { }

else throw i;

Node*s = new Node < T > ; s->data = x; s->next = p->next; p->next = s;

Node*p = front->next; int k = 1;

while (p&&(p->data != x)) { } return k;

p = p->next; k++;

第15页

北京邮电大学信息与通信工程学院

}

}

}

p->next = q->next; T x = q->data; delete q; return x;

else throw i;

catch (int i) { }

cout << \删除位置 \处\为错误位置\

template

int LinkList::GetLength() { }

void main() {

int m=1;

int a[7] = { 3, 2, 1, 4, 6, 5, 7 }; LinkList list(a, 7); cout << \排序后的链表为:\list.PrintList();

cout << \

<< \※ ※\<< \※ 对该单链表的操作 ※\<< \※ ※\<< \※ 1. 获取线性表的长度 ※\<< \※ ※\<< \※ 2. 查找值为x的元素，并返回其位置 ※\<< \※ ※\<< \※ 3. 在线性表的第i个位置上插入值为x的新元素 ※\<< \※ ※\<< \※ 4. 删除线性表第i个元素，并将该元素返回 ※\<< \※ ※\

<< \Node*p = front->next; int i;

for (i = 0; p != NULL; i++) { } return i;

p = p->next;

while (m != 0)

第16页