数据结构学习总结-2-两种基本数据结构(数组和链表)-R

第一篇：数据结构学习总结-2-两种基本数据结构(数组和链表)-R

数据结构学习总结－2－两种基本数据结构（数组和链表）－RTime:2007-5-26

1：一维数组地址的计算

Loc(a[i])= Loc(a[0])+ i*k（已知一个元素占k个字节）

2：多维数组存储的两种方式

1> 行优先

2> 列优先

3：二维数组地址的计算：

已知a是m行n列的数组，则a[i][j]地址的计算公式： Loc(a[i][j])= Loc(a[0][0])+(i*n + j)*k

4：多维数组地址的计算：

设有n维数组a，各维的长度是m1,m2,m3, … 每个元素占据k个单元，则在行优先情况下，数组元素：Loc(a[i1][i2][i3]…[in])= Loc(a[0][0][0]…[0])+((m2*m3*m3…)*i1 +(m3*m4*m5…)*i2 +(mn*i(n-1))+ in)5：头结点

单链表的 第一个 结点

6：表头结点

此结点存储链表相关信息

7：循环链表

8：双向链表

/******************************************************************************************** ** Program Name : Correlative Operation Of Single Chain

** Anthor: Lu jian Hua

** Time: 2007-5-26

*********************************************************************************************/

#include

using namespace std;

const int DEL_NULL_LIST=-1;

const int DEL_NO_SUCH_DATA= 0;

const int DEL_NORMAL= 4;

class Node// class Of Node{

public:

int data;// data segment

Node *next;// pointer segment

};

/******************************************************************************************** ** Function Name : List_Builder

** Parameters: void

** Return Value: Node *(return the front node of the chain)

*********************************************************************************************/ Node* List_Builder()// List_Builder

{

Node *front= NULL;

Node *recent = front;

char c = 0;

while(true)

{

cout << “Another node?(Y/N)”;

cin>> c;

if(c!= 'n' && c!= 'N')

{

Node *temp = new Node();

cout << “The value of the node : ”;

cin>> temp->data;

temp->next = NULL;// initialize the NEXT of the new node NULL

if(front == NULL)// if front node, update front node firstfront = temp;

else

recent->next = temp;// if not front node, added it to the chain directly

recent = temp;// update recent

}

else

break;

数据结构学习总结－2－两种基本数据结构（数组和链表）－RTime:2007-5-26

}

return front;

}

/******************************************************************************************** ** Function Name : List_Printer

** Parameters: Node *front(the front node address of the chain to be realease)

** Return Value: void

*********************************************************************************************/ void List_Printer(const Node *header)// List_Printer

{

const Node *recent = header;

while(recent)

{

cout << recent->data << “--> ”;

recent = recent->next;

if(recent == NULL)

cout << “NULL”;

}

cout << endl << endl;

}

/******************************************************************************************** ** Function Name : List_Cleaner

** Parameters: Node *front(the front node address of the chain to be realease)

** Return Value: Node *(return the front node of the chain)

*********************************************************************************************/ void List_Cleaner(Node** front)// release all the space that nodes occupancy {

Node *record = NULL;// record the next node of the node to be released

while(*front)

{

record =(*front)->next;

delete(*front);// release the front node

(*front)= record;//update the front node

}

cout << “nCleaner has done its work...” << endl << endl;

}

/******************************************************************************************** ** Function Name : Get_Node_Count

** Parameters: Node *front(ponter to the front node address of the chain to be realease)

** Return Value: int(return the count of nodes of the chain)

*********************************************************************************************/ int Get_Node_Count(Node** header)

{

Node *recent = *header;

int count = 0;

while(recent)

{

++count;

recent = recent->next;

}

return count;

}

/******************************************************************************************** ** Function Name : Get_Certain_Node

** Parameters: Node *front(the front node address of the chain to be realease)

** Return Value: Node *(return the certain node of the chain)

*********************************************************************************************/ Node* Get_Certain_Node(Node **front, int no)// get the ceration node of a chain Eg:1,2,3,4,5...n

{

if(no < 0 || no > Get_Node_Count(front))// check for security

return NULL;

while(recent)

{

++count;

if(count == no)

return recent;

recent = recent->next;

}

return NULL;

}

