第一篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)-2-兩種基本數(shù)據(jù)結(jié)構(gòu)(數(shù)組和鏈表)-R

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)－2－兩種基本數(shù)據(jù)結(jié)構(gòu)（數(shù)組和鏈表）－RTime:2007-5-26

1：一維數(shù)組地址的計(jì)算

Loc(a[i])= Loc(a[0])+ i*k（已知一個(gè)元素占k個(gè)字節(jié)）

2：多維數(shù)組存儲(chǔ)的兩種方式

1> 行優(yōu)先

2> 列優(yōu)先

3：二維數(shù)組地址的計(jì)算：

已知a是m行n列的數(shù)組，則a[i][j]地址的計(jì)算公式： Loc(a[i][j])= Loc(a[0][0])+(i*n + j)*k

4：多維數(shù)組地址的計(jì)算：

設(shè)有n維數(shù)組a，各維的長(zhǎng)度是m1,m2,m3, … 每個(gè)元素占據(jù)k個(gè)單元，則在行優(yōu)先情況下，數(shù)組元素：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：頭結(jié)點(diǎn)

單鏈表的 第一個(gè) 結(jié)點(diǎn)

6：表頭結(jié)點(diǎn)

此結(jié)點(diǎn)存儲(chǔ)鏈表相關(guān)信息

7：循環(huán)鏈表

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;

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)－2－兩種基本數(shù)據(jù)結(jié)構(gòu)（數(shù)組和鏈表）－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 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)－2－兩種基本數(shù)據(jù)結(jié)構(gòu)（數(shù)組和鏈表）－RTime:2007-5-26 Node *recent =(*front);int count = 0;

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)－2－兩種基本數(shù)據(jù)結(jié)構(gòu)（數(shù)組和鏈表）－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《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)報(bào)告 鏈表

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華數(shù)學(xué)與計(jì)算機(jī)學(xué)院上機(jī)實(shí)踐報(bào)告

課程名稱：數(shù)據(jù)結(jié)構(gòu) 指導(dǎo)教師：唐劍梅 上機(jī)實(shí)踐名稱：

上機(jī)實(shí)踐編號(hào)：1 年級(jí)： 2011 姓名：蔣俊 學(xué)

號(hào)

：

***

上機(jī)實(shí)踐成績(jī)：

上機(jī)實(shí)踐日期：2012-11-6

上機(jī)實(shí)踐時(shí)間：8:00-9:30

一、實(shí)驗(yàn)?zāi)康?/p>

1.了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計(jì)算機(jī)內(nèi)的兩種存儲(chǔ)結(jié)構(gòu)。

2.重點(diǎn)是線性表的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；其中以鏈表的操作為側(cè)重點(diǎn)；并進(jìn)一步學(xué)習(xí)程序設(shè)計(jì)方法。

3.掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。

4.掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。

5.了解和掌握遞歸程序設(shè)計(jì)的基本原理和方法。

6.掌握使用 C++面向?qū)ο蟮某绦蛟O(shè)計(jì)技術(shù)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)源程序的方法。

二、實(shí)驗(yàn)內(nèi)容

1.熟悉前面的【程序示例2】，按照約瑟夫問題的方法2，試著不設(shè)頭結(jié)點(diǎn)改寫原來的程序，上機(jī)調(diào)試運(yùn)行。

2.用鏈表建立通訊錄。通訊錄內(nèi)容有：姓名、通訊地址、電話號(hào)碼。

要求：（1）通訊錄按姓名項(xiàng)的字母順序排列；

（2）能查找通訊錄中某人的信息；

[提示] 用鏈表來存放這個(gè)通訊錄，一個(gè)人的信息作為一個(gè)結(jié)點(diǎn)。成鏈的過程可以這樣考慮：先把頭結(jié)點(diǎn)后面的

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

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

輸入總?cè)藬?shù) n=”;cin>>n;

pre=new NodeType;

Head=new NodeType;

pre->num=1;

cout<<“n 編號(hào)”<<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 編號(hào)”<

姓名=”;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

根據(jù)m值，開始報(bào)數(shù)輸出：”<

while(q->next!=q)

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

{ for(i=1;inext;}

cout<<“編號(hào)為：”<num<<“ 的人的姓名：”<name<

cout<<“n 編號(hào)為:”<num<<“的人的密碼：”<psw<

m=q->psw;

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

q=p->next;

}

cout<<“編號(hào)為：”<num<<“的人的姓名：”<name<

cout<<“n 編號(hào)為:”<num<<“的人的密碼：”<psw<

delete q;}

int main()

{

Jose h;

h.creat();

h.outs();

return 0;}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

