數(shù)據(jù)結(jié)構(gòu)與算法實驗報告-線性表

1、沈 陽 工 程 學 院學 生 實 驗 報 告（課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 ）實驗題目： 線性表 班 級 學 號 姓 名 地 點 指導教師 實 驗 日 期 : 年 月 日13 / 14文檔可自由編輯打印一、實驗目的1 了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計算機內(nèi)的兩種存儲結(jié)構(gòu)。2 掌握線性表的順序存儲結(jié)構(gòu)的定義及其C語言的實現(xiàn)。3 掌握線性表的鏈式存儲結(jié)構(gòu)單鏈表的定義及其C語言的實現(xiàn)。4 掌握線性表的基本操作二、實驗環(huán)境Turbo C或是Visual C+三、實驗內(nèi)容與要求實驗1 順序表的操作請編制C程序，利用順序存儲方式來實現(xiàn)下列功能：根據(jù)鍵盤輸入數(shù)據(jù)建立一個線性表，并輸出該線性表；然后根

2、據(jù)屏幕菜單的選擇，可以進行表的創(chuàng)建，數(shù)據(jù)的插入刪除并在插入和刪除數(shù)據(jù)后再輸出線性表；最后在屏幕菜單中選擇0，即可結(jié)束程序的運行。分析：當我們要在順序表的第i個位置上插入一個元素時，必須先將線性表的第i個元素之后的所有元素一次后移一個位置，以便騰出一個位置，再把新元素插入到該位置。當要刪除第i個元素時，也只需將第i個元素之后的所有元素前移一個位置。算法描述：對每個算法，都要寫出算法的中文描述。本實驗中要求分別寫出在第i個（從1開始計數(shù)）結(jié)點前插入數(shù)據(jù)為x的結(jié)點、刪除指定結(jié)點、創(chuàng)建一個線性表。打印線性表等的算法描述。實驗2 單鏈表的操作請編制C程序，利用鏈式存儲方式來實現(xiàn)線性表的創(chuàng)建、插入、刪除和

3、查找等操作。具體地說，就是要根據(jù)鍵盤輸入的數(shù)據(jù)建立一個單鏈表；然后根據(jù)屏幕菜單的選擇，可以進行數(shù)據(jù)的插入或刪除，并在插入或刪除數(shù)據(jù)后，再輸出單鏈表；最后在屏幕菜單中選擇0，即可結(jié)束程序的運行。算法描述：本實驗要求分別寫出在單鏈表中第i（從1開始計數(shù)）個位置之后插入元素、創(chuàng)建單鏈表、在單鏈表中刪除第i個位置的元素、順序輸出單鏈表的內(nèi)容等的算法描述。四、實驗過程及結(jié)果分析實驗1 順序表的操作#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#include<stdio.h>#includ

4、e<stdlib.h>#define ML 1/線性表#define TURE 1#define FALSE 0#define OK 1#define ERR 0typedef struct int listML;int size;int MAXSIZE;sqList;sqList *Init_List(sqList *L,int ms);void Disp_List(sqList *L);int LocateElem_List(sqList *L,int x);int Insert_List(sqList *L,int x,int mark);int Delete_List1(s