/******************************************************************************************** ** Function Name : List_Converter

** Parameters: Node *front(the front node address of the chain to be realease)

** Return Value: void

*********************************************************************************************/ void List_Converter(Node **header)// inverse a chain

{

Node *prev = NULL;// previous node

Node *recent =(*header);// currentnode

while(recent)

{

Node *NEXT = recent->next;// record the next node first

recent->next = prev;// deal with the current node

if(NEXT == NULL)// if the current node is the last node, stop and return{

(*header)= recent;// make last node front node

break;// break

}

// prepare for the next disposal

prev = recent;// next previous node = current node

recent = NEXT;// current node = the record node(has been backed up)}

}

/******************************************************************************************** ** Function Name : Del_Node

** Parameters: Node *front(the front node address of the chain to be realease)

int del_data(for query the certain node)

** Return Value: NO_SUCH_DATA(no data founded!)

DEL_NOMAL(delete normally)

*********************************************************************************************/ int Del_Node(Node **front, int del_data)// delelte a node from the chain

{

bool deleted = false;// tag: indicate some nodes has been deleted?

Node *HEADER = new Node();// if no HEADER exists, a HEADER will be addedHEADER->next =(*front);

Node *prev = HEADER;// previous node of the current node

while(prev->next)// recent->the last priv->previous of the last{

Node *recent = prev->next;

if(recent->data == del_data)

{

if(recent ==(*front))// if front is the node to be delete

{

Node *link =(*front)->next;

delete(*front);// 1> delete

(*front)= link;// 2> repoint the front node

deleted = true;

HEADER->next =(*front);// repoint HEADER

prev = HEADER;// repoint prev 数据结构学习总结－2－两种基本数据结构（数组和链表）－RTime:2007-5-26 Node *recent =(*front);int count = 0;

数据结构学习总结－2－两种基本数据结构（数组和链表）－RTime:2007-5-26

continue;// continue searching...}

else// middle node and tail node have the same disposal{

Node *link = recent->next;

delete recent;// 1> delete

prev->next = link;// 2> reconnect

deleted = true;

continue;// continue searching...}

}

prev = prev->next;

}

if(deleted)

return DEL_NORMAL;

else

{

cout << “--------No Such Data Found!-----------” << endl << endl;

returnDEL_NO_SUCH_DATA;

}

}

int main()

{

int select = 0;

Node *front = List_Builder();// build a chain

while(true)

{

cout << “Please select : ” << endl << endl

<< “1> Print the list” << endl << endl

<< “2> Convert the list” << endl << endl

<< “3> Delete nodes of list”;

cin >> select;

cout << endl;

switch(select)

{

case 1:

List_Printer(front);break;

case 2:

List_Converter(&front);

List_Printer(front);break;

case 3:

while(true)

{

char c = 0;

cout << “Delete Again ?(Y/N)”;

cin >> c;

cout << endl;

if(c == 'n' || c == 'N')

break;

else

{

int value = 0;

cout << “Delete Value ? ”;

cin >> value;

cout << endl;

Del_Node(&front, value);

List_Printer(front);

}

}

break;

}

}

return 0;

}

第二篇：2012《数据结构》上机实验报告 链表

西华大学数计学院学生上机实践报告

西华数学与计算机学院上机实践报告

课程名称：数据结构 指导教师：唐剑梅 上机实践名称：

上机实践编号：1 年级： 2011 姓名：蒋俊 学

号

：

***

上机实践成绩：

上机实践日期：2012-11-6

上机实践时间：8:00-9:30

一、实验目的

1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。

3.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

4.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

5.了解和掌握递归程序设计的基本原理和方法。

6.掌握使用 C++面向对象的程序设计技术设计数据结构源程序的方法。

二、实验内容

1.熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。

2.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。

要求：（1）通讯录按姓名项的字母顺序排列；

（2）能查找通讯录中某人的信息；

[提示] 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的

西华大学数计学院学生上机实践报告

char name[20];

// 姓名子域

NodeType *next;

// 指针域

};class Jose

//类声明