{ 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,“電話號(hào)碼”);} Sqlist::~Sqlist(){

NodeType *p=Head->next;

while(p!=NULL)

{Head->next=p->next;

delete p;

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

//初步建立一個(gè)通訊錄

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

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

int a;q=Head;cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號(hào)碼：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“輸入一個(gè)數(shù)。若為-1，結(jié)束輸入:”<>a;

while(a!=-1){ cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號(hào)碼：=”;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<<“輸入一個(gè)數(shù)。若為-1，結(jié)束輸入:”<>a;} } void Sqlist::Insert(ElemType x)//插入 { NodeType *p,*q,*s;s=new NodeType;

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

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<<“刪除結(jié)點(diǎn)成功”<

{ 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.初步建立一個(gè)通訊錄（單鏈表）

”;

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

cout<<“nn

2.插入新的電話記錄 ”;

cout<<“nn

3.刪除一個(gè)電話記錄”;

cout<<“nn

4.結(jié)束程序”;

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

cout<<“n

請(qǐng)輸入你的選擇(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break;

case 2:{

cout<<“n 插入的數(shù)據(jù) 姓名”;cin>>e.name;

cout<<“n 插入的數(shù)據(jù) 電話號(hào)”;cin>>e.tel;

cout<<“n 插入的數(shù)據(jù) 地址”;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;}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

const int MAXSIZE=100;

// 數(shù)組的容量 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<

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

} 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<<“請(qǐng)輸入一個(gè)正整數(shù):”<>a;cout<<“請(qǐng)輸入要轉(zhuǎn)換的進(jìn)制:”<>m;SqStack as;as.f(a,m);}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

五、總結(jié)

通過本次實(shí)驗(yàn)，我熟悉了鏈表的操作，了解了線性表在現(xiàn)實(shí)生活中的運(yùn)用，認(rèn)識(shí)了順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)這兩種結(jié)構(gòu)。本次上機(jī)實(shí)踐基本完成了實(shí)驗(yàn)內(nèi)容，但完成的不是很好，以后需要更加努力地掌握基本的知識(shí)。實(shí)驗(yàn)內(nèi)容對(duì)于隊(duì)列的運(yùn)用沒有涉及，希望以后有所涉及。

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

第三篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)總結(jié)

數(shù)據(jù)結(jié)構(gòu)與算法課程論文綜述

摘要

如何合理的組織數(shù)據(jù)、高效率的處理數(shù)據(jù)是擴(kuò)大計(jì)算機(jī)應(yīng)用領(lǐng)域、提高軟件效率的關(guān)鍵。在軟件開發(fā)過程中要求“高效地”組織數(shù)據(jù)和設(shè)計(jì)出“好的”算法，并使算法用程序來實(shí)現(xiàn)，通過調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計(jì)領(lǐng)域的專門知識(shí)。

《數(shù)據(jù)結(jié)構(gòu)與算法》課程就是主要學(xué)習(xí)在軟件開發(fā)中涉及的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用算法，在此基礎(chǔ)上，學(xué)習(xí)如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應(yīng)用問題。

課程主要內(nèi)容

本學(xué)期一共學(xué)習(xí)了十章的內(nèi)容，下面就這十章的內(nèi)容作了詳細(xì)的介紹。第一章：數(shù)據(jù)結(jié)構(gòu)與算法概述

本章主要是對(duì)數(shù)據(jù)、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法及算法分析等基本概念的掌握，而如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)正是擴(kuò)大計(jì)算機(jī)領(lǐng)域、提高軟件效率的關(guān)鍵，所以對(duì)這些概念的理解就顯得十分重要。

數(shù)據(jù)是指描述客觀事物的數(shù)值、字符、相關(guān)符號(hào)等所有能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱，其基本單位是數(shù)據(jù)元素，而數(shù)據(jù)類型是一個(gè)同類值的集合和定義在這個(gè)值集上的一組操作的總稱。在高級(jí)程序語言中定義一種數(shù)據(jù)類型時(shí)，編譯程序編譯系統(tǒng)就能獲得如下信息：（1）、一組性質(zhì)相同的值的集合；（2）、一個(gè)預(yù)訂的存儲(chǔ)體系；（3）、定義在這個(gè)值集合上的一組操作。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系，它包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、一組運(yùn)算集合；數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)方法有：順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法和散列存儲(chǔ)方法。接下來便是關(guān)于算法的有關(guān)概念，算法是為解決一個(gè)特定問題而采取的確定的有限步驟集合，它具有有窮性、確定性、可行性、輸入和輸出。關(guān)于算法的性能分析，分為時(shí)間性能分析和空間性能分析。第二章：順序表及其應(yīng)用

本章主要是對(duì)順序表、順序表的結(jié)構(gòu)、數(shù)據(jù)類型、基本算法及相關(guān)應(yīng)用的介紹。順序表是一種簡(jiǎn)單而常用的數(shù)據(jù)結(jié)構(gòu)，其應(yīng)用范圍較為廣泛，包括查找問題、排序問題、字符處理問題等內(nèi)容。第三章：鏈表及其應(yīng)用

鏈表是一種簡(jiǎn)單、常用的數(shù)據(jù)結(jié)構(gòu)，與順序表相比，具有插入、刪除結(jié)點(diǎn)不需要移動(dòng)元素，不必事先估計(jì)存儲(chǔ)空間大小等優(yōu)點(diǎn)，操作較為靈活。它有六種基本運(yùn)算：（1）、置空表（2）、求表長(zhǎng)（3)、按序號(hào)取元素（4）、按值查找

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

單鏈表即鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，用來存儲(chǔ)其直接后繼的存儲(chǔ)位置。但是這樣就使得對(duì)結(jié)點(diǎn)前面的元素的操作很困難，所以就在每個(gè)結(jié)點(diǎn)增加一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域，從而構(gòu)成雙向鏈表。同時(shí)由于每個(gè)結(jié)點(diǎn)的地址既存放在其前驅(qū)結(jié)點(diǎn)的后繼指針中，又存放在其后繼結(jié)點(diǎn)的前驅(qū)指針域中，所以雙向鏈表的插入操作分為前插和后插。第四章：堆棧及其應(yīng)用

首先要明白棧是一種受限制的線性結(jié)構(gòu)，遵守“先進(jìn)后出”的規(guī)則，其插入與刪除操作都在棧頂進(jìn)行。

