实验一——链式结构实现线性表

北京邮电大学信息与通信工程学院 第1页 数据结构实验报告 实验名称： 实验一——链式结构实现线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期：

1． 实验要求 实验目的： 通过选择下面四个题目之一进行实现，掌握如下内容： ➢ 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 ➢ 学习指针、模板类、异常处理的使用 ➢ 掌握线性表的操作的实现方法 ➢ 学习使用线性表解决实际问题的能力 实验内容： 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、 带头结点的单链表 2、 不带头结点的单链表 3、 循环链表 4、 双链表 5、 静态链表 线性表的基本功能：  构造：使用头插法、尾插法两种方法 1、插入：要求建立的链表按照关键字从小到大有序 2、删除 3、查找 4、获取链表长度 5、销毁 北京邮电大学信息与通信工程学院 第2页 6、其他：可自行定义 编写测试main()函数测试线性表的正确性。

2. 程序分析 2.1 存储结构 存储结构：顺序表

2.2 关键算法分析 头插法示意图：

算法步骤： ① 堆中建立新结点 ② S->next指向front->next ③ front->next指向s Node *s=new Node; s->data=a[i]; s->next=front->next; front->next=s;

时间复杂度：O(n) 尾插法 算法步骤： ① 堆中建立新结点Node *s=new Node; ② 将新结点加入到链表中r->next=front->next ③ 修改尾指针 r=s 按值查找结点示意图： 北京邮电大学信息与通信工程学院 第3页 ○1定位计数和定位指针

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

○2比较P指向的元素是否与检索值相同

if(p) while(p) { if(p->data==n) cout<<"元素序号："next; i++; } else throw"空链表！"; 时间复杂度：O(n)

插入操作：

算法步骤： ① 堆中建立新结点Node *s=new Node; ② 将新结点插入到要插入位置后一节点p的后面，将后一结点数据写入s ③ P指向s，在p中写入新的值 s->data=p->data; s->next=p->next; p->next=s; p->data=x; 时间复杂度：O（1） 北京邮电大学信息与通信工程学院 第4页 删除结点示意图：

x……

p……q①②③④⑤

删除结点示意图 算法步骤： ①从第一个结点开始，查找第i-1个元素，设为p指向该结点； ②设q指向第i个元素：q = p->next; ③摘链，即将q元素从链表中摘除：p->next = q->next; ④保存q元素的数据：x = q->data; ⑤释放q元素：delete q;

说明：如果算法比较复杂，可以将多句代码合成一个步骤进行说明。比如也可以这样写： ①从第一个结点开始，查找第i-1个元素，设为p指向该结点； ②设q指向第i个元素：q = p->next; ③摘链，即将q元素从链表中摘除： p->next = q->next; x = q->data delete q;

时间复杂度：O(n)

2.3 其他 程序代码： #include using namespace std; template struct Node { T data; struct Node * next; }; template 北京邮电大学信息与通信工程学院 第5页 class LinkList { public: LinkList(){front=new Node;front->next=NULL;} LinkList(T a[],int n); ~LinkList(); Node* Get(int i); Node* Locate(int n,Node* s); void Insert(int i,T x); T Delete(int i); int GetLength(); void Print(); private: Node* front;

}; template LinkList::LinkList(T a[],int n) //头插法 { front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) { Node *s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } /*template LinkList::LinkList(T a[],int n) //尾插法 { front=new Node; Node *r=front; for(inti=0;i{ Node* s=new Node; s->data=a[i]; r->next=s; r=s; } r->next=NULL;

}*/ 北京邮电大学信息与通信工程学院 第6页 template LinkList::~LinkList() //析构函数 { Node* p=front; while(p) { front=p; p=p->next; delete front; } }

template Node* LinkList::Get(int i) { Node* p=front->next; int j=1; while(p&&j!=i) { p=p->next; j++; } return p;

}

template Node* LinkList::Locate(int n,Node* s) { int i=1; Node* p; p=front->next; if(p) while(p) { if(p->data==n) cout<<"元素序号："next; i++; } else throw"空链表！";

北京邮电大学信息与通信工程学院 第7页 /*while(p&&p->data!=n) { p=p->next; } return p; t=0; if(p->next) // Locate(n,p->next) ; else return NULL;*/

}

template void LinkList::Insert(int i,T x) { Node* p=Get(i); if(p) {Node* s=new Node; s->data=p->data; // s->next=p->next; p->next=s; p->data=x; } else throw"输入有误";

} template T LinkList::Delete(int i) { Node * p=front; if(i!=1) p=Get(i-1); Node* q=p->next; p->next=q->next; T x=q->data; delete q; return x; }

template int LinkList::GetLength() 北京邮电大学信息与通信工程学院 第8页 { int i=0; Node* p=front->next; if(p) { i++; p=p->next; } return i; }

template void LinkList::Print() { Node* p=front->next; if(front->next) { while(p) { coutnext; } cout<} else throw"该表没有元素"; } void main() { int x,y; int a[6]={1,2,3,4,5,6}; LinkList L(a,6); L.Print(); cout<<"请输入要插入的位置和数值："; cin>>x>>y; L.Insert(x,y); L.Print(); cout<<"请输入要删除的元素序号："; cin>>x; L.Delete(x); L.Print(); cout<<"请输入需要查找的元素序号："; cin>>x; cout