{ private: NodeType *Head;

public:

Jose(){};

~Jose(){ };

void creat();

void outs();

};void Jose::creat(){ int i=0, n;

NodeType *newp, *pre;

cout<<“n

输入总人数 n=”;cin>>n;

pre=new NodeType;

Head=new NodeType;

pre->num=1;

cout<<“n 编号”<<1<<“的人

姓名=”;

cin>>pre->name;

cout<<“n 密码”<<1<<“的人

密码=”;

cin>>pre->psw;

Head=pre;

Head->next=Head;

for(i=1;i

{ newp=new NodeType;

newp->num=i+1;

cout<<“n 编号”<

姓名=”;cin>>newp->name;

cout<<“n 密码”<

密码=”;

cin>>newp->psw;

newp->next=Head;

pre->next=newp;

pre=newp;

} }

void Jose::outs()

{ int m,i;

NodeType *q=Head, *p;

cout<<“n 输入m值(m>=2)”;cin>>m;

cout<<“n

根据m值，开始报数输出：”<

while(q->next!=q)

西华大学数计学院学生上机实践报告

{ for(i=1;inext;}

cout<<“编号为：”<num<<“ 的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

m=q->psw;

p->next=q->next;delete q;

q=p->next;

}

cout<<“编号为：”<num<<“的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

delete q;}

int main()

{

Jose h;

h.creat();

h.outs();

return 0;}

西华大学数计学院学生上机实践报告

{ char Add[20];

char name[20];

char tel[20];

};struct NodeType {

ElemType data;

NodeType *next;};class Sqlist

{ private:

NodeType *Head;

public:

Sqlist();

~Sqlist();

void creat();

void Insert(ElemType x);

void Delet(ElemType x);

void PrintOut();

};Sqlist::Sqlist(){

Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“电话号码”);} Sqlist::~Sqlist(){

NodeType *p=Head->next;

while(p!=NULL)

{Head->next=p->next;

delete p;

p=Head->next;} } void Sqlist::creat()

//初步建立一个通讯录

{ NodeType*p,*s,*q;ElemType x;

西华大学数计学院学生上机实践报告

int a;q=Head;cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“输入一个数。若为-1，结束输入:”<>a;

while(a!=-1){ cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL;

p=s;} else{ s->next=p;q->next=s;} q=q->next;

cout<<“输入一个数。若为-1，结束输入:”<>a;} } void Sqlist::Insert(ElemType x)//插入 { NodeType *p,*q,*s;s=new NodeType;

西华大学数计学院学生上机实践报告

s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//删除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“删除结点成功”<

{ NodeType *p;p=Head->next;while(p!=NULL){ cout<

data.name<<“ ”;cout<

data.tel<<“ ”;cout<

data.Add<<“ ”;p=p->next;} cout<

Sqlist as;

cout<<“n

通讯录演示”;

do{

cout<<“nn”;

cout<<“nn

1.初步建立一个通讯录（单链表）

”;

西华大学数计学院学生上机实践报告

cout<<“nn

2.插入新的电话记录 ”;

cout<<“nn

3.删除一个电话记录”;

cout<<“nn

4.结束程序”;

cout<<“n******************************** ”;

cout<<“n

请输入你的选择(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break;

case 2:{

cout<<“n 插入的数据 姓名”;cin>>e.name;

cout<<“n 插入的数据 电话号”;cin>>e.tel;

cout<<“n 插入的数据 地址”;cin>>e.Add;

as.Insert(e);as.PrintOut();

}break;

case 3:{

cout<<“n 被删除的姓名= ”;

cin>>e.name;

as.Delet(e);

as.PrintOut();

}break;

default:break;

}

}while(k>=1&&k<4);

cout<<“n

再见!”;

return 0;}

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

const int MAXSIZE=100;

// 数组的容量 class SqStack

