1、青 島 理 工 大 學數據結構課程實驗報告課程名稱數據結構班級軟件131實驗日期4.15姓名學號實驗成績實驗名稱線性表的順序表示與鏈式表示實驗目的及要求實驗目的1.加深理解線性表的順序表示與鏈式表示的意義和區別，掌握用它們表示時各基本操作的設計與實現。2.學會定義線性表的順序存儲類型和鏈式存儲類型，實現C程序的基本結構，對線性表的一些基本操作和具體的函數定義。3.掌握線性表的基本操作（初始化、建立、插入、刪除、遍歷等）。4.掌握對多函數程序的輸入、編輯、調試和運行過程。5.進一步熟練C語言的使用，特別是指針和鏈表的使用。能在實際應用背景下恰當選擇順序存儲和鏈式存儲。實驗要求1.預習C語言中的結

2、構的定義和基本操作方法2.對線性表的每個基本操作用單獨的函數實現3.編寫完整程序完成下面的實驗內容并上機運行4.整理并上交實驗報告實驗環境硬件平臺：普通的PC機軟件平臺：Windows 2003操作系統 編程環境：VisualC+實驗內容1.分別建立包含10個數據元素的順序線性表和鏈式線性表； 2.從鍵盤輸入一個數據元素和插入位置k，將元素插入到線性表中第k（包含0號位置）個位置； 3.從鍵盤輸入一個數據元素關鍵字或位置k（包含1號位置），從線性表中刪除相應數據元素；4.能完成查找功能； 5.給出程序及插入、刪除前和插入、刪除后線性表結果。 算法描述及實驗步驟/創建順式線性表struct nu