其次根據(jù)順序存儲(chǔ)和鏈接存儲(chǔ)，棧分為順序棧和鏈棧。其中順序棧棧是用地址連續(xù)的存儲(chǔ)空間依次存儲(chǔ)棧中數(shù)據(jù)元素，并記錄當(dāng)前棧頂數(shù)據(jù)元素的位置；基本算法包括置空棧、判?？?、判棧滿、取棧頂元素、入棧和出棧。而鏈棧則使用鏈?zhǔn)酱鎯?chǔ)堆棧的數(shù)據(jù)元素，并記錄當(dāng)前棧頂數(shù)據(jù)元素的位置；每個(gè)結(jié)點(diǎn)包括data數(shù)據(jù)域：用來存放數(shù)據(jù)元素的值，next指針域：用來存放其直接后繼結(jié)點(diǎn)的存儲(chǔ)地址，其基本運(yùn)算和順序棧相同。

最后是關(guān)于堆棧的應(yīng)用：（1）、數(shù)值轉(zhuǎn)換問題；由于在將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)時(shí)，最先得到的余數(shù)是d進(jìn)制數(shù)的最低位，在顯示結(jié)果時(shí)需要最后輸出；而最后求得的余數(shù)是d進(jìn)制數(shù)的最高位，需要最先輸出。這與棧的“先入后出”性質(zhì)相吻合，所以可用棧來存放逐次求得的余數(shù)，然后輸出。（2）、括號(hào)匹配問題；當(dāng)讀取一個(gè)表達(dá)式時(shí)，一旦讀到括號(hào)就進(jìn)棧，而讀到下一個(gè)括號(hào)時(shí)就與棧中括號(hào)比較，若相匹配，則出棧，否則繼續(xù)讀取表達(dá)式。到最后，如果棧為空棧，則說明括號(hào)匹配，否則括號(hào)不匹配。第五章：隊(duì)列及其應(yīng)用

首先和棧一樣，要知道隊(duì)列是一種受限制的線性結(jié)構(gòu)，遵守“先進(jìn)先出”的規(guī)則，其插入在隊(duì)尾、刪除在對(duì)頭。

其次根據(jù)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，隊(duì)列也分為順序隊(duì)列和鏈隊(duì)列。其中順序隊(duì)列是用地址連續(xù)的向量空間依次存儲(chǔ)隊(duì)列中的元素，同時(shí)記錄當(dāng)前對(duì)頭元及隊(duì)尾元素在向量中的位置。然后是鏈隊(duì)列，即在存儲(chǔ)器中占用任意的、連續(xù)或不連續(xù)的物理存儲(chǔ)區(qū)域，使用動(dòng)態(tài)結(jié)點(diǎn)空間分配；在這其中，值得注意的是鏈隊(duì)列不存在隊(duì)滿的情況。

第六章：特殊矩陣、廣義表及其應(yīng)用

首先是關(guān)于矩陣的概念即存儲(chǔ)方法；

1、二維數(shù)組中元素aij的地址為：（1）、以行序?yàn)橹鞔鎯?chǔ)，Loc（aij）=Loc（a00）+[j*（m+1）+i]*d（2）、以列序?yàn)橹鞔鎯?chǔ)，Loc（aij）=Loc（a00）+[i*（n+1）+j]*d，其中m為行數(shù)、n為列數(shù)、d為每個(gè)元素所占的存儲(chǔ)單元的個(gè)數(shù)。

2、對(duì)稱矩陣：即將下三角存儲(chǔ)在一個(gè)一維數(shù)組sa[k]中，其中0≤k<(n+1)/2；當(dāng)i≥j時(shí)，k=i*（i+1）/2+j，當(dāng)i

3、三角矩陣：和對(duì)稱矩陣的存儲(chǔ)思路一樣用一維數(shù)組sa[k]存儲(chǔ)，若是上三角矩陣（下三角中元素均為常數(shù)c），則當(dāng)i≥j時(shí)，k=i*（i+1）/2+j，當(dāng)ij時(shí)，k=n*（n+1）/2

4、對(duì)角矩陣：同樣存儲(chǔ)在一維數(shù)組sa[k]中，k=2i+j

5、稀疏矩陣：即矩陣中非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)，可用三元組表存儲(chǔ)，將非零元素的值與其行號(hào)、列號(hào)存放在一起。

其次是關(guān)于廣義表的概念；廣義表是n（n≥0）個(gè)元素a1、a2、a3、?、an的有限序列，而ai或是原子或是一個(gè)廣義表，所以廣義表是遞歸定義。第七章：二叉樹及其應(yīng)用

首先關(guān)于二叉樹的概念及其性質(zhì)；二叉樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。在這其中有兩種特殊的二叉樹，滿二叉樹和完全二叉樹。同時(shí)二叉樹具有如下五個(gè)性質(zhì)：（1）、在二叉樹的第i層上至多有2（i-1）個(gè)結(jié)點(diǎn)（i>0）（2）、深度為k的二叉樹至多有2（k）-1個(gè)結(jié)點(diǎn)（k>0）（3）、對(duì)任意一棵非空二叉樹，若果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1（4）、有n個(gè)結(jié)點(diǎn)的完全二叉樹（n>0）的高度為∟log2n」+1（5）、若對(duì)滿二叉樹或完全二叉樹按照“從上到下，每層從左到右，根結(jié)點(diǎn)編號(hào)為1”的方式編號(hào)，則編號(hào)為i的結(jié)點(diǎn)，它的兩個(gè)孩子結(jié)點(diǎn)編號(hào)分別為2i和2i+1，它的父節(jié)點(diǎn)編號(hào)為i/2。

