《數(shù)據(jù)結(jié)構(gòu)》上機實驗一

1、青 島 理 工 大 學(xué)數(shù)據(jù)結(jié)構(gòu)課程實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)班級軟件131實驗日期4.15姓名學(xué)號實驗成績實驗名稱線性表的順序表示與鏈?zhǔn)奖硎緦嶒災(zāi)康募耙髮嶒災(zāi)康?.加深理解線性表的順序表示與鏈?zhǔn)奖硎镜囊饬x和區(qū)別，掌握用它們表示時各基本操作的設(shè)計與實現(xiàn)。2.學(xué)會定義線性表的順序存儲類型和鏈?zhǔn)酱鎯︻愋停瑢崿F(xiàn)C程序的基本結(jié)構(gòu)，對線性表的一些基本操作和具體的函數(shù)定義。3.掌握線性表的基本操作（初始化、建立、插入、刪除、遍歷等）。4.掌握對多函數(shù)程序的輸入、編輯、調(diào)試和運行過程。5.進一步熟練C語言的使用，特別是指針和鏈表的使用。能在實際應(yīng)用背景下恰當(dāng)選擇順序存儲和鏈?zhǔn)酱鎯Α嶒炓?.預(yù)習(xí)C語言中的結(jié)

2、構(gòu)的定義和基本操作方法2.對線性表的每個基本操作用單獨的函數(shù)實現(xiàn)3.編寫完整程序完成下面的實驗內(nèi)容并上機運行4.整理并上交實驗報告實驗環(huán)境硬件平臺：普通的PC機軟件平臺：Windows 2003操作系統(tǒng) 編程環(huán)境：VisualC+實驗內(nèi)容1.分別建立包含10個數(shù)據(jù)元素的順序線性表和鏈?zhǔn)骄€性表； 2.從鍵盤輸入一個數(shù)據(jù)元素和插入位置k，將元素插入到線性表中第k（包含0號位置）個位置； 3.從鍵盤輸入一個數(shù)據(jù)元素關(guān)鍵字或位置k（包含1號位置），從線性表中刪除相應(yīng)數(shù)據(jù)元素；4.能完成查找功能； 5.給出程序及插入、刪除前和插入、刪除后線性表結(jié)果。 算法描述及實驗步驟/創(chuàng)建順式線性表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您輸入的數(shù)據(jù)為：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請輸入您要查找的數(shù)據(jù)：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沒有您所要查找的數(shù)據(jù)n);elseprintf(n找到您所需數(shù)據(jù)%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請輸入您要插入的數(shù)據(jù)：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請輸入要刪除的數(shù)據(jù)：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n沒有您要刪除的數(shù)據(jù)n);return(0);elsefor(;p1num=(p1+1)-num;L-; return(head);struct list *creat_n()/創(chuàng)建有n個元素的鏈表 struct list *q,*p,*head=NULL; printf(n輸入你所要創(chuàng)建的結(jié)點數(shù): ); scanf(%d,&length); head=p=(list*)malloc(sizeof(list); /創(chuàng)建一個新結(jié)點并用頭指針指

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

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

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

10、x)/在要求的X結(jié)點前插入新結(jié)點 k-next=p; q-next=k; printf(插入成功nn); length=length+1; output(); int delet()/刪除結(jié)點函數(shù) struct list *q,*p; int x,y; printf(請輸入你所要刪除的結(jié)點值: ); scanf(%d,&x); if(head=NULL)/表空 printf(表空n); return 0 ; else if(x=head-data)/第一個結(jié)點為刪除的結(jié)點 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的結(jié)點 q=p; p=p-next; if(p=NULL) printf(沒有刪除對象n); if(x=p-data)/刪除值為X的結(jié)點 q-next=p-next; y=p-data; free(p); printf(刪除成功nn); length=length-1; output(); return (y); else printf(表中沒有指定的結(jié)點n); output(); return

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

13、了鏈表，結(jié)果輸出結(jié)果符合情況，程序成功?？偨Y(jié)通過此次試驗，我理解到線性表的順序表示和鏈?zhǔn)奖硎痉椒▽嶋H存在相當(dāng)明顯的區(qū)別，順序結(jié)構(gòu)的表示方法建立在已存在的固定的空間區(qū)域內(nèi)，數(shù)據(jù)超過最大存儲空間就會溢出并丟失，無法實現(xiàn)添加或刪除操作，線性表可以隨機存取表中任意一元素，但在插入或刪除操作時需要移動大量元素，但表示方式精簡、易操作；而鏈?zhǔn)浇Y(jié)構(gòu)的表示方法雖然不如順序結(jié)構(gòu)簡單，卻能動態(tài)分配存儲空間，可以對數(shù)據(jù)進行添加、刪除和修改等操作，功能更為強大，可以提高存儲效率。附錄#include #include #define SIZE 100int L=0;struct numberlong num;/創(chuàng)建順

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您輸入的數(shù)據(jù)為：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請輸入您要查找的數(shù)據(jù)：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沒有您所要查找的數(shù)據(jù)n);elseprintf(n找到您所需數(shù)據(jù)%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請輸入您要插入的數(shù)據(jù)：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請輸入要刪除的數(shù)據(jù)：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n沒有您要刪除的數(shù)據(jù)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 創(chuàng)建鏈表 *n); printf( * 2 插入節(jié)

18、點 *n); printf( * 3 查找數(shù)據(jù) *n); printf( * 4 刪除結(jié)點 *n); printf( * 5 輸出 *n); printf( * 0 退出 *n); printf( *n); printf(*n);scanf(%d,&a);while(a!=0)switch(a)case 1:printf(請創(chuàng)建順序表:); 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繼續(xù)操作請輸入，否則請按0退出：n);scanf(%d,&a);#include #include #include struct list /結(jié)點類型 int data; struct list *next; ; struct list *head;/聲明結(jié)點指針int static length;/聲明表長變量struct list *creat_n()/創(chuàng)建有n個元素的鏈表 struct list *q,*p,*head=NULL; printf(n輸入你所要創(chuàng)建的結(jié)點數(shù): ); scanf(%d,&length); head=p=(list*)ma

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

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

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

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