{ private:

ElemType elem[MAXSIZE];

int top;

public:

SqStack();

~SqStack(){};

void SqStack::push(ElemType e);

ElemType SqStack::pop();

void SqStack::PrintOut();

int SqStack::IsEmpty();

void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s;

ElemType e;while(N){

s.push(N%M);

N=N/M;} while(!s.IsEmpty()){

e=s.pop();

if(e>=10)

{

e=e%10;

switch(e)

{

case 1:cout<<“b”<

case 2:cout<<“c”<

case 3:cout<<“d”<

case 4:cout<<“e”<

case 5:cout<<“f”<

default:cout<<“a”<

}

} else

cout<

西华大学数计学院学生上机实践报告

} cout<

{cout<<“栈满溢出”<

return;

}

else{top++;

elem[top]=e;} } ElemType SqStack::pop(){ElemType x;

if(top==0)

{ cout<< “ 栈为空，不能出栈操作”<

else { x=elem[top];

top--;

return x;} } void SqStack::PrintOut()

{int k;

cout<<“n PrintOut Data:n”;

for(k=top;k>=1;k--)cout<

cout<

else return 0;} void main(){ ElemType a,m;cout<<“请输入一个正整数:”<>a;cout<<“请输入要转换的进制:”<>m;SqStack as;as.f(a,m);}

西华大学数计学院学生上机实践报告

五、总结

通过本次实验，我熟悉了链表的操作，了解了线性表在现实生活中的运用，认识了顺序存储和链式存储这两种结构。本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。实验内容对于队列的运用没有涉及，希望以后有所涉及。

西华大学数计学院学生上机实践报告

第三篇：数据结构学习总结

数据结构与算法课程论文综述

摘要

如何合理的组织数据、高效率的处理数据是扩大计算机应用领域、提高软件效率的关键。在软件开发过程中要求“高效地”组织数据和设计出“好的”算法，并使算法用程序来实现，通过调试而成为软件，必须具备数据结构领域和算法设计领域的专门知识。

《数据结构与算法》课程就是主要学习在软件开发中涉及的各种常用数据结构及其常用算法，在此基础上，学习如何利用数据结构和算法解决一些基本的应用问题。

课程主要内容

本学期一共学习了十章的内容，下面就这十章的内容作了详细的介绍。第一章：数据结构与算法概述

本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的掌握，而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键，所以对这些概念的理解就显得十分重要。

数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称，其基本单位是数据元素，而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言中定义一种数据类型时，编译程序编译系统就能获得如下信息：（1）、一组性质相同的值的集合；（2）、一个预订的存储体系；（3）、定义在这个值集合上的一组操作。数据结构是指数据元素之间的关系，它包括数据的逻辑结构、存储结构、一组运算集合；数据的逻辑结构分为线性结构和非线性结构。数据的存储方法有：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念，算法是为解决一个特定问题而采取的确定的有限步骤集合，它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析，分为时间性能分析和空间性能分析。第二章：顺序表及其应用

本章主要是对顺序表、顺序表的结构、数据类型、基本算法及相关应用的介绍。顺序表是一种简单而常用的数据结构，其应用范围较为广泛，包括查找问题、排序问题、字符处理问题等内容。第三章：链表及其应用

链表是一种简单、常用的数据结构，与顺序表相比，具有插入、删除结点不需要移动元素，不必事先估计存储空间大小等优点，操作较为灵活。它有六种基本运算：（1）、置空表（2）、求表长（3)、按序号取元素（4）、按值查找

(5)、插入（6）、删除。

单链表即链表的每个结点只有一个指针域，用来存储其直接后继的存储位置。但是这样就使得对结点前面的元素的操作很困难，所以就在每个结点增加一个指向其前驱结点的指针域，从而构成双向链表。同时由于每个结点的地址既存放在其前驱结点的后继指针中，又存放在其后继结点的前驱指针域中，所以双向链表的插入操作分为前插和后插。第四章：堆栈及其应用

首先要明白栈是一种受限制的线性结构，遵守“先进后出”的规则，其插入与删除操作都在栈顶进行。

其次根据顺序存储和链接存储，栈分为顺序栈和链栈。其中顺序栈栈是用地址连续的存储空间依次存储栈中数据元素，并记录当前栈顶数据元素的位置；基本算法包括置空栈、判栈空、判栈满、取栈顶元素、入栈和出栈。而链栈则使用链式存储堆栈的数据元素，并记录当前栈顶数据元素的位置；每个结点包括data数据域：用来存放数据元素的值，next指针域：用来存放其直接后继结点的存储地址，其基本运算和顺序栈相同。

最后是关于堆栈的应用：（1）、数值转换问题；由于在将十进制数N转换为d进制数时，最先得到的余数是d进制数的最低位，在显示结果时需要最后输出；而最后求得的余数是d进制数的最高位，需要最先输出。这与栈的“先入后出”性质相吻合，所以可用栈来存放逐次求得的余数，然后输出。（2）、括号匹配问题；当读取一个表达式时，一旦读到括号就进栈，而读到下一个括号时就与栈中括号比较，若相匹配，则出栈，否则继续读取表达式。到最后，如果栈为空栈，则说明括号匹配，否则括号不匹配。第五章：队列及其应用

