可以參考的數(shù)據(jù)結(jié)構(gòu)實驗報告，用C語言編寫鏈表
數(shù)據(jù)結(jié)構(gòu)上機實驗報告
----線性表
專 業(yè)：計算機科學(xué)與技術(shù)學(xué)院
班 級：
姓 名
學(xué) 號：
指導(dǎo)教師：
日 期：
一.實驗題目
線性表的實現(xiàn)與操作
二.實驗?zāi)康?br />
(1).掌握順序表的存儲結(jié)構(gòu)形式及其描述和基本運算的實現(xiàn)。
(2).熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計。
(3).掌握用鏈表表示特定形式的數(shù)據(jù)的方法，并能編寫出有關(guān)
運算的算法。
*(4).理解單循環(huán)鏈表及雙循環(huán)鏈表的特點。
三.實驗要求
1.線性表的順序存儲與操作
(1). 輸入一組整型元素序列，建立順序表.
(2). 實現(xiàn)該順序表的遍歷.
(3). 在該順序表中進行順序查找某一元素,查找成功返回1,否則返回0.
(4). 判斷該順序表中元素是否對稱,對稱返回1,否則返回0.
(5). 實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù).
(6). 輸入整型元素序列利用有序表插入算法建立一個有序表.
(7). 利用算法6建立兩個非遞減有序表并把它們合并成一個非遞減有序表.
(8). 編寫一個主函數(shù),調(diào)試上述算法.
2.線性表的鏈式存儲與操作
(1). 隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表（無序）.
(2). 遍歷單向鏈表.
(3). 把單向鏈表中元素逆置（不允許申請新的結(jié)點空間）.
(4). 在單向鏈表中刪除所有的偶數(shù)元素結(jié)點.
(5). 編寫在非遞減有序鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單向鏈表.
(6). 利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞增鏈表.
(7). 利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞減鏈表.
(8). 利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）.
(9). 采用單向鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相
加并輸出結(jié)果
(10) 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法.
四.實驗內(nèi)容
為線性表的順序存儲與鏈式存儲建兩個工程,分別為SqList和LinkList.函數(shù)的實現(xiàn)部分采用頭文件的形式,在主函數(shù)中引用各個頭文件,并調(diào)用相關(guān)函數(shù)實現(xiàn)實驗的要求.
1. 線性表的順序存儲與操作
下面的頭文件是一個類型定義文件.
//Instruction.h
#ifndef INSTRUCTION_H
#define INSTRUCTION_H
#define MAXSIZE 100 //表中元素的最大個數(shù)
typedef int ElemType;//元素類型
typedef struct list{
ElemType elem[MAXSIZE];//靜態(tài)線性表
int length; //表的實際長度
}SqList;//順序表的類型名
#endif
(1). 輸入一組整型元素序列，建立順序表.
說明:這個功能用CreatList.h來實現(xiàn).這個函數(shù)已經(jīng)實現(xiàn)了元素的有序插入.在輸入數(shù)據(jù)時需以一個字符來作為結(jié)束符.另外,在源程序中還增加了任意插入和刪除操作的函數(shù).這里只列出了創(chuàng)建有序順序表的部分.
//CreatList.h
#ifndef CREATLIST_H
#define CREATLIST_H
#include"Instruction.h"
#include<stdio.h>
#include<stdlib.h>
void CreatList(SqList *mysqlist){ //創(chuàng)建一個整數(shù)順序鏈表
int count=0;
int temp;
mysqlist->length=0;
printf("輸入一組整數(shù)(以字符結(jié)束):\n");
while(scanf("%d",&temp))
{
if(mysqlist->length==MAXSIZE)
{
printf("順序表已滿!\n");
return ;
}
else //有序插入
{
int i;
for(i=0;i<mysqlist->length;i++)
{
if(temp<mysqlist->elem[ i])
{
int j;
for(j=mysqlist->length;j>i;j--) //后移
mysqlist->elem[j]=mysqlist->elem[j-1];
mysqlist->elem[ i]=temp; //插入
break;
}
}
if(i==mysqlist->length)mysqlist->elem[ i]=temp; //插入到表尾
count++;
mysqlist->length++;
}
}
fflush(stdin); //清空緩存
}
(2).實現(xiàn)該順序表的遍歷.
//Traversal.h
#ifndef TRAVERSAL_H
#define TRAVERSAL_H
#include"Instruction.h"
#include<stdio.h>
void Traversal(SqList mysqlist){
int count=0;
printf("此順序表中的元素為:\n");
for(count;count<mysqlist.length;count++) // 遍歷
printf("%d ",mysqlist.elem[count]);
printf("\n");
}
#endif
(3) 在該順序表中進行順序查找某一元素,查找成功返回1,否則返回0
//Search.h
#ifndef SEARCH_H
#define SEARCH_H
#include"Instruction.h"
int Search(SqList mysqlist,int elem)
{
int count=0;
for(count;count<mysqlist.length;count++) //查找
if(mysqlist.elem[count]==elem)
return 1;
return 0;
}
#endif
(4). 判斷該順序表中元素是否對稱,對稱返回1,否則返回0.
//IsSimilar.h
#ifndef ISSIMILAR_H
#define ISSIMILAR_H
#include"Instruction.h"
int IsSimilar(SqList mysqlist){
int i;
for(i=0;i<mysqlist.length/2;i++) //對于順序表,只需到length/2
{
if(mysqlist.elem[ i]!=mysqlist.elem[mysqlist.length-1-i])//判斷是否對稱
return 0; //不對稱
}
return 1; //對稱
}
#endif
(5). 實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)
//ReOrder.h
#ifndef REORDER_H
#define REORDER_H
#include"Instruction.h"
void ReOrder(SqList *mysqlist){
int temp,count=0,newLocation=0;
for(count;count<mysqlist->length;count++)
{
if(mysqlist->elem[count]%2!=0) //元素為奇數(shù)
{
temp=mysqlist->elem[count];
mysqlist->elem[count]=mysqlist->elem[newLocation]; //將奇數(shù)調(diào)到前面(對調(diào))
mysqlist->elem[newLocation]=temp;
newLocation++;
}
}
}
#endif
(6). 輸入整型元素序列利用有序表插入算法建立一個有序表.
說明:這個功能與第一個功能合并.已在(1)中.此處略
(7).利用算法6建立兩個非遞減有序表并把它們合并成一個非遞減有序表.
//MergeList.h
#ifndef MERGELIST_H
#define MERGELIST_H
#include"Instruction.h"
#include"CreatList.h"
SqList MergeList(SqList *ListA,SqList *ListB){
int counta=0,countb=0,countc=0;
SqList C;
C.length=0;
while((counta<ListA->length)&&(countb<ListB->length)) //A,B為非空
{
if(ListA->elem[counta]<ListB->elem[countb])
{
C.elem[countc]=ListA->elem[counta];counta++;
countc++;C.length++;
}
else
{
C.elem[countc]=ListB->elem[countb];countb++;
countc++;C.length++;
}
}
while(counta<ListA->length) //將A的剩余部分插到C后面
{
for(counta;counta<ListA->length;counta++)
{
C.elem[countc]=ListA->elem[counta];
countc++;C.length++;
}
}
while(countb<ListB->length) //將B的剩余部分插到C后面
{
for(countb;countb<ListB->length;countb++)
{
C.elem[countc]=ListB->elem[countb];
countc++;C.length++;
}
}
return C;
}
#endif
(8). 編寫一個主函數(shù),調(diào)試上述算法.
說明:在主函數(shù)中包含上述所有頭文件,Menu頭文件給出一個菜單,用戶輸入選項并執(zhí)行函數(shù)調(diào)用,這里不將其列出以免冗余.
//ListTest.c
#include<stdio.h>
#include<stdlib.h>
#include"Instruction.h"
#include"CreatList.h"
#include"Traversal.h"
#include"IsSimilar.h"
#include"Search.h"
#include"ReOrder.h"
#include"MergeList.h"
#include"Menu.h"
int main()
{
Menu();
return 0;
}
2. 線性表的鏈式存儲與操作
說明:鏈式存儲與順序存儲大同小異,只不過鏈式存儲用的是指針,而順序存儲用數(shù)組.
首先給出下列的類型定義
//LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
typedef struct LinkList{
int element; //數(shù)據(jù)元素
struct LinkList *next; //結(jié)點指針
}LkList;
#endif
(1). 隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表（無序）.
說明:下面這個函數(shù)實現(xiàn)從鍵盤輸入元素,建立的鏈表是無序的,有頭結(jié)點.與順序表的輸入一樣,需鍵入一個字符以作為結(jié)束符
//CreatLinkList
#ifndef BUILDLINKLIST_H
#define BUILDLINKLIST_H
#include"LinkList.h"
LkList * CreatLinkList(){
int buffer;
LkList *Head=(LkList*)malloc(sizeof(LkList));
LkList *NewElement,*p;
Head->next=NULL;
p=Head;
printf("輸入一行整數(shù)(以字符結(jié)束):\n");
while(scanf("%d",&buffer))
{
NewElement=(LkList*)malloc(sizeof(LkList)); //為新結(jié)點分配空間
NewElement->element=buffer;
p->next=NewElement;
p=p->next;
p->next=NULL;
}
fflush(stdin); //清空緩沖輸入
return Head;
}
#endif
(2). 遍歷單向鏈表.
//Traversal.h
#ifndef TRAVERSAL_H
#define TRAVERSAL_H
#include"LinkList.h"
void Traversal(LkList* List){
LkList *p;
if(List->next==NULL)
{
printf("這是一個空表!\n");
return ;
}
printf("遍歷鏈表:"); //遍歷鏈表
for(p=List->next;p!=NULL;p=p->next)
printf("%d ",p->element);
printf("\n");
}
#endif
(3). 把單向鏈表中元素逆置（不允許申請新的結(jié)點空間）.
說明:這個函數(shù)在習(xí)題集上有一道.要注意的主要是如何在不申請新的結(jié)點空間的情況下逆置.解決的辦法是依次將頭結(jié)點后面的結(jié)點插入到頭結(jié)點之后,作為它的直接后繼.這樣,第一個插入的是第一個結(jié)點,到插入完畢已變成了最后一個結(jié)點.而最后插入的結(jié)點變成了第一個結(jié)點.
//Reserve.h
#ifndef REVERSE_H
#define REVERSE_H
#include"LinkList.h"
void Reverse(LkList *L){
LkList *p,*q;
p=L->next;
L->next=NULL;
for(p;p!=NULL;)
{
q=p->next; //將結(jié)點插入到頭結(jié)點之后
p->next=L->next;
L->next=p;
p=q;
}
printf("成功逆置!\n");
}
#endif
(4). 在單向鏈表中刪除所有的偶數(shù)元素結(jié)點.
//DeleteEven.h
#ifndef DELETEEVEN_H
#define DELETEEVEN_H
#include"LinkList.h"
void DeleteEven(LkList *L){
LkList *p,*q;
p=L;
for(p;p->next!=NULL;)
{
if((p->next->element)%2==0) //結(jié)點元素為偶數(shù)
{
q=p->next;
p->next=p->next->next;
free(q); //釋放已刪除的結(jié)點
continue;
}
p=p->next;
}
printf("已成功刪除偶數(shù)結(jié)點!\n");
}
#endif
(5). 編寫在非遞減有序鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單向鏈表.
說明:與函數(shù)(1)的功能相似,增加了有序非遞減的要求
//BuildIncreaseLinkList.h
#ifndef BUILDINCREASELINKLIST_H
#define BUILDINCREASELINKLIST_H
#include"LinkList.h"
LkList *BuildIncreaseLinkList(){
int buffer;
LkList *Head=(LkList*)malloc(sizeof(LkList));
LkList *NewElement,*p,*q;
Head->next=NULL;
p=Head;
printf("輸入一行整數(shù)(以字符結(jié)束):\n");
while(scanf("%d",&buffer))
{
NewElement=(LkList*)malloc(sizeof(LkList));
NewElement->element=buffer;
for(p=Head;p!=NULL;p=p->next) //按遞增順序插入
{
if(p==Head)continue;
if(p->element>buffer)
{
for(q=Head;q->next!=p;q=q->next){} //將新元素插入到P之前
q->next=NewElement;
NewElement->next=p;
break;
}
}//for
if(p==NULL)
{
for(p=Head;p->next!=NULL;p=p->next){}
p->next=NewElement; //若是為空表或者要插入的元素在鏈表中是最大的,
p=p->next; //則將其直接插入到表尾
p->next=NULL;
}
}//while
fflush(stdin); //清空緩沖輸入
return Head;
}
#endif
(6). 利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞增鏈表.
說明:這個功能與(7)基本一樣,因為在(7)的基礎(chǔ)上利用(3)功能即可實現(xiàn).此處略寫,而只列出(7)的實現(xiàn)方法.
(7). 利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞減鏈表.
說明:為了節(jié)省空間,合并之后的頭結(jié)點即為Lc=La;
//MergeLinkList.h
#ifndef MERGELINKLIST_H
#define MERGELINKLIST_H
#include"LinkList.h"
LkList * MergeLinkList(LkList *La,LkList *Lb){
LkList *Lc,*pa,*pb,*pc;pa=La->next;
pb=Lb->next;Lc=pc=La;
while(pa&&pb) //La,Lb為非空
{
if(pa->element<pb->element)
{
pc->next=pa;pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;pc=pb;
pb=pb->next;
}
}
while(pa) //插入La剩余部分
{
pc->next=pa;pc=pa;
pa=pa->next;
}
while(pb) //插入Lb剩余部分
{
pc->next=pb;pc=pb;
pb=pb->next;
}
free(Lb);
printf("合并成功!\n");
return Lc;
}
#endif
(8). 利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）.
說明:這里不用(1)建立的鏈表,而是用合并后的Lc來完成.分解后奇數(shù)部分以O(shè)ddpart為頭結(jié)點.剩余的偶數(shù)部分以Lc作為頭結(jié)點
//Separate.h
#ifndef SEPARATE_H
#define SEPARATE_H
#include"LinkList.h"
void Separate(LkList *OddPart,LkList *Source){
LkList *p,*q;
p=Source;
q=OddPart;
if(Source->next==NULL)
{
printf("這是一個空表!\n");
return ;
}
for(p;p->next!=NULL;)
{
if((p->next->element)%2!=0)
{
q->next=p->next;
q=q->next;
p->next=p->next->next;
q->next=NULL;
}
else p=p->next;
}
}
#endif
(9). 采用單向鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相
加并輸出結(jié)果
//暫未實現(xiàn)，不寫了。
(10) 在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法.
說明:給出了一個菜單,由用戶選擇操作
//LinkListTest.h
#include<stdio.h>
#include<stdlib.h>
#include"LinkList.h"
#include"Traversal.h"
#include"BuildLinkList.h"
#include"Reverse.h"
#include"DeleteEven.h"
#include"BuildIncreaseLinkList.h"
#include"MergeLinkList.h"
#include"Separate.h"
int main(){
LkList *lklist,*OddPart;
LkList *La,*Lb,*Lc;
int option;
lklist=(LkList*)malloc(sizeof(LkList));lklist->next=NULL;//初始化lklist
La=(LkList*)malloc(sizeof(LkList));La->next=NULL; //初始化La
Lb=(LkList*)malloc(sizeof(LkList));Lb->next=NULL; //初始化Lb
Lc=(LkList*)malloc(sizeof(LkList));Lc->next=NULL; //初始化Lc
loop:printf("選項:\n1.創(chuàng)建一個鏈表lklist\n2.遍歷鏈表lklist\n3.逆置鏈表lklist\n4.刪除lklist中偶數(shù)結(jié)點");
printf("\n5.建立兩個非遞減有序鏈表La,Lb\n6.合并La,Lb\n7.將合并得到的Lc分解成奇偶兩部分\n8.多項式相加\n");
printf("輸入選項:");
scanf("%d",&option);
switch(option)
{
case 1:lklist=CreatLinkList(); //創(chuàng)建一個鏈表
break;
case 2:Traversal(lklist); //遍歷鏈表
break;
case 3:Reverse(lklist); //逆置鏈表
break;
case 4:DeleteEven(lklist); //刪除偶數(shù)結(jié)點
break;
case 5:
{
printf("建立有序非遞減鏈表La:");
La=BuildIncreaseLinkList();
Traversal(La);
printf("建立有序非遞減鏈表Lb:");
Lb=BuildIncreaseLinkList();
Traversal(Lb);
break;
}
case 6:Lc=MergeLinkList(La,Lb);//遍歷合并后的非遞減鏈表,若想得到遞增鏈表,逆置即可.
Traversal(Lc);
break;
case 7:
{
OddPart=(LkList*)malloc(sizeof(LkList));OddPart->next=NULL;//初始化OddPart
Separate(OddPart,Lc);//將Lc分解為奇偶兩部分
printf("奇數(shù)部分");
Traversal(OddPart);
printf("偶數(shù)部分");
Traversal(Lc);
break;
}
case 8:{}break;
default:printf("輸入錯誤!\n");
}//switch
fflush(stdin);
getchar();
system("cls");
goto loop;
return 0;
}
五.實驗結(jié)果（以上所列程序如與源程序有所不同，則以源程序為主）
1.線性表的順序存儲:
輸入一組整數(shù)(以字符結(jié)束):
1 2 3 45 6 7 89 543 5 a
此順序表中的元素為:
1 2 3 5 6 7 45 89 543
選項:
1.插入元素.
2.刪除元素.
3.查找元素.
4.判斷順序表是否對稱.
5.重新按奇偶排列.
6.合并兩個順序表.
輸入選項:1
輸入要加入順序表的元素和位置:12,0
不合法的位置!
此順序表中的元素為:
1 2 3 5 6 7 45 89 543
輸入選項:1
輸入要加入順序表的元素和位置:234,6
插入成功!
此順序表中的元素為:
1 2 3 5 6 234 7 45 89 543
輸入選項:2
輸入要刪除結(jié)點的位置:3
刪除成功!
此順序表中的元素為:
1 2 5 6 234 7 45 89 543
輸入選項:3
請輸入要查找的元素:234
找到了這個元素
輸入選項:4
不對稱
輸入選項:5
已重新排列!
此順序表中的元素為:
1 5 7 45 89 543 6 234 2
輸入選項:6
創(chuàng)建有序表A:輸入一組整數(shù)(以字符結(jié)束):
12 3435 67 89 0 a
創(chuàng)建有序表B:輸入一組整數(shù)(以字符結(jié)束):
7 6543 7 853 a
合并完成!此順序表中的元素為:
0 7 7 12 67 89 853 3435 6543
輸入選項:9
輸入錯誤:
Press any key to continue
2.線性表的鏈式存儲:
說明:輸入數(shù)據(jù)后,再一次按ENTER鍵時會清屏,并再輸出選項.所以此處只列出需要的結(jié)果.而不重復(fù)列出選項.
選項:
1.創(chuàng)建一個鏈表lklist
2.遍歷鏈表lklist
3.逆置鏈表lklist
4.刪除lklist中偶數(shù)結(jié)點
5.建立兩個非遞減有序鏈表La,Lb
6.合并La,Lb
7.將合并得到的Lc分解成奇偶兩部分
8.多項式相加
輸入選項:1
輸入一行整數(shù)(以字符結(jié)束):
12 45 67 89 34 a
輸入選項:2
遍歷鏈表:12 45 67 89 34
輸入選項:3
成功逆置!
輸入選項:2
遍歷鏈表:34 89 67 45 12
輸入選項:4
已成功刪除偶數(shù)結(jié)點!
輸入選項:5
建立有序非遞減鏈表La:輸入一行整數(shù)(以字符結(jié)束):
12 467 8 90 a
遍歷鏈表:8 12 90 467
建立有序非遞減鏈表Lb:輸入一行整數(shù)(以字符結(jié)束):
45 89 5 3 32 a
遍歷鏈表:3 5 32 45 89
輸入選項:6
合并成功!
遍歷鏈表:3 5 8 12 32 45 89 90 467
輸入選項:7
奇數(shù)部分遍歷鏈表:3 5 45 89 467
偶數(shù)部分遍歷鏈表:8 12 32 90
六.實驗體會
總體來說,這種實驗沒什么難度,只不過按照功能要求一一實現(xiàn).雖然如此,在寫代碼的過程中,也鞏固了以前的知識.也在編程的過程中發(fā)現(xiàn)了一些問題.比如一些隱蔽的錯誤很難找出來,因為不太會用DEBUG工具,往往一找錯誤就是幾十分鐘.嚴重降低了效率.
實驗中,也有些功能要求實現(xiàn)得不是很好.就拿創(chuàng)建鏈表來說,輸入數(shù)據(jù)一定要以非數(shù)字符結(jié)束.但我又始終無法在不必輸結(jié)束符的情況下完成鏈表的創(chuàng)建.原因是對鍵盤緩沖區(qū)了解甚少.
實驗中還有一個問題：LinkList的第（9）問沒有完成。代碼寫到最后自己都看不明白在寫什么，索性全刪掉不做了，就這樣交了吧。等有空時再去將它解決。
最后，實驗報告太長，但是也沒有好的辦法。如果不貼上源程序，則又太短。
完整的Word格式文檔51黑下載地址：
數(shù)據(jù)結(jié)構(gòu)上機實驗報告.doc
(84.5 KB, 下載次數(shù): 6)
2018-6-5 20:26 上傳
點擊文件名下載附件
下載積分: 黑幣 -5
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
