1、精選優質文檔-傾情為你奉上成績：實 驗 報 告課程名稱：數據結構實驗項目：線性表姓 名：zhangsan專 業：網絡工程班 級：09-1班0000010000計算機科學與技術學院實驗教學中心20 11年 5 月 17 日專心-專注-專業實驗項目名稱： 線性表 （ 學時）一、實驗目的了解順序表的結構特點及有關概念，掌握順序表建立、插入、刪除的基本操作算法。2了解單鏈表的結構特點及有關概念，掌握單鏈表建立、插入、刪除的基本操作算法。二、實驗內容1順序表的實踐。1) 建立4個元素的順序表list=2，3，4，5，實現順序表建立的基本操作。2) 在list=2，3，4，5的元素4和5之間插入一個元素9

2、，實現順序表插入的基本操作。3) 在list=2，3，4，9，5中刪除指定位置（i=3）上的元素9，實現順序表的刪除的基本操作。2單鏈表的實踐。1) 建立一個包括頭結點和3個結點的（4，2，1）的單鏈表，實現單鏈表建立的基本操作。2) 在已建好的單鏈表中的指定位置（x=2）插入一個結點3，實現單鏈表插入的基本操作。3) 在一個包括頭結點和4個結點的（4，2，3，1）的單鏈表的指定位置刪除一個結點，實現單鏈表刪除的基本操作。三、實驗步驟線性表（linear list）是n（n0）個數據元素a1，a2，an組成的有限序列。其中n 稱為數據元素的個數或線性表的長度，當n=0時稱為空表，n>0時

3、稱為非空表。通常將非空的線性表記為（a1，a2，,an），其中的數據元素ai（1in）是一個抽象的符號， ai是第i個數據元素,稱i為數據元素ai在線性表中的位置。其具體含義在不同情況下是不同的，即它的數據類型可以根據具體情況而定，本書中，我們將它的類型設定為elemtype，表示某一種具體的已知數據類型。順序表也稱為線性表的順序存儲結構。其存儲方式為：在內存中用一組地址連續的存儲單元依次存儲線性表的數據元素，但該連續存儲空間的大小要大于或等于順序表的長度。一般讓線性表中第一個元素存放在連續存儲空間第一個位置，第二個元素緊跟著第一個之后，其余依此類推。可定義順序表如下： #define max

4、num elemtype listmaxnum; int num=-1;線性表的鏈式存貯結構，也稱為鏈表。其存貯方式是：在內存中利用存貯單元(可以不連續)來存放元素值及它在內存的地址，各個元素的存放順序及位置都可以以任意順序進行，原來相鄰的元素存放到計算機內存后不一定相鄰，從一個元素找下一個元素必須通過地址(指針)才能實現。故不能像順序表一樣可隨機訪問。常用的鏈表有單鏈表、循環鏈表和雙向鏈表、多重鏈表等。單鏈表是線性表的鏈式存貯結構中每個結點只有一個指針域的鏈表。可定義單鏈表的結點結構如下： typedef struct node elemtype data; struct node *nex

5、t; slnode;必做順序表、單鏈表的建立，選作順序表、單鏈表的插入或刪除。四、實驗結果1）建立順序表： 2）順序表插入：3）線性表鏈式存儲：五、程序代碼1建立順序表#include<stdio.h>#define max 10main()int i=0,x,num,ch; int listmax; printf("input list:"); while(ch= getchar()!='n') listi=ch; i+; num=i-1; for(i=0;i<=num;i+) printf("list%d=%c ",

6、i,listi);2順序表插入#include<stdio.h>#define max 100#define true 1#define false 0int insertq(int list,int num,int i,int x) int j; if(i<0)|(i>num+1) printf("mistake."); return(false);if(num>=max-1)printf("list is full."); return(false);for(j=num+1;j>i;j-) listj=listj-

7、1;listi=x;(num)+;return(true);main() int i=0,x,num,ch; int listmax; printf("input list:"); while(ch=getchar()!='n') listi=ch; i+; num=i-1; printf("insert No.i:"); scanf("%d",&i); getchar(); printf("insert data:"); x=getchar(); getchar(); insertq(li

8、st,num,i,x); for(i=0;i<=num+1;i+) printf("list%d=%cn",i,listi); printf("n"); 3線性表鏈式存儲#include<iostream.h>#define elemtype intclass link public: elemtype data; link *next;link *hcreat() link *s,*p; elemtype i; p=new link; p->next=NULL;cout<<"輸入多個結點數值,以空格為間隔，

9、以0為終止符"<<endl; cin>>i; while(i) s=new link; s->data=i; s->next=p->next; p->next=s; cin>>i; return p;void print(link *head) link *p; p=head->next; while(p->next!=NULL) cout<<p->data<<"->" p=p->next; cout<<p->data<<

10、endl;link *Locate(link *head,elemtype x) link *p; p=head->next; while(p!=NULL)&&(p->data!=x) p=p->next; return p;void deletel(link *head,elemtype x) link *p,*q; q=head; p=head->next; while(p!=NULL)&&(p->data!=x) q=p; p=p->next; if(p=NULL) cout<<"要刪除的結點不存在

11、!" else q->next=p->next; delete(p);void insert(link *head,elemtype x,elemtype y) link *p,*s; s=new link; s->data=y; if(head->next=NULL) head->next=s; s->next=NULL; p=Locate(head,x); if(p=NULL) cout<<"插入位置非法!" else s->next=p->next; p->next=s;void change(link *p,elemtype x,elemtype y) link *q; q=p->next; while(q!=NULL) if(q->data=x) q->data=y; q=q->next;void main() int n; elemtype x,y; link *p,*q; p=hcreat(); print(p); cout<<"請輸入要刪除的元素:" cin>>y; deletel(p,y); print(p); cout<<"請輸入插入位置的元素值（將待插元