資料結構–順序表的c語言實作（超詳細注釋/實驗報告）
知識小回顧
線性表是一種最基本、最常用的資料結構，它有兩種存盤結構——順序表和鏈表，順序表是由地址連續的的向量實作的，便于實作隨機訪問，順序表進行插入和洗掉運算時，平均需要移動表中大約一半的資料元素，容量難以擴充，
實驗題目
實作順序表各種基本運算
實驗目的
- 熟悉將演算法轉換為程式代碼的程序；
- 了解順序表的邏輯結構特性，熟練掌握順序表存盤結構的C語言描述方法；
- 熟練掌握順序表的基本運算：查找、插入、洗掉等，掌握順序表的隨機存取特性，
實驗要求
- 以順序表作為存盤結構；
- 實作順序表上的資料元素的插入運算；
- 實作順序表上的資料元素的洗掉運算；
- 實作順序表上的資料元素的查找運算，
實驗內容和實驗步驟
1.需求分析
以選單的形式作為用戶與程式的介面，用戶輸入選單號來實行相應的操作，
2. 概要設計
設計幾個函式來實作初始化、插入、洗掉和查找的功能，然后再主函式中呼叫函式來實作操作，
3. 詳細設計
匯入一些庫，并定義表的大小以及表中元素的型別，
#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定義表的大小
#define MaxSize 20
//用typedef 給int定義個名字為ElemType，意思是表中元素的type
typedef int ElemType;
線性表的順序存盤結構借助于高級程式設計語言中的一維陣列來表示，一維陣列的下表與元素再線性表中的序號相對應，
//順序表結構定義，包括了表的長度和一個陣列
typedef struct Seqlist
{
ElemType elem[MaxSize];
int length;
}SeqList;
將線性表L初始化為空表，即長度length為0.
//定義順序表初始化函式
int Init_SeqList(SeqList *L)
{
L->length=0; //設定長度為0，空表
//printf("%d",L->length);
return 1;
}
回傳輸入元素的位置
//定義查找某個元素位置的函式
int Locate_SeqList(SeqList *L,int x)
{
int i=0;
//從第0個開始到最后結束，結束條件是①索引到了length了②在表中找到值與輸入的值相等了
for(i=0;i<L->length&&L->elem[i]!=x;i++)
{
;;
}
/* while(i<L->length&&L->elem[i]!=x)
i++;*/
//結束回圈，第一種情況
if(i>=L->length)
{
printf("順序表中不存在該元素！\n");
return 0;
}
//第二種情況，因為這是陣列，所以回傳的序數應該加1
else
return i+1;
}
定義插入順序表的函式：在第i個元素之前插入，
在寫的時候要注意：對用戶來說第1個是陣列的第0個，
//定義插入順序表的函式：在第i個元素之前插入x
//注意：對用戶來說第1個是陣列的第0個
int Insert_SeqList(SeqList *L,int i,int x)
{
int j;
//printf("MaxSize\n");
//printf("%d",MaxSize);
//printf("%d",L.length);
if(L->length>=MaxSize)
{
printf("順序表已滿，無法進行插入操作！");
return 0;
}
else if(i<=0||i>L->length+1)
{
printf("插入的位置不正確！");
return 0;
}
//從最后一個元素開始，一個一個地往后移一位，給要插入的元素留出空間
for(j=L->length-1;j>=i-1;j--)
{
L->elem[j+1]=L->elem[j];
}
//在第i個元素之前插入就是把從i開始的元素往后移，然后賦值給第i個元素，在陣列中就是i-1了
L->elem[i-1]=x;
L->length++; //插入完之后陣列長度+1
return 1;
}
洗掉順序表元素函式，洗掉第i個元素，
//定義洗掉順序表元素函式，洗掉第i個元素
int Delete_SeqList(SeqList *L,int i)
{
int j;
if((i<1)||(i>L->length))//和插入是一樣的判斷條件
{
printf("洗掉位置不正確！");
return 0;
}
//洗掉第i個元素就是從第i個元素開始一個一個地從后向前覆寫
for(j=i;j<L->length;j++)
{
L->elem[j-1]=L->elem[j];
}
L->length--;//陣列長度-1
return 1;
}
顯示線性表的函式，
//定義顯示線性表的函式
int Display_SeqList(SeqList *L)
{
int i;
//一個一個地列印出來
for(i=0;i<L->length;i++)
{
printf("%d",L->elem[i]);
//return 1; 嚴重錯誤，其實插入也已經插入了，只是顯示出來1個 (之前的一個小bug)
}
return 1;
}
主函式部分，用一種“選單”的形式使線性表的操作更加地清晰地展示出來，
int main()
{
SeqList L;
ElemType e,x;
int i=1,k,j,n,ii;
Init_SeqList(&L);
//printf("%d",Init_SeqList(&L));
//printf("初始化\n建立順序表如下：");
//printf("%d",L.length);
//插入元素5201314
Insert_SeqList(&L,1,5);
Insert_SeqList(&L,2,2);
Insert_SeqList(&L,3,0);
Insert_SeqList(&L,4,1);
Insert_SeqList(&L,5,3);
Insert_SeqList(&L,6,1);
Insert_SeqList(&L,7,4);
//printf("\n");
while(i)//保證一直進行
{
printf("當前的順序表如下： ");
Display_SeqList(&L);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 洗掉某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 結束程式 \n");
printf("------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入查找元素：");
scanf("%d",&x);
j=Locate_SeqList(&L,x);
if(j!=0)//找到元素回傳的是i+1,可以看看前面函式
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("請輸入插入元素位置：");
scanf("%d",&k);
printf("請輸入插入元素值：");
scanf("%d",&x);
j=Insert_SeqList(&L,k,x);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("請輸入洗掉元素位置：");
scanf("%d",&k);
j=Delete_SeqList(&L,k);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
return 0;
}
}
4. 除錯分析
遇到的問題及解決方法
- 實驗指導書上給出的代碼在code blocks環境下會報錯，有的陳述句書寫規范不一樣，不過改正后就好了，
演算法的時空分析
- 順序表比較簡單，都是依托著陣列來實作的，值得改進的地方就是插入函式，用戶自己來輸入順序表的元素會更好一些，
實驗結果
實驗結果很不錯，所有操作都能正常執行，并且自己加入了“清屏”選項，使得界面更加的整潔，
實驗總結
這是第一個資料結構的代碼實作，主要還是跟著實驗指導書上寫，原創性不足，不過也學到了很多知識，也為之后的程式撰寫搭建了一個不錯的框架！多多重復，百煉成鋼！
最后附上完整的代碼
#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定義表的大小
#define MaxSize 20
//用typedef 給int定義個名字為ElemType，意思是表中元素的type
typedef int ElemType;
//順序表結構定義，包括了表的長度和一個陣列
typedef struct Seqlist
{
ElemType elem[MaxSize];
int length;
}SeqList;
//定義順序表初始化函式
int Init_SeqList(SeqList *L)
{
L->length=0; //設定長度為0，空表
//printf("%d",L->length);
return 1;
}
//定義查找某個元素位置的函式
int Locate_SeqList(SeqList *L,int x)
{
int i=0;
//從第0個開始到最后結束，結束條件是①索引到了length了②在表中找到值與輸入的值相等了
for(i=0;i<L->length&&L->elem[i]!=x;i++)
{
;;
}
/* while(i<L->length&&L->elem[i]!=x)
i++;*/
//結束回圈，第一種情況
if(i>=L->length)
{
printf("順序表中不存在該元素！\n");
return 0;
}
//第二種情況，因為這是陣列，所以回傳的序數應該加1
else
return i+1;
}
//定義插入順序表的函式：在第i個元素之前插入x
//注意：對用戶來說第1個是陣列的第0個
int Insert_SeqList(SeqList *L,int i,int x)
{
int j;
//printf("MaxSize\n");
//printf("%d",MaxSize);
//printf("%d",L.length);
if(L->length>=MaxSize)
{
printf("順序表已滿，無法進行插入操作！");
return 0;
}
else if(i<=0||i>L->length+1)
{
printf("插入的位置不正確！");
return 0;
}
//從最后一個元素開始，一個一個地往后移一位，給要插入的元素留出空間
for(j=L->length-1;j>=i-1;j--)
{
L->elem[j+1]=L->elem[j];
}
//在第i個元素之前插入就是把從i開始的元素往后移，然后賦值給第i個元素，在陣列中就是i-1了
L->elem[i-1]=x;
L->length++; //插入完之后陣列長度+1
return 1;
}
//定義洗掉順序表元素函式，洗掉第i個元素
int Delete_SeqList(SeqList *L,int i)
{
int j;
if((i<1)||(i>L->length))//和插入是一樣的判斷條件
{
printf("洗掉位置不正確！");
return 0;
}
//洗掉第i個元素就是從第i個元素開始一個一個地從后向前覆寫
for(j=i;j<L->length;j++)
{
L->elem[j-1]=L->elem[j];
}
L->length--;//陣列長度-1
return 1;
}
//定義顯示線性表的函式
int Display_SeqList(SeqList *L)
{
int i;
//一個一個地列印出來
for(i=0;i<L->length;i++)
{
printf("%d",L->elem[i]);
//return 1; 嚴重錯誤，其實插入也已經插入了，只是顯示出來1個 (之前的一個小bug)
}
return 1;
}
int main()
{
SeqList L;
ElemType e,x;
int i=1,k,j,n,ii;
Init_SeqList(&L);
//printf("%d",Init_SeqList(&L));
//printf("初始化\n建立順序表如下：");
//printf("%d",L.length);
//插入元素5201314
Insert_SeqList(&L,1,5);
Insert_SeqList(&L,2,2);
Insert_SeqList(&L,3,0);
Insert_SeqList(&L,4,1);
Insert_SeqList(&L,5,3);
Insert_SeqList(&L,6,1);
Insert_SeqList(&L,7,4);
//printf("\n");
while(i)//保證一直進行
{
printf("當前的順序表如下： ");
Display_SeqList(&L);
printf("\n------------------------------------\n");
printf(" Main Menu \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 洗掉某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 結束程式 \n");
printf("------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入查找元素：");
scanf("%d",&x);
j=Locate_SeqList(&L,x);
if(j!=0)//找到元素回傳的是i+1,可以看看前面函式
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("請輸入插入元素位置：");
scanf("%d",&k);
printf("請輸入插入元素值：");
scanf("%d",&x);
j=Insert_SeqList(&L,k,x);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("請輸入洗掉元素位置：");
scanf("%d",&k);
j=Delete_SeqList(&L,k);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_SeqList(&L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/303041.html
標籤：其他
上一篇：ABAP開發知識點整理