數(shù)據(jù)結(jié)構(gòu)--順序表的c語(yǔ)言實(shí)現(xiàn)（超詳細(xì)注釋/實(shí)驗(yàn)報(bào)告）

知識(shí)小回顧

線性表是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)，它有兩種存儲(chǔ)結(jié)構(gòu)——順序表和鏈表。順序表是由地址連續(xù)的的向量實(shí)現(xiàn)的，便于實(shí)現(xiàn)隨機(jī)訪問(wèn)。順序表進(jìn)行插入和刪除運(yùn)算時(shí)，平均需要移動(dòng)表中大約一半的數(shù)據(jù)元素，容量難以擴(kuò)充。

也可以在csdn上查看喲~

https://blog.csdn.net/dream_of_grass/article/details/120353409?spm=1001.2014.3001.5501

實(shí)驗(yàn)題目

實(shí)現(xiàn)順序表各種基本運(yùn)算

實(shí)驗(yàn)?zāi)康?/h1>

1. 熟悉將算法轉(zhuǎn)換為程序代碼的過(guò)程；

2. 了解順序表的邏輯結(jié)構(gòu)特性，熟練掌握順序表存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述方法；

3. 熟練掌握順序表的基本運(yùn)算：查找、插入、刪除等，掌握順序表的隨機(jī)存取特性。

實(shí)驗(yàn)要求

1. 以順序表作為存儲(chǔ)結(jié)構(gòu)；

2. 實(shí)現(xiàn)順序表上的數(shù)據(jù)元素的插入運(yùn)算；

3. 實(shí)現(xiàn)順序表上的數(shù)據(jù)元素的刪除運(yùn)算；

4. 實(shí)現(xiàn)順序表上的數(shù)據(jù)元素的查找運(yùn)算。

實(shí)驗(yàn)內(nèi)容和實(shí)驗(yàn)步驟

1.需求分析

以菜單的形式作為用戶與程序的接口，用戶輸入菜單號(hào)來(lái)實(shí)行相應(yīng)的操作。

2. 概要設(shè)計(jì)

設(shè)計(jì)幾個(gè)函數(shù)來(lái)實(shí)現(xiàn)初始化、插入、刪除和查找的功能，然后再主函數(shù)中調(diào)用函數(shù)來(lái)實(shí)現(xiàn)操作。

3. 詳細(xì)設(shè)計(jì)

導(dǎo)入一些庫(kù)，并定義表的大小以及表中元素的類型。

#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定義表的大小
#define MaxSize 20
//用typedef 給int定義個(gè)名字為ElemType，意思是表中元素的type
typedef int ElemType;

線性表的順序存儲(chǔ)結(jié)構(gòu)借助于高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組來(lái)表示，一維數(shù)組的下表與元素再線性表中的序號(hào)相對(duì)應(yīng)。

//順序表結(jié)構(gòu)定義，包括了表的長(zhǎng)度和一個(gè)數(shù)組
typedef struct Seqlist
{
? ?ElemType elem[MaxSize];
? ?int length;
}SeqList;

將線性表L初始化為空表，即長(zhǎng)度length為0.

//定義順序表初始化函數(shù)
int Init_SeqList(SeqList *L)
{
? ?L->length=0; ? ? //設(shè)置長(zhǎng)度為0，空表
? ?//printf("%d",L->length);
? ?return 1;
}

返回輸入元素的位置

//定義查找某個(gè)元素位置的函數(shù)
int Locate_SeqList(SeqList *L,int x)
{
? ?int i=0;
? ?//從第0個(gè)開(kāi)始到最后結(jié)束，結(jié)束條件是①索引到了length了②在表中找到值與輸入的值相等了
? ?for(i=0;i<L->length&&L->elem[i]!=x;i++)
? ?{
? ? ? ?;;
? ?}
? /* while(i<L->length&&L->elem[i]!=x)
? ? ? ?i++;*/

? ?//結(jié)束循環(huán)，第一種情況
? ?if(i>=L->length)
? ?{
? ? ? ?printf("順序表中不存在該元素！\n");
? ? ? ?return 0;
? ?}
? ?//第二種情況，因?yàn)檫@是數(shù)組，所以返回的序數(shù)應(yīng)該加1
? ?else
? ? ? ?return i+1;
}