首先和栈一样，要知道队列是一种受限制的线性结构，遵守“先进先出”的规则，其插入在队尾、删除在对头。

其次根据顺序存储和链式存储，队列也分为顺序队列和链队列。其中顺序队列是用地址连续的向量空间依次存储队列中的元素，同时记录当前对头元及队尾元素在向量中的位置。然后是链队列，即在存储器中占用任意的、连续或不连续的物理存储区域，使用动态结点空间分配；在这其中，值得注意的是链队列不存在队满的情况。

第六章：特殊矩阵、广义表及其应用

首先是关于矩阵的概念即存储方法；

1、二维数组中元素aij的地址为：（1）、以行序为主存储，Loc（aij）=Loc（a00）+[j*（m+1）+i]*d（2）、以列序为主存储，Loc（aij）=Loc（a00）+[i*（n+1）+j]*d，其中m为行数、n为列数、d为每个元素所占的存储单元的个数。

2、对称矩阵：即将下三角存储在一个一维数组sa[k]中，其中0≤k<(n+1)/2；当i≥j时，k=i*（i+1）/2+j，当i

3、三角矩阵：和对称矩阵的存储思路一样用一维数组sa[k]存储，若是上三角矩阵（下三角中元素均为常数c），则当i≥j时，k=i*（i+1）/2+j，当ij时，k=n*（n+1）/2

4、对角矩阵：同样存储在一维数组sa[k]中，k=2i+j

5、稀疏矩阵：即矩阵中非零元素个数远远小于矩阵元素个数，可用三元组表存储，将非零元素的值与其行号、列号存放在一起。

其次是关于广义表的概念；广义表是n（n≥0）个元素a1、a2、a3、„、an的有限序列，而ai或是原子或是一个广义表，所以广义表是递归定义。第七章：二叉树及其应用

首先关于二叉树的概念及其性质；二叉树是由n（n≥0）个结点组成的有限集合。在这其中有两种特殊的二叉树，满二叉树和完全二叉树。同时二叉树具有如下五个性质：（1）、在二叉树的第i层上至多有2（i-1）个结点（i>0）（2）、深度为k的二叉树至多有2（k）-1个结点（k>0）（3）、对任意一棵非空二叉树，若果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1（4）、有n个结点的完全二叉树（n>0）的高度为∟log2n」+1（5）、若对满二叉树或完全二叉树按照“从上到下，每层从左到右，根结点编号为1”的方式编号，则编号为i的结点，它的两个孩子结点编号分别为2i和2i+1，它的父节点编号为i/2。

其次是二叉树的存储结构分为顺序存储和链接存储。顺序存储是按在完全二叉树中的编号顺序，依次存储在一维数组中。这样的存储方式可以很方便地找到任一结点的父结点及左右孩子，但对于一般的二叉树会造成很大的空间浪费，且在插入或删除结点时需大量移动节点，不利于运算的实现。那么就引出了二叉树的链接存储，每个结点包括三个域，lchild指针域：记录该结点左孩子的地址、rchild指针域：记录该结点右孩子的地址、data域：存储该结点的信息。

接下来是二叉树的遍历及线索化，不仅要能对二叉树进行遍历、线索化操作，而且还要能够根据给出的遍历结果构造出二叉树。最后是二叉树的应用，例如哈夫曼树：为数据压缩提供了一种方法、二叉排序树：即中序遍历的结果是递增的有序序列。

第八章：树和森林及其应用

首先是关于树和森林的有关概念及存储结构；树或森林与二叉树之间有一个自然地一一对应关系，任何一个森林或一棵树可以唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。在这里，要会如何将树或森林转换成二叉树、二叉树转换成树或森林。对于树的顺序存储结构：双亲表示法，链接存储结构：（1）、孩子表示法（2）、孩子兄弟表示法，只需了解。

其次是树和森林的遍历，要知道树只有先序遍历和后序遍历、森林只有先序遍历和中序遍历，且（1）、树的先序遍历与二叉树的先序遍历相同（2）、树的后序遍历与二叉树的中序遍历相同（3）、森林的先序遍历和中序遍历分别与二叉树的先序遍历和中序遍历结果相同。

最后是树的一个典型应用——B树，它是一种平衡的多路查找树，学习是根据实例走一遍算法，理解算法即可。第九章：散列结构及其应用

