1、數 據 結 構 課 程 設 計設計題目：順序表的基本實現和存儲結構學生姓名：刁二亮郭敏 顧大勝吳晴 王瑋專業班級：10 計算機應用 (1)班指導教師：余云完成時間：2011 年 12 月 3 日信 息 工 程院計算機科學系2 安徽新華學院課程設計成績評定表(專科 ) 課題名稱順序表基本實現和存儲結構院系信息工程學院年級專業10 計應 1 班成員姓名成員學號承擔的任務成 績刁二亮1032101102 程序編寫及文檔匯總干敏1032101136 程序編寫及文字部分編寫顧大勝1032101104 程序編寫及文檔排版吳晴1032101132 程序編寫及概述編寫王瑋1032101112 程序編寫課題設計

2、目的與設計意義1、課題設計目的：了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統的觀點和軟件開發一般規范進行軟件開發， 培養軟件工作者所應具備的科學的工作方法和作風。2、課題設計意義：鍛煉我們的編碼能力， 真正理解數據結構的編碼思想,并且鍛煉我們的動手能力和成員間的配合，提高程3 序編寫能力。在信息傳遞時， 希望長度能盡可能短， 即采用最短碼。順序的應用，就是采用這種有效的數據壓縮技術可以節省數據文件的存儲空間和計算機網絡的傳送時間。指

3、導教師：余云2011年 12 月 3 日4 目錄一 .目的 . 5 1、設計目的：. 5 2、試驗目的：. 6 二 .實驗環境 . 7 三 .實驗學時 . 7 四 .實驗內容 . 7 五 .需求分析 . 7 六 .概述 . 8 1、順序表的概述：. 8 2、.初始化操作：. 8 3、.求長度操作：. 9 4、.判空操作： . 9 5、.清空操作： . 10 6、取元素操作：. 10 7、按值查找操作：. 11 8、插入操作：. 11 9、刪除操作：. 12 七、實驗步驟與源程序. 13 八、程序測試結果. 18 九、順序表的優點和缺點. 19 1、順序表的優點：. 20 2、順序表的缺點：.

4、20 十、總結 . 20 5 一.目的1、設計目的：數據結構作為一門學科主要研究數據的各種邏輯結構和存儲結構，以及對數據的各種操作。因此，主要有三個方面的內容：數據的邏輯結構；數據的物理存儲結構；對數據的操作（或算法）。通常，算法的設計取決于數據的邏輯結構， 算法的實現取決于數據的物理存儲結構。數據結構是信息的一種組織方式， 其目的是為了提高算法的效率， 它通常與一組算法的集合相對應，通過這組算法集合可以對數據結構中的數據進行某種操作。在當今信息時代， 信息技術己成為當代知識經濟的核心技術。我們時刻都在和數據打交道。 比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯網查新聞、 以及遠程

5、教育報名等， 所有這些都在與數據發生關系。實際上，現實世界中的實體經過抽象以后，就可以成為計算機上所處理的數據。數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。數據結構是介于數學、計算機軟件和計算機硬件之間的一門計算機專業的核心課程，它是計算機程序設計、 數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統工程等各種領域。學習數據結構是為了將實際問題中所涉及的對象在計算機中表示出6 來并對它們進行處理。 通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。通過此次課程設計主要達到以下目的：(1)

6、、了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；(2)、初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；(3)、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；(4)、訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。2、試驗目的：(1)、掌握線性表的順序存儲結構和鏈式存儲結構；(2)、熟練掌握順序表和鏈表基本算法的實現；(3)、掌握利用線性表數據結構解決實際問題的方法和基本技巧；(4)、按照實驗題目要求獨立正確地完成實驗內容（編寫、調試算法程序，提交程序清單及及相關實驗數據與運行結果）；(5)