定義插入順序表的函數(shù)：在第i個(gè)元素之前插入。 在寫(xiě)的時(shí)候要注意：對(duì)用戶來(lái)說(shuō)第1個(gè)是數(shù)組的第0個(gè)。

//定義插入順序表的函數(shù)：在第i個(gè)元素之前插入x
//注意：對(duì)用戶來(lái)說(shuō)第1個(gè)是數(shù)組的第0個(gè)
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("順序表已滿，無(wú)法進(jìn)行插入操作！");
? ? ? ?return 0;
? ?}
? ?else if(i<=0||i>L->length+1)
? ?{
? ? ? ?printf("插入的位置不正確！");
? ? ? ?return 0;
? ?}
? ?//從最后一個(gè)元素開(kāi)始，一個(gè)一個(gè)地往后移一位，給要插入的元素留出空間
? ?for(j=L->length-1;j>=i-1;j--)
? ?{
? ? ? ?L->elem[j+1]=L->elem[j];
? ?}
? ?//在第i個(gè)元素之前插入就是把從i開(kāi)始的元素往后移，然后賦值給第i個(gè)元素，在數(shù)組中就是i-1了
? ?L->elem[i-1]=x;
? ?L->length++; //插入完之后數(shù)組長(zhǎng)度+1
? ?return 1;
}

刪除順序表元素函數(shù)，刪除第i個(gè)元素。

//定義刪除順序表元素函數(shù)，刪除第i個(gè)元素
int Delete_SeqList(SeqList *L,int i)
{
? ?int j;
? ?if((i<1)||(i>L->length))//和插入是一樣的判斷條件
? ?{
? ? ? ?printf("刪除位置不正確！");
? ? ? ?return 0;
? ?}
? ?//刪除第i個(gè)元素就是從第i個(gè)元素開(kāi)始一個(gè)一個(gè)地從后向前覆蓋
? ?for(j=i;j<L->length;j++)
? ?{
? ? ? ?L->elem[j-1]=L->elem[j];
? ?}
? ?L->length--;//數(shù)組長(zhǎng)度-1
? ?return 1;
}

顯示線性表的函數(shù)。

//定義顯示線性表的函數(shù)
int Display_SeqList(SeqList *L)
{
? ?int i;
? ?//一個(gè)一個(gè)地打印出來(lái)
? ?for(i=0;i<L->length;i++)
? ?{
? ? ? ?printf("%d",L->elem[i]);
? ? ? ?//return 1; 嚴(yán)重錯(cuò)誤，其實(shí)插入也已經(jīng)插入了，只是顯示出來(lái)1個(gè) ?(之前的一個(gè)小bug)
? ?}
? ?return 1;
}