散列结构是以存储结点中的关键字作为自变量，通过确定的函数H（即散列函数或哈希函数）进行计算，把所求的函数值作为地址存储该结点。

首先是散列函数有：（1）、直接定址法（2）、除留余数法（3）、数字分析法（4）、平方取中法（5）、折叠法

其次是冲突处理，由于散列函数很可能将不同的关键字计算出相同的散列地址，所以就需要为发生冲突的关键字结点找到一个“空”的散列地址。冲突处理的方法有

1、开放定址法：Hi=（H（key）+di）mod m，i=1,2,3，„，K（K≤m-1）例如（1）、线性探测再散列，取di=1,2,3，„，m-1（2）、二次探测再散列，取di=1（2），-1（2），2（2），-2（2），„（3）、伪随机探测再散列，取di=伪随机数；

2、链地址法：在散列表的每一个存储单元中增加一个指针域，把产生冲突的关键字以链表结构存放在指针指向的单元中。第十章：图及其应用 首先是图的有关概念；图是一种数据结构，可以用二元组表示，形式化定义为：Graph（V，VR），其中V={x|x∈dataobject}，R={VR}，VR={＜x，y＞ P（x，y）∧（x，y∈V）}。顶点的度、入度和出度，以顶点V为头的弧的数目称为V的入度，以顶点V为尾的弧的数目称为V的出度，而出度与入度之和即为顶点V的度。

其次是图的存储结构；（1）、邻接矩阵（2)、邻接表

最后的图遍历和图的典型应用；对于遍历图的深度优先算法或广度优先算法、最小生成树的普利姆算法或克鲁斯卡尔算法、最短路径的迪杰特斯拉算法和弗洛伊德算法以及有向无环图拓扑排序算法，都需要根据实例走一遍算法，从而掌握这些算法。

心得体会

最开始学习这门课时，我对它没有很深刻的认识，只是听说这门课比较难。学习起来会比较累。通过这一学期的学习也确实证实了这一点。在学习这门课的过程中自己也确实遇到了一些问题，主要是书本上的知识与老师的讲解都比较容易理解，但是当自己利用已学的知识编写程序时就感到非常的棘手，很多时候都是把大概的算法思想想出来后，又把书本上的程序抄写一遍来完成程序的编写。针对这一问题以后自己会尽量学习摆脱掉书本，自己慢慢学会独立编写程序。

结语

通过对数据结构与算法的整理和实际应用，我深刻了解到数据结构与算法的重要性，同时也加深了对它的认识和了解，了解到了数据结构与算法在生活、工作等生活各个方面的重要性和不可缺少性。我通过整理数据结构与算法的学习而获得的极大收获。我相信这次的学习会对我以后的学习和工作产生非常大的影响力。

参考文献

《数据结构与算法》（第二版）王昆仑

李红 主编

第四篇：北邮数据结构实验报告 单链表

北京邮电大学 数据结构试验报告

实验名称： 实验一

线性表 学生姓名：

班

级：

班内序号：

学

号：

日

期： 2014年1月3日

实验目的

 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法  学习指针、模板类、异常处理的使用  掌握线性表的操作的实现方法  学习使用线性表解决实际问题的能力 实验内容

2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：

1、带头结点的单链表

2、不带头结点的单链表

3、循环链表

4、双链表

5、静态链表

线性表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序

3、删除

4、查找

5、获取链表长度

6、销毁

7、其他：可自行定义

编写测试main()函数测试线性表的正确性。程序分析

3.1 存储结构 单链表的存储结构：

3.2 关键算法分析

一、关键算法 1.头插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.修改新结点的指针域

d.修改头结点的指针域,将新结点加入链表中 代码描述： 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;时间复杂度：O(n)

2.尾插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.将新结点加入到链表中

d.修改修改尾指针 代码描述: template LinkList::LinkList(T a[], int n)//尾插法建立 {

front = new Node;front->next=NULL;Node * r = front;for(int i=0;i * s = new Node;

}

} s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度：O(n)

3.析构函数

自然语言描述：a.新建立一个指针，指向头结点

b.移动a中建立的指针

c.逐个释放指针

代码描述: template LinkList::~LinkList()//析构函数，销毁链表 {