5、qList *L,int item);int Delete_List2(sqList *L,int mark);sqList *Init_List(sqList *L,int ms)L=(sqList *)malloc(ms*sizeof(sqList);if(!L)printf("Memory allocation failuren");exit(OVERFLOW);elseL->size=0; L->MAXSIZE=ms;return L;void Disp_List(sqList *L)int i;for(i=0;i<L->size;i+)pr

6、intf("%d",L->listi);printf("n");int LocateElem_List(sqList *L,int x)int i=0;for(i=0;i<=L->size;i+)if(L->listi=x)return i;if(i>L->size) return -1;int Insert_List(sqList *L,int x,int mark)int i=1;if(L->size>=L->MAXSIZE)return -1;if(mark>0)for(i=L->s

7、ize+1;i>=mark;i-)L->listi+1=L->listi; L->listi=x;else if(mark<0)L->listL->size=x; L->size+;return FALSE;int Delete_List1(sqList *L,int item)int i,j;for(i=0;i<L->size;i+)if(item=L->listi)break;if(i<L->size)for(j=i+1;j<L->size-1;j+)L->listj=L->listj+1

8、;L->size-;return i;return FALSE;int Delete_List2(sqList *L,int mark)int i,item;if(mark>0)item=L->listmark;for(i=mark+1;i<L->size-1;i+)L->listi=L->listi+1;L->size-;return i;return FALSE;void main()int p,n,x=0; sqList a,*b;b=Init_List(&a,ML);printf("listaddr=%dtsize=%d

9、tMaxSize=%d",b->list,b->size,b->MAXSIZE);while(1)printf("n請輸入值，0為結(jié)束輸入：");scanf("%d",&x);if(!x) break;printf("請輸入插入位置：");scanf("%d",&p);Insert_List(b,x,p);printf("線性表為：n"); Disp_List(b);while(1)printf("請輸入查找值，輸入0結(jié)束查找操作："

10、;);scanf("%d",&x);if(!x) break;n=LocateElem_List(b,x);if(n<0) printf("沒找到n");elseprintf("又符合條件的值，位置為：%dn",n+1);while(1)printf("請輸入刪除值，輸入0結(jié)束查找操作：");scanf("%d",&x);if(!x) break;n=Delete_List1(b,x);if(n<0)printf("沒找到n");elseprint

11、f("刪除成功，線性表為:");Disp_List(b);while(1)printf("請輸入刪除值位置，輸入o結(jié)束查找操作:");scanf("%d",&p);if(!p) break;n=Delete_List2(b,p);if(p<0) printf("位置越界n");elseprintf("線性表為:");Disp_List(b);實驗2 單鏈表的操作#include <stdio.h>#include <malloc.h>#define null

12、 0typedef int ElemType; /* 字符型數(shù)據(jù)*/struct LNodeElemType data;struct LNode *next;void setnull(struct LNode *p);int length (struct LNode *p);ElemType get(struct LNode *p,int i);void insert(struct LNode *p,ElemType x,int i);void dele(struct LNode *p,int i);void display(struct LNode *p);int locate(struct

13、 LNode *p,ElemType x);void main()struct LNode *head,*q; /*定義靜態(tài)變量*/int select,x1,x2,x3,x4;int i,n; int m,g;char e,y; setnull(&head); /*建設鏈表并設置為空表*/ printf("請輸入數(shù)據(jù)長度: "); scanf("%d",&n); for(i=1;i<=n;i+) printf("將數(shù)據(jù)插入到單鏈表中: "); scanf("%d",&y); inse

14、rt(&head,y,i); /*插入數(shù)據(jù)到鏈表*/ display(&head); /*顯示鏈表所有數(shù)據(jù)*/ printf("select 1 求長度 length()n"); printf("select 2 取結(jié)點 get()n"); printf("select 3 求值查找 locate()n"); printf("select 4 刪除結(jié)點 delete()n");printf("select 0 退出n"); printf("input your sele

15、ct: "); scanf("%d",&select); while(select!=0) switch(select)case 1:x1=length(&head);printf("輸出單鏈表的長度%d ",x1); display(&head); break; case 2: printf("請輸入要取得結(jié)點: "); scanf("%d",&m); x2=get(&head,m); printf("%d",x2); display(&

16、;head); break; case 3: printf("請輸入要查找的數(shù)據(jù): "); scanf("%d",&e); x3=locate(&head,e); printf("%d",x3); display(&head); break; case 4: printf("請輸入要刪除的結(jié)點: "); scanf("%d",&g); dele(&head,g); display(&head); break; printf("select

17、 1 求長度 length()n"); printf("select 2 取結(jié)點 get()n"); printf("select 3 求值查找 locate()n"); printf("select 4 刪除結(jié)點 delete()n");printf("select 0 退出n"); printf("input your select: "); scanf("%d",&select); void setnull(struct LNode *p)*p=nul

18、l;int length (struct LNode *p)int n=0; struct LNode *q=*p; while (q!=null) n+; q=q->next; return(n);ElemType get(struct LNode *p,int i)int j=1;struct LNode *q=*p;while (j<i&&q!=null) q=q->next; j+; if(q!=null) return(q->data); elseprintf("位置參數(shù)不正確!n");return 0;int locate

19、(struct LNode *p,ElemType x)int n=0; struct LNode *q=*p;while (q!=null&&q->data!=x) q=q->next; n+; if(q=null) return(-1); else return(n+1);void insert(struct LNode *p,ElemType x,int i)int j=1; struct LNode *s,*q; s=(struct LNode *)malloc(sizeof(struct LNode); s->data=x; q=*p; if(i=1) s->next=q; *p=s; else while(j<i-1&&q->next!=null) q=q->next; j+; if(j=i-1) s->next=q->next; q->next=s; else printf("位置參數(shù)不正確!n")