實驗報告專用紙

延安大學計算機學院試驗匯報專用紙學號2姓名陳世龍班級計科15-1課程名稱數(shù)據構造試驗項目名稱線性表任課教師曹軍梅指導教師曹軍梅試驗組別第組同組者教師評語及成績：試驗成績：教師簽字：（請按照試驗匯報的有關規(guī)定書寫，一般必須包括：1、試驗目的；2、試驗內容；3、試驗環(huán)節(jié)與措施；4、試驗數(shù)據與程序清單；5、出現(xiàn)的問題及處理措施；6、試驗成果、成果分析與體會等內容。）1、試驗目的：（1）、掌握線性表的基本運算；（2）、掌握次序存儲的概念，學會對次序存儲構造進行操作；（3）、加深對次序存儲數(shù)據構造的理解，處理實際問題。2、試驗內容：（1）、線性表的次序存儲的基本操作；（2）、線性表的鏈式存儲的基本操作；（3）、線性表的應用---一元多項式的表達及相加都基本操作。3、試驗環(huán)節(jié)與措施：（1）、采用線性表的鏈式存儲構造；（2）、用菜單的形式完畢線性表鏈式存儲構造的基本操作；（3）、采用線性表的次序存儲構造；（4）、用菜單的形式完畢線性表次序存儲構造的基本操作；（5）、運用線性表鏈式存儲構造處理常見實際應用問題；（6）、運用線性表次序構造處理常見實際應用問題。4、試驗數(shù)據與程序清單：試驗一：線性表中查找元素位置#include<stdio.h>#include<stdlib.h>#defineNULL0#defineOVERFLOW-2試驗室：機號：試驗日期：年月日延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE100/*此處的宏定義常量表達線性表也許到達的最大長度*/typedefstruct{ ElemTypeelem[MAXSIZE];/*線性表占用的數(shù)組空間*/ intlast;/*記錄線性表中最終一種元素在數(shù)組elem[]中的位置（下標值），空表置為-1*/}SeqList;intLocate(SeqListL,ElemTypee){ inti=0;/*i為掃描計數(shù)器，初值為0，即從第一種元素開始比較*/ while((i<=L.last)&&(L.elem[i]!=e))i++; if(i<=L.last) return(i+1);/*若找到值為e的元素，則返回其序號*/ else return(-1);/*若沒找到，則返回空序號*/}voidmain(){ SeqListl; intp,q,r; inti; printf("請輸入線性表的長度:"); scanf("%d",&r); l.last=r-1; printf("請輸入線性表的各元素值:\n"); for(i=0;i<=l.last;i++) { scanf("%d",&l.elem[i]); } printf("請輸入要查找的元素值:\n"); scanf("%d",&q); p=Locate(l,q); if(p==-1) printf("在此線性表中沒有該元素!\n"); else printf("該元素在線性表中的位置為:%d\n",p);}延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表試驗二：線性表中插入元素操作#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE100/*此處的宏定義常量表達線性表也許到達的最大長度*/typedefstruct{ ElemTypeelem[MAXSIZE];/*線性表占用的數(shù)組空間*/ intlast;/*記錄線性表中最終一種元素在數(shù)組elem[]中的位置（下標值），空表置為-1*/}SeqList;intInsList(SeqList*L,inti,ElemTypee){ intk; if((i<1)||(i>L->last+2))/*首先判斷插入位置與否合法*/延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表{ printf("插入位置i值不合法"); return(ERROR);} if(L->last>=MAXSIZE-1) { printf("表已滿無法插入"); return(ERROR); } for(k=L->last;k>=i-1;k--)/*為插入元素而移動位置*/ L->elem[k+1]=L->elem[k]; L->elem[i-1]=e;/*在C語言數(shù)組中，第i個元素的下標為i-1*/ L->last++; return(OK);}voidmain(){ SeqList*l; intp,q,r; inti; l=(SeqList*)malloc(sizeof(SeqList)); printf("請輸入線性表的長度:"); scanf("%d",&r); l->last=r-1; printf("請輸入線性表的各元素值:\n"); for(i=0;i<=l->last;i++) { scanf("%d",&l->elem[i]); } printf("請輸入要插入的位置:\n"); scanf("%d",&p); printf("請輸入要插入的元素值:\n"); scanf("%d",&q); InsList(l,p,q); for(i=0;i<=l->last;i++) { printf("%d",l->elem[i]); }}延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表試驗三：線性表中刪除元素操作#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE100/*此處的宏定義常量表達線性表也許到達的最大長度*/typedefstruct{ ElemTypeelem[MAXSIZE];/*線性表占用的數(shù)組空間*/ intlast;/*記錄線性表中最終一種元素在數(shù)組elem[]中的位置（下標值），空表置為-1*/}SeqList;intDelList(SeqList*L,inti,ElemType*e){ intk; if((i<1)||(i>L->last+1)) { printf("刪除位置不合法!"); return(ERROR); } *e=L->elem[i-1];/*將刪除的元素寄存到e所指向的變量中*/ for(k=i;i<=L->last;k++)延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表 L->elem[k-1]=L->elem[k];/*將背面的元素依次前移*/ L->last--; return(OK);}voidmain(){ SeqList*l; intp,r; int*q; inti; l=(SeqList*)malloc(sizeof(SeqList)); q=(int*)malloc(sizeof(int)); printf("請輸入線性表的長度:"); scanf("%d",&r); l->last=r-1; printf("請輸入線性表的各元素值:\n"); for(i=0;i<=l->last;i++) { scanf("%d",&l->elem[i]); } printf("請輸入要刪除的元素位置:\n"); scanf("%d",&p); DelList(l,p,q); printf("刪除的元素值為:%d\n",*q);}試驗四：線性表的合并#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#defineERROR0#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE100/*此處的宏定義常量表達線性表也許到達的最大長度*/typedefstruct{ ElemTypeelem[MAXSIZE];/*線性表占用的數(shù)組空間*/ intlast;/*記錄線性表中最終一種元素在數(shù)組elem[]中的位置（下標值），空表置為-1*/}SeqList;void merge(SeqList*LA,SeqList*LB,SeqList*LC){ inti,j,k; i=0;j=0;k=0; while(i<=LA->last&&j<=LB->last) if(LA->elem[i]<=LB->elem[j]) { LC->elem[k]=LA->elem[i]; i++; k++; } else { LC->elem[k]=LB->elem[j]; j++; k++;} while(i<=LA->last) /*當表LA有剩余元素時，則將表LA余下的元素賦給表LC*/ { LC->elem[k]=LA->elem[i]; i++; k++; } while(j<=LB->last)/*當表LB有剩余元素時，則將表LB余下的元素賦給表LC*/ { LC->elem[k]=LB->elem[j]; j++; k++; } LC->last=LA->last+LB->last+1;}voidmain(){ SeqList*la,*lb,*lc; intr;inti; la=(SeqList*)malloc(sizeof(SeqList)); printf("請輸入線性表A的長度:"); scanf("%d",&r); la->last=r-1; printf("請輸入線性表A的各元素值:\n");延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表 for(i=0;i<=la->last;i++) { scanf("%d",&la->elem[i]); } lb=(SeqList*)malloc(sizeof(SeqList)); printf("請輸入線性表B的長度:"); scanf("%d",&r); lb->last=r-1; printf("請輸入線性表B的各元素值:\n"); for(i=0;i<=lb->last;i++) { scanf("%d",&lb->elem[i]); } lc=(SeqList*)malloc(sizeof(SeqList)); merge(la,lb,lc); printf("合并后線性表C中的元素為:\n"); for(i=0;i<=lc->last;i++) { printf("%d",lc->elem[i]); }}試驗五：用頭插法建立單鏈表#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#include<stdlib.h>延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#defineElemTypechartypedefstructNode/*結點類型定義*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/LinkListCreateFromHead(){ LinkListL; Node*s; char c; int flag=1; L=(LinkList)malloc(sizeof(Node));/*建立頭結點*/ L->next=NULL;/*建立空的單鏈表L*/ while(flag)/*flag初值為1，當輸入"$"時，置flag為0，建表結束*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node));/*建立新結點s*/ s->data=c; s->next=L->next;/*將s結點插入表頭*/ L->next=s; } else flag=0; } returnL;}voidmain(){ LinkListl; Node*p; printf("用頭插法建立單鏈表,請輸入鏈表數(shù)據,以$結束!\n"); l=CreateFromHead(); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next;}}延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表試驗六：用尾插法建立單鏈表#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/*結點類型定義*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/voidinit_linklist(LinkList*l)/*對單鏈表進行初始化*/{ *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL;}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*設置一種標志，初值為1，當輸入"$"時，flag為0，建表結束*/ r=L;/*r指針動態(tài)指向鏈表的目前表尾，以便于做尾插入，其初值指向頭結點*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結點s插入表尾*/ { c=getchar(); if(c!='$') {

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表 s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*將最終一種結點的next鏈域置為空，表達鏈表的結束*/ } }}voidmain(){ LinkListl; Node*p; init_linklist(&l); printf("用尾插法建立單鏈表,請輸入鏈表數(shù)據,以$結束!\n"); CreateFromTail(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; }}試驗七：查找線性表結點值#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#defineERROR0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/*結點類型定義*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/voidinit_linklist(LinkList*l)/*對單鏈表進行初始化*/{ *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL;}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*設置一種標志，初值為1，當輸入"$"時，flag為0，建表結束*/ r=L;/*r指針動態(tài)指向鏈表的目前表尾，以便于做尾插入，其初值指向頭結點*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結點s插入表尾*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*將最終一種結點的next鏈域置為空，表達鏈表的結束*/ } }}Node*Get(LinkListL,inti){ intj; Node*p; p=L; j=0;/*從頭結點開始掃描*/ while((p->next!=NULL)&&(j<i)){ p=p->next;/*掃描下一結點*/ j++;/*已掃描結點計數(shù)器*/ } if(i==j)

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表 returnp;/*找到了第i個結點*/ else returnNULL;/*找不到，i≤0或i>n*/}voidmain(){ LinkListl; Node*p; intj; init_linklist(&l); printf("請輸入鏈表數(shù)據,以$結束!\n"); CreateFromTail(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; } printf("請輸入要查找的結點序號:\n"); scanf("%d",&j); p=Get(l,j); if(p!=NULL) printf("該結點的值為:%c\n",p->data); else printf("未找到此結點!\n");}試驗八：判斷線性表長度#include<stdio.h>#include<stdlib.h>#include<malloc.h>

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/*結點類型定義*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/voidinit_linklist(LinkList*l)/*對單鏈表進行初始化*/{ *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL;}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*設置一種標志，初值為1，當輸入"$"時，flag為0，建表結束*/ r=L;/*r指針動態(tài)指向鏈表的目前表尾，以便于做尾插入，其初值指向頭結點*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結點s插入表尾*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*將最終一種結點的next鏈域置為空，表達鏈表的結束*/ } }}int ListLength(LinkListL)/*求帶頭結點的單鏈表L的長度*/{ Node*p; intj; p=L->next; j=0;/*用來寄存單鏈表的長度*/ while(p!=NULL) { p=p->next; j++; }

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表 returnj; /*j為求得的單鏈表長度*/}voidmain(){ LinkListl; Node*p; init_linklist(&l); printf("請輸入鏈表數(shù)據,以$結束!\n"); CreateFromTail(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; } printf("該單鏈表的長度為%d\n",ListLength(l));}試驗九：線性表結點插入操作#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefcharElemType;typedefstructNode/*結點類型定義*/{ ElemTypedata; structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表voidinit_linklist(LinkList*l)/*對單鏈表進行初始化*/{ *l=(LinkList)malloc(sizeof(Node)); (*l)->next=NULL;}voidCreateFromTail(LinkListL){ Node*r,*s; charc; intflag=1;/*設置一種標志，初值為1，當輸入"$"時，flag為0，建表結束*/ r=L;/*r指針動態(tài)指向鏈表的目前表尾，以便于做尾插入，其初值指向頭結點*/ while(flag)/*循環(huán)輸入表中元素值，將建立新結點s插入表尾*/ { c=getchar(); if(c!='$') { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s; } else { flag=0; r->next=NULL;/*將最終一種結點的next鏈域置為空，表達鏈表的結束*/ } }}intInsList(LinkListL,inti,ElemTypee){ Node*pre,*s; intk; pre=L; k=0; while(pre!=NULL&&k<i-1)/*表未查完且未查到第i-1個時反復，找到pre指向第i-1個*/{ pre=pre->next; k=k+1; } /*查找第i-1結點*/ if(!pre)/*如目前位置pre為空表已找完尚未數(shù)到第i個，闡明插入位置不合理*/ { printf("插入位置不合理!"); returnERROR; } s=(Node*)malloc(sizeof(Node));/*申請一種新的結點S*/ s->data=e;/*值e置入s的數(shù)據域*/ s->next=pre->next; /*修改指針，完畢插入操作*/ pre->next=s; returnOK;}voidmain()

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表{ LinkListl; Node*p; intflag=0; inti; charc; init_linklist(&l); printf("請輸入鏈表數(shù)據,以$結束!\n"); CreateFromTail(l); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; } printf("請輸入插入的位置和元素:\n"); scanf("%d,%c",&i,&c); flag=InsList(l,i,c); if(flag) printf("插入操作成功!\n"); else printf("插入操作失敗!\n"); p=l->next; while(p!=NULL) { printf("%c\n",p->data); p=p->next; }}試驗十：兩個單鏈表合并為一種單鏈表#include<stdio.h>

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintElemType;typedefstructNode/*結點類型定義*/{ElemTypedata;structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/voidCreateFromTail(LinkListL){Node*r,*s;charc;intflag=1;r=L;while(flag){scanf("%d",&c);if(c!=-1){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL;/*將最終一種結點的next鏈域置為空，表達鏈表的結束*/}}}LinkListMergeLinkList(LinkListLA,LinkListLB){Node*pa,*pb;Node*r;LinkListLC;pa=LA->next;pb=LB->next;LC=LA;LC->next=NULL;r=LC;while(pa!=NULL&&pb!=NULL){if(pa->data<=pb->data){r->next=pa;r=pa;pa=pa->next;

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表}else{r->next=pb;r=pb;pb=pb->next;}}if(pa)/*若表LA未完，將表LA中后續(xù)元素鏈到新表LC表尾*/r->next=pa;else/*否則將表LB中后續(xù)元素鏈到新表LC表尾*/r->next=pb;free(LB);return(LC);}voidmain(){LinkListla,lb,lc;Node*p;la=(Node*)malloc(sizeof(Node));la->next=NULL;printf("請輸入單鏈表A中的元素(以-1結束!):\n");CreateFromTail(la);printf("單鏈表A中元素為:\n");p=la->next;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");printf("請輸入單鏈表B中的元素(以-1結束!):\n");lb=(Node*)malloc(sizeof(Node));lb->next=NULL;CreateFromTail(lb);printf("單鏈表B中元素為:\n");p=lb->next;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");lc=MergeLinkList(la,lb);printf("單鏈表C中元素為:\n");p=lc->next;while(p!=NULL){

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表printf("%d",p->data);p=p->next;}}試驗十一：循環(huán)鏈表合并操作#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintElemType;typedefstructNode/*結點類型定義*/{ElemTypedata;structNode*next;}Node,*LinkList;/*LinkList為構造指針類型*/voidcreate_clinklist(LinkListl)/*創(chuàng)立循環(huán)鏈表*/{intnum;Node*p;l->data=-1;l->next=l;printf("請輸入循環(huán)鏈表的元素(以-1結束):\n");scanf("%d",&num);

延安大學計算機學院試驗匯報附頁學號2姓名陳世龍班級計科15-1試驗名稱線性表while(num!=-1){p=(Node*)malloc(sizeof(structNode));p->data=num;p->next=l->next;l->next=p;scanf("%d",&num);}}LinkListmerge_1(LinkListLA,LinkListLB){Node*p,*q;p=LA;q=LB;while(p->next!=LA) p=p->next;while(q->next!=LB) q=q->next;q->next=LA;p->next=LB->next;free(LB);return(LA);}voidmain(){LinkListla,lb,lc;Node*p;printf("建立循環(huán)鏈表A，請輸入數(shù)據!:\n");la=(Node*)malloc(sizeof(structNode));create_clinklist(la);p=la->next;while(p!=la){printf("%d\n",p->data);p=p->next;}printf("建立循環(huán)鏈表B，請輸入數(shù)據!:\n");lb=(Node*)malloc(sizeof(structNode));create_clinklist(lb);p=lb->next;while(p!=lb){printf("%d\n",p->