數(shù)據(jù)結(jié)構(gòu)與算法實驗報告(共10頁)

1、數(shù)據(jù)結(jié)構(gòu)與算法綜合實驗報告系 別： 專 業(yè)： 學(xué)生姓名： 指導(dǎo)教師： 2011年 11月 25日實驗?zāi)康恼莆站€性表的建立、插入、刪除算法；掌握查找算法；掌握排序算法；實驗要求使用C語言（環(huán)境任意）開發(fā)程序，能夠?qū)τ脩糨斎氲娜我庖唤M數(shù)據(jù)，建立一個線性表，可以輸出此線性表。并且能夠?qū)Υ司€性表進行插入、刪除、查找、排序等操作。程序流程建表如下：定義一個整型的數(shù)據(jù)類型data和next指針：定義頭指針和當(dāng)前結(jié)點指針，申請連續(xù)空間將單個字節(jié)大小復(fù)制給頭指針，把頭指針賦值給當(dāng)前節(jié)點指針：若輸入的數(shù)是0，則若輸入不為0，把輸入的數(shù)賦值給已申請的新結(jié)點，把新結(jié)點賦給當(dāng)前節(jié)點的next域，再把新結(jié)點賦值給當(dāng)前結(jié)

2、點，以此方法重復(fù)執(zhí)行得到如下鏈表：輸出函數(shù)：把頭指針賦值給當(dāng)前結(jié)點指針，當(dāng)當(dāng)前節(jié)點的next域不為空時輸出當(dāng)前節(jié)點所指向的數(shù)據(jù)，把當(dāng)前結(jié)點的next域賦值給當(dāng)前節(jié)點，否則輸出鏈表為空對此線性表進行插入、刪除、查詢、排序操作把已申請的結(jié)點數(shù)據(jù)域指向所輸入的數(shù)再把插入w結(jié)點賦值頭結(jié)點，是插入的位置，如果w=0則插入結(jié)點的next域賦值給頭結(jié)點否則如果w>表長，則輸出超出范圍代碼及運行結(jié)果（主要語句要求有注釋）#include"stdafx.h"#include<stdio.h>#include<malloc.h>#define NULL 0type