其次是二叉樹的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)和鏈接存儲(chǔ)。順序存儲(chǔ)是按在完全二叉樹中的編號(hào)順序，依次存儲(chǔ)在一維數(shù)組中。這樣的存儲(chǔ)方式可以很方便地找到任一結(jié)點(diǎn)的父結(jié)點(diǎn)及左右孩子，但對(duì)于一般的二叉樹會(huì)造成很大的空間浪費(fèi)，且在插入或刪除結(jié)點(diǎn)時(shí)需大量移動(dòng)節(jié)點(diǎn)，不利于運(yùn)算的實(shí)現(xiàn)。那么就引出了二叉樹的鏈接存儲(chǔ)，每個(gè)結(jié)點(diǎn)包括三個(gè)域，lchild指針域：記錄該結(jié)點(diǎn)左孩子的地址、rchild指針域：記錄該結(jié)點(diǎn)右孩子的地址、data域：存儲(chǔ)該結(jié)點(diǎn)的信息。

接下來是二叉樹的遍歷及線索化，不僅要能對(duì)二叉樹進(jìn)行遍歷、線索化操作，而且還要能夠根據(jù)給出的遍歷結(jié)果構(gòu)造出二叉樹。最后是二叉樹的應(yīng)用，例如哈夫曼樹：為數(shù)據(jù)壓縮提供了一種方法、二叉排序樹：即中序遍歷的結(jié)果是遞增的有序序列。

第八章：樹和森林及其應(yīng)用

首先是關(guān)于樹和森林的有關(guān)概念及存儲(chǔ)結(jié)構(gòu)；樹或森林與二叉樹之間有一個(gè)自然地一一對(duì)應(yīng)關(guān)系，任何一個(gè)森林或一棵樹可以唯一地對(duì)應(yīng)到一棵二叉樹；反之，任何一棵二叉樹也能唯一地對(duì)應(yīng)到一個(gè)森林或一棵樹。在這里，要會(huì)如何將樹或森林轉(zhuǎn)換成二叉樹、二叉樹轉(zhuǎn)換成樹或森林。對(duì)于樹的順序存儲(chǔ)結(jié)構(gòu)：雙親表示法，鏈接存儲(chǔ)結(jié)構(gòu)：（1）、孩子表示法（2）、孩子兄弟表示法，只需了解。

其次是樹和森林的遍歷，要知道樹只有先序遍歷和后序遍歷、森林只有先序遍歷和中序遍歷，且（1）、樹的先序遍歷與二叉樹的先序遍歷相同（2）、樹的后序遍歷與二叉樹的中序遍歷相同（3）、森林的先序遍歷和中序遍歷分別與二叉樹的先序遍歷和中序遍歷結(jié)果相同。

最后是樹的一個(gè)典型應(yīng)用——B樹，它是一種平衡的多路查找樹，學(xué)習(xí)是根據(jù)實(shí)例走一遍算法，理解算法即可。第九章：散列結(jié)構(gòu)及其應(yīng)用

散列結(jié)構(gòu)是以存儲(chǔ)結(jié)點(diǎn)中的關(guān)鍵字作為自變量，通過確定的函數(shù)H（即散列函數(shù)或哈希函數(shù)）進(jìn)行計(jì)算，把所求的函數(shù)值作為地址存儲(chǔ)該結(jié)點(diǎn)。

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

其次是沖突處理，由于散列函數(shù)很可能將不同的關(guān)鍵字計(jì)算出相同的散列地址，所以就需要為發(fā)生沖突的關(guān)鍵字結(jié)點(diǎn)找到一個(gè)“空”的散列地址。沖突處理的方法有

1、開放定址法：Hi=（H（key）+di）mod m，i=1,2,3，?，K（K≤m-1）例如（1）、線性探測(cè)再散列，取di=1,2,3，?，m-1（2）、二次探測(cè)再散列，取di=1（2），-1（2），2（2），-2（2），?（3）、偽隨機(jī)探測(cè)再散列，取di=偽隨機(jī)數(shù)；

2、鏈地址法：在散列表的每一個(gè)存儲(chǔ)單元中增加一個(gè)指針域，把產(chǎn)生沖突的關(guān)鍵字以鏈表結(jié)構(gòu)存放在指針指向的單元中。第十章：圖及其應(yīng)用 首先是圖的有關(guān)概念；圖是一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組表示，形式化定義為：Graph（V，VR），其中V={x|x∈dataobject}，R={VR}，VR={＜x，y＞ P（x，y）∧（x，y∈V）}。頂點(diǎn)的度、入度和出度，以頂點(diǎn)V為頭的弧的數(shù)目稱為V的入度，以頂點(diǎn)V為尾的弧的數(shù)目稱為V的出度，而出度與入度之和即為頂點(diǎn)V的度。

其次是圖的存儲(chǔ)結(jié)構(gòu)；（1）、鄰接矩陣（2)、鄰接表

最后的圖遍歷和圖的典型應(yīng)用；對(duì)于遍歷圖的深度優(yōu)先算法或廣度優(yōu)先算法、最小生成樹的普利姆算法或克魯斯卡爾算法、最短路徑的迪杰特斯拉算法和弗洛伊德算法以及有向無環(huán)圖拓?fù)渑判蛩惴ǎ夹枰鶕?jù)實(shí)例走一遍算法，從而掌握這些算法。

心得體會(huì)

