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