3、def struct linknode int data; struct linknode *next;node;node *head;node *creat() node *currnode,*newnode; int x; head=(node*)malloc(sizeof(node); currnode=head; do scanf("%d",&x);newnode=(node*)malloc(sizeof(node);newnode->data=x;currnode->next=newnode;currnode=newnode; while(x!

4、=NULL); head=head->next; currnode->next=NULL; return head;int length() node *currnode; int i=0; currnode=head; while(currnode->data!=NULL) currnode=currnode->next; i+; ; return i;void print() node *currnode; currnode=head; printf("鏈表如下.linklist"); while(currnode->data!=NULL)

5、 printf("%d->",currnode->data); currnode=currnode->next; ; printf("NULLn"); printf("鏈表長度為.linklist length%dn",length();void delete1() int x; node *delnode,*currnode; printf("輸入要刪除的數(shù)據(jù).input delete data："); scanf("%d",&x); if(head->data

6、=NULL) printf("此鏈表為空無法刪除.this linklist empty！n"); if(head->data=x) delnode=head; head=head->next; free(delnode); if(head=NULL) printf("此鏈表為空.this linklist enpty！"); else currnode=head; delnode=currnode->next; while(delnode->data!=x&&delnode!=NULL) currnode=cur

7、rnode->next;delnode=currnode->next; ; if(delnode=NULL)printf("無此數(shù)據(jù).no this data！n"); else currnode->next=delnode->next; free(delnode); ; ;void find() node *currnode; int count=1,x; currnode=head; printf("輸入要查找的數(shù)據(jù).input search data:"); scanf("%d",&x); whi

8、le(currnode->data!=NULL&&currnode->data!=x) currnode=currnode->next; count+; ; if(currnode->data!=NULL) printf("n%d為第.is no.",currnode->data); printf("%d個數(shù)據(jù).data。n",count); else printf("n無此數(shù)據(jù).not this data!n");void insert() int x,w,i; node *insert

9、node, *afternode,*currnode; printf("輸入要插入的數(shù)據(jù)Y.input inserte data："); scanf("%d",&x); printf("插入n結(jié)點后.insert after no. data n=:(0，1，)"); scanf("%d",&w); insertnode=(node*)malloc(sizeof(node); insertnode->data=x; if(w=0) insertnode->next=head; head=

10、insertnode; else if(w>length() printf("超出范圍.overflow!n"); else currnode= head;afternode=currnode->next; for(i=1;i<w;i+) afternode=afternode->next; currnode=currnode->next;currnode->next=insertnode;insertnode->next=afternode; ;void sort(node * *head)node *p,*q,*r,*s,*h1

11、;h1=p=(node *)malloc(sizeof(node);p->next=*head;while(p->next->data!=NULL) q=p->next; r=p;while(q->next->data!=NULL)if (q->next->data<r->next->data)r=q;q=q->next;if(r!=p)s=r->next;r->next=s->next;s->next=p->next;p->next=s;p=p->next;*head=h1-&g

12、t;next;free(h1);void operation() printf("nn刪除數(shù)據(jù)輸入.delete1: 1n"); printf("n查找數(shù)據(jù)輸入.search: 2n"); printf("n插入數(shù)據(jù)輸入.insert: 3n"); printf("n排序數(shù)據(jù)輸入.sort: 4n"); printf("n結(jié)束操作.end: 5n"); printf("n?:");void main() int choic; printf("n輸入數(shù)據(jù)以0結(jié)束.in

13、put data 0 end:n"); head=creat(); print(); operation(); do scanf("%d",&choic); switch(choic) case 1: delete1(); print(); operation(); break; case 2: find(); operation(); break; case 3:insert(); print(); operation(); break; case 4:sort(&head); print(); operation(); break; defau

14、lt:printf("操作結(jié)束.operate end!"); break; ; while(choic!=5);個人總結(jié)（要求1000字以上）數(shù)據(jù)結(jié)構(gòu)學(xué)科的章節(jié)劃分基本上為：概論，線性表，棧和隊列，串，多維數(shù)組和廣義表，樹和二叉樹，圖，查找，內(nèi)排，外排，文件，動態(tài)存儲分配。對于絕大多數(shù)的學(xué)校而言，“外排，文件，動態(tài)存儲分配”三章基本上是不考的，在大多數(shù)高校的計算機本科教學(xué)過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對于報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那么這部分朋友就要留意這三章了。按

15、照以上我們給出的章節(jié)以及對后三章的介紹，數(shù)據(jù)結(jié)構(gòu)的章節(jié)比重大致為：概論：內(nèi)容很少，概念簡單，分?jǐn)?shù)大多只有幾分，有的學(xué)校甚至不考。線性表：基礎(chǔ)章節(jié)，必考內(nèi)容之一。考題多數(shù)為基本概念題，名?？碱}中，鮮有大型算法設(shè)計題。如果有，也是與其它章節(jié)內(nèi)容相結(jié)合。棧和隊列：基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。而棧常與其它章節(jié)配合考查，也常與遞歸等概念相聯(lián)系進行考查。串 ：基礎(chǔ)章節(jié)，概念較為簡單。專門針對于此章的大型算法設(shè)計題很少，較常見的是根據(jù)KMP進行算法分析。多維數(shù)組及廣義表 ：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見的，分?jǐn)?shù)比例波動較大，是出題的“可選單元”或“侯補單元”。一般如果要出題，多數(shù)不會作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來作為大題考查。樹和二叉樹 ：重點難點章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設(shè)計題。通過對多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過出大型算法設(shè)計題的歷史。圖 ：重點難點章節(jié)