線性表數(shù)據(jù)結(jié)構(gòu)試驗

1、淮海工學院計算機科學系實驗報告書課程名：數(shù)據(jù)結(jié)構(gòu)線性表數(shù)據(jù)結(jié)構(gòu)試驗題目：班級：學號：姓名：評語:成績： 指導教師： 批閱時間:線性表實驗報告要求1 目的與要求 :1）掌握線性表數(shù)據(jù)結(jié)構(gòu)的基本概念和抽象數(shù)據(jù)類型描述；2）熟練掌握線性表數(shù)據(jù)結(jié)構(gòu)的順序和鏈式存儲存表示；3）熟練掌握線性表順序存儲結(jié)構(gòu)的基本操作算法實現(xiàn)；4）熟練掌握線性表的鏈式存儲結(jié)構(gòu)的基本操作算法實現(xiàn) ;5）掌握線性表在實際問題中的應用和基本編程技巧 ;6）按照實驗題目要求獨立正確地完成實驗內(nèi)容（提交程序清單及相關(guān)實驗數(shù)據(jù)與運行結(jié) 果）；7）按照報告格式和內(nèi)容要求， 認真書寫實驗報告， 并在試驗后的第三天提交電子 （全班同 學提交到

2、學委，再統(tǒng)一打包提交給老師）和紙質(zhì)（每班每次 5 份，學委安排，保證每個同學至 少提交一次） ；8）積極開展實驗組組內(nèi)交流和輔導，嚴禁復制和剽竊他人實驗成果，一旦發(fā)現(xiàn)嚴肅處理；9）上實驗課前，要求每個同學基本寫好程序，并存儲在自己的 U盤上，用于實驗課堂操作時調(diào)試和運行。凡不做準備，沒有提前編寫程序者，拒絕上機試驗。2 實驗內(nèi)容或題目一、順序表的基本操作實現(xiàn)實驗要求：數(shù)據(jù)元素類型 ElemType 取整型 int 。按照順序存儲結(jié)構(gòu)實現(xiàn)如下算法：1） 創(chuàng)建任意整數(shù)線性表（即線性表的元素值隨機在鍵盤上輸入）的順序存儲結(jié)構(gòu)（即順序表），長度限定在 25 之內(nèi)；2）打印 / 顯示（遍歷）該線性表（依

3、次打印 /顯示出表中元素值） ；3）在順序表中查找第 i 個元素，并返回其值；4）在順序表第 i 個元素之前插入一已知元素；5）在順序表中刪除第 i 個元素；6）求順序表中所有元素值（整數(shù)）之和；二、鏈表（帶頭結(jié)點）基本操作實驗要求：數(shù)據(jù)元素類型 ElemType 取字符型 char 。按照動態(tài)單鏈表結(jié)構(gòu)實現(xiàn)如下算法：1）按照頭插法或尾插法創(chuàng)建一個帶頭結(jié)點的字符型單鏈表（鏈表的字符元素從鍵盤輸入），長度限定在 10 之內(nèi)；2）打?。ū闅v）該鏈表（依次打印出表中元素值，注意字符的輸入順序與鏈表的結(jié)點順序）3）在鏈表中查找第 i 個元素， i 合法返回元素值，否則，返回FALSE；4） 在鏈表中查

4、找與一已知字符相同的第一個結(jié)點，有則返回TRUE否則，返回FALSE5）在鏈表中第 i 個結(jié)點之前插入一個新結(jié)點；6）在線性表中刪除第 i 個結(jié)點； 7）計算鏈表的長度。3 實驗步驟與源程序一、 順序表的基本操作實現(xiàn)實驗Common.h#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0Seqlist.h#define ElemType int#define MAXSIZE 25typed

5、ef structElemType elemMAXSIZE;int last;SeqList;#include "common.h"#include "seqlist.h"int Locate（SeqList L, int n）int i=0;while （i<L.last&&i!=n）i+;if （i<=L.last）return L.elemi;elsereturn(-1);int InsList(SeqList *L,int i,ElemType e)int k;if(i<1) | (i>L->last

6、+2)printf(" 插入位置 i 值不合法 "); return(ERROR);if(L->last>= MAXSIZE-1)printf(" 表已滿無法插入 ");return(ERROR);for(k=L->last;k>=i-1;k-)L->elemk+1=L->elemk;L->elemi-1=e;L->last+;return(OK);int DelList(SeqList *L,int i,ElemType *e)int k;if(i<1)|(i>L->last+1)pri