主函數(shù)部分，用一種“菜單”的形式使線性表的操作更加地清晰地展示出來(lái)。

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)//保證一直進(jìn)行
? ?{
? ? ? ?printf("當(dāng)前的順序表如下： ");
? ? ? ?Display_SeqList(&L);
? ? ? ?printf("\n------------------------------------\n");
? ? ? ?printf(" ? ? ? ? Main Menu ? ? ? ? \n");
? ? ? ?printf(" ? ?1 ? 查找指定元素 ? ?\n");
? ? ? ?printf(" ? ?2 ? 插入元素到指定位置 ? \n");
? ? ? ?printf(" ? ?3 ? 刪除某一指定位置元素 ? \n");
? ? ? ?printf(" ? ?4 ? 清屏 ? \n");
? ? ? ?printf(" ? ?0 ? 結(jié)束程序 ? ? ?\n");
? ? ? ?printf("------------------------------------\n");
? ? ? ?printf("請(qǐng)輸入你選擇的菜單號(hào)<1, 2, 3, 0>:\n");
? ? ? ?scanf("%d",&i);
? ? ? ?switch(i)
? ? ? ?{
? ? ? ?case 1:
? ? ? ? ? ? ? ?printf("請(qǐng)輸入查找元素：");
? ? ? ? ? ? ? ?scanf("%d",&x);
? ? ? ? ? ? ? ?j=Locate_SeqList(&L,x);
? ? ? ? ? ? ? ?if(j!=0)//找到元素返回的是i+1,可以看看前面函數(shù)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?printf("指定元素位置是 %d",j);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?printf("\n\n");
? ? ? ? ? ?break;
? ? ? ?case 2:
? ? ? ? ? ?printf("請(qǐng)輸入插入元素位置：");
? ? ? ? ? ?scanf("%d",&k);
? ? ? ? ? ?printf("請(qǐng)輸入插入元素值：");
? ? ? ? ? ?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("請(qǐng)輸入刪除元素位置：");
? ? ? ? ? ?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. 調(diào)試分析

遇到的問(wèn)題及解決方法

• 實(shí)驗(yàn)指導(dǎo)書(shū)上給出的代碼在code blocks環(huán)境下會(huì)報(bào)錯(cuò)，有的語(yǔ)句書(shū)寫(xiě)規(guī)范不一樣。不過(guò)改正后就好了。

算法的時(shí)空分析

• 順序表比較簡(jiǎn)單，都是依托著數(shù)組來(lái)實(shí)現(xiàn)的，值得改進(jìn)的地方就是插入函數(shù)，用戶自己來(lái)輸入順序表的元素會(huì)更好一些。

實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果很不錯(cuò)，所有操作都能正常執(zhí)行，并且自己加入了“清屏”選項(xiàng)，使得界面更加的整潔。

實(shí)驗(yàn)總結(jié)

這是第一個(gè)數(shù)據(jù)結(jié)構(gòu)的代碼實(shí)現(xiàn)，主要還是跟著實(shí)驗(yàn)指導(dǎo)書(shū)上寫(xiě)，原創(chuàng)性不足，不過(guò)也學(xué)到了很多知識(shí)，也為之后的程序編寫(xiě)搭建了一個(gè)不錯(cuò)的框架！多多重復(fù)，百煉成鋼！

最后附上完整的代碼

#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
//定義表的大小
#define MaxSize 20
//用typedef 給int定義個(gè)名字為ElemType，意思是表中元素的type
typedef int ElemType;
//順序表結(jié)構(gòu)定義，包括了表的長(zhǎng)度和一個(gè)數(shù)組
typedef struct Seqlist
{
? ?ElemType elem[MaxSize];
? ?int length;
}SeqList;

//定義順序表初始化函數(shù)
int Init_SeqList(SeqList *L)
{
? ?L->length=0; ? ? //設(shè)置長(zhǎng)度為0，空表
? ?//printf("%d",L->length);
? ?return 1;
}

//定義查找某個(gè)元素位置的函數(shù)
int Locate_SeqList(SeqList *L,int x)
{
? ?int i=0;
? ?//從第0個(gè)開(kāi)始到最后結(jié)束，結(jié)束條件是①索引到了length了②在表中找到值與輸入的值相等了
? ?for(i=0;i<L->length&&L->elem[i]!=x;i++)
? ?{
? ? ? ?;;
? ?}
? /* while(i<L->length&&L->elem[i]!=x)
? ? ? ?i++;*/

? ?//結(jié)束循環(huán)，第一種情況
? ?if(i>=L->length)
? ?{
? ? ? ?printf("順序表中不存在該元素！\n");
? ? ? ?return 0;
? ?}
? ?//第二種情況，因?yàn)檫@是數(shù)組，所以返回的序數(shù)應(yīng)該加1
? ?else
? ? ? ?return i+1;
}

//定義插入順序表的函數(shù)：在第i個(gè)元素之前插入x
//注意：對(duì)用戶來(lái)說(shuō)第1個(gè)是數(shù)組的第0個(gè)
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("順序表已滿，無(wú)法進(jìn)行插入操作！");
? ? ? ?return 0;
? ?}
? ?else if(i<=0||i>L->length+1)
? ?{
? ? ? ?printf("插入的位置不正確！");
? ? ? ?return 0;
? ?}
? ?//從最后一個(gè)元素開(kāi)始，一個(gè)一個(gè)地往后移一位，給要插入的元素留出空間
? ?for(j=L->length-1;j>=i-1;j--)
? ?{
? ? ? ?L->elem[j+1]=L->elem[j];
? ?}
? ?//在第i個(gè)元素之前插入就是把從i開(kāi)始的元素往后移，然后賦值給第i個(gè)元素，在數(shù)組中就是i-1了
? ?L->elem[i-1]=x;
? ?L->length++; //插入完之后數(shù)組長(zhǎng)度+1
? ?return 1;
}