Node * p = front;while(p){ front = p;p = p->next;

} } delete front;4.按位查找函数

自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1

b.循环以下操作，直到p为空或者j等于1

b1：p指向下一个结点

b2：j加1

c.若p为空，说明第i个元素不存在，抛出异常

d.否则，说明p指向的元素就是所查找的元素，返回元素地址

代码描述: template Node* LinkList::Get(int i)//按位查找 {

Node * p = front;int j=0;while(p){

if(j

} else break;p = p->next;j++;

} if(!p)throw“查找位置非法”;else

return p;} 时间复杂度：O(n)

5.按值查找函数

自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1

b.循环以下操作，找到这个元素或者p指向最后一个结点

b1.判断p指向的结点是不是要查找的值，如果是，返回j;

b2.否则p指向下一个结点,并且j的值加一

c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息

代码描述: template int LinkList::Locate(T x)//按值查找 {

Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else { p = p->next;

j++;} } 时间复杂度：O(n)6.插入函数

自然语言描述： a.在堆中建立新结点

b.将要插入的结点的数据写入到新结点的数据域

c.修改新结点的指针域

d.修改前一个指针的指针域，使其指向新插入的结点的位置

代码描述: template void LinkList::Insert(int i,T x)//插入函数 {

Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 时间复杂度：O(n)7.按位删除函数

自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点

b.设q指向第i个元素

c.将q元素从链表中删除

d.保存q元素的数据

e.释放q元素 代码描述: template T LinkList::Delete(int i)//删除函数 { Node *p = Get(i-1);Node *q = p->next;

T x=q->data;

} p->next = q->next;delete q;return x;

8.遍历打印函数

自然语言描述: a.判断该链表是否为空链表，如果是，报错

b.如果不是空链表，新建立一个temp指针

c.将temp指针指向头结点

d.打印temp指针的data域

e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空

代码描述: template void LinkList::PrintList()//打印链表 {

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;9.获取链表长度函数

自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0

b.如果不是空链表，新建立一个temp指针，初始化整形数n为0

c.将temp指针指向头结点

d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n

e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template int LinkList::GetLength()//分析链表长度 {

} Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;4 程序运行结果

4.1主函数流程图

4.2程序运行框图

实验心得

1.调试时出现的问题及解决的方法

在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。2.心得体会

了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进

可以增加完善报错机制，增强程序的健壮性

完整源代码

#include using namespace std;

template struct Node {

};

template class LinkList { public:

};

//template //LinkList::LinkList(T a[], int n)//头插法建立 LinkList(){ front = new Node;front->next = NULL;}//无参构造函数 LinkList(T a[],int n);//构造函数 void Insert(int i,T x);//插入函数 T Delete(int i);//删除函数

Node* Get(int i);//查找第几个的元素，返回的是该元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析链表长度 ~LinkList();//析构函数 void PrintList();//打印链表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

template LinkList::LinkList(T a[], int n)//尾插法建立 {

}

template LinkList::~LinkList()//析构函数，销毁链表 {

}

template void LinkList::PrintList()//打印链表 { Node * p = front;while(p){

} front = p;p = p->next;delete front;front = new Node;front->next=NULL;Node * r = front;for(int i=0;i

} Node * s = new Node;s->data = a[i];s->next = r->next;r->next= s;r=s;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;

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;

template Node* LinkList::Get(int i)//按位查找 {

}

template int LinkList::Locate(T x)//按值查找 {

} Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else

{ } p = p->next;

j++;Node * p = front;int j=0;while(p){

} if(!p)throw“查找位置非法”;else

return p;if(j

} else break;p = p->next;j++;

template void LinkList::Insert(int i,T x)//插入函数 {

}

template T LinkList::Delete(int i)//删除函数 {

}

template int LinkList::GetLength()//分析链表长度 {

}

void main(){ Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;Node *p = Get(i-1);Node *q = p->next;p->next = q->next;delete q;return x;Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;

T x=q->data;

} int n;cout<<“将要输入的链表长度为：”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“链表的长度:”<>i;cout<<“被删除掉的元素是：”<>j;cout<<“要将其插入在哪个位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的链表是：”;a.PrintList();cout<<“要查找第几个元素：”;cin>>i;cout<<“要查找的元素为：”<data<>j;cout<<“输入的元素位置在：”<

第五篇：数据结构总结[推荐]