7、ntf(" 刪除位置不合法 !"); return(ERROR);*e = L->elemi-1;for(k=i; k<=L->last; k+)L->elemk-1 = L->elemk;L->last-;return(OK);int AddList(SeqList *L)int k,s=0;for(k=0;k<=L->last;k+)s=s+L->elemk;return s;void main()SeqList l;int p,q,r,*q1;int i;q1=(int*)malloc(sizeof(int);pr

8、intf(" 請輸入線性表的長度 :");scanf("%d",&r);l.last = r-1;:n");printf(" 請輸入線性表的各元素值for(i=0; i<=l.last; i+)scanf("%d",&l.elemi);4printf（" 請輸入要查找的元素的位置 :n"）;scanf("%d",&q);p=Locate(l,q);if(p = -1)!n");printf(" 在此線性表中沒有這樣的元素 el

9、seprintf(" 該位置的元素為 :%dn",p);printf(" 請輸入要插入的位置 :n"); scanf("%d",&p);printf(" 請輸入要插入的元素值 :n");scanf("%d",&q);InsList(&l,p,q);for(i=0; i<=l.last; i+)printf("%d ",l.elemi);printf("n");printf(" 請輸入要刪除的元素位置 :n"

10、);scanf("%d",&p);DelList(&l,p,&q);printf(" 刪除的元素值為 :%dn",q);printf(" 刪除后的元素序列 :n");for(i=0; i<=l.last; i+)printf(" %d ",l.elemi);printf("n");printf(" 剩余數(shù)字之和為： ");printf(" n %d n",AddList(&l);二、鏈表（帶頭結(jié)點）基本操作實驗 Com

11、mon.h#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSELinklist.htypedef char ElemType; typedef struct NodeElemType data; struct Node * next;Node, *LinkList;#include <stdio.h>#include <stdlib.h>#define ElemType

12、 char typedef struct Node ElemType data; struct Node * next;Node, *LinkList;LinkList CreateFromHead()LinkList L;Node *s;charc;intflag=1,i=1;L=(LinkList)malloc(sizeof(Node);L->next=NULL;while(flag&&i<=10)c=getchar();if(c!='$')s=(Node*)malloc(sizeof(Node); s->data=c;s->next

13、=L->next;L->next=s;elseflag=0;i+;return L;Node *search(LinkList L,int i)int j=0;Node *p;p=L;while(p->next!=NULL&&j<i)p=p->next;j+;if(i=j) return p;else return NULL;Node *locate(LinkList L,ElemType key)Node *p;p=L->next;while(p!=NULL)if(p->data!=key) p=p->next;else bre

14、ak;return p;void InsList(LinkList L,int i,ElemType e)Node *p,*s;int k;p=L;k=0;while(p!=NULL&&k<i-1)p=p->next;k=k+1;if(k!=i-1)printf("error!");s=(Node *)malloc(sizeof(Node);s->data=e;s->next=p->next;p->next=s;void delLink(LinkList L,int i,ElemType *e) Node *p,*r;in

15、t k;p=L;k=0;while(p->next!=NULL&&k<i-1)p=p->next;k=k+1;if(k!=i-1)printf(" 位置不合理 ");r=p->next;p->next=p->next->next;*e=r->data;free(r);int Listlength(LinkList L)Node *p;p=L->next;int j=0;while(p!=NULL)p=p->next;j+;return j;void main()LinkList l;Node *p;

16、char e;char a;int i,n;, 以 $ 結(jié)束 !n");printf(" 用頭插法建立單鏈表 , 請輸入鏈表數(shù)據(jù) l = CreateFromHead();p = l->next;printf(" 輸入的字符依次為 :");while(p!=NULL)printf("%c ",p->data);p=p->next;printf("%cn");Node *p1;printf(" 請輸入要查找的字符的序號 :");scanf("%d",&

17、n);printf(" 要查找的字符 :n");p1=search(l,n);printf("%c ",p1->data);printf("%cn");printf(" 插入后的字符 :n");scanf("%c",&a);InsList(l,3,'a');p1=l->next;while(p1!=NULL)printf("%c ",p1->data);p1=p1->next;printf("%cn");de

18、lLink(l,2,&e);p1=l->next;printf(" 刪除后的字符為 :n");while(p1!=NULL)printf("%c ",p1->data);p1=p1->next;printf("%cn");printf(" 該字符串的長度為 :n");i=Listlength(l);printf("%dn",i);printf(" 輸入要查找的字符 :n");scanf("%c",&a);p1=locate(l,a);if(p1!=NULL)printf("true");printf("%cn");elseprintf("flase!");printf("%cn");4 測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）一 順序表的基本操作實現(xiàn)實驗*C:U se reA dm inistrat orDe slcto