7、、按時提交實驗報告二.實驗環境計算機、 c 語言程序設計環境。三.實驗學時10學時，必做實驗。四.實驗內容1、實現順序表的基本操作， 線性表中數據元素類型為結構體，成員包括學生的姓名、學號、若干課程的成績（int 型） ，按照順序存儲結構實現如下算法：(1)、創建任意線性表，長度限定在100 個學生信息之內；(2)、打印（遍歷）該線性表（依次打印出表中元素值）；(3)、在線性表中查找第i 個元素，并返回其值；(4)、在線性表中第i 個元素之前插入一已知元素；(5)、在線性表中刪除第i 個元素；五.需求分析線性表的順序存儲結構是把線性表中所有數據元素，按照其邏輯順序一次存儲到計算機存儲器中從指定

8、位置開始的一塊連續的存儲空間中，數據元素間的存儲（物理）位置即表示了它的邏輯位置。也就是說，邏輯上的第一個元素就存放在指定的第一個位置，邏輯上的第二個元素就存放在指定的空間的第二個元素，.依次類推。設線性表 l=（a1,a2,a3, .an）,假定 l 中的每個元素需占用k 個存儲單元，則在線性表存儲結構中，l 的第 i+1 個元素的存儲地址loc(ai+1)8 和第 i 個數據元素的存儲地址loc（ai）之間滿足下列關系：loc(ai+1)=loc(ai)+k 一般地，線性表中第i 個數據元素 ai 的存儲地址為：loc(ai)=loc(ai)+(i-1)*k (1=n) 其中，loc(ai

9、) 為線性表的第一個元素a1 的存儲位置， 通常又稱作線性表的起始地址或基地址，n 為線性表的表長。六.概述1、順序表的概述：通常把使用順序存儲實現的線性表稱為順序表線性表的順序存儲結構是把線性表中所有數據元素， 按照其邏輯順序一次存儲到計算機存儲器中從指定位置開始的一塊連續的存儲空間中，數據元素間的存儲（物理）位置即表示了它的邏輯位置。2、.初始化操作：在程序中，使用sqlist 類型用如下語句定義順序表l：此時， l 實際上只是一個機構體變量，其有3 個分量 base 、length及 listsize，但這3 個分量并沒有確切的值，并且base僅為一個指針量，還沒有與之對應的順序表所需的