最開始學(xué)習(xí)這門課時(shí)，我對(duì)它沒有很深刻的認(rèn)識(shí)，只是聽說這門課比較難。學(xué)習(xí)起來會(huì)比較累。通過這一學(xué)期的學(xué)習(xí)也確實(shí)證實(shí)了這一點(diǎn)。在學(xué)習(xí)這門課的過程中自己也確實(shí)遇到了一些問題，主要是書本上的知識(shí)與老師的講解都比較容易理解，但是當(dāng)自己利用已學(xué)的知識(shí)編寫程序時(shí)就感到非常的棘手，很多時(shí)候都是把大概的算法思想想出來后，又把書本上的程序抄寫一遍來完成程序的編寫。針對(duì)這一問題以后自己會(huì)盡量學(xué)習(xí)擺脫掉書本，自己慢慢學(xué)會(huì)獨(dú)立編寫程序。

結(jié)語

通過對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的整理和實(shí)際應(yīng)用，我深刻了解到數(shù)據(jù)結(jié)構(gòu)與算法的重要性，同時(shí)也加深了對(duì)它的認(rèn)識(shí)和了解，了解到了數(shù)據(jù)結(jié)構(gòu)與算法在生活、工作等生活各個(gè)方面的重要性和不可缺少性。我通過整理數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)而獲得的極大收獲。我相信這次的學(xué)習(xí)會(huì)對(duì)我以后的學(xué)習(xí)和工作產(chǎn)生非常大的影響力。

參考文獻(xiàn)

《數(shù)據(jù)結(jié)構(gòu)與算法》（第二版）王昆侖

李紅 主編

第四篇：北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 單鏈表

北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

實(shí)驗(yàn)名稱： 實(shí)驗(yàn)一

線性表 學(xué)生姓名：

班

級(jí)：

班內(nèi)序號(hào)：

學(xué)

號(hào)：

日

期： 2014年1月3日

實(shí)驗(yàn)?zāi)康?/p>

? 熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法 ? 學(xué)習(xí)指針、模板類、異常處理的使用 ? 掌握線性表的操作的實(shí)現(xiàn)方法 ? 學(xué)習(xí)使用線性表解決實(shí)際問題的能力 實(shí)驗(yàn)內(nèi)容

2.1題目1 根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表，并完成線性表的基本功能。

線性表存儲(chǔ)結(jié)構(gòu)（五選一）：

1、帶頭結(jié)點(diǎn)的單鏈表

2、不帶頭結(jié)點(diǎn)的單鏈表

3、循環(huán)鏈表

4、雙鏈表

5、靜態(tài)鏈表

線性表的基本功能：

1、構(gòu)造：使用頭插法、尾插法兩種方法

2、插入：要求建立的鏈表按照關(guān)鍵字從小到大有序

3、刪除

4、查找

5、獲取鏈表長(zhǎng)度

6、銷毀

7、其他：可自行定義

編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性。程序分析

3.1 存儲(chǔ)結(jié)構(gòu) 單鏈表的存儲(chǔ)結(jié)構(gòu)：

3.2 關(guān)鍵算法分析

一、關(guān)鍵算法 1.頭插法

自然語言描述：a.在堆中建立新結(jié)點(diǎn)

b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.修改新結(jié)點(diǎn)的指針域

d.修改頭結(jié)點(diǎn)的指針域,將新結(jié)點(diǎn)加入鏈表中 代碼描述： 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;時(shí)間復(fù)雜度：O(n)

2.尾插法

自然語言描述：a.在堆中建立新結(jié)點(diǎn)

b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.將新結(jié)點(diǎn)加入到鏈表中

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;時(shí)間復(fù)雜度：O(n)

3.析構(gòu)函數(shù)

自然語言描述：a.新建立一個(gè)指針，指向頭結(jié)點(diǎn)

b.移動(dòng)a中建立的指針

c.逐個(gè)釋放指針

代碼描述: template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

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

} } delete front;4.按位查找函數(shù)

自然語言描述: a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1

b.循環(huán)以下操作，直到p為空或者j等于1

b1：p指向下一個(gè)結(jié)點(diǎn)

b2：j加1

c.若p為空，說明第i個(gè)元素不存在，拋出異常

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;} 時(shí)間復(fù)雜度：O(n)

5.按值查找函數(shù)

自然語言描述：a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1

b.循環(huán)以下操作，找到這個(gè)元素或者p指向最后一個(gè)結(jié)點(diǎn)

b1.判斷p指向的結(jié)點(diǎn)是不是要查找的值，如果是，返回j;

b2.否則p指向下一個(gè)結(jié)點(diǎn),并且j的值加一

c.如果找到最后一個(gè)結(jié)點(diǎn)還沒有找到要查找的元素，返回查找失敗信息

代碼描述: 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++;} } 時(shí)間復(fù)雜度：O(n)6.插入函數(shù)

自然語言描述： a.在堆中建立新結(jié)點(diǎn)

b.將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.修改新結(jié)點(diǎn)的指針域

d.修改前一個(gè)指針的指針域，使其指向新插入的結(jié)點(diǎn)的位置

代碼描述: template void LinkList::Insert(int i,T x)//插入函數(shù) {

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

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 時(shí)間復(fù)雜度：O(n)7.按位刪除函數(shù)

自然語言描述：a.從第一個(gè)結(jié)點(diǎn)開始，查找要?jiǎng)h除的位數(shù)i前一個(gè)位置i-1的結(jié)點(diǎn)

b.設(shè)q指向第i個(gè)元素