《数据结构与算法》课程学习总结报告

本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。

一、《数据结构与算法》知识点

第一章是这门学科的基础章节，从整体方面介绍了“数据结构和算法”，同时引入相关的学术概念和术语，如数据、数据元素、数据类型以及数据结构的定义。重点是数据结构的括逻辑结构、存储结构和运算集合的含义及其相互联系。数据结构和两大逻辑结构的4四种常用存储方法；逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。难点是算法复杂度的分析方法和性能的分析。

第二章详细地分析了顺序表。介绍了顺序表的相关概念及其有关运算。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等，在各种算法思想的先分析后，要弄清各种算法的时间复杂度与空间性能的优点和缺点，在什么特定的场合适合哪种算法思想。最后介绍了顺序串的概念，顺序串是顺序表的一个特例；区别在于组成顺序串的数据元素是一组字符，其重点在于串的模式匹配。

第三章介绍链表。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高，且在存储空间上有动态申请的优点。这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。弄清其个运算的算法思想及其时间复杂度和空间性能。最后介绍了链表之中存储结构在实际中的相关应用。

第四章，堆栈是运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；堆栈在文字处理，匹配问题和算术表达式的求值问题方面的应用。

第五章，队列是一种够类似堆栈的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进先出”的规则，对堆栈的操作只能在栈顶进行；其运算有入队、出队等操作。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。

第六章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。其中三元组和十字链表这两种结构尤为重要；对着两种结构的建立了应用要掌握。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。

第七章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序，其中关于二叉排序树和哈弗曼书的构建是重点。

第八章介绍了树。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。

第九章，散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有：散列结

构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。

最后一章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。

二、对各知识点的掌握情况

总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象，对某些具体的问题和应用仍有一些模糊与措手。各个章节出现的知识点理解和掌握情况明确一下。

第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。算法的时间、空间性能分析是重点，同样也是难点，尤其是空间性能分析需要加强。在某些强大与复杂的算法面前的处理有些棘手。

第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊。删除方面的问题比较容易些。排序问题中，由于冒泡排序在大一C语言课上已经学习过，再来学习感觉相对轻松些。对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。

第三章链表中，除对双向循环链表这一知识点理解困难之外，在对链表进行插入删除和排序相关操作上同顺序表的操作基本相当。其他的知识点像单链表的建立和基本算法等都较为熟悉。

第四章和第五章有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。在一些实际问题的应用与处理方面，对其进行存储结构的选择还是需要认真考虑的。在算法的时间复杂度和空间性能的分析仍有些困难。

第六章的学习感觉较为困难的部分在于矩阵的应用上。在矩阵的存储结构中，使用三元组表发相对较为简单，而使用十字链表就有些困难了。但在某些问题的处理上又必须或从节省空间考虑采用十字链表来处理，想矩阵的加法运算。广义表的定义还是比较容易理解的，其存储结构也不难掌握，关于应用也只局限于在多项式的表示上。

第七章是全书的重点。在这一章中概念和定义都很多，有些很昏人但都很重要，要区分开来。二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用。关于二叉排序树和的哈弗曼树却相对有些压力，其生成和对其关键字的插入和删除时重点。

第八章关于树的分析，首先要明确树和二叉树的区别，以及书中的相关定义和概念。关于二叉树、树和森林之间的转换和遍历方法是重点，但不算是难。接着就是数的存储结构的选择及转化为二叉树的算法，这部分有些吃力。再就介绍了特殊的树-B树，关于对B树的操作，插入关键字是中带领和难点。

第九章散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用C语言描述上。

最后一章，图及其应用中，相关定义及其概念很多，容易混淆，这就要慢慢来，仔细分辨。图的邻接矩阵、邻接表表示法及其之间的转换时重点和难点。而对十字链表和邻接多重表的表示法则较为陌生。感觉理解较为吃力的内容有图的遍历（包括深度和广度优先遍历），以及最小生成树的问题。最短路径、AOV网、关键路径、AOE网和拓扑排序的学习也是相对较轻松的。，三、学习体会

在学习开始，王教授就明确提出它不是一种计算机语言，不会介绍新的关键词，而是通过学习可以设计出良好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言，我深刻认识到了这一点。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。

这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。

四、对《数据结构与算法》课程教学的建议

1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。

2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。

以上便是我对《数据结构与算法》这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！