原文托管在Github: https://github.com/shellhub/blog/issues/52

數據結構與算法之線性表-順序表實現(C語言版本)

前言

數據結構與算法是一個程序員必備的技能之一,而順序表更是每個程序員在面試過程中要經常被問到的，如Java語言中的ArrayList類的底層實現就是使用順序表實現的,別把順序表想的有多么高大上，其實就是使用數組實現的一種線性表

什么是線性表

線性表（英語：Linear List）是由n（n≥0）個數據元素（結點）a[0]，a[1]，a[2]…，a[n-1]組成的有限序列。 其中： 數據元素的個數n定義為表的長度 = "list".length() （"list".length() = 0（表里沒有一個元素）時稱為空表） 將非空的線性表（n>=1）記作：（a[0]，a[1]，a[2]，…，a[n-1]） * 數據元素a[i]（0≤i≤n-1）只是個抽象符號，其具體含義在不同情況下可以不同

一個數據元素可以由若干個數據項組成。數據元素稱為記錄，含有大量記錄的線性表又稱為文件。這種結構具有下列特點：存在一個唯一的沒有前驅的（頭）數據元素；存在一個唯一的沒有后繼的（尾）數據元素；此外，每一個數據元素均有一個直接前驅和一個直接后繼數據元素。

什么是順序表

順序表是在計算機內存中以數組的形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。

順序表的實現

為了能實現順序表的基本操作如(增，刪，改，查),我們使用結構體封裝一個指向一維數組的指針base，同時提供一個名字叫做length的整型變量表示順序表中實際有用的元素個數,當插入一個元素時length++, 當刪除一個元素時length--,所以length可以記錄當前順序表的長度

順序表綜合案列-學生信息管理系統

#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #include <assert.h>#define INIT_SIZE 1 #define INCREMENT_SIZE 5 typedef struct {int id; //學號int age; //年齡char name[10]; //姓名 } Student;typedef Student ElemType;typedef struct {ElemType *base;int size; /* 順序表的最大容量 */int length; /* 記錄順序表的元素個數 */ } SqList;/*** 初始化順序表* @param p 指向順序表的指針* @return 如果初始化成功返回true否則返回false*/ bool init(SqList *p) {p->base = malloc(sizeof(SqList) * INIT_SIZE);if (p->base == NULL) {return false;}p->size = INIT_SIZE;p->length = 0;return true; }/*** 指定位置插入數據元素* @param p 指向順序表的指針* @param index 插入的下標* @param elem 插入的元素值* @return 如果插入成功返回true，否則返回false*/ bool insert(SqList *p, int index, ElemType elem) {if (index < 0 || index > p->length) {perror("插入下標不合法");return false;}//如果順序表滿了，則重新分配更大的容量if (p->length == p->size) {int newSize = p->size + INCREMENT_SIZE;ElemType *newBase = realloc(p->base, newSize);if (newBase == NULL) {perror("順序表已滿，重新分配內存失敗");return false;}p->base = newBase;p->size = newSize;}//從最后一個元素開始依次把元素復制到后面的位置for (int i = p->length - 1; i >= index; --i) {p->base[i + 1] = p->base[i];}p->base[index] = elem;p->length++;return true; }/*** 刪除指定下標的數據元素* @param p 指向順序表的指針* @param index 刪除的元素的下標* @param elem 返回刪除的元素* @return 如果刪除成功返回true否則返回false*/ bool del(SqList *p, int index, ElemType *elem) {if (p->length == 0) {perror("順序是空的，無法執行刪除操作");return false;}if (index < 0 || index > p->length - 1) {perror("刪除位置不合法");return false;}//把刪除的元素保存起來*elem = p->base[index];//從刪除位置開始依次把后面的元素賦值到前面for (int i = index; i < p->length - 1; ++i) {p->base[i] = p->base[i + 1];}p->length--;return true; }/*** 更新順序表中特定的元素值* @param p 指向順序表的指針* @param index 更新下標* @param elem 更改后的新元素值* @return 如果更改成功則返回true，否則返回false*/ bool update(SqList *p, int index, ElemType elem) {if (p->length == 0) {perror("順序表是空的，無法指向更新");return false;}if (index < 0 || index > p->length - 1) {perror("更新下標不合法");return false;}p->base[index] = elem;return true; }/*** 搜索順序表中特定下標的元素* @param list 指定的順序表* @param index 搜索的下標* @param elem 保存搜索到的元素* @return 如果搜索成功則返回true，否則返回false*/ bool search(SqList list, int index, ElemType *elem) {if (list.length == 0) {perror("順序表沒有任何元素，無法查找");return 0;}if (index < 0 || index > list.length - 1) {perror("查找下標不合法");return false;}*elem = list.base[index - 1];return true; }/*** 打印順序表* @param list 指定順序表*/ void output(SqList list) {printf("學號t年齡t姓名n");for (int i = 0; i < list.length; ++i) {printf("%dt%dt%sn", list.base[i].id, list.base[i].age, list.base[i].name);}printf("n"); }int main() {SqList list;while (1) {printf("tt順序表的基本操作n");printf("tt1.初始化順序表n");printf("tt2.順序表的插入n");printf("tt3.順序表的刪除n");printf("tt4.順序表的查找(下標)n");printf("tt5.順序表的修改n");printf("tt6.打印n");printf("tt0.退出n");int choice;printf("請輸入功能編號:");scanf("%d", &choice);switch (choice) {case 1:if (init(&list)) {printf("初始化成功n");}assert(list.length == 0);break;case 2:;ElemType elem;printf("請輸入插入的學生學號:");scanf("%d", &elem.id);printf("請輸入插入的學生年齡:");scanf("%d", &elem.age);printf("請輸入插入的學生姓名:");scanf("%s", elem.name);printf("請輸入插入位置:");int index;scanf("%d", &index);if (insert(&list, index, elem)) {printf("插入成功n");}break;case 3:printf("請輸入刪除位置:");scanf("%d", &index);if (del(&list, index, &elem)) {printf("刪除的學生 學號:%dt年齡:%dt姓名:%sn", elem.id, elem.age, elem.name);}break;case 4:printf("請輸入要查找的位置:");scanf("%d", &index);if (search(list, index, &elem)) {printf("查找的學生 學號:%dt年齡:%dt姓名:%sn", elem.id, elem.age, elem.name);}break;case 5:printf("請輸入更新位置:");scanf("%d", &index);printf("請輸入更新后的學生學號:");scanf("%d", &elem.id);printf("請輸入更新后的學生年齡:");scanf("%d", &elem.age);printf("請輸入更新后的學生姓名:");scanf("%s", elem.name);if (update(&list, index, elem)) {printf("更新成功n");}break;case 6:output(list);break;case 0:exit(0);default:printf("輸入編號有誤，請重新輸入n");break;}}return 0; }

順序表優缺點

• 優點
  • 因為順序表使用數組實現，可以通過下標存取，所以存取速度極快，T(n)=O(1)
  • 無需為表中元素之間的邏輯關系而增加額外的存儲空間
  • 空間利用效率高
• 缺點
  • 插入刪除均需要循環移動元素,比較浪費時間 T(n)=O(n)
  • 需要提前預估順序表的長度(INIT_SIZE),分配太大浪費，造成內存的碎片化

總結

以上是生活随笔為你收集整理的rsa算法c语言实现_数据结构与算法之线性表-顺序表实现(C语言版本)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。