10、存儲空間。因此在使用順序表l 時，首先應對其進行初始化。 所以此初始化操作的作用就是從內存中申請一塊可共使用順序表 l 使用的大小為 initsize 的存儲空間。并使 l 成為一個空表（將其長度賦值為 0）9 順序表的初始化操作算法見下：void initlist(sqlist *l,int initsize) l-base=(int *)malloc(initsize * sizeof(int); if(l-base=null) return -2; l-length=0; l-listsize=initsize; return 1; 3、.求長度操作：順序表 l 的 length分量的值

11、即為其長度。該操作的實現算法見下：int listlength(sqlist l) return l-length; 4、.判空操作：判斷順序表 l 是否為空即判斷其length 分量的值是否為0.該操作的實現算法見下：status lengthisempty(sqlist l) 10 if(!l-length) return 1 else return 0 5、.清空操作：將順序表 l 清空，只需將 length 值為 0 即可。該操作的實現算法見下：void clearlist(sqlist &l) l-length=0; 6、取元素操作：當順序表 l 非空時，數組下標為i-1 的

12、元素即為其第i 個元素。該操作算法見下：status getelem(sqlist l,int i,lelemtype &e) if(!l-length) return 0; e=l-basei-1; 11 return 1; 7、按值查找操作：該操作用來在順序表 l 中查找死一個與給定的數據元素e值相等的元素，并返回其位序。所以可從l 中的第一個元素（下標為0 的元素）開始一次與 e 進行比較，若某個元素與e 相等則返回其位序（下標加1） 。若未找到與 e 相等的元素，因為順序表中位序最小為1 因此可返回 0 表示查找失敗。順序表的按值查找操作算法見下：int locateelem(

13、sqlist l,lelemtype e) int i=0; while(ilength & *(l-base+i)!=e) i+; if(ilength) return i+1; else return 0; 8、插入操作：在線性表 l 的第 i 個位置插入一個新的元素e，則原來的第 i 個元素變為第 i+1 個，原來的第i+1 個元素就變為第i+2依次類推。該操作算法見下：12 void insertlist(sqlist *l,int i,int e) lelemtype *newbase; int j; if(i1 | ilength+1) printf( 不合理); retu

14、rn 0; if(l-length=l-listsize) printf( 滿表); return 0; for(j=l-length-1;j=i-1;j-) l-basej+1=l-basej; l-basei-1=e; l-length+; return 1; 9、刪除操作：該操作作用于刪除順序表l 的第 i（0i=listlength(l) ）個數據元素并用 e返回其值 .時原來的長度為 n的順序表變成長度為n-1.該操作算法見13 下: void deletelist(sqlist *l,int i) int j; if(il-length-1) printf( 不合理); retur

15、n 0; if(l-length=0) printf( 空表); return 0; for(j=1;jbasej=l-basej+1; l-length-; return 1; 七、實驗步驟與源程序#include #define listspaceincr 10 14 typedef struct int *base; int length; int listsize; sqlist; void initlist(sqlist *l,int initsize) l-base=(sqlist*)malloc(sizeof(sqlist); if(!l-base) return; l-leng

16、th=0; l-listsize=initsize; void creatlist(sqlist *l) int i; for(i=0;ilength;i+) scanf(%d,&l-basei); void print(sqlist *l) 15 int i; for(i=0;ilength;i+) printf(%6d,l-basei); void insertlist(sqlist *l,int i,int e) int *newbase; int j; if(il-length+1) return 0; if(l-length=l-listsize) newbase=(int*

17、)realloc(l-base,(l-listsize+listspaceincr) *sizeof(int); if(!newbase) return -2; l-base=newbase; l-listsize+=listspaceincr; for(j=l-length-1;j=i-1;j-) l-basej+1=l-basej; l-basei-1=e; l-length+; return 1; 16 void deletelist(sqlist *l,int i) int j; if(il-length)return 0; for(j=i;jlength;j+) l-basej-1=

18、l-basej; l-length-; return 1; void main() int flag=1,a,i,e,n,j; sqlist l; while(flag) printf(ntt1: 初始化 ntt2:建立順序表 ntt3:輸出順序表 ntt4:在順序表中插入元素 ntt5:在順序表中刪除元素 ntt:其他退出 n); printf(ntt 請選擇 :); scanf(%d,&a); switch(a) 17 case 1: printf(n 請輸入初始化空間的大小 :); scanf(%d,&n); initlist(&l,n); break; case

19、 2: printf(n 請輸入順序表的元素個數 :); scanf(%d,&l.length); creatlist(&l); break; case 3:print(&l); break; case 4:printf(n 請輸入插入的位置與插入的元素:); scanf(%d%d,&i,&e); insertlist(&l,i,e); break; case 5:printf(n 請輸入刪除的位置 :); scanf(%d,&j); deletelist(&l,j); break; default :flag=0; 18 八、程序測試結果選擇“從文件讀取信息”，程序將從文件讀取信息， 如果讀取失敗（不存在該信息文件），則結束，如果讀取成功， 則輸出讀取成功的提示信息，19 九、順序表的優點和缺點20 1、順序表的優點：(1)、實現方法簡單 ,各種高級語言中都有數組,容易實現 ; (2)、訪問元素的速度快 ,因為在順序表中邏輯張相鄰的兩個元素在存儲位置上也必定相鄰 ,所以只要知道了第一個元素的地址,其他任何一個元素的地址都可以通過簡單的計算求的,故可實現隨即存取 ,即順序表 l 的第i 個元素即為 l.basei-1. 2、順序表的缺點：(1)、需占用連續的空間 .存儲要求高 ,不能