c.將q元素從鏈表中刪除

d.保存q元素的數(shù)據(jù)

e.釋放q元素 代碼描述: template T LinkList::Delete(int i)//刪除函數(shù) { Node *p = Get(i-1);Node *q = p->next;

T x=q->data;

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

8.遍歷打印函數(shù)

自然語言描述: a.判斷該鏈表是否為空鏈表，如果是，報(bào)錯(cuò)

b.如果不是空鏈表，新建立一個(gè)temp指針

c.將temp指針指向頭結(jié)點(diǎn)

d.打印temp指針的data域

e.逐個(gè)往后移動(dòng)temp指針，直到temp指針的指向的指針的next域?yàn)榭?/p>

代碼描述: template void LinkList::PrintList()//打印鏈表 {

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

} cout<data<<' ';p = p->next;9.獲取鏈表長(zhǎng)度函數(shù)

自然語言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長(zhǎng)度0

b.如果不是空鏈表，新建立一個(gè)temp指針，初始化整形數(shù)n為0

c.將temp指針指向頭結(jié)點(diǎn)

d.判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n

e.使temp指針逐個(gè)后移，重復(fù)d操作，直到temp指針指向的結(jié)點(diǎn)的next域?yàn)?，返回n 代碼描述: template int LinkList::GetLength()//分析鏈表長(zhǎng)度 {

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

} return i-1;p = p->next;i++;4 程序運(yùn)行結(jié)果

4.1主函數(shù)流程圖

4.2程序運(yùn)行框圖

實(shí)驗(yàn)心得

1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法

在編寫按值查找函數(shù)時(shí)，由于沒有處理好指針類型的原因，導(dǎo)致指針無法正常返回，屢屢報(bào)錯(cuò)。最后意識(shí)到c++沒有指針強(qiáng)制類型的轉(zhuǎn)換機(jī)制，經(jīng)過細(xì)致檢查后才改正錯(cuò)誤使得程序正常運(yùn)行。2.心得體會(huì)

了解了單鏈表的基本的操作函數(shù)實(shí)現(xiàn)，對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有了較好的認(rèn)識(shí) 3.下一步的改進(jìn)

可以增加完善報(bào)錯(cuò)機(jī)制，增強(qiáng)程序的健壯性

完整源代碼

#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;}//無參構(gòu)造函數(shù) LinkList(T a[],int n);//構(gòu)造函數(shù) void Insert(int i,T x);//插入函數(shù) T Delete(int i);//刪除函數(shù)

Node* Get(int i);//查找第幾個(gè)的元素，返回的是該元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析鏈表長(zhǎng)度 ~LinkList();//析構(gòu)函數(shù) void PrintList();//打印鏈表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

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

}

template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

}

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)//插入函數(shù) {

}

template T LinkList::Delete(int i)//刪除函數(shù) {

}

template int LinkList::GetLength()//分析鏈表長(zhǎng)度 {

}

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<<“將要輸入的鏈表長(zhǎng)度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“鏈表的長(zhǎng)度:”<>i;cout<<“被刪除掉的元素是：”<>j;cout<<“要將其插入在哪個(gè)位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的鏈表是：”;a.PrintList();cout<<“要查找第幾個(gè)元素：”;cin>>i;cout<<“要查找的元素為：”<data<>j;cout<<“輸入的元素位置在：”<

第五篇：數(shù)據(jù)結(jié)構(gòu)總結(jié)[推薦]

《數(shù)據(jù)結(jié)構(gòu)與算法》課程學(xué)習(xí)總結(jié)報(bào)告

本學(xué)期開設(shè)的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落，現(xiàn)就其知識(shí)點(diǎn)及其掌握情況、學(xué)習(xí)體會(huì)以及對(duì)該門課程的教學(xué)建議等方面進(jìn)行學(xué)習(xí)總結(jié)。

一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識(shí)點(diǎn)

第一章是這門學(xué)科的基礎(chǔ)章節(jié)，從整體方面介紹了“數(shù)據(jù)結(jié)構(gòu)和算法”，同時(shí)引入相關(guān)的學(xué)術(shù)概念和術(shù)語，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)的括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合的含義及其相互聯(lián)系。數(shù)據(jù)結(jié)構(gòu)和兩大邏輯結(jié)構(gòu)的4四種常用存儲(chǔ)方法；邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)和散列存儲(chǔ)四類。難點(diǎn)是算法復(fù)雜度的分析方法和性能的分析。

第二章詳細(xì)地分析了順序表。介紹了順序表的相關(guān)概念及其有關(guān)運(yùn)算?；具\(yùn)算有：初始化表、求表長(zhǎng)、排序、元素的查找、插入及刪除等。元素查找方法有：簡(jiǎn)單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等，在各種算法思想的先分析后，要弄清各種算法的時(shí)間復(fù)雜度與空間性能的優(yōu)點(diǎn)和缺點(diǎn)，在什么特定的場(chǎng)合適合哪種算法思想。最后介紹了順序串的概念，順序串是順序表的一個(gè)特例；區(qū)別在于組成順序串的數(shù)據(jù)元素是一組字符，其重點(diǎn)在于串的模式匹配。

