資料結構嚴蔚敏C語言版—線性表順序儲存結構（順序表）C語言實現相關程式碼
2020-09-23 16:00:54
資料結構嚴蔚敏C語言版—線性表順序儲存結構（順序表）C語言實現相關程式碼
1.執行環境
這裡說明一下這裡所有的C語言程式碼都是基於code::blocks 20.03編譯執行的。當然一些其他整合式開發環境應該也是可以的，個人不太喜歡功能太過強大的IDE，因為那同樣意味著相關設定，使用的複雜性也大大提高，夠用就行。
另外提一個可能比較常見的問題，報錯如下：
這裡之所以會這樣是因為沒有把各個C檔案和標頭檔案連結到一起，解決方法後面會說到。
2.準備工作
1）專案構建
1>新建一個SeqList專案
點選File–>New–>Project…–>Console application–>Go,如下圖，其餘預設，專案名稱SeqList（順序表）。
2>新建兩個檔案Sources和Headers
新建兩個檔案Sources和Headers
分別用來存放原始檔和標頭檔案，有利於程式碼的封裝與重用，養成良好的習慣。
3>新建兩個C/C++ source和一個C/C++ header
如下圖
原始檔下新建main.c和SeqList.c兩個C檔案，標頭檔案下新建了SeqList.h標頭檔案，關於命名，考慮大家應該是有一定C語言基礎的，這裡不在贅述。
最後專案構建完成，如下圖所示
2)開頭問題解決
這裡出現開頭的問題是因為三個檔案沒有連結到一起，
1.選中專案SeqList右鍵–>properties…開啟如下圖
2.選擇Build targets,如下圖選擇三個檔案
點選OK就好。言歸正傳，先上程式碼。
3.實現原始碼
1）main.c
#include"SeqList.h"
void main()
{
SeqList mylist;
InitSeqList(&mylist);
ElemType Item; ///ElemType型別資料，用來傳遞引數
int pos; ///位置下標
int select ; //選擇引數0~14
while(select)
{
printf("*************************************\n");
/// [1]尾部插入 [2]頭部插入
printf("* [1] push_back [2] push_font *\n");
/// [3] 顯示線性表 [4] 尾部刪除
printf("* [3] show_list [4] pop_back *\n");
/// [4]頭部刪除 [6] 按位元置插入
printf("* [5] pop_front [6] insert_pos *\n");
/// [7] 查詢 [8] 返回順序表的長度
printf("* [7] find [8] length *\n");
/// [9] 按位元置刪除 [10] 按值刪除
printf("* [9] delete_pos [10] delete_val *\n");
/// [11] 排序 [12] 逆置
printf("* [11] sort [12] resver *\n");
/// [13] 清除 [14] 銷燬
printf("* [13] clear [14] destry *\n");
printf("* [0] quit_system *\n"); ///按0退出
printf("*************************************4\n");
printf("請選擇:>");
scanf("%d", &select);
if(select == 0)
break;
switch(select)
{
case 1:
printf("請輸入要從尾部插入的資料:>(-1結束)");
while(scanf("%d",&Item), Item!=-1)
{
push_back(&mylist,Item);
}
printf("\n");
break;
case 2:
printf("請輸入要從頭部插入的資料:>(-1結束)");
while(scanf("%d",&Item), Item!=-1)
{
push_front(&mylist,Item);
}
printf("\n");
break;
case 3:
show_list(&mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
printf("請輸入要插入的資料(按位元置插入):>");
scanf("%d",&Item);
printf("請輸入要插入的下標位置(從0開始):>");
scanf("%d",&pos);
insert_pos(&mylist,Item,pos);
break;
case 7:
printf("請輸入要查詢的資料:>");
scanf("%d",&Item);
pos = find(&mylist,Item);
if(pos == -1)
printf("要查詢的資料 %d 在順序表裡不存在.\n\n",Item);
else
printf("要查詢的資料 %d 在順序表中下標位置為 %d.\n\n",Item,pos);
break;
case 8:
printf("順序表的長度為 %d\n\n",length(&mylist));
break;
case 9:
printf("請輸入要刪除資料的下標位置:>");
scanf("%d",&pos);
delete_pos(&mylist,pos);
printf("順序表中下標位置為 %d 的資料已刪除.\n\n",pos);
break;
case 10:
printf("請輸入要刪除的資料:>");
scanf("%d",&Item);
delete_val(&mylist,Item);
break;
case 11:
sort(&mylist);
show_list(&mylist);
break;
case 12:
resver(&mylist);
show_list(&mylist);
break;
case 13:
clear(&mylist);
break;
case 14:
destroy(&mylist);
break;
default:
printf("輸入的選擇錯誤，請重新輸入.\n");
break;
}
}
}
#include"SeqList.h"
一般情況下參照系統標頭檔案使用<>，而使用自己定義的標頭檔案使用「」。而#include"SeqList.h"是我們自己定義的檔案，不要忘記參照。
一共實現了十五種需求，即十五個函數模組，列印出十四種功能需求，還有一種是空間增加函數功能模組。程式有main函數開始，我的程式設計基於資料結構嚴蔚敏C語言版的教材，並以此為依託儘量實現書上的各種函數。為了更好的實現與使用者的互動，我在main函數出大量使用的printf函數，以便使用者可以指定程式的執行，即程式做了什麼。
2）SeqList.h
#ifndef HEADER_FILES_H_INCLUDED
#define HEADER_FILES_H_INCLUDED
#include<stdio.h>
///初始化順序表用到的兩個函數所在的標頭檔案的引入
#include<malloc.h>
#include<assert.h>
///布林型別的標頭檔案引入
#include<stdbool.h>
#define SEQLIST_INIT_SIZE 8 ///順序表初始開闢8個空間
#define INC_SIZE 3 ///順序表增加3空間
typedef int ElemType; ///EleType為int型別，方便其他型別的改動
///結構體型別
typedef struct SeqList
{
ElemType *base;
int capacity;
int size;
}SeqList;
///空間增加函數
bool Inc(SeqList *list);
///初始化
void InitSeqList(SeqList *list);
///1.尾部插入
void push_back(SeqList *list, ElemType x);
///2.頭部插入
void push_front(SeqList *list, ElemType x);
///3.顯示線性表
void show_list(SeqList *list);
///4.尾部刪除
void pop_front(SeqList *list);
///5.頭部刪除
void pop_back(SeqList *list);
///6.按位元置插入
void insert_pos(SeqList *list, ElemType x, int pos);
///7.查詢
int find(SeqList *list,ElemType key);
///8.順序表的長度
int length(SeqList *list);
///9.按位元置刪除
void delete_pos(SeqList *list,int pos);
///10.按值刪除
void delete_val(SeqList *list,ElemType x);
///11.排序
void sort(SeqList *list);
///12.逆置
void resver(SeqList *list);
///13.清除
void clear(SeqList *list);
///14.摧毀
void destroy(SeqList *list);
SeqList.h中進行了呼叫系統標頭檔案、定義結構體型別、宣告函數。
值得一提的是，這裡並不支援布林型別的使用。
我這裡給出兩種解決方法
第一種像我的程式碼裡一樣引入
#include<stdbool.h>
標頭檔案，因為在最新C語言標準(C99)種解決了布林型別，即提供了這樣的一共標頭檔案
第二種自己定義，程式碼如下
#dfine BOOL in
或者直接定義true和flase
#define FLASE 0
#define TRUE 1
其餘註釋已經解釋清楚，這裡不再贅述。
3） SeqList.c
#include"SeqList.h"
///初始化順序表
void InitSeqList(SeqList *list)
{
list->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
assert(list->base != NULL);
list->capacity = SEQLIST_INIT_SIZE;
list->size = 0;
}
//1.尾部插入
void push_back(SeqList *list, ElemType x)
{
if(list->size >= list->capacity && !Inc(list))
{
printf("順序表空間已滿，%d 不能在尾部插入資料\n\n", x);
return;
}
list->base[list->size] = x;
list->size++;
}
//2.頭部插入
void push_front(SeqList *list, ElemType x)
{
if(list->size >= list->capacity && !Inc(list))
{
printf("順序表空間已滿，不能在頭部插入資料\n\n");
return;
}
int i;
for(i=list->size;i>0;--i)
{
list->base[i] = list->base[i-1];
}
list->base[0] = x;
list->size++;
}
//3.顯示線性表
void show_list(SeqList *list)
{
if(list->size == 0)
{
printf("順序表無資料.\n\n");
}
else
{
printf("順序表中的資料顯示如下:>\n");
int i;
for(i=0; i<list->size; ++i)
{
printf("%d ", list->base[i]);
}
printf("\n");
printf("\n");
}
}
//4.尾部刪除
void pop_back(SeqList *list)
{
if(list->size == 0)
{
printf("順序表已空，無法刪除尾部資料\n\n");
return;
}
list->size--;
printf("已刪除順序表尾部一個資料.\n\n");
}
//5.頭部刪除
void pop_front(SeqList *list)
{
if(list->size == 0)
{
printf("順序表已空，無法刪除頭部資料\n\n");
return;
}
int i;
for(i=0; i<list->size-1; i++)
{
list->base[i] = list->base[i+1];
}
list->size--;
printf("已刪除順序表頭部一個資料.\n\n");
}
//6.按位元置插入
void insert_pos(SeqList *list,ElemType x,int pos)
{
///判空
if(list->size >= list->capacity && !Inc(list))
{
printf("順序表空間已滿，不能在該位置插入資料\n\n");
return;
}
///檢視位置是否合理，即是否符合順序表特點
if(pos<0 || pos>list->size)
{
printf("插入資料的位置不合理，不能插入！！！\n\n");
return;
}
if(pos == 0) ///相當於頭插
{
push_front(list, x);
}
else if(pos == list->size) ///相當於尾插
{
push_back(list, x);
}
else
{
int i;
///元素依次後移，空出pos位置
for(i=list->size; i>pos; i++)
{
list->base[i] = list->base[i-1];
}
list->base[pos] = x; ///插入元素
list->size++; ///長度加一
}
printf("\n");
}
//7.查詢
int find(SeqList *list,ElemType key)
{
int i;
for(i=0; i<list->size; i++)
{
if(list->base[i] == key)
return i;
}
return -1;
}
//8.順序表的長度
int length(SeqList *list)
{
return list->size;
}
//9.按位元置刪除
void delete_pos(SeqList *list,int pos)
{
if(list->size == 0)
{
printf("順序表已空，不能刪除該位置資料.\n\n");
return;
}
if(pos<0 || pos>list->size-1)
{
printf("要刪除資料的下標位置不合理，不能刪除！！！\n\n");
return;
}
int i;
for(i=pos; i<list->size-1; i++)
{
list->base[i] = list->base[i+1];
}
list->size--;
}
//10.按值刪除
void delete_val(SeqList *list ,ElemType x)
{
if(list->size == 0)
{
printf("順序表已空，不存在該資料.\n\n");
return;
}
int pos = find(list,x);
if(pos == -1)
{
printf("要刪除的資料在順序表中不存在.\n\n");
return;
}
delete_pos(list,pos);
printf("順序表中 %d 資料已刪除.\n\n",x);
}
///11.排序
void sort(SeqList *list)
{
if(list->size == 0)
{
printf("順序表已空，無法排序.\n");
}
else
{
printf("順序表中資料已從小到大排序:>\n\n");
///氣泡排序(從小到大)
int i,j;
for(i=0; i<list->size-1; i++)
{
for(j=0; j<list->size-1-i; j++)
{
if(list->base[j] > list->base[j+1])
{
ElemType temp = list->base[j];
list->base[j] = list->base[j+1];
list->base[j+1] = temp;
}
}
}
}
//12逆置
void resver(SeqList *list)
{
if(list->size == 0)
{
printf("順序表為空，無法逆置.\n\n");
return;
}
else if(list ->size == 1)
{
printf("順序表已逆置.\n\n");
return ;
}
int low = 0, high = list->size-1;
ElemType temp;
while(low < high)
{
temp = list->base[low];
list->base[low] = list->base[high];
list->base[high] = temp;
low++;
high--;
}
printf("順序表已逆置.\n\n");
}
//13.清除
void clear(SeqList *list)
{
list->size = 0;
printf("順序表中資料已清除\n\n");
}
//14.摧毀
void destroy(SeqList *list)
{
free(list->base);
list->base = NULL;
list->capacity = 0;
list->size = 0;
printf("順序表已摧毀\n\n");
}
4） 執行效果展示
4.寫在最後
至此函數全部實現，測試無誤，下面準備寫一個兩個順序表合併為一個順序表，也是資料結構中的經典函數。我準備基於資料結構嚴蔚敏C語言版這本書寫下去。本人不過是在讀本科小白一枚，程式碼多有不足，歡迎大家留言交流心得體會，或者程式碼改進。