//定義刪除順序表元素函數(shù)，刪除第i個(gè)元素
int Delete_SeqList(SeqList *L,int i)
{
? ?int j;
? ?if((i<1)||(i>L->length))//和插入是一樣的判斷條件
? ?{
? ? ? ?printf("刪除位置不正確！");
? ? ? ?return 0;
? ?}
? ?//刪除第i個(gè)元素就是從第i個(gè)元素開(kāi)始一個(gè)一個(gè)地從后向前覆蓋
? ?for(j=i;j<L->length;j++)
? ?{
? ? ? ?L->elem[j-1]=L->elem[j];
? ?}
? ?L->length--;//數(shù)組長(zhǎng)度-1
? ?return 1;
}

//定義顯示線性表的函數(shù)
int Display_SeqList(SeqList *L)
{
? ?int i;
? ?//一個(gè)一個(gè)地打印出來(lái)
? ?for(i=0;i<L->length;i++)
? ?{
? ? ? ?printf("%d",L->elem[i]);
? ? ? ?//return 1; 嚴(yán)重錯(cuò)誤，其實(shí)插入也已經(jīng)插入了，只是顯示出來(lái)1個(gè) ?(之前的一個(gè)小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)//保證一直進(jìn)行
? ?{
? ? ? ?printf("當(dāng)前的順序表如下： ");
? ? ? ?Display_SeqList(&L);
? ? ? ?printf("\n------------------------------------\n");
? ? ? ?printf(" ? ? ? ? Main Menu ? ? ? ? \n");
? ? ? ?printf(" ? ?1 ? 查找指定元素 ? ?\n");
? ? ? ?printf(" ? ?2 ? 插入元素到指定位置 ? \n");
? ? ? ?printf(" ? ?3 ? 刪除某一指定位置元素 ? \n");
? ? ? ?printf(" ? ?4 ? 清屏 ? \n");
? ? ? ?printf(" ? ?0 ? 結(jié)束程序 ? ? ?\n");
? ? ? ?printf("------------------------------------\n");
? ? ? ?printf("請(qǐng)輸入你選擇的菜單號(hào)<1, 2, 3, 0>:\n");
? ? ? ?scanf("%d",&i);
? ? ? ?switch(i)
? ? ? ?{
? ? ? ?case 1:
? ? ? ? ? ? ? ?printf("請(qǐng)輸入查找元素：");
? ? ? ? ? ? ? ?scanf("%d",&x);
? ? ? ? ? ? ? ?j=Locate_SeqList(&L,x);
? ? ? ? ? ? ? ?if(j!=0)//找到元素返回的是i+1,可以看看前面函數(shù)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?printf("指定元素位置是 %d",j);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?printf("\n\n");
? ? ? ? ? ?break;
? ? ? ?case 2:
? ? ? ? ? ?printf("請(qǐng)輸入插入元素位置：");
? ? ? ? ? ?scanf("%d",&k);
? ? ? ? ? ?printf("請(qǐng)輸入插入元素值：");
? ? ? ? ? ?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("請(qǐng)輸入刪除元素位置：");
? ? ? ? ? ?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;
}