第三章介紹鏈表。鏈表中數(shù)據(jù)元素的存儲(chǔ)不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲(chǔ)區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動(dòng)元素，給算法的效率帶來較大的提高，且在存儲(chǔ)空間上有動(dòng)態(tài)申請(qǐng)的優(yōu)點(diǎn)。這一章中介紹了鏈表的節(jié)點(diǎn)結(jié)構(gòu)、靜態(tài)與動(dòng)態(tài)鏈表的概念、鏈表的基本運(yùn)算（如求表長(zhǎng)、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。弄清其個(gè)運(yùn)算的算法思想及其時(shí)間復(fù)雜度和空間性能。最后介紹了鏈表之中存儲(chǔ)結(jié)構(gòu)在實(shí)際中的相關(guān)應(yīng)用。

第四章，堆棧是運(yùn)算受限制的線性結(jié)構(gòu)。其基本運(yùn)算方法與順序表和鏈表運(yùn)算方法基本相同，不同的是堆棧須遵循“先進(jìn)后出”的規(guī)則，對(duì)堆棧的操作只能在棧頂進(jìn)行；堆棧在文字處理，匹配問題和算術(shù)表達(dá)式的求值問題方面的應(yīng)用。

第五章，隊(duì)列是一種夠類似堆棧的線性結(jié)構(gòu)。其基本運(yùn)算方法與順序表和鏈表運(yùn)算方法基本相同，不同的是堆棧須遵循“先進(jìn)先出”的規(guī)則，對(duì)堆棧的操作只能在棧頂進(jìn)行；其運(yùn)算有入隊(duì)、出隊(duì)等操作。在介紹隊(duì)列時(shí)，提出了循環(huán)隊(duì)列的概念，以避免“假溢出”的現(xiàn)象。

第六章介紹了特殊矩陣和廣義表的概念與應(yīng)用。其中，特殊矩陣包括對(duì)稱矩陣、三角矩陣、對(duì)角矩陣和稀疏矩陣，書中分別詳細(xì)介紹了它們的存儲(chǔ)結(jié)構(gòu)。其中三元組和十字鏈表這兩種結(jié)構(gòu)尤為重要；對(duì)著兩種結(jié)構(gòu)的建立了應(yīng)用要掌握。稀疏矩陣的應(yīng)用包括轉(zhuǎn)置和加法運(yùn)算等。最后介紹了廣義表的相關(guān)概念及存儲(chǔ)結(jié)構(gòu)，關(guān)于它的應(yīng)用，課本中舉了m元多項(xiàng)式的表示問題。

第七章二叉樹的知識(shí)是重點(diǎn)內(nèi)容。在介紹有關(guān)概念時(shí)，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲(chǔ)和鏈接存儲(chǔ)以及生成算法。重點(diǎn)介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應(yīng)用：基本算法、哈弗曼樹、二叉排序樹和堆排序，其中關(guān)于二叉排序樹和哈弗曼書的構(gòu)建是重點(diǎn)。

第八章介紹了樹。樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲(chǔ)結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。

第九章，散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識(shí)點(diǎn)有：散列結(jié)

構(gòu)的概念及其存儲(chǔ)結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測(cè)散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。

最后一章介紹了圖的概念及其應(yīng)用，是本書的難點(diǎn)。圖的存儲(chǔ)結(jié)構(gòu)的知識(shí)點(diǎn)有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識(shí)點(diǎn)有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點(diǎn)理解AOV網(wǎng)和拓?fù)渑判蚣捌渌惴ā?/p>

二、對(duì)各知識(shí)點(diǎn)的掌握情況

總體來看，對(duì)教材中的知識(shí)點(diǎn)理解較為完善，但各個(gè)章節(jié)均出現(xiàn)有個(gè)別知識(shí)點(diǎn)較為陌生的現(xiàn)象，對(duì)某些具體的問題和應(yīng)用仍有一些模糊與措手。各個(gè)章節(jié)出現(xiàn)的知識(shí)點(diǎn)理解和掌握情況明確一下。

第一章中我對(duì)數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹，熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。算法的時(shí)間、空間性能分析是重點(diǎn)，同樣也是難點(diǎn)，尤其是空間性能分析需要加強(qiáng)。在某些強(qiáng)大與復(fù)雜的算法面前的處理有些棘手。

第二章，順序表的概念、生成算法理解較為清晰，并且熟悉簡(jiǎn)單順序查找和二分查找，對(duì)分塊查找較為含糊。刪除方面的問題比較容易些。排序問題中，由于冒泡排序在大一C語言課上已經(jīng)學(xué)習(xí)過，再來學(xué)習(xí)感覺相對(duì)輕松些。對(duì)插入排序和選擇排序理解良好，但是，在實(shí)際運(yùn)用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習(xí)中感覺較吃力，現(xiàn)在對(duì)這種排序方法仍然非常模糊，所以需要花較多的時(shí)間來補(bǔ)習(xí)。此外串的模式匹配也是較難理解的一個(gè)地方。

第三章鏈表中，除對(duì)雙向循環(huán)鏈表這一知識(shí)點(diǎn)理解困難之外，在對(duì)鏈表進(jìn)行插入刪除和排序相關(guān)操作上同順序表的操作基本相當(dāng)。其他的知識(shí)點(diǎn)像單鏈表的建立和基本算法等都較為熟悉。

第四章和第五章有關(guān)堆棧以及隊(duì)列的知識(shí)點(diǎn)比較少，除有關(guān)算法較為特殊以外，其余算法都是先前學(xué)過的順序表和鏈表的知識(shí)，加上思想上較為重視，因此這部分內(nèi)容是我對(duì)全書掌握最好的一部分。在一些實(shí)際問題的應(yīng)用與處理方面，對(duì)其進(jìn)行存儲(chǔ)結(jié)構(gòu)的選擇還是需要認(rèn)真考慮的。在算法的時(shí)間復(fù)雜度和空間性能的分析仍有些困難。

第六章的學(xué)習(xí)感覺較為困難的部分在于矩陣的應(yīng)用上。在矩陣的存儲(chǔ)結(jié)構(gòu)中，使用三元組表發(fā)相對(duì)較為簡(jiǎn)單，而使用十字鏈表就有些困難了。但在某些問題的處理上又必須或從節(jié)省空間考慮采用十字鏈表來處理，想矩陣的加法運(yùn)算。廣義表的定義還是比較容易理解的，其存儲(chǔ)結(jié)構(gòu)也不難掌握，關(guān)于應(yīng)用也只局限于在多項(xiàng)式的表示上。

第七章是全書的重點(diǎn)。在這一章中概念和定義都很多，有些很昏人但都很重要，要區(qū)分開來。二叉樹的性質(zhì)容易懂卻很難記憶。對(duì)二叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好，能夠熟練運(yùn)用。關(guān)于二叉排序樹和的哈弗曼樹卻相對(duì)有些壓力，其生成和對(duì)其關(guān)鍵字的插入和刪除時(shí)重點(diǎn)。

第八章關(guān)于樹的分析，首先要明確樹和二叉樹的區(qū)別，以及書中的相關(guān)定義和概念。關(guān)于二叉樹、樹和森林之間的轉(zhuǎn)換和遍歷方法是重點(diǎn)，但不算是難。接著就是數(shù)的存儲(chǔ)結(jié)構(gòu)的選擇及轉(zhuǎn)化為二叉樹的算法，這部分有些吃力。再就介紹了特殊的樹-B樹，關(guān)于對(duì)B樹的操作，插入關(guān)鍵字是中帶領(lǐng)和難點(diǎn)。

第九章散列結(jié)構(gòu)這一章理解比較完善的知識(shí)點(diǎn)有：基本概念和存儲(chǔ)結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學(xué)得比較扎實(shí)，對(duì)數(shù)字分析法等方法則感覺較為陌生。對(duì)兩種沖突處理的算法思想的理解良好，問題在于用C語言描述上。

最后一章，圖及其應(yīng)用中，相關(guān)定義及其概念很多，容易混淆，這就要慢慢來，仔細(xì)分辨。圖的鄰接矩陣、鄰接表表示法及其之間的轉(zhuǎn)換時(shí)重點(diǎn)和難點(diǎn)。而對(duì)十字鏈表和鄰接多重表的表示法則較為陌生。感覺理解較為吃力的內(nèi)容有圖的遍歷（包括深度和廣度優(yōu)先遍歷），以及最小生成樹的問題。最短路徑、AOV網(wǎng)、關(guān)鍵路徑、AOE網(wǎng)和拓?fù)渑判虻膶W(xué)習(xí)也是相對(duì)較輕松的。，三、學(xué)習(xí)體會(huì)

在學(xué)習(xí)開始，王教授就明確提出它不是一種計(jì)算機(jī)語言，不會(huì)介紹新的關(guān)鍵詞，而是通過學(xué)習(xí)可以設(shè)計(jì)出良好的算法，高效地組織數(shù)據(jù)。一個(gè)程序無論采用何種語言，其基本算法思想不會(huì)改變。聯(lián)系到在大一和大二上學(xué)期學(xué)習(xí)的C和C++語言，我深刻認(rèn)識(shí)到了這一點(diǎn)?！败浖_發(fā)好比寫作文，計(jì)算機(jī)語言提供了許多華麗的辭藻，而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來?！痹趯W(xué)習(xí)這門課中，要熟悉對(duì)算法思想的一些描述手段，包括文字描述、圖形描述和計(jì)算機(jī)語言描述等。因此，計(jì)算機(jī)語言基礎(chǔ)是必須的，因?yàn)樗峁┝艘环N重要的算法思想描述手段——機(jī)器可識(shí)別的描述。

這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上的知識(shí)與老師的講解都比較容易理解，但是當(dāng)自己采用剛學(xué)的知識(shí)點(diǎn)編寫程序時(shí)卻感到十分棘手，有時(shí)表現(xiàn)在想不到適合題意的算法，有時(shí)表現(xiàn)在算法想出來后，只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。針對(duì)這一情況，我會(huì)嚴(yán)格要求自己，熟練掌握算法思想，盡量獨(dú)立完成程序的編寫與修改工作，只有這樣，才能夠提高運(yùn)用知識(shí)，解決問題的能力。

四、對(duì)《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)的建議

1、建議在上課過程中加大隨堂練習(xí)的分量，以便學(xué)生能當(dāng)堂消化課堂上學(xué)習(xí)的知識(shí)，也便于及時(shí)了解學(xué)生對(duì)知識(shí)點(diǎn)的掌握情況，同時(shí)有助于學(xué)生保持良好的精神狀態(tài)。

2、建議在課時(shí)允許的情況下，增加習(xí)題課的分量，通過課堂的習(xí)題講解，加深對(duì)知識(shí)點(diǎn)的掌握，同時(shí)對(duì)各知識(shí)點(diǎn)的運(yùn)用有一個(gè)更為直觀和具體的認(rèn)識(shí)。

以上便是我對(duì)《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學(xué)習(xí)總結(jié)，我會(huì)抓緊時(shí)間將沒有吃透的知識(shí)點(diǎn)補(bǔ)齊。今后我仍然會(huì)繼續(xù)學(xué)習(xí)，克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進(jìn)！