標籤：

線性表實例講解

10-15
線性表實例講解

來自專欄 Code的集散地

數據結構 - 線性表

線性表就是一個隊列

類似於node.js的隊列，但是感覺很像，也不清楚是不是

直接上題，?(?*)

使用線性表來儲存一組學生信息，並支持常規的增刪查改

需要以下的幾個子函數

  1. 建立順序表
  2. 求線性表的長度
  3. 輸出線性表
  4. 在線性表的指定位置插入一個元素
  5. 根據鍵值查找指定的元素
  6. 獲取指定位置的元素信息
  7. 刪除指定位置的元素
  8. 釋放線性表
  9. 需要儲存學生的信息有
  10. 學號
  11. 姓名
  12. 年齡
  13. 專業
  14. 入學年份

定義基本的數據類型

需要知道學生的學號，姓名，年齡，專業，入學年份，所以需要定義基本的數據類型

typedef struct { char num[20]; char name[20]; int age; char major; int registerYear;}ElemType;

定義物理儲存

定義線性表的物理儲存方式

typedef struct { ElemType data[MAXCOUNT]; // 定義數據 int len; // 定義長度};

以上完成了線性表的物理儲存方式

定義主函數實現功能

暫時不考慮輸入和輸出

int main() { int option; printf("學生管理系統進入成功"); printf("************選項*******************"); printf("1 建立線性表"); printf("2 求線性表的長度"); printf("3 輸出詳細表"); printf("4 在線性表的位置插入一個元素"); printf("5 根據鍵值對查找指定的元素"); printf("6 獲取指定位置的元素的信息"); printf("7 刪除指定位置的元素"); printf("8 釋放線性表"); printf("9 退出系統"); printf("**************end!*********************"); while(1) { printf("請輸入選項"); scanf("%d", &option); switch(option) { case 1: createList(); break; case 2: listLength(); break; case 3: printfList(); break; case 4: insterList(); break; case 5: selectList(); break; case 6: infoList(); break; case 7: deleteList(); break; case 8: freeList(); break; case 9: return 0; default: printf("您輸入的有錯誤，請重新輸入"); break; } } return 0;}

下面實現分開的函數

建立線性表

思路：申請內存空間

/* * 建立線性表*/// in 傳入空指針 out 線性表的首地址int createList(SeqList *myLIst) { myList = (SeqList *)malloc(sizeof(SeqList)); // 申請一塊儲存空間 if (myLIst == NULL) { return -1; // 創建儲存空間失敗 } else { return 1; // 創建儲存空間成功 }}

求線性表長度

// in 線性表 out 長度int listLength(const SeqList *myList) { // 未創建線性表 if (myList == NULL) return -1; // 創建線性表 return myList -> len;};

輸出線性表

/* * 輸出線性表*/// in 線性表 out 線性表的內容int printfList(const SeqList *myList) { int i, len; // 判斷是否為空指針 if (myList == NULL) return -1; // 獲取線性表長度 len = myList -> len; if (len == 0) { printf ("您輸入的線性表為空"); } // 輸出線性表 for (i = 0; i < len; i++) { printf("輸出第%d組數組", i + 1); printf("學號 = %s", myList->data[i].num); printf("年齡 = %d", myList ->data[i].age); printf("專業 = %s", myList ->data[i].major); printf("姓名 = %s", myList ->data[i].name); printf("入學年份 = %d", myList ->data[i].registerYear); } printf("線性表輸出成功"); return 1;}

在線性表的指定位置插入

設計子函數中的主函數

/* * 在線性表的指定位置插入*/// in 線性表 out 結果int insterList(SeqList *myList) { int tmp, col; ElemType *tmpList = NULL; // 判斷傳入地址是否為空 if (myList == NULL) { return -1; } /* * 進行插入 */ // 獲取用戶輸入 tmp = inputList(&tmpList, &col); // 判斷是否獲取成功 if (tmp == -1) return -1; // 進行插入操作 // 調用函數，往後逐步移動 tmp = moveList(myList, col, 1); // 1代表向後移動 0 向前移動 // 判斷獲取結果 if (tmp == -1) { return -1; } // 將值插入 myList->data[col-1] = *tmpList; // 維護長度 (myList ->len)++; // 釋放儲存空間 free(tmpList); // 設置空指針 tmpList = NULL; return 1;}

接著繼續設計插入信息的子函數

// 獲取用戶輸入要插入線性表的信息// in 插入的信息 插入的位置 out 結果int inputList(ElemType **tmpList, int *col) { // 申請儲存的內存空間 *tmpList = (ElemType *)malloc(sizeof(ElemType)); if (*tmpList == NULL){ printf("空間不足，無法申請"); return -1; } // 獲取用戶的要插入的內容 fflush(stdin); printf("請輸入學號"); gets(((*tmpList) ->num)); fflush(stdin); printf("請輸入姓名"); gets((*tmpList) ->name); fflush(stdin); printf("請輸入年齡"); scanf("%d",&((*tmpList) ->age)); fflush(stdin); printf("請輸入主修專業"); gets((*tmpList)->major); fflush(stdin); printf("請輸入入學年份"); scanf("%d", &((*tmpList)->registerYear)); fflush(stdin); printf("請輸入要插入的位置"); scanf("%d", col); fflush(stdin); return 1; // 獲取用戶輸入的信息完成}

接著設計移動元素的子函數，分為前移動和後移動

// 移動線性表函數// 其中option中1往後移動，0往前移動 col 為要插入的位置，從1開始int moveList(SeqList *myList, int col, int option) { int i; // 判斷傳入的線性表是否為空 if (myList == NULL) { printf ("線性表為空"); return -1; } // 判斷線性表是否已滿 if (listLength(myList) >= MAXCOUNT) { printf("線性表已滿，無法插入，請刪除後插入"); return -1; } // 判斷col是否越界，導致線性表不連貫 if ((col > listLength(myList) && col - listLength(myList) != 1 ) || col < 1) { printf("輸入的插入位置錯誤，請確認後重新插入"); return -1; } // 判斷前移還是後移 switch(option) { case 1: // 線性表往後移動 // 移動線性表 col--; for(i = listLength(myList); i >= col; i--) { myList ->data[i] = myList ->data[i-1]; }; break; case 0: // 線性表往前移動 for(i = col; i < listLength(myList); i++) { myList ->data[i - 1] = myList ->data[i]; } break; default: printf("輸入的選型錯誤"); return -1; } return 1;}

根據鍵值查找線性表

// 根據鍵值查找線性表int selectList(SeqList *myList) { if (myList == NULL) { return -1; } char key[20]; int i; // 獲取鍵值 printf("請輸入鍵值,即學號"); gets(key); // 進行遍歷操作 for (i = 0; i< listLength(myList); i++) { if (strcmp(myList ->data[i].num, key) == 0) { break; } } return i;}

獲取指定位置的元素信息

// 獲取指定位置的元素信息int infoList(SeqList *myList) { int key; // 獲取需要的索引值 printf("請輸入索引值"); scanf("%d", &key); // 檢查輸入的key if (key > listLength(myList) || key < 0) { return -1; // 輸入的索引錯誤 } // 輸出值對應的學號 printf("學號 = %s", myList ->data[key].num); return 1;}

刪除元素

// 刪除元素int deleteList(SeqList *myList) { char num[20]; int tmp; // 檢查myList是否為空 if (myList == NULL) { return -1; } // 獲取要刪除的學號 printf("請輸入要刪除的學號"); fflush(stdin); gets(num); // 查找對應的索引值 tmp = selectList(myList, num); if (tmp == -1) { return -1; } // 向前移動 tmp = moveList(myList, tmp, 1); if (tmp == -1) { return -1; } return 1;}

釋放線性表

// 釋放線性表int DestroyList(SeqList *myList) { if (myList == NULL) { return -1; } free(myList); return 1;}

總文件

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXCOUNT 50// 定義要儲存的線性表typedef struct { char num[20]; // 定義學號 char name[20]; // 定義姓名 int age; // 定義年齡 char major[20]; // 定義專業 int registerYear; // 定義入學年份}ElemType;// 定義線性表的物理儲存typedef struct { ElemType data[MAXCOUNT]; // 定義數據 int len; // 定義長度}SeqList;int createList(SeqList **myList);int listLength(const SeqList *myList);int printfList(const SeqList *myList);int inputList(ElemType **tmpList, int *col);int moveList(SeqList *myList, int col, int option);int selectList(SeqList *myList, char *key);int infoList(SeqList *myList, int key);int DestroyList(SeqList *myList);int main() { // 定義一些變數 int option, tmp; SeqList *myList; // 定義一個SeqList類型的空指針，用來儲存線性表 myList = NULL; char key[20]; int num; // 輸出選項 printf("學生管理系統進入成功"); printf("************選項*******************"); printf("1 建立線性表"); printf("2 求線性表的長度"); printf("3 輸出詳細表"); printf("4 在線性表的位置插入一個元素"); printf("5 根據鍵值對查找指定的元素"); printf("6 獲取指定位置的元素的信息"); printf("7 刪除指定位置的元素"); printf("8 釋放線性表"); printf("9 退出系統"); printf("**************end!*********************"); // 進行選項的輸入 // 進行基本邏輯的處理 while(1) { printf("請輸入選項"); scanf("%d", &option); switch(option) { // 建立線性表 case 1: tmp = createList(&myList); // 捕獲結果，並創建線性表 // 輸出結果 if (tmp == 1) { printf("建立線性表成功！"); } else { printf("建立線性表失敗!"); }; break; // 查詢線性表的長度 case 2: tmp = listLength(myList); if (tmp == -1) { printf("查詢線性表長度失敗，未指定線性表"); } else { printf("查詢線性表的長度為%d", tmp); }; break; // 輸出線性表 case 3: tmp = printfList(myList); if (tmp == -1) printf("輸出線性表失敗，未指定線性表"); else printf("輸出線性表如上"); break; // 插入線性表 case 4: tmp = insterList(myList); if (tmp == -1) printf("插入線性表失敗"); else printf("插入線性表成功"); break; case 5: // 根據鍵值查找索引值 printf("請輸入鍵值,即學號"); fflush(stdin); gets(key); fflush(stdin); tmp = selectList(myList, key); if (tmp == -1) printf("查找錯誤"); else if (tmp >= listLength(myList)) printf("未找到！"); else printf("索引值為 %d", tmp); break; case 6: // 根據索引值查找鍵值 printf("請輸入索引值"); scanf("%d", &num); tmp = infoList(myList, num); if (tmp == -1) { printf("查找失敗"); } else { printf("輸出的信息如上"); } break; case 7: // 根據鍵值刪除對應的數據 tmp = deleteList(myList); if (tmp == -1) printf("刪除失敗"); else printf("刪除成功"); break; case 8: tmp = DestroyList(myList); if (tmp == -1) { printf("釋放失敗"); } else { printf("釋放成功"); } break; case 9: return 0; default: printf("您輸入的有錯誤，請重新輸入"); break; } } return 0;}/* * 建立線性表*/// in 傳入空指針 out 線性表的首地址int createList(SeqList **myList) { *myList = (SeqList *)malloc(sizeof(SeqList)); // 申請一塊儲存空間 if (*myList == NULL) { return -1; // 創建儲存空間失敗 } else { return 1; // 創建儲存空間成功 }}/* * 求線性表長度,*/// in 線性表 out 長度int listLength(const SeqList *myList) { // 未創建線性表 if (myList == NULL) return -1; // 創建線性表 return myList -> len;};/* * 輸出線性表*/// in 線性表 out 線性表的內容int printfList(const SeqList *myList) { int i, len; // 判斷是否為空指針 if (myList == NULL) return -1; // 獲取線性表長度 len = myList -> len; if (len == 0) { printf ("您輸入的線性表為空"); return 1; } // 輸出線性表 for (i = 0; i < len; i++) { printf("輸出第%d組數組", i + 1); printf("學號 = %s", myList->data[i].num); printf("年齡 = %d", myList ->data[i].age); printf("專業 = %s", myList ->data[i].major); printf("姓名 = %s", myList ->data[i].name); printf("入學年份 = %d", myList ->data[i].registerYear); } printf("線性表輸出成功"); return 1;}/* * 在線性表的指定位置插入*/// in 線性表 out 結果int insterList(SeqList *myList) { int tmp, col; ElemType *tmpList = NULL; // 判斷傳入地址是否為空 if (myList == NULL) { return -1; } /* * 進行插入 */ // 獲取用戶輸入 tmp = inputList(&tmpList, &col); // 判斷是否獲取成功 if (tmp == -1) return -1; // 進行插入操作 // 調用函數，往後逐步移動 tmp = moveList(myList, col, 1); // 1代表向後移動 0 向前移動 // 判斷獲取結果 if (tmp == -1) { return -1; } // 將值插入 myList->data[col-1] = *tmpList; // 維護長度 (myList ->len)++; // 釋放儲存空間 free(tmpList); // 設置空指針 tmpList = NULL; return 1;}// 獲取用戶輸入要插入線性表的信息// in 插入的信息 插入的位置 out 結果int inputList(ElemType **tmpList, int *col) { // 申請儲存的內存空間 *tmpList = (ElemType *)malloc(sizeof(ElemType)); if (*tmpList == NULL){ printf("空間不足，無法申請"); return -1; } // 獲取用戶的要插入的內容 fflush(stdin); printf("請輸入學號"); gets(((*tmpList) ->num)); fflush(stdin); printf("請輸入姓名"); gets((*tmpList) ->name); fflush(stdin); printf("請輸入年齡"); scanf("%d",&((*tmpList) ->age)); fflush(stdin); printf("請輸入主修專業"); gets((*tmpList)->major); fflush(stdin); printf("請輸入入學年份"); scanf("%d", &((*tmpList)->registerYear)); fflush(stdin); printf("請輸入要插入的位置"); scanf("%d", col); fflush(stdin); return 1; // 獲取用戶輸入的信息完成}// 移動線性表函數// 其中option中1往後移動，0往前移動 col 為要插入的位置，從1開始int moveList(SeqList *myList, int col, int option) { int i; // 判斷傳入的線性表是否為空 if (myList == NULL) { printf ("線性表為空"); return -1; } // 判斷線性表是否已滿 if (listLength(myList) >= MAXCOUNT) { printf("線性表已滿，無法插入，請刪除後插入"); return -1; } // 判斷col是否越界，導致線性表不連貫 if ((col > listLength(myList) && col - listLength(myList) != 1 ) || col < 1) { printf("輸入的插入位置錯誤，請確認後重新插入"); return -1; } // 判斷前移還是後移 switch(option) { case 1: // 線性表往後移動 // 移動線性表 col--; for(i = listLength(myList); i >= col; i--) { myList ->data[i] = myList ->data[i-1]; }; break; case 0: // 線性表往前移動 col--; for(i = col; i < listLength(myList); i++) { myList ->data[i] = myList ->data[i+1]; } break; default: printf("輸入的選型錯誤"); return -1; } return 1;}// 根據鍵值查找線性表int selectList(SeqList *myList, char * key) { if (myList == NULL) { return -1; } int i; // 進行遍歷操作 for (i = 0; i< listLength(myList); i++) { if (strcmp(myList ->data[i].num, key) == 0) { break; } } return i;}// 獲取指定位置的元素信息int infoList(SeqList *myList, int key) { if (myList == NULL) { return -1; } // 檢查輸入的key if (key > listLength(myList) || key < 0) { return -1; // 輸入的索引錯誤 } // 輸出值對應的學號 printf("學號 = %s", myList ->data[key].num); return 1;}// 刪除元素int deleteList(SeqList *myList) { char num[20]; int tmp; // 檢查myList是否為空 if (myList == NULL) { return -1; } // 獲取要刪除的學號 printf("請輸入要刪除的學號"); fflush(stdin); gets(num); // 查找對應的索引值 tmp = selectList(myList, num); if (tmp == -1) { return -1; } // 向前移動 tmp = moveList(myList, tmp, 1); if (tmp == -1) { return -1; } return 1;}// 釋放線性表int DestroyList(SeqList *myList) { if (myList == NULL) { return -1; } free(myList); return 1;}

運行如下

源文件 gitlab.com/melovemingmi

推薦閱讀：

TAG:數據結構 | 數學 |