第一篇：《數據結構》實驗教學大綱
《數據結構》實驗教學大綱
實驗1 線性表的基本操作
1實驗目的
(1)熟練掌握線性表的邏輯特征。
（2）熟練掌握線性表的基本操作在兩種存儲結構上的實現。2實驗內容
（1）設計一個順序表的基本操作的演示程序（2）設計一個單鏈表的基本操作的演示程序（3）設計一個雙鏈表的基本操作的演示程序 【基本要求】
實現下列4種基本運算：（1）初始化線性表；（2）在第I個元素前插入一個元素e；（3）刪除第I個元素；（4）遍歷線性表；（5）將單鏈表逆置
【測試數據】自定 參考程序如下： //順序表的基本操作 #include
typedef struct{
int elem[MAX];
int length;}Sqlist;
void Initlist_sq(Sqlist &L);void ListInsert_sq(Sqlist &L,int i, int e);void ListDel_sq(Sqlist &L,int i, int &e);void print_sq(Sqlist L);
// 函數的定義
void Initlist_sq(Sqlist &L){
L.length =0;}
void ListInsert_sq(Sqlist &L,int i, int e){
int *p,*q;if(i<1||i>L.length +1)return;
q=&L.elem[i-1];//插入位置
for(p=&L.elem[L.length-1];p>=q;--p)
*(p+1)=*p;*q=e;++L.length;return;} void ListDel_sq(Sqlist &L,int i, int &e){
if(i<1||i>L.length)return;e=L.elem[i-1];
for(int j=i;j L.elem[j-1]=L.elem[j];--L.length;} void print_sq(Sqlist L){ int *p,*q=L.elem+L.length-1;for(p=L.elem;p<=q;p++) cout<<*p<<' ';cout<<“n”;} void main(){ int a[11]={10,20,30,40,50,60,70,80,90,100};Sqlist L; //初始化順序表 Initlist_sq(L);cout<<“現在的表長： ”< // 插入10個數據元素 for(int i=1;i<=10;++i) ListInsert_sq(L, i, a[i-1]); cout<<“插入10個元素后的線性表：”< //遍歷 print_sq(L); cout<<“現在的表長： ”< //刪除第5個元素 int x; ListDel_sq(L,5, x); cout<<“刪除的元素值是：”< cout<<“刪除第5個元素后的表：”< print_sq(L); cout<<“現在的表長： ”< // 單鏈表的操作 #include int data;NODE *next;}; void print(NODE *&head);//遍歷 int data[6]={25,41,17,98,5,6};void Setup_L(NODE *&head,int n);//生成單鏈表 void Insert_L(NODE *&head, int I, int e);//插入 void Delete_L(NODE * &head, int I,int &e);//刪除 void Convert_L(NODE *&head)； //逆序 void main() { NODE *L; Setup_L(L,6);print(L);//Insert_L(L,7,50);print(L);int x;Delete_L(L,0,x);cout<<“X=”< print(L);Convert_L(L);print(L); } void print(NODE *&head){ NODE *p;p=head->next; while(p){ cout< data<<“, ”;//輸出元素值 p=p->next;//后移指針 } cout< NODE *q,*p;head=(NODE*)new NODE; head->next=NULL;//先建立一個帶頭結點的單鏈表 q=head; for(int i=0;i p=(NODE *)new NODE;//生成新結點 p->data=data[i]; q->next=p;q=p;//插入到表頭 } q->next =NULL;} void Insert_L(NODE *&L,int i, int e){ NODE *p=L,*q;int j=0;while(p&&j j++; } if(!p||j>i-1){ cout<<“插入值超出范圍！”< return;} q=(NODE*)new NODE;q->data=e;q->next =p->next;p->next =q;} void Delete_L(NODE *&L,int i,int &e){ NODE *p=L,*q;int j=0;while(p&&j j++; } if(!p||j>i-1){ cout<<“刪除值超出范圍！”< return;} q=p->next;e=q->data;p->next =q->next;delete q;} void Convert_L(NODE *&L){ NODE *p,*q,*r;p=L->next; q=p->next;p->next =NULL;while(q){ r=q->next; q->next =p; L->next=q; p=q; q=r; } } //雙鏈表的基本操作 struct NODE { int data;NODE *next;NODE *prior;};int data[6]={3,5,7,19,20,21};//測試用數據 // 函數聲明 void print(NODE *&head);void Setup_L(NODE*&head,int n);void Insert_L(NODE *&L,int i,int e);void Delete_L(NODE *&L,int i,int &e);void Convert_L(NODE*&L);// 主函數和各函數的定義 void main(){ NODE *L;Setup_L(L,6);print(L);Insert_L(L,7,50);print(L);int x;Delete_L(L,1,x);cout<<“X=”< NODE *p;p=head->next;while(p){cout< data<<“,”;p=p->next;} cout< NODE *q,*p;head=(NODE*)new NODE;head->next=NULL;q=head;for(int i=0;i p=(NODE*)new NODE; p->data=data[i]; //cin>>p->data; p->prior=q;q->next=p;q=p;} q->next=NULL;//return(head);} void Insert_L(NODE *&L,int i,int e){//在帶頭結點的雙鏈表中第i個位置插入元素e NODE*p=L,*q;int j=0;//j為計數器 while(p&&j if(!p||j>i-1)//i小于1或大于表長 {cout<<“插入值超出范圍!”< q->data=e;if(p->next==NULL){q->next=p->next;p->prior=q;p->next=q;} else {q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;} //插入L中 } void Delete_L(NODE*&L,int i,int &e){//在帶頭結點的雙鏈表L中，刪除第i個元素，并由e返回其值 NODE *p=L,*q;int j=0;while(p&&j {p=p->next;j++;} if(!p||j>i-1){cout<<“刪除值超出范圍!”< return;} q=p->next;e=q->data;q->next->prior=p;p->next=q->next;delete q;}//刪除并釋放結點 3 實驗要求 按要求編寫實驗程序，將實驗程序上機調試運行，并提交實驗報告。 實驗2 棧和隊列的基本操作 1實驗目的 (1)(2)(3)(4) 深入了解棧和隊列的基本特性 熟練掌握棧的基本操作在兩種存儲結構上的實現。熟練掌握循環隊列的基本操作 熟練掌握鏈隊列的基本操作 2實驗內容 （1）設計一個順序棧的基本操作的演示程序（2）設計一個鏈棧的基本操作的演示程序（3）設計一個循環隊列的基本操作的演示程序（4）設計一個鏈隊列的基本操作的演示程序 【基本要求】 實現下列6種基本運算：（1）初始化；（2）入棧（隊列）；（3）出棧（隊列）；（4）遍歷；（5）求棧（隊列）的長度 【測試數據】自定 參考程序如下： //順序棧的基本操作 #include int base; int top; int st[MAX];}SqStack; //基本操作說明 void InitStack(SqStack &S);void push(SqStack &S, int e);void pop(SqStack &S,int &e); //基本操作的算法描述 void InitStack(SqStack &S){ S.base=S.top=0;} void push(SqStack &S, int e){ if(S.top==MAX) {cout<<”棧滿n”; return;} S.st[S.top] =e;S.top+=1;} void pop(SqStack &S,int &e){ if(S.top ==0) { cout<<”棧空n”;return;} S.top-=1; e=S.st[S.top];} void print(SqStack S){ cout<<”棧的各個元素如下：n”; for(int I=0;I cout< “; cout< void main(){ SqStack S; //初始化 cout<<”初始化棧n”;InitStack(S);cout<<”棧底和棧頂：”< cout<<”5個元素入棧n”; for(int I=0;I<5;I++){ push(S, 2*I+1); cout<<”棧頂為：”< int x;pop(S,x);cout<<”出棧元素為：”< } //循環隊列的基本操作 #include /*********** 初始化 **************/ void InitQueue(SqQueue &Q) { Q.front=Q.rear=0;} //******求隊列長度******// int QueueLength(SqQueue Q){ return(Q.rear-Q.front+MAX)%MAX;} //*****入隊列****************// void EnQueue(SqQueue &Q,int e){ if((Q.rear+1)%MAX==Q.front) cout<<”隊列滿！”< else { Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX;} } //*******遍歷隊列******// void traverse(SqQueue &Q){ int I, k; if(Q.front<=Q.rear) k=0; else k=1; switch(k) { case 0: for(I=Q.front;I cout< “; break; case 1: for(I=Q.front;I cout< “; for(I=0;I cout< } } /**************出隊************/ int DeQueue(SqQueue &Q,int &e){ if(Q.rear==Q.front)return –1; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX; return 1;} void main(){ SqQueue Q; InitQueue(Q);int j,m,x;for(j=0;j<7;j++) EnQueue(Q,2*j);traverse(Q);m=QueueLength(Q);cout<<”n長度”< “; m=QueueLength(Q);cout<<”n長度”< 按要求編寫實驗程序，將實驗程序上機調試運行，并提交實驗報告。 實驗3 二叉樹的基本操作 1實驗目的 （1）掌握二叉樹的非線性和遞歸特點。（2）熟練掌握二叉樹的存儲結構。 （3）熟練掌握二叉樹的各種遍歷操作和其它操作的實現方法。2 實驗內容 設計一個可進行二叉樹基本操作的演示程序。【基本要求】 實現下列六種基本運算：（1）創建二叉樹；（2）先序遍歷二叉樹；（3）中序遍歷二叉樹；（4）后序遍歷二叉樹；（5）層序遍歷二叉樹；（6）求度為1的結點的個數；（7）求葉子結點的個數；（8）求度為2的結點的個數。 二叉樹以鏈式結構表示，主程序以菜單方式的用戶界面。【測試數據】自定 //二叉樹的基本操作 #include typedef struct node //定義結點 { char data; struct node *lchild, *rchild;} BinTNode; typedef BinTNode *BinTree;//定義二叉樹 void CreateBinTree(BinTree &T); //先序創建二叉樹 void PreOrder(BinTree T); //先序遍歷二叉樹 void InOrder(BinTree T); //中序遍歷二叉樹 void PostOrder(BinTree T); //后序遍歷二叉樹 int onechild(BinTree T); //求度為1的結點的個數 int leafs(BinTree T); //求葉子結點的個數 int twochild(BinTree T); //度為2的結點的個數 void translevel(BinTree b) //層序遍歷二叉樹 void main(){ int n; BinTree T; char ch1,ch2; cout<<“Welcome to enter the testing program for bintree basic operator”< cout<<“Please Chose”< ch1='y'; while(ch1=='y'||ch1=='Y') { cout<<“A--------building n”; cout<<“B------PreOrdern”; cout<<“C------InOrdern”; cout<<“D-------PostOrdern”; cout<<”E-------transleveln”; cout<<“ F------onechildn”; cout<<“G-----twochildn”; cout<<“ H------leafsn”; cout<<“X-------Quitn”; cin>>ch2; switch(ch2) { case 'a': case 'A': cout<<“請輸入按先序建立二叉樹的結點序列：n”; CreateBinTree(T); break; case 'b': case 'B': cout<<“二叉樹的先序遍歷序列：n”; PreOrder(T); break; case 'c': case 'C': cout<<“二叉樹的中序遍歷序列：n”; InOrder(T); break; case 'd': case 'D': cout<<“二叉樹的后序遍歷序列：n”; PostOrder(T); break; case 'f': case 'F': cout<<“二叉樹的單孩子結點數：n”; n=onechild(T); cout< break; case 'g': case 'G': cout<<“二叉樹的雙孩子結點數：n”; n=twochild(T); cout< break; case 'h': case 'H': cout<<“二叉樹的葉子結點數：n”; n=leafs(T); cout< break;case ?e?: case ?E?: cout<<“二叉樹的層序遍歷序列：n”; translevel(T); break; case 'x': case 'X': ch1='x'; break; } } } void CreateBinTree(BinTree &T){ char ch; cin>>ch; if(ch=='0') T=NULL; else { T=(BinTNode *)new BinTNode; T->data=ch; CreateBinTree(T->lchild); CreateBinTree(T->rchild); } } void InOrder(BinTree T){ if(T){ InOrder(T->lchild); cout< InOrder(T->rchild); } } void PostOrder(BinTree T){ if(T){ PostOrder(T->lchild); PostOrder(T->rchild); cout< void PreOrder(BinTree T){ if(T){ cout< PreOrder(T->lchild); PreOrder(T->rchild);} } //層序遍歷二叉樹 //采用一個隊列q，先將二叉樹的根 結點入隊列，然后退隊列，輸出該結點，若它有左子樹，便將左子樹根結點入隊列，若它有右子樹，便將右子樹根結點入隊列，如此直到隊列空為止。 因為隊列的特點是先進先出，從而達到按層序遍歷的目的。 #define MAXLEN 100 void translevel(BinTree b){ struct node { BinTree vec[MAXLEN]; int f, r;}q;//定義隊列q，f 表示隊頭指針，r隊尾指針 q.f=0; //置隊列為空隊列 q.r=0; if(b!=NULL)cout<< b->data<<” “;q.vec[q.r]=b; //結點指針進入隊列 q.r=q.r+1; //隊尾指針后移 while(q.f //隊列不為空 { b=q.vec[q.r]; //隊頭出隊列 q.f=q.f+1;if(b->lchild!=NULL) //輸出左孩子，并入隊列 { cout<< b->lchild->data<<” “; q.vec[q.r]=b->lchild; q.r=q.r+1;} if(b->rchild!=NULL) //輸出右孩子，并入隊列 { cout<< b->rchild->data<<” “; q.vec[q.r]=b->rchild; q.r=q.r+1;} } } int onechild(BinTree T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild ==NULL && T->rchild!=NULL||T->lchild!=NULL && T->rchild==NULL) return 1;else { num1=onechild(T->lchild); num2=onechild(T->rchild); return num1+num2; } } int leafs(BinTree T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild==NULL &&T->rchild ==NULL)return 1;else { num1=leafs(T->lchild); num2=leafs(T->rchild); return num1+num2;} } 3 實驗要求 按要求編寫實驗程序，將實驗程序上機調試運行，并提交實驗報告。 實驗4 哈夫曼樹及哈夫曼編碼 1實驗目的 （1）熟練掌握哈夫曼樹的特點。（2）熟悉哈夫曼樹的構造方法 實驗內容 哈夫曼算法 3 實驗要求 按要求編寫實驗程序，將實驗程序上機調試運行，并提交實驗報告。參考代碼： #include int weight; int parent,lchild,rchild;}huffnode;typedef struct { char cd[MAX];int start;}huffcode; void main(){ huffnode ht[2*MAX];huffcode hcd[MAX],d;int i, k,f ,l,r, n,c,m1,m2;printf(“元素個數:”); cout< for(i=1;i<=n;i++){ cout<<“第”< cin>>ht[i].data);cout<<“t權重:”;cout< ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=n+1;i<=2*n-1;i++){ m1=m2=32767; l=r=0; for(k=1;k<=i-1;k++) if(ht[k].parent==0) if(ht[k].weight { m2=m1; r=1; } m1=ht[k].weight; l=k; } else if(ht[k].weight { m2=ht[k].weight; r=k; } ht[l].parent=i; ht[r].parent=i; ht[i].weight=ht[l].weight+ht[r].weight; ht[i].lchild=l; ht[i].rchild=r;} for(i=1;i<=n;i++){ d.start=n+1;c=i;f=ht[i].parent;while(f!=0){ if(ht[f].lchild==c) d.cd[--d.start]='0'; else d.cd[--d.start]='1'; c=f; f=ht[f].parent;} hcd[i]=d;} cout<<“輸出哈夫曼編碼:n”;for(i=1;i<=n;i++){ cout< for(k=hcd[i].start;k<=n;k++) cout< 實驗5 圖的基本操作 1實驗目的 （3）熟練掌握圖的非線性結構的特點。 （4）掌握圖的鄰接矩陣和鄰接表的存儲結構。 （5）掌握圖的兩種常用存儲結構下的深度優先搜索和廣度優先搜索操作和其它操作的實現 2 實驗內容 (1)設計一個基于圖的鄰接矩陣的圖的基本操作的演示程序。(2)設計一個基于圖的鄰接表的圖的基本操作的演示程序。【基本要求】 實現下列六種基本運算：（1）創建圖；（2）深度優先遍歷圖；（3）廣度優先遍歷圖；（4）轉換圖的存儲結構 分別在圖的鄰接矩陣和鄰接表的存儲結構實現 【測試數據】自定 參考程序如下： //圖的鄰接矩陣的基本操作 #define MAX_VERTEX_NUM 20 typedef struct ArcCell { int adj;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct { int vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;//鄰接矩陣圖的定義 typedef struct ArcNode{ int adjvex;struct ArcNode *next;}ArcNode;typedef struct VNode{ int data;ArcNode *first;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ AdjList vertices;int vexnum,arcnum;}ALGraph; //圖的鄰接表的定義 bool visited[MAX_VERTEX_NUM];void CreateUDG(MGraph &G);void printMGraph(MGraph G);void DFSTraverse(MGraph G);void DFSM(MGraph G,int i);void BDFTraverse(MGraph G);void change(ALGraph &R,MGraph G);void printALGraph(ALGraph R); void main(){ MGraph G;ALGraph R;cout<<“Building the Graphn”; CreateUDG(G);cout<<“Output the Matrixn”;printMGraph(G);DFSTraverse(G); BDFTraverse(G); change(R,G);printALGraph(R);} void CreateUDG(MGraph &G){ int v1,v2; int i,j,k;cout<<“圖的頂點數和圖的邊數：”; cin>>G.vexnum >>G.arcnum; cout<<“輸入頂點編號(從1開始）n”; for(i=0;i cin>>G.vexs[i]; for(i=0;i for(j=0;j G.arcs[i][j].adj=0;for(k=0;k cout<<“輸入第”< cin>>v1>>v2; i=v1-1; j=v2-1; G.arcs[i][j].adj=1; G.arcs[j][i].adj=G.arcs[i][j].adj;}} void printMGraph(MGraph G){ int i,j;cout<<“n”;for(i=0;i for(j=0;j {cout< ”; if((1+j)%G.vexnum ==0) cout<<“n”;} } void DFSM(MGraph G,int i){ int j;cout<<“visit vertex ”< if(G.arcs[i][j].adj==1 &&!visited[j]) DFSM(G,j);} void DFSTraverse(MGraph G){ int i; for(i=0;i visited[i]=0; for(i=0;i if(!visited[i]) DFSM(G,i);} void change(ALGraph &R,MGraph G){ int i,j;ArcNode *p;R.arcnum =G.arcnum;R.vexnum =G.vexnum;for(i=0;i R.vertices[i].data=G.vexs[i]; R.vertices[i].first =NULL;} for(i=0;i for(j=0;j if(G.arcs[i][j].adj ==1) { p= new ArcNode; p->adjvex =j; p->next =R.vertices[i].first; R.vertices[i].first =p; } } void printALGraph(ALGraph R){ int i; ArcNode *p; for(i=0;i { cout< p=R.vertices[i].first; while(p!=NULL) { cout<<“->”< adjvex+1; p=p->next; } cout< void BDFTraverse(MGraph G){ int queue[MAX_VERTEX_NUM]; int front=0,rear=0; int j,v; cout<<“廣度優先遍歷序列：”< for(v=0;v visited[v]=0; //初始頂點為 1 v=0; visited[v]=1; cout<<“visited vertex”< queue[rear]=v;//入隊 rear=(rear+1)%MAX_VERTEX_NUM; while(front!=rear){ v=queue[front]; front=(front+1)% MAX_VERTEX_NUM;//出隊 //訪問與v鄰接的頂點 for(j=0;j if(G.arcs[v][j].adj==1 &&!visited[j]) { queue[rear]=j;//入隊 rear=(rear+1)%MAX_VERTEX_NUM; cout<<“visited vertex”< visited[j]=1; } } } //基于鄰接表的圖的基本操作 #include #define MAX_VERTEX_NUM 10 //最大頂點數 #define NULL 0 typedef enum{FALSE,TRUE} Boolean; //false表示0，TRUE表示1 typedef struct ArcNode //弧結點類型 { int adjvex; //以i為頂點（弧尾）的另一個頂點j在表頭數組中的位置 struct ArcNode *nextarc; //指向下一條弧的指針 }ArcNode;typedef struct VNode //表頭結點頂點類型 { int data; //頂點 i的數據，按編號，從1開始。 ArcNode *firstarc;//該頂點的第一條弧指針 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //鄰接表圖 { AdjList vertices; int vexnum,arcnum;}ALGraph; typedef struct ArcCell { int adj;}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct { int vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;//鄰接矩陣圖的定義 Boolean visited[MAX_VERTEX_NUM];//訪問數組 void CreateALGraph(ALGraph *G) //創建圖 { ArcNode *s; int i,j,k; cout<<“Please enter the number of 頂點和邊數n”; //對于有向圖指弧的數目，對無向圖邊數為弧的2倍 cin>>G->vexnum>>G->arcnum; cout<<“請輸入”< for(i=0;i { cin>>G->vertices[i].data; G->vertices[i].firstarc =NULL; } cout<<“請輸入”< for(k=0;k { cout<<“輸入邊的頂點號”< cin>>i>>j; s=(ArcNode *)new ArcNode; s->adjvex =j-1; s->nextarc =G->vertices [i-1].firstarc; G->vertices[i-1].firstarc =s; } } void BFS(ALGraph *G,int k) //寬度優先搜索 { for(int v=0;v visited[v]=FALSE;ArcNode *p;int i,Q[MAX_VERTEX_NUM],front,rear;front=rear=0;cout<<“廣度優先搜索鄰接表圖”< while(front!=rear){ i=Q[front]; front=(front+1)%MAX; p=G->vertices[i].firstarc; while(p) { if(!visited[p->adjvex]) { cout< visited[p->adjvex]=TRUE; Q[rear]=p->adjvex; rear=(rear+1)%MAX; } p=p->nextarc; } } } void DFS(ALGraph *G,int v); void DFSTraverse(ALGraph *G)//深度優先搜索 { int i; for(i=0;i visited[i]=FALSE;cout<<“深度優先搜索頂點序列”; for(i=0;i if(!visited[i])DFS(G,i);} void DFS(ALGraph *G,int v){ cout< visited[v]=TRUE; ArcNode *p; p=G->vertices[v].firstarc; while(p) { if(!visited[p->adjvex])DFS(G,p->adjvex); p=p->nextarc; } } void change(ALGraph G,MGraph &M){ M.arcnum=G.arcnum; M.vexnum=G.vexnum; int i,j; ArcNode *p; for(i=0;i for(j=0;j M.arcs[i][j].adj =0; for(i=0;i { p=G.vertices[i].firstarc; while(p) { j=p->adjvex; M.arcs[i][j].adj=1; p=p->nextarc; } } } void printMGraph(MGraph G){ int i,j;cout<<“n”;for(i=0;i for(j=0;j {cout< ”; if((1+j)%G.vexnum ==0) cout<<“n”;} } printMGraph();void main(){ ALGraph G;MGraph M;int v;CreateALGraph(&G);for(v=0;v if(!visited[v]) BFS(&G,v); cout<<“n”; DFSTraverse(&G);cout<<“n”;change(G,M);printMGraph(M);} 3 實驗要求 按要求編寫實驗程序，將實驗程序上機調試運行，并提交實驗報告。 《數據結構與算法》教學大綱 課程編號：030816 適用專業：教育技術學 總學時數：64 學 分：4 編制單位：茂名學院理學院教育與信息技術系 編制時間：2008年6月20日 一、課程地位、性質和任務 《數據結構與算法》課程是計算機相關學科專業的基礎課程中的一門重要的核心課程。通過本課程的教學，使學生知道求解非數值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據問題設計和選擇好的算法，為學習后續的操作系統、編譯原理和軟件工程等專業課程，設計應用程序打下基礎。 本課程以提高學生的計算機應用能力和綜合素質為目標，通過課程教學，為學生構建數據結構與算法方面的知識體系，使學生一方面能夠根據問題選擇合適的數據結構，設計高效的算法，提高程序設計能力，另一方面，在工程應用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學生的程序設計能力。 二、與其他課程的關系 先修課：程序設計基礎、離散數學、計算機組成原理、計算機文化基礎 三、教學內容、課時安排和基本要求 （一）教學部分 第1章 緒論（2學時）1.1什么是數據結構 1.2 基本概念和術語 1.3 抽象數據類型的表示與實現 1.4 算法和算法分析（算法及其設計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解 基本要求： 了解：抽象數據類型，算法設計方法與算法分析。 掌握：數據與數據結構、算法的基本概念；問題求解的方法與步驟 重點：數據結構和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標準和評價方法，最壞情況和平均情況的區分。 第2章 線性表（8學時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現 2.3 線性表的鏈式表示和實現（線性鏈表，循環鏈表，雙向鏈表）2.4 一元多項式的表示及相加 基本要求： 了解：兩種存儲結構（順序存儲結構和鏈式存儲結構）及一元多項式的表示及相加。 掌握：要求熟練掌握處理線性表的各種算法。為后繼章節的學習打基礎。重點：各種算法。難點：鏈表的理解。 第3章 棧與隊列（4學時） 3.1 棧（定義，棧的表示和實現） 3.2 棧的應用舉例（數制轉換，括號匹配的檢驗，行編輯程序，迷宮求解，表達式求值） 3.3 棧與遞歸的實現 3.4 隊列及其實現（定義，鏈隊列，循環隊列）3.5 *離散事件模擬 教學要求：熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。棧和隊列是表最基本和重要的數據結構，是數據結構課程的基礎。 基本要求： 了解： 棧和隊列的定義及其實現。 掌握： 熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。重點： 棧和隊列的算法實現。難點： 棧和隊列的算法實現。 第4章 串（2學時）4.1 串類型的定義 4.2 串的表示和實現（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數，模式匹配的一種改進算法）4.4 串操作應用舉例（文本編輯，建立詞索引表） 基本要求： 了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應用。 第5章 數組（2學時）5.1 數組的定義 5.2 數組的順序表示和實現 5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結構 5.6 m元多項式的表示 5.7 廣義表的遞歸算法（求廣義表的深度，復制廣義表，建立廣義表的存儲結構） 基本要求： 了解：了解作為抽象數據類型的數組和C語言的數組。認識到數組可以作為順序存儲結構用于順序表、字符串和稀疏矩陣的實現。也可以采用鏈式存儲結構。 掌握：掌握基本概念和算法。重點：算法。 難點：廣義表的遞歸算法。 第6章 樹與二叉樹（15學時）6.1 樹的定義和基本術語 6.2 二叉樹（二叉樹的定義，二叉樹的性質，二叉樹的存儲結構）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹） 6.4 樹和森林（樹的存儲結構，森林與二叉樹的轉換，樹和森林的遍歷）6.5 樹與等價問題 6.6 赫夫曼樹及其應用（最優二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數 基本要求： 了解：理解樹與森林的定義與術語。 掌握：熟練掌握二叉樹性質和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構造的方法和算法。重點： 樹的存儲結構和遍歷算法。難點：哈夫曼樹構造的方法和算法 第7章 圖（11學時）7.1 圖的定義和術語 7.2 圖的存儲結構（數組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優先搜索，廣度優先搜索） 7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關節點和重連通分量） 7.5 有向無環圖及其應用（拓撲排序，關鍵路徑） 7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求： 了解：圖的基本概念和相關術語。 掌握：圖的兩種主要存儲結構及遍歷算法。掌握最小生成樹、最短路徑和活動網算法的思想。 重點：圖的兩種主要存儲結構及遍歷算法。難點：圖的遍歷算法，最短路徑算法。 第8章 查找（8學時） 9.1 靜態查找表（順序表，有序表，靜態樹表，索引順序表）9.2 動態查找表（二叉排序樹和平衡二叉樹，B_樹和B+樹，鍵樹）9.3 哈希表（定義，構造方法，處理沖突的方法，查找及其分析） 基本要求： 了解： 各種查找法的基本概念及實現的基本思想。 掌握：熟練掌握搜索結構的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現。難點：哈希表查找算法。 第9章 內部排序（8學時）10.1 概述 10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序 10.6 基數排序（多關鍵字，鏈式）10.7 排序算法分析 基本要求： 了解：基數排序，排序算法分析方法 掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內部排序算法 難點：基數排序（多關鍵字，鏈式） 第10章 *外部排序（2學時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現 11.4 置換-選擇排序 11.5 最佳歸并樹 基本要求： 了解：外部排序的基本概念和相關術語。 掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現 第11章 算法設計的一般方法（2學時） 1．重點 （1）有效算法的概念，問題固有難度的概念； （2）遞歸法；分治法；平衡原則；貪心法；動態規劃的基本原理；（3）搜索-回溯法的基本原理和本質.2．難點 （1）問題固有難度的概念； （2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態規劃法中的狀態轉移方程的確定。 （二）實驗、實習部分 課程安排五個類別的實驗，實驗時數為12課時，其中： 實驗 一、線性鏈表及運算 2課時 實驗 二、棧和隊列 2課時 實驗 三、樹和二叉樹 4課時 實驗 四、圖及其應用 2課時 實驗 五、查找與排序 2課時 四、課程考核方式 閉卷考試70%、平時作業與實驗30% 五、建議教材和教學參考書 參考教材： 1、《數據結構》（C語言描述）高等教育出版社 耿國華主編 2、《數據結構》（C語言版）清華大學出版社 嚴蔚敏，吳偉民編者 3、《數據結構題集》（C語言版）清華大學出版社 嚴蔚敏，吳偉民編者 4、《數據結構》算法實現及解析（第二版）西安電子科技大學出版社 高一凡 六、說明 1、因課時安排少，教學內容多。建議采用多媒體教學。 2、由于本課程內容較多，在實際教學中可根據大綱內容，進行適當調整。 中央廣播電視大學“開放教育試點”計算機科學與技術專業（本科） 《數據結構》課程教學大綱 第一部分 大綱說明 一、課程的性質和任務 《數據結構》是計算機科學與技術專業本科生的一門必修課程。本課程介紹如何組織各種數據在計算機中的存儲、傳遞和轉換。內容包括：數組、鏈接表、棧和隊列、遞歸、樹與森林、圖、堆與優先級隊列、集合與搜索結構、排序、索引與散列結構等。課程采用面向對象的觀點討論數據結構技術，并以兼有面向過程和面向對象雙重特色的C++語言作為算法的描述工具，強化數據結構基本知識和面向對象程序設計基本能力的雙基訓練。為后續計算機專業課程的學習打下堅實的基礎。 二、先修課要求 面向對象程序設計、計算機數學(離散數學)。 三、課程的教學基本要求 1、掌握重要數據結構的概念、使用方法及實現技術； 2、學會做簡單的算法分析，包括算法的時間代價和空間代價。 四、教學方法和教學形式建議 電視授課為主，結合面授輔導、面授或電子郵件答疑，進行必要的上機實驗。 五、課程教學要求的層次 1、熟練掌握：要求學生能夠全面、深入理解和熟練掌握所學內容，并能夠用其知識分析、設計和解答相關的應用問題。 2、掌握：要求學生能夠較好地理解和掌握，并且能夠做簡單的分析。 3、了解：要求學生能夠一般地了解的所學內容。 六、課程實驗 實驗內容和要求由省級電大作出具體規定，從2004年春開始按該課程實驗教材規定進行。 第二部分 多種媒體教材一體化總體設計初步方案 一、學時分配 課程教學總學時數為 72學時，4學分，其中講授學時48，實驗24 教 學 內 容 講授學時 實驗學時 一、數據結構基本概念及算法分析 3學時 2學時 二、數組 3學時 2學時 三、鏈表 3學時 3學時 四、棧和隊列 3學時 2學時 五、遞歸 3學時 2學時 六、樹與森林 9學時 4學時 七、集合與搜索 5學時 2學時 八、圖 7學時 4學時 九、排序 7學時 3學時 十、索引與散列結構 5學時 二、教學環節 1、電視教學 本課程是計算機專業基礎課，內容多且帶有一定的抽象性，學習起來有一定難度。為保證教學效果，采取電視集中授課方式。聘請有經驗的教師擔任主講教師，盡可能利用多種媒體進行教學，使學生能夠很快掌握課程的主要知識和解決問題的方法。 2、面授輔導或答疑 本課程教學過程中，面授輔導和答疑是必不可少的教學環節。各地方電大應聘請有經驗、認真負責的教師任教，以習題課、專題討論或答疑的方式，對課程中的重要概念和典型問題的解決方法進行總結和深入討論，鞏固和加深課堂內學到的知識。面授輔導或答疑安排兩周一次為宜。必要時可采用電子郵件方式直接與主講教師聯系進行答疑。 3、自學與練習 自學是獲取知識的重要手段。教師講課只是起到拋磚引玉的作用，關鍵還在于學生的自學。為達到自學的效果，除讀懂教科書中所講內容外，還需大量做題。其目的是要通過做題弄懂、加深對概念的理解，提高程序設計，解決問題的能力。為此，安排一定的實驗上機學時。要求學生珍惜實驗機時，真正做到學有所獲。 學生在上機做實驗前，應事先將程序、調試數據、上機操作順序準備好，并提前使用這些調試數據人工執行過。目的是提高上機的效率和成功率，嚴禁抄襲或拷貝他人的成果，自覺培養科學、嚴謹的作風。 除學校提供的時間外，要求課外學生利用自己可能擁有的計算機條件，完成更多的練習，不通過大量的實踐，能力和知識水平得不到有效得提高。 4、考試 考試是對學生掌握知識水平的檢驗。本著多練多考的原則，各地方電大可以再平時多做一些小考。要求考試內容緊扣大綱要求，既要能夠檢驗學生的掌握情況，又要體現水平。因此，不要出難題、怪題，但也不要過于簡單，適當有一些編程題。 課程考試具體規定請參看該課程考核說明。 第三部分 教學內容和教學要求 一、數據結構基本概念及簡單的算法分析 3學時 1、教學內容： 什么是數據結構 抽象數據類型及面向對象概念：數據類型；數據抽象與抽象數據類型；面向對象的概念；用于描述數據結構的語言 數據結構的抽象層次 算法定義 性能分析與度量：算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜度 2、教學要求： 了解：什么是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系 了解：什么是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什么是面向對象 了解：算法的定義、算法的特性、算法的時間代價、算法的空間代價 掌握：用C++語言描述算法的方法，能夠使用C++語言編寫程序 二、數組 3學時 1、教學內容： 作為抽象數據類型的數組：數組的定義和初始化；作為抽象數據類型的數組；數組的順序存儲方式 順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例 字符串：字符串的抽象數據類型；字符串操作的實現；字符串的模式匹配 2、教學要求： 了解：線性表的邏輯結構特性，以及線性表的兩種存儲實現方式 了解：作為抽象數據類型的數組的定義，數組的按行順序存儲與按列順序存儲 熟練掌握：順序表的定義與實現，包括搜索、插入、刪除算法的實現及其平均比較次數的計算，掌握應用順序表作為集合的簡單操作 了解：稀疏矩陣的定義及其數組實現 熟練掌握：字符串的定義及實現 三、鏈表 3學時 1、教學內容： 單鏈表：單鏈表的結構；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結點的單鏈表；用模板定義的單鏈表類；靜態鏈表 循環鏈表：循環鏈表的類定義；用循環鏈表解約瑟夫問題； 多項式及其相加：多項式的類定義；多項式的加法 雙向鏈表 2、教學要求： 了解：鏈表與數組一樣，是一種實現級結構。有動態鏈表和靜態鏈表之分 了解：鏈表有單鏈表、循環單鏈表、雙向鏈表之分 了解：單鏈表的結構、特點 掌握：單鏈表的類定義、構造函數、單鏈表的插入與刪除算法 了解：帶表頭結點的單鏈表的優點和類定義及相應操作的實現 熟練掌握：用模板定義的單鏈表類 了解：循環鏈表的特點，循環鏈表的類定義，以及用循環鏈表解決問題的方法 掌握：雙向鏈表的特點，雙向鏈表的類定義及相關操作的實現，用雙向鏈表解決問題的方法。 四、棧和隊列 3學時 1、教學內容： 棧：棧的抽象數據類型；棧的順序存儲表示；棧的鏈接存儲表示 表達式求值：中綴表達式求值；中綴表示到后綴表示的轉換 隊列 ：隊列的抽象數據類型；隊列的順序存儲表示；隊列的鏈接存儲表示；隊列的應用舉例 優先級隊列：優先級隊列的定義；優先級隊列的存儲表示 2、教學要求： 熟練掌握：棧的定義、特性和棧的抽象數據類型，棧的順序表示、鏈表表示以及相應操作的實現。特別注意棧空和棧滿的條件 了解：在表達式計算時棧是如何使用的，重點了解用后綴表示計算表達式及中綴表示改后綴表示的方法和算法思路 熟練掌握：隊列的定義、特性和隊列的抽象數據類型，隊列的順序表示、鏈表表示以及相應操作的實現。特別是循環隊列中隊頭與隊尾指針的變化情況 掌握：優先級隊列的定義、特性和優先級隊列的抽象數據類型，優先級隊列的插入與刪除算法 五、遞歸 3學時 1、教學內容： 遞歸的概念：遞歸問題的求解 遞歸過程與遞歸工作棧：單向遞歸和尾遞歸的迭代實現；一般遞歸問題利用棧實現非遞歸解法 廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲結構的實現；廣義表的訪問算法；廣義表的遞歸算法 2、教學要求： 掌握：遞歸的概念。包括什么是遞歸，有那些種類的遞歸，遞歸問題的遞歸求解方法 掌握：遞歸過程的機制與利用遞歸工作棧實現遞歸的方法 了解：迷宮問題的遞歸求解思路及如何利用棧實現迷宮問題的非遞歸解法 掌握：利用遞歸解決問題的分治法和回溯法 掌握：廣義表的定義及其實現方法 掌握：廣義表的遞歸算法 六、樹與森林 9學時 1、教學內容： 樹和森林的概念：樹的定義；樹的術語；樹的抽象數據類型 二叉樹：二叉樹的定義；二叉樹的性質；二叉樹的抽象數據類型 二叉樹的表示：順序表示；二叉鏈表表示 遍歷二叉樹：中序遍歷；前序遍歷；后序遍歷；應用二叉樹遍歷的事例；二叉樹的計數 線索化二叉樹：線索；中序線索化二叉樹 堆：堆的定義；堆的建立；堆的插入與刪除；堆的調整算法 樹與森林：樹的存儲表示；森林與二叉樹的轉換；遍歷樹；遍歷森林 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼編碼 2、教學要求： 了解：樹和森林的概念。包括樹的定義、樹的術語、樹的抽象數據類型 掌握：二叉樹的概念、性質及二叉樹的表示 熟練掌握：二叉樹的遍歷方法 掌握：線索化二叉樹的特性及尋找某結點的前驅和后繼的方法 熟練掌握：堆的定義，堆的建立、堆的插入與刪除、堆的向上和向下調整等算法以及用來實現優先級隊列的方法 掌握：樹與森林的實現，重點在用二叉樹實現 掌握：森林與二叉樹的轉換；樹的遍歷算法 掌握：二叉樹的計數方法及從二叉樹遍歷結果得到二叉樹的方法 掌握：霍夫曼樹的實現方法、構造霍夫曼編碼的方法及帶權路徑長度的計算 七、集合與搜索 5學時 1、教學內容： 集合及其表示：集合基本概念；以集合為基礎的抽象數據類型；用位向量實現集合抽象據類型；用有序鏈表實現集合的抽象數據類型 并查集：并查集的定義；并查集的實現 簡單的搜索結構：搜索的概念；靜態搜索結構；順序搜索；基于有序順序表的順序搜索和折半搜索 二叉搜索樹：二叉搜索樹的定義；二叉搜索樹上的搜索；二叉搜索樹的插入；二叉搜索樹的刪除 AVL樹：AVL樹定義；平衡化旋轉；AVL樹的插入和刪除；AVL樹高度 2、教學要求： 掌握：集合的基本概念及其表示方法，包括位數組及有序鏈表的表示及其相關操作的實現算法 掌握：利用并查集實現集合的方法 熟練掌握：靜態搜索表的順序搜索和折半搜索算法及其性能分析方法 熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法 掌握：AVL樹的平衡化旋轉、構造、插入、刪除時的調整方法及其性能分析 八、圖 7學時 1、教學內容： 圖的基本概念：圖的基本概念；圖的抽象數據類型 圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表 圖的遍歷與連通性：深度優先搜索；廣度優先搜索；連通分量；關節點與重連通分量 最小生成樹：kruskul算法；prim算法 單源最短路徑問題：dijkstra算法 活動網絡：AOV網絡與拓撲排序；AOE網絡與關鍵路徑 2、教學要求： 理解：圖的基本概念和圖的抽象數據類型 掌握：圖的3種存儲表示：鄰接矩陣、鄰接表和鄰接多重表。對于前兩種，要求掌握典型操作，如構造、求根、找第一個鄰接頂點、找下一個鄰接頂點等操作的實現算法 熟練掌握：圖的兩種遍歷算法與求解連通性問題的方法。包括深度優先搜索和廣度優先搜索算法、求連通分量的方法(不要求算法) 理解：求解關節點及構造重連通圖的方法(不要求算法) 掌握：構造最小生成樹的Prim算法和Kruskal算法，要求理解算法 理解：如何用Dijkstra方法求解單源最短路徑問題(不要求算法) 熟練掌握：活動網絡的拓撲排序算法 掌握：求解關鍵路徑的方法 九、排序 7學時 1、教學內容： 概述 插入排序：直接插入排序；折半插入排序；鏈表插入排序；希爾排序 交換排序：起泡排序；快速排序 選擇排序：直接選擇排序；錦標賽排序；堆排序 歸并排序：歸并；迭代的歸并排序算法；遞歸的鏈表歸并排序 基數排序：多關鍵碼排序；鏈式基數排序 外排序：外排序的基本過程；k路平衡歸并；初始歸并段的生成；最佳歸并樹 2、教學要求： 掌握：排序的基本概念和性能分析方法 掌握：插入排序、交換排序、選擇排序、歸并排序等內排序的方法及其性能分析方法 了解：基數排序方法及其性能分析方法 掌握：多路平衡歸并等外排序方法及敗者樹構造方法 掌握：生成初始歸并段及敗者樹構造方法 掌握：最佳歸并樹的建立方法 十、索引與散列結構 5學時 1、教學內容： 靜態索引結構：線性索引；倒排索引；m路靜態查找樹 動態索引結構：動態的m路查找樹；B樹的定義；B樹的插入；B樹的刪除；B+樹 散列：散列表與散列方法；散列函數；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析 2、教學要求： 熟練掌握：靜態索引結構，包括線性索引、倒排索引、靜態索引樹的搜索和構造方法 熟練掌握：動態索引結構，包括B樹、B+樹的搜索和構造方法 熟練掌握：散列法，包括散列函數的構造、解決沖突的方法 《數據結構》課內實驗教學大綱 課程英文名稱：Data Structure 課程編號：006A1060 學時：54+18(實驗) 學分：4.0 一、課程教學對象 本教學大綱適用于五邑大學信息學院計算機科學與技術專業的普通本科生數據結構課程的教學。 二、課程性質、目的和任務 1．本實驗課在培養實驗能力中的地位和作用 《數據結構》是計算機科學與技術專業的重要的專業基礎課，它所討論的知識內容和提倡的技術和方法，無論對計算機領域的其它課程，還是從事軟件工程的開發，都有著不可替代的作用。本實驗課程是配合理論課程的實踐環節，其主要任務是理論與實踐相結合，通過實踐提高學生對數據結構的基本原理和算法的理解和認識，進而提高對程序設計語言的理解和算法設計的能力。 2．應達到的實驗能力標準 學會從問題入手，分析研究數據結構中數據表示和數據處理的特性，以便為應用所涉及的數據選擇適當的邏輯結構、存儲結構及其相應的操作算法，并初步掌握時間和空間分析技術。要求學生編寫符合軟件工程規范的文件，程序代碼應體現結構清晰、正確易讀，通過上機調試程序、排除錯誤。 三、對先修課的要求 高級程序設計語言、離散數學是學習數據結構的主要先修課程。具體要求如下： 1． 掌握程序設計語言的基本概念。 2． 掌握結構化程序設計的的基本原理、良好的設計習慣，并具備較好的程序調試能力。3． 掌握離散數學的基本理論。4．具有一定的邏輯思維和推理能力 四、課程的主要內容、基本要求和學時分配建議（總學時數:18學時） 實驗內容可根據實驗條件及教學情況由任課教師自定。上機課時為18機時。實驗內容的選擇要盡量結合基本內容的應用實例，要具有一定的典型性和方法的靈活性，但一次實驗內容不宜太多、太難。《數據結構（C++版）學習輔導和實驗指導》中每章有大量的習題，還有相當數量的實驗題，要求學生根據自身學習基礎，選擇驗證性實驗或設計性實驗或綜合性實驗作為課程考核內容的一部分，最好能選3～5個設計性或綜合性的實驗題，要求完成上機調試、獲取實驗結果、寫出實驗報告。實驗一 線性表(2學時)實驗內容和基本要求： 分別設計兩類順序表。一類為順序存儲結構的線性表，另一類為鏈式存儲結構線性表。對這兩種線性表進行以下基本操作： 1．查找 2．插入 3．刪除 要求考慮時間復雜度和空間復雜度進行算法設計，編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。實驗二 棧（2學時）實驗內容和基本要求： 設計一個或多個順序棧。實現對棧的以下基本操作： 1．建立初始棧 2．入棧 3．退棧 要求需要考慮棧空和棧滿的情況，編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。實驗三 隊列（2學時） 實驗內容和基本要求： 設計一個或若干多個順序（循環）隊列。實現對隊列的以下基本操作： 1．建立初始隊列 2．入隊 3．出隊 要求需要考慮隊列空和隊列滿的情況，編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。實驗四 二叉樹（2學時） 實驗內容和基本要求： 1．設計一個二叉樹，采用鏈接存儲方式存儲。實現對該二叉樹遍歷的遞歸算法或非遞歸算法。2．設計一個完全二叉樹，采用順序存儲方式存儲。實現對該二叉樹遍歷的遞歸算法或非遞歸算法。要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。 實驗五 哈夫曼樹（2學時） 實驗內容和基本要求： 給定一組數據，根據這組數據建立一棵Huffman樹，求出該樹的WPL，并給出每一個數據的Huffman編碼。 要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。實驗六 圖的存儲（2學時）實驗內容和基本要求： 設計一個無向圖或一個帶權的有向圖，采用鄰接表存儲該圖。實現對圖的以下基本操作： 1．建立圖（圖的鄰接表）2．深度優先遍歷或廣度優先遍歷 要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。 實驗七 圖的應用（2學時） 實驗內容和基本要求： 在實驗六的基礎上，實現或部分實現對圖的以下操作： 1．拓撲排序 2．構造最小生成樹 3．求解關鍵路徑 4．求解最短路徑 要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。 實驗八 查找（2學時） 實驗內容和基本要求： 實現或部分實現以下功能： 1．給出一組有序數據，實現二分查找算法，并對這組數據中的任一數據進行查找。2．給出一組數據，構造二叉排序樹。3．給出一組數據，構造平衡二叉樹。 4．給出一組數據，選擇一種哈希函數構造哈希表。給出一種解決沖突的方案。 要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現運行過程。按要求完成實驗報告。 實驗九 排序（2學時） 實驗內容和基本要求： 實現或部分實現以下功能： 1．給出一組數據，實現直接插入排序算法，并對這組數據進行排序。2．給出一組數據，實現希爾排序算法，并對這組數據進行排序。3．給出一組數據，實現快速排序算法，并對這組數據進行排序。4．給出一組數據，實現堆排序算法，并對這組數據進行排序。5．給出一組數據，實現歸并排序算法，并對這組數據進行排序。6．給出一組3位整數，實現基數排序算法，并對這組數據進行排序。7．實現其它排序算法。 要求編寫完整程序，調試，程序執行的輸出結果要求至少包含輸入數據和運行結果，最好能體現 運行過程。按要求完成實驗報告。 說明：實驗報告的要求：見《數據結構實驗報告模板》。 課外實踐（可選） 實驗項目名稱：應用實例的設計與實現 指導思想： 訓練學生自主學習、綜合知識和查閱、收集資料的能力。利用一些表現力強的平臺，以動畫形式展現數據結構原理，需要學生自學Flash、Powerpoint、網頁制作等，通過自主學習、查閱和收集所需的知識點完成。給學生充分展示才華的舞臺，對學生設計的軟件作品要提供一個自由展示的平臺、互動交流的平臺，可以大大提高學生的學習激情和科學研究的精神，也能顯著提高學習效果。實踐目的及要求： 在各個章節的基本編程訓練的基礎上，再結合課程重點和難點進行較大軟件編制的選題，并在具體題目上提倡與實際應用相結合并由學生自主選題，教師審核。引導學生利用“思維導圖”等工具進行設計和交流，提高教與學的效果。 該實踐項目主要占用課外時間進行，可由任課教師根據授課情況和學生的要求決定是否開展此項活動或部分開展此項活動。 五、教材及參考書 1．理論課教材 理論課教材： 王紅梅等．數據結構（C++版）[M]．北京：清華大學出版社，2007 實驗課教材： 王紅梅等．數據結構（C++版）學習輔導和實驗指導[M]．北京：清華大學出版社，2006 2．主要參考文獻 [1] 許卓群．數據結構[M]．北京：高等教育出版社，2006 [2] 殷人昆．數據結構C＋＋實現[M]．北京：清華大學出版社，2006 [3] 黃國瑜，葉乃菁．數據結構[M]．北京：清華大學出版社，2005 [4] 胡學剛．數據結構算法設計指導[M]．北京：清華大學出版社，2004 [5] 胡元義，鄧亞玲，徐睿琳．數據結構課程輔導與習題解析[M]．北京：人民郵電出版社，2003 [6] 羅文，王苗，石強．數據結構習題解答與實驗指導[M]．北京：中國鐵道出版社，2003 [7] 王曉東．數據結構（C語言版）[M]．北京：電子工業出版社，2007 [8] 陳慧南．數據結構——使用C++語言描述[M]．北京：人民郵電出版社，2006 [9] 呂國英．算法設計與分析[M]．北京：清華大學出版社，2006 [10] Sartaj Sahni．Data Structures, Algorithms and Applications in C++[M]．北京：機械工業出版社，2003 [11] William Ford．Data Structure with C++[M]．北京：清華大學出版社，2001 [12] 蘇光奎．數據結構導學[M]．北京：清華大學出版社，2002 [13] 嚴蔚敏等．數據結構（C語言版）[M]．北京：清華大學出版社，2002 六、考核方式 以閉卷考試為主，結合平時作業及自主應用和設計綜合評定成績。各部分分配比例為： 期末考試成績70%，平時作業及考勤10%，實驗占10%，自主設計作品或期中考核10%。執筆人： 編寫日期：2007-10-31 白明 數據結構課程教學大綱 一、課程基本概況 課程名稱：數據結構 課程名稱（英文）： Data Structures 課程編號：B09042 課程總學時：60（其中，講課48，實驗12） 課程學分：3 課程分類：專業選修課 開設學期：4 適用專業：計算機網絡工程本科 先修課程：集合論，圖論，高級語言（結構或記錄，指針） 后續課程：數據庫，編譯原理，操作系統等 二、課程的性質、目的和任務 數據結構是計算機專業的一門核心專業課程，是軟件課程中非常重要的一門課程，在整個專業教學中占有十分重要的地位，是一門理論性非常強的課程。通過課堂教學、課外練習和上機實習，使學生了解數據對象的特性，數據組織的基本方法，并初步具備分析和解決現實世界問題在計算機中如何表示和處理的能力以及培養良好的程序設計技能，為后續課程的學習和科研工作的參與打下良好的基礎。 三、主要內容、重點及深度 本門課程共60學時，其中理論教學48學時，實驗教學12學時。其中，理論教學部分： 第一章 緒論 （一）目的要求 了解數據結構的意義與發展過程、數據結構在計算機科學中的作用、學習本課程的目的、任務及要求。理解數據結構的基本概念；算法設計；掌握算法的時間和空間復雜度。 （二）教學內容 本章知識點： 1.相關的基本概念(掌握)； 2.算法五大要素(掌握)； 3.計算語句頻度和估算算法時間復雜度的方法（掌握）。 （三）重點與難點 重點：數據結構的定義；算法的描述方法。 難點：數據結構的定義；算法與程序的區別；時間復雜度及其計算。 第二章 線性表 （一）目的要求 掌握線性表的邏輯結構；線性表的存儲結構及操作的實現；理解一元多項式的表示； （二）教學內容 本章知識點： 1.線性表的邏輯結構(掌握)；2.線性表的存儲結構(掌握)； 3.線性表在順序結構和鏈式結構上實現基本操作的方法(掌握)； 4.從時間和空間復雜度的角度比較線性表兩種存儲結構的不同特點及其適用場合(掌握)。 （三）重點與難點 重點：線性表的概念；線性表的順序存儲結構、鏈式存儲結構及其常用算法。難點：鏈式存儲結構及其常用算法；雙向循環鏈表。 第三章 棧和隊列 （一）目的要求 掌握棧的定義，表示及實現；表達式求值；棧與遞歸過程；隊列的定義、表示及實現。 （二）教學內容 本章知識點： 1.棧和隊列的特點(掌握)； 2.在兩種存儲結構上棧的基本操作的實現(掌握)； 3.循環隊列和鏈隊列的基本運算(熟練掌握)； 4.遞歸算法執行過程中棧狀態的變化過程(掌握)。 （三）重點與難點 重點：堆棧和隊列的概念；遞歸的定義；循環隊列和鏈隊列的基本運算。難點：遞歸的編程實現；循環隊列和鏈隊列的基本運算。 第四章 串 （一）目的要求 了解串的邏輯結構，存儲結構；掌握串操作的實現(重點難點BF和KMP算法)串的應用。 （二）教學內容 本章知識點： 1.串的七種基本運算的定義（了解）； 2.利用這些基本運算來實現串的其它各種運算的方法(掌握)； 3.在順序存儲結構上實現串的各種操作的方法(掌握)； 4.KMP算法，熟悉NEXT函數和改進NEXT函數的定義和計算(掌握)； 5.串名的存儲映象和在堆存儲結構實現串操作的方法(理解)。 （三）重點與難點 重點：串定義和存儲方法；串的操作 難點：串操作實現方法 第五章 數組和廣義表 （一）目的要求 掌握數組的存儲結構；稀疏矩陣的表示及操作的實現；廣義表的定義和存儲結構；廣義表的遞歸算法。 （二）教學內容 本章知識點：1.數組在以行為主的存儲結構中的地址計算方法(掌握)； 2.矩陣實現壓縮存儲時的下標變換(掌握)； 3.理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領會以三元組表示稀疏矩陣時進行運算采用的處理方法(掌握)； 4.廣義表的定義及其存儲結構，學會廣義表的表頭，表尾分析方法(掌握)； 5.學習編制廣義表的遞歸算法(掌握)。 （三）重點與難點 重點：多維數組元素存儲地址的計算；稀疏矩陣的三元組表示；廣義表的存儲定義、操作。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。 第六章 樹和二叉樹 （一）目的要求 了解樹的基本概念；理解二叉樹的性質和存儲結構；遍歷二叉樹和線索二叉樹；理解樹的存儲結構和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應用； （二）教學內容 本章知識點： 1.二叉樹的結構特點(理解)； 2.二叉樹的各種存儲結構的特點及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)； 4.二叉樹的線索化，在中序線索樹上找給定結點的前驅和后繼的方法(掌握)； 5.樹的各種存儲結構及其特點(掌握)； 6.編寫樹的各種運算的算法(掌握)； 7.建立最優二叉樹和哈夫曼編碼的方法(掌握)。 （三）重點與難點 重點：二叉樹的概念、性質；二叉樹的遍歷方式；構造二叉排序樹。難點：二叉樹的遍歷方式；二叉排序樹的構造方法；二叉樹的線索化。 第七章 圖 （一）目的要求 理解圖的基本概念；圖的存儲結構；掌握圖的遍歷及應用{最小生成樹，最短路徑等}；拓撲排序和關鍵路徑。 （二）教學內容 本章知識點： 1.熟悉圖的各種存儲結構； 2.了解實際問題與采用何種存儲結構和算法有密切聯系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)； 4.應用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓撲排序、關鍵路徑等）(掌握)。 （三）重點與難點 重點：圖的存儲結構；圖的遍歷 難點：圖遍歷的算法； 第八章 動態存儲管理 （一）目的要求 了解邊界標識法和伙伴系統；無用單元收集和緊縮； （二）教學內容 本章知識點： 1.存儲器分配策略和算法（了解）； 2.無用單元收集時的標志算法（了解）。 （三）重點與難點 存儲器分配策略和算法、無用單元收集時的標志算法 第九章 查找 （一）目的要求 了解靜態查找表(順序表，有序表，索引順序表)；動態查找表(二叉排序樹，平衡二叉樹，B-樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析； （二）教學內容 本章知識點： 1.順序查找、折半查找和索引查找的方法、應用(掌握)； 2.二叉排序樹的構造方法(掌握)； 3.二叉平衡樹的建立方法(掌握)； 4.B-樹，B+樹和鍵樹的特點以及它們的建立過程（理解）； 5.哈希表的構造方法(掌握)； 6.按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度； 7.哈希表在查找不成功時的平均查找長度的計算方法(掌握)。 （三）重點與難點 重點：二叉排序樹的構造方法、二叉平衡樹的建立方法；哈希表的構造、應用； 難點：二叉排序樹的構造及應用；哈希表的構造方法；查找的平均長度。 第十章 內部排序 （一）目的要求 掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數排序等算法。 （二）教學內容 本章知識點： 1.各種排序方法的特點并能靈活應用(掌握)； 2.各種方法的排序過程(掌握)； 3.各種排序方法的時間復雜度分析(掌握)。 （三）重點與難點 重點：各種排序方法的特點及其應用；實現排序的各種算法。難點：各種排序算法的時間復雜度分析。 十一章 外部排序 （一）目的要求 理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實現；置換--選擇排序；最佳歸并樹。 （二）教學內容 本章知識點： 1.外部排序的兩個過程(理解)； 2.外排過程中所需進行外存讀/寫次數的計算方法(掌握)； 3.敗者樹的建立過程(掌握)； 4.實現多路歸并的算法(掌握)； 5.置換-選擇排序的過程(掌握)； 6.最佳歸并樹的構造方法（熟悉）； 7.按最佳歸并樹的歸并方案進行平衡歸并時，外存讀/寫次數的計算方法(掌握)。 （三）重點與難點 重點：外部排序過程和實現方法；多路并歸算法及其實現； 難點：最佳并歸樹的構造方法及其應用。 實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。 實驗一 停車場管理系統 （一）實驗內容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。棧以順序結構實現，隊列以鏈表結構實現。 （二）實驗過程 編程實現實驗內容。 （三）實驗教學基本要求 通過實例，使學生掌握棧和隊列兩種特殊的線性結構，掌握棧和隊列的特點。實驗后學生提交實驗報告。 （四）實驗設備和材料 計算機。 （五）實驗學時 4學時 實驗二 教學計劃編制問題 （一）實驗內容 假設任何專業都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。編制一個教學計劃程序。 （二）實驗過程編程實現實驗內容。 （三）實驗教學基本要求 通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。 （四）實驗設備和材料 計算機。 （五）實驗學時 2學時 實驗三 最小生成樹問題 （一）實驗內容 利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權值。 （二）實驗過程 編程實現實驗內容 （三）實驗教學基本要求 通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。 （四）實驗設備和材料 計算機。 （五）實驗學時 2學時 實驗四 哈希表設計 （一）實驗內容 假設人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數用除留余數法構造，用偽隨機探測再散列法處理沖突。 （二）實驗過程 編程實現實驗內容 （三）實驗教學基本要求 掌握索引技術的使用。 （四）實驗設備和材料 計算機 （五）實驗學時 4學時 五、課程教學的基本要求和主要環節 本課程可采用課堂講授、課堂討論、習題課等進行課堂教學;條件允許可采用CAI、電子教案、幻燈片、參觀等進行輔助教學;每章布置3~6道習題以鞏固教學;在課程后半程，安排3~4個上機實驗，讓學生應用數據結構的理論、方法，分組設計幾個較大的軟件，使理論與實際相結合。 考試采用閉卷方式。總成績由平時成績和考試成績組成。平時成績占30%，考試成績占70%。 六、本課程與其它課程的聯系與分工 先修課包括：集合論，圖論，高級語言（結構或記錄，指針）； 后續課包括：數據庫，編譯原理，操作系統等。 七、建議教材與參考教材 《數據結構》（C語言版） 嚴蔚敏等 清華大學出版社 1997 《數據結構題集》 嚴蔚敏等 清華大學出版社 1999 《數據結構習題與解析》 李春葆 清華大學出版社 2004 八、負責人 撰稿人：劉景匯、李玉香 審稿人： 系（院）領導：第二篇：數據結構教學大綱
第三篇：數據結構教學大綱
第四篇：006A1060-《數據結構》實驗教學大綱[小編推薦]
第五篇：數據結構課程教學大綱
點擊咨詢 