3、mber *creat(void)struct number *head,*p1;p1=head=(struct number*)malloc( SIZE * sizeof(struct number);scanf(%ld,&p1-num);for(;p1-num!=0;L+)p1+;scanf(%ld,&p1-num);return(head);/輸出順式線性表中的元素void print(struct number*head)struct number *p;int s=L;p=head;if(p!=0)printf(n您輸入的數據為：n);for(;s0;p+,s-)printf(%ld

4、 ,p-num);/查找順式線性表中的元素void search(struct number *head)struct number *p;long num1;int n=0,s=0;p=head;printf(n請輸入您要查找的數據：n);scanf(%ld,& num1);if(head!=0)for(;p-num!=0;p+)n+;if(p-num=num1)s=1;break;if(s=0)printf(n沒有您所要查找的數據n);elseprintf(n找到您所需數據%ld在表中第%d個n,num1,n);/插入順式線性表的元素struct number *insert(struct

5、 number*head)struct number *p1,*p2;int n=1;long num1;p1=p2=head;p2=p2+L-1;printf(n請輸入您要插入的數據：n);scanf(%ld,&num1);if(num1num)for(p1=head;p1-num=p1;p2-)(p2+1)-num=p2-num;(p2+1)-num=num1;L+;return(head);/刪除順式線性表的元素struct number *del(struct number*head)struct number *p1,*p2;long num1;int n=1;p1=p2=head;

6、printf(n請輸入要刪除的數據：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n沒有您要刪除的數據n);return(0);elsefor(;p1num=(p1+1)-num;L-; return(head);struct list *creat_n()/創建有n個元素的鏈表 struct list *q,*p,*head=NULL; printf(n輸入你所要創建的結點數: ); scanf(%d,&length); head=p=(list*)malloc(sizeof(list); /創建一個新結點并用頭指針指

7、向它 printf(輸入該結點的值: ); scanf(%d, &p-data); p-next=NULL; for(int i=length-1;i=1;i-) q=p; p=(list*)malloc(sizeof(list); /創建新結點 printf(輸入該結點的值: ); scanf(%d, &p-data); q-next=p; printf(輸入完畢nn); p-next=NULL; return head; struct list * output()/輸出表長與結點值函數 struct list *p; p=head; printf(n當前鏈表中存有的元素:n); whil

8、e(p!=NULL) printf(%dn,p-data); p=p-next; printf(當前的表長是: %dnn,length);/輸出當前表長 return head;void insert()/插入結點函數 struct list *k,*p,*q; int x; printf(請輸入你要在哪個結點值之前插入新結點: ); scanf(%d,&x); k=(list*)malloc(sizeof(list);/創建新結點 printf(請輸入新結點的值: ); scanf(%d,&k-data); k-next=NULL; if(head=NULL)/若鏈表為空,則直接入鏈表 he

9、ad=k; length=length+1; printf(插入成功nn); else if(head-data=x)/在第一個結點前插入新結點 k-next=head; head=k; printf(插入成功nn); length=length+1; else q=head; p=head-next; while(p != NULL) & (p-data != x)/找出值為X的結點的位置 q = p; p = p-next; if (p = NULL) q-next=k;/在鏈表末插入新結點 printf(插入成功n); length=length+1; else if(p-data =

10、x)/在要求的X結點前插入新結點 k-next=p; q-next=k; printf(插入成功nn); length=length+1; output(); int delet()/刪除結點函數 struct list *q,*p; int x,y; printf(請輸入你所要刪除的結點值: ); scanf(%d,&x); if(head=NULL)/表空 printf(表空n); return 0 ; else if(x=head-data)/第一個結點為刪除的結點 q=head; head=head-next; y=q-data; free(q); printf(刪除成功nn); le

11、ngth=length-1; output(); return(y); else q=head; p=head-next; while(p != NULL) & (p-data != x)/找出值為X的結點 q=p; p=p-next; if(p=NULL) printf(沒有刪除對象n); if(x=p-data)/刪除值為X的結點 q-next=p-next; y=p-data; free(p); printf(刪除成功nn); length=length-1; output(); return (y); else printf(表中沒有指定的結點n); output(); return

12、0; return 0; void find() struct list *p; int k,x,i=1; char y,n; LOOP: p=head; printf(請輸入你要查找的結點值: ); scanf(%d,&x); while(p-data!=x) p=p-next; i+; printf(你所查找的結點是表中第 %d 個結點!nn,i); printf(是否要繼續查找,請輸入y/nnn); k=getch(); if(k=y) i=1; goto LOOP; else return;調試過程及實驗結果程序運行過程中輸入了順序表，結果輸出結果符合情況，程序成功。程序運行過程中輸入

13、了鏈表，結果輸出結果符合情況，程序成功。總結通過此次試驗，我理解到線性表的順序表示和鏈式表示方法實際存在相當明顯的區別，順序結構的表示方法建立在已存在的固定的空間區域內，數據超過最大存儲空間就會溢出并丟失，無法實現添加或刪除操作，線性表可以隨機存取表中任意一元素，但在插入或刪除操作時需要移動大量元素，但表示方式精簡、易操作；而鏈式結構的表示方法雖然不如順序結構簡單，卻能動態分配存儲空間，可以對數據進行添加、刪除和修改等操作，功能更為強大，可以提高存儲效率。附錄#include #include #define SIZE 100int L=0;struct numberlong num;/創建順

14、式線性表struct number *creat(void)struct number *head,*p1;p1=head=(struct number*)malloc( SIZE * sizeof(struct number);scanf(%ld,&p1-num);for(;p1-num!=0;L+)p1+;scanf(%ld,&p1-num);return(head);/輸出順式線性表中的元素void print(struct number*head)struct number *p;int s=L;p=head;if(p!=0)printf(n您輸入的數據為：n);for(;s0;p+,

15、s-)printf(%ld ,p-num);/查找順式線性表中的元素void search(struct number *head)struct number *p;long num1;int n=0,s=0;p=head;printf(n請輸入您要查找的數據：n);scanf(%ld,& num1);if(head!=0)for(;p-num!=0;p+)n+;if(p-num=num1)s=1;break;if(s=0)printf(n沒有您所要查找的數據n);elseprintf(n找到您所需數據%ld在表中第%d個n,num1,n);/插入順式線性表的元素struct number *

16、insert(struct number*head)struct number *p1,*p2;int n=1;long num1;p1=p2=head;p2=p2+L-1;printf(n請輸入您要插入的數據：n);scanf(%ld,&num1);if(num1num)for(p1=head;p1-num=p1;p2-)(p2+1)-num=p2-num;(p2+1)-num=num1;L+;return(head);/刪除順式線性表的元素struct number *del(struct number*head)struct number *p1,*p2;long num1;int n=

17、1;p1=p2=head;printf(n請輸入要刪除的數據：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n沒有您要刪除的數據n);return(0);elsefor(;p1num=(p1+1)-num;L-; return(head);void main()struct number *head,*head1,*head2;int a;/*head=creat(); print(head);*/printf(n*n);printf( *n); printf( * 1 創建鏈表 *n); printf( * 2 插入節

18、點 *n); printf( * 3 查找數據 *n); printf( * 4 刪除結點 *n); printf( * 5 輸出 *n); printf( * 0 退出 *n); printf( *n); printf(*n);scanf(%d,&a);while(a!=0)switch(a)case 1:printf(請創建順序表:); head=creat();break;case 2:head1=insert(head);break;case 3:search(head);break;case 4:head2=del(head);break; case 5:print(head);ca

19、se 0:break;printf(n繼續操作請輸入，否則請按0退出：n);scanf(%d,&a);#include #include #include struct list /結點類型 int data; struct list *next; ; struct list *head;/聲明結點指針int static length;/聲明表長變量struct list *creat_n()/創建有n個元素的鏈表 struct list *q,*p,*head=NULL; printf(n輸入你所要創建的結點數: ); scanf(%d,&length); head=p=(list*)ma

20、lloc(sizeof(list); /創建一個新結點并用頭指針指向它 printf(輸入該結點的值: ); scanf(%d, &p-data); p-next=NULL; for(int i=length-1;i=1;i-) q=p; p=(list*)malloc(sizeof(list); /創建新結點 printf(輸入該結點的 值: ); scanf(%d, &p-data); q-next=p; printf(輸入完畢nn); p-next=NULL; return head; struct list * output()/輸出表長與結點值函數 struct list *p; p

21、=head; printf(n當前鏈表中存有的元素:n); while(p!=NULL) printf(%dn,p-data); p=p-next; printf(當前的表長是: %dnn,length);/輸出當前表長 return head;void insert()/插入結點函數 struct list *k,*p,*q; int x; printf(請輸入你要在哪個結點值之前插入新結點: ); scanf(%d,&x); k=(list*)malloc(sizeof(list);/創建新結點 printf(請輸入新結點的值: ); scanf(%d,&k-data); k-next=N

22、ULL; if(head=NULL)/若鏈表為空,則直接入鏈表 head=k; length=length+1; printf(插入成功nn); else if(head-data=x)/在第一個結點前插入新結點 k-next=head; head=k; printf(插入成功nn); length=length+1; else q=head; p=head-next; while(p != NULL) & (p-data != x)/找出值為X的結點的位置 q = p; p = p-next; if (p = NULL) q-next=k;/在鏈表末插入新結點 printf(插入成功n);

23、length=length+1; else if(p-data = x)/在要求的X結點前插入新結點 k-next=p; q-next=k; printf(插入成功nn); length=length+1; output(); int delet()/刪除結點函數 struct list *q,*p; int x,y; printf(請輸入你所要刪除的結點值: ); scanf(%d,&x); if(head=NULL)/表空 printf(表空n); return 0 ; else if(x=head-data)/第一個結點為刪除的結點 q=head; head=head-next; y=q-data; free(q); printf(刪除成功nn); length=length-1; output(); return(y); else q=head; p=head-next; while(p != NULL) & (p-data != x)/找出值為X的結點 q